单纯形法例题.docx

单纯形法例题
1、 例1、目标函数 max z=2x1+3x2
约束条件：x1+2x2≤84x1≤164x2≤12x1，x1≥0
解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量，x3，x4，x5，并且它们都大于等于0.得到的标准形式为：
max z=2x1+3x2+ 0x3+0x4+0x5
x1+2x2+x3＝84x1+x4=164x2+x5＝12x1，x2，x3，x4，x5≥0
然后要将其初始的单纯形表画出来：
cj
2
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
0
x3
8
1
2
1
0
0
4
0
x4
16
4
0
0
1
0
-
0
x5
12
0
4
0
0
1
3
cj-zj
2
3
0
0
0

由初始单纯形表可以看出，x2为换入变量，而x5为换出变量；然后根据：
aij=aij-aljalk*aiki≠laljalki=l
bi=bi-aikalk*bli≠lblalki=l
(也就是如果与主元素同行，则用现在的值除以主元素即可得到即将要填入的值，否则，就用现在的值减去与主元素构成矩形的边角上的值的乘积再除以主元素之后的值。例如：上面的第一行所对应的b值为8-(12*2)/4=2,故填入值应该为2。而θi则是由我们根据非基变量的检验数的大小，挑选出最大的那个，作为换入变量，然后用b的值除以该换入变量所在的列的所有值，得到θi列的值。

cj
2
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
0
x3
2
1
0
1
0
-1/2
2
0
x4
16
4
0
0
1
0
4
3
x2
3
0
1
0
0
1/4
-
cj-zj
2
0
0
0
-3/4

由于在检验数中仍然存在大于等于0的数，而且P1，P5的坐标中有正分量存在，所以需要继续进行迭代运算。通过观察可以看出主元素为1，换入变量为x1，换出变量为x3，故得到的单纯形表如下：
cj
2
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
2
x1
2
1
0
1
0
-1/2
-
0
x4
8
0
0
-4
1
2
4
3
x2
3
0
1
0
0
1/4
12
cj-zj
0
0
-2
0
1/4

由于检验数中存在正数，且P5和P3中有正分量存在，所以需要继续迭代(换入变量为x5，换出变量为x4：得到单纯形表如下：
cj
2
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
2
x1
4
1
0
0
1/4
0

0
x5
4
0
0
-2
1/2
1

3
x2
2
0
1
1/2
-1/8
0

cj-zj
0
0
-3/2
-1/8
0

此时可以发现检验数中没有大于0的数，表明已经得到了最优解，所以最优解是：
（4,2,0,0,4），故目标函数值z=2*4+2*3=14
2、 合理利用线材问题，现在要做100套钢架，每套用长为2.9m，2.1m，和1.5m的钢各一根，已知原料长7.4m，问应如何下料，使用的原材料最省；
解：首先我们必须要清楚该问题的需要设立的变量是什么。我们分析一下问题，做100套钢架，需要2.9m长的钢100根，2.1m的钢100根，1.5m的钢100根。而一份原料长度是7.4m，它的截取的方法有多少种，我们可以用表格列举出来：

长度/m

下料根数
截取方案
1
2
3
4
5
2.9
1
1
2

2.1

2

1
2
1.5
3

1
3
2
所用长度
7.4
7.1
7.3
6.6
7.2
剩余长度
0
0.3
0.1
0.8
0.2
求解的问题是关于如何去进行下料，使得原材料最省，也就是说如何搭配使用这些方案，使得剩余的总长度最少。由此，我们可以将目标函数和约束条件表述出来：
目标函数：min z=0.3x2+0.1x3+0.8x4+0.2x5
约束条件x1+x2+2x3=1002x2+x4+2x5=1003x1+x3+3x4+2x5=100x1，x2，x3，x4，x5≥0
首先可以写出线性方程组的矩阵形式：112000201230132发现不存在单位矩阵，所以要采用人造基的方式，也就是要添加人工变量：x6，x7，x8，那么线性方程组可以表示为：x1+x2+2x3+x6=1002x2+x4+2x5+x7=1003x1+x3+3x4+2x5+x8=100x1，x2，x3，x4，x5，x6，x7，x8≥0，目标函数可以表示为：min z=0x1+0.3x2+0.1x3+0.8x4+0.2x5+Mx6+Mx7+Mx8
转换为求目标最大化max Z=-0x1-0.3x2-0.1x3-0.8x4-0.2x5-Mx6-Mx7-Mx8
然后列出初始单纯形表：(注意，加入人工变量之后，它所对应的系数为-M，而非0)
cj
0
-0.3
-0.1
-0.8
-0.2
-M
-M
-M
θi
CB
XB
b
x1
x2
x3
x4
x5
x6
x7
x8
-M
x6
100
1
1
2
0
0
1
0
0
100
-M
x7
100
0
2
0
1
2
0
1
0
-
-M
x8
100
3
0
1
3
2
0
0
1
100/3
cj-zj
4M
-0.3+3M
-0.1+3M
-0.8+4M
-0.2+4M
0
0
0

换入变量为x1，换出变量为x8，得到单纯形表为：
cj
0
-0.3
-0.1
-0.8
-0.2
-M
-M
-M
θi
CB
XB
b
x1
x2
x3
x4
x5
x6
x7
x8
-M
x6
200/3
0
1
5/3
-1
-2/3
1
0
-1/3
200/3
-M
x7
100
0
2
0
1
2
0
1
0
100/2
0
x1
100/3
1
0
1/3
1
2/3
0
0
1/3
-
cj-zj
0
-0.3+3M
-0.1+5/3M
-0.8
-0.2+4/3M
0
0
-4/3M

换入变量为x2，换出变量为x7，得到的单纯形表为：
cj
0
-0.3
-0.1
-0.8
-0.2
-M
-M
-M
θi
CB
XB
b
x1
x2
x3
x4
x5
x6
x7
x8
-M
x6
50/3
0
0
5/3
-3/2
-5/3
1
-1/2
-1/3
10
-0.3
x2
50
0
1
0
1/2
1
0
1/2
0
-
0
x1
100/3
1
0
1/3
1
2/3
0
0
1/3
-100
cj-zj
0
0
-0.1+5/3M
-0.65-3/2M
0.1-5/3M
0
0.15-3/2M
-4/3M

换入变量为x3，换出变量为x6，得到的单纯形表为：
cj
0
-0.3
-0.1
-0.8
-0.2
-M
-M
-M
θi
CB
XB
b
x1
x2
x3
x4
x5
x6
x7
x8
-0.1
x3
10
0
0
1
-9/10
-1
3/5
-3/10
-1/5

-0.3
x2
50
0
1
0
1/2
1
0
1/2
0

0
x1
30
1
0
0
13/10
1
-1/5
1/10
2/5

cj-zj
0
0
0
-0.74
0
-M+0.06
-M+0.12
-M-0.02

所以，最优解为：（30,50,10，0,0,0,0,0）。也就是说最优的下料方案为：按照第一个方案下料30根，第二种方案下料50根，按照第三种方案下料10根。即需要90根原材料可以制造出100套钢架。

3、 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下表：
班次
时间
所需人数
1
6:00-10:00
60
2
10:00-14:00
70
3
14:00-18:00
60
4
18:00-22:00
50
5
22:00-2:00
20
6
2:00-6:00
30
设司机和乘务人员分别在各时间区段一开始时上班，并连续工作八个小时，问该公交线路至少配备多少名司机和乘务人员，列出这个问题的线性规划模型。

解：

目标函数：min z=x1+x2+x3+x4+x5+x6
约束条件:x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1，x2，x3，x4，x5，x6≥0

4、 利用单纯形算法求解线性规划问题
目标函数为：Max Z=4x1+3x2
约束条件为：2x1+2x2≤16005x1+2.5x2≤2500x1≤400x1,x2≥0
解：首先将线性方程组化为标准形式：添加松弛变量：x3，x4，x5，得到的方程式为：

目标函数：Max Z=4x1+3x2+0x3+0x4+0x5
约束条件为：2x1+2x2+ x3=16005x1+2.5x2+x4=2500x1+x5 =400x1, x2,x3, x4,x5≥0

接着将初始单纯形表列出：

cj
4
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
0
x3
1600
2
2
1
0
0
800
0
x4
2500
5
2.5
0
1
0
500
0
x5
400
1
0
0
0
1
400
cj-zj
4
3
0
0
0

由上表可以看出，x1为换入变量，而x5为换出变量。然后根据变换公式可以得到变换之后的单纯形表如下：
cj
4
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
0
x3
800
0
2
1
0
-2
400
0
x4
500
0
2.5
0
1
-5
200
4
x1
400
1
0
0
0
1
0
cj-zj
0
3
0
0
-4

由上表可以看出，换入变量为x2，换出变量为x4，单纯形表如下：
cj
4
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
0
x3
400
0
0
1
-4/5
2
200
3
x2
200
0
1
0
2/5
-2
-
4
x1
400
1
0
0
0
1
400
cj-zj
0
0
0
-6/5
2

由上表可以看出，换入变量为x5，换出变量为x3
得到的单纯形表如下：

cj
4
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
0
x5
200
0
0
1/2
-2/5
1

3
x2
600
0
1
1
-2/5
0

4
x1
200
1
0
0
2/5
0

cj-zj
0
0
-3
-2/5
0

由于，检验数均为非负，所以得到了最优解，且最优解为(200,600,0,0,200);
故目标函数的最大值为： Z=2600