文档介绍：本节重点:
单纯形表(特别是检验数行)
单纯形法的计算步骤
大M法
两阶段法
解的存在情况判别
单纯形表
用表格法求解LP,规范的表格——单纯形表如下:
计算步骤
(1).找出初始可行基,确定初始基可行解,建立初始单纯形表。
(2).检验各非基变量xj的检验数,若j 0,j=m+1,…,n;则
已得到最优解,可停止计算,否则转入下一步。
(3).在j > 0,j=m+1,…,n中,若有某个k对应xk的系数列向量Pk 0,则此问题是无界解,停止计算。否则,转入下一步。
(4).根据max(j > 0) =k,确定xk为换入变量,按规则计算
=min{bi/aik\aik>0}
可确定第l行的基变量为换出变量。转入下一步。
2 3 0 0 0
1 2 1 0 0
4 0 0 1 0
0 4 0 0 1
0 2 3 0 0 0
0
0
0
8
16
12
x3
x4
x5
4
-
3
2 3 0 0 0
2 1 0 1 0 -1/2
- 9 2 0 0 0 -3/4
0
0
3
x3
x4
x2
2
4
-
( )
3 0 1 0 0 1/4
16 4 0 0 1 0
X(0)=(0,0,8,16,12)T, z0 =0
2 3 0 0 0
2 1 0 1 0 -1/2
-13 0 0 -2 0 1/4
2
0
3
x1
x4
x2
-
4
12
3 0 1 0 0 1/4
8 0 0 -4 1 2
2 3 0 0 0
2 1 0 1 0 -1/2
-9 2 0 0 0 -3/4
0
0
3
x3
x4
x2
2
4
-
3 0 1 0 0 1/4
16 4 0 0 1 0
( )
X(1)=(0,3,2,16,0)T, z1 =9
2 3 0 0 0
2 1 0 1 0 -1/2
-13 0 0 -2 0 1/4
2
0
3
x1
x4
x2
-
4
12
3 0 1 0 0 1/4
8 0 0 -4 1 2
( )
2 3 0 0 0
4 1 0 0 1/4 0
-14 0 0 - -1/8 0
2
0
3
x1
x5
x2
2 0 1 1/2 -1/8 0
4 0 0 -2 1/2 1
X(2)=(2,3,0,8,0)T, z2 =13
X(3)=(4,2,0,0,4)T, z3 =14
§5 单纯形法的进一步讨论
人工变量法
解决初始基可行解的问题。当某个约束方程中没有明显的基变量时,在该方程中加上人工变量。
其中第2、3个约束方程中无明显基变量,分别加上人工变x6, x7
这时,初始基和初始基可行解很明显。X(0)=(0,0,0,11,0,3,1)T不满足原来的约束条件。如何使得可从X(0)开始,经迭代逐步得到x6=0,x7=0 的基可行解,从而求得问题的最优解,有两种方法:
反之,若加了人工变量的问题解后最优解中仍含人工变量为基变量,便说明原问题无可行解。例3的单纯形表格为:
只要原问题有可行解,随着目标函数向最大化方向的改善,人工变量一定会逐步换出基,从而得到原问题的基可行解,进而得到基最优解。
在目标函数中加上惩罚项
max =3x1-x2-x3-Mx6-Mx7
其中M为充分大的正数。