文档介绍：1
单纯形法初始基的产生
一、标准形初始基的产生
前面介绍的单纯形算法是建立在初始基解的基础上的,下面着重介绍怎样得到初始基
X1 4
X2 3
X1+2X2 8
X1 , X2 0
maxZ=X1 +2X2
X1 + X3 = 4
X2 + X4 = 3
X1+2X2 + X5 = 8
X1 , X2 0
所有约束全为
2
得到如示的系数矩阵
由上述矩阵可知,其初始基变量为X3、X4 、X5 ,初始基解为(0,0,4,3,8)
1
2
0
0
0
X1
X2
X3
X4
X5
(换出)
CB
XB
0(Z0)
1
2
0
0
0
0
X3
4(b1)
1
0
1
0
0
4/0=
0
X4
3(b2)
0
1
0
1
0
3/1=3
0
X5
8(b3)
1
2
0
0
1
8/2=4
3
1
2
0
0
0
X1
X2
X3
X4
X5
(换出)
CB
XB
0(Z0)
1
2
0
0
0
0
X3
4(b1)
1
0
1
0
0
4/0=
0
X4
3(b2)
0
1
0
1
0
3/1=3
0
X5
8(b3)
1
2
0
0
1
8/2=4
6 (Z1)
1
2
0
-2
0
0
X3
4(b1)
1
0
1
0
0
4/1=4
2
X2
3(b2)
0
1
0
1
0
3/0=3
0
X5
2
1
0
0
-2
1
2/1=2
8 (Z2)
1
0
0
0
-1
0
X3
2(b1)
0
0
1
2
-1
4/1=4
2
X2
3(b2)
0
1
0
1
0
3/0=3
1
X1
2
1
0
0
-2
1
2/1=2
本问题的最优解 X=(2, 3, 2, 0,0)T , Z=8
4
maxZ= 6X1 +4X2
2X1 +3X2 100
4X1 +2X2 120
X1 =14
X2 22
X1 X2 0
二、大M法产生初始基
5
maxZ=6X1+4X2
2X1 +3X2 +X3 =100
4X1 +2X2 +X4 =120
X1 =14
X2 - X5 = 22
X1 … X5 0
x1 x2 x3 x4 x5 x6 x7
知x6加在式3
知x7加在式4
6
2X1 +3X2 +X3 =100 (a)
4X1 +2X2 +X4 =120 (b)
X1 + X6 =14 (c)
X2 - X5 + X7 = 22 (d)
X1 … X7 0
maxZ=6X1+4X2-MX6 –MX7
这里X6 、X7是人为添加上去的(不同于前面介绍的为变不等式为等式而加的变量),被称为人工变量。
7
由于约束条件(c)(d)在添加人工变量前已是等式,为使这些等式得到满足,因此在最优解中人工变量取值必须为零。为此,令目标函数中人工变量的系数为任意大的负值,用“-M”代表。“-M”称为“罚因子”,即只要人工变量取值大于零,目标函数就不可能实现最优。因而添加人工变量后,上例目标函数必须-MX6 –MX7
该模型中X3、X4、X6、X7为基变量,令非基变量X1、X2、X5等于零,即得到初始基可行解X=(0,0,100,120,0,14,22),并列出初始单纯形表。
注
意
在单纯形迭代运算中,M可当作一个数学符号一起参加运算。检验数中含M符号的,当M的系数为正时,该检验数为正,当M的系数为负时,该检验数为负。
最后的优化解中,基变量不含人工变量
8
6
4
0
0
0
-M
-M
X1
X2
X3
X4
X5
X6
X7
(换出)
CB
XB
-14M-22M
6+M
4+M
0
0
-M
0
0
0
X3
100(b1)
2
3
1
0
0
0
0
50
0
X4
120(b2)
4
2
0
1
0
0
0
30
-M
X6
14
1
0
0
0
0
1
0
14
-M
X7
22(b3)
0
1
0
0
-1
0
1
84-22M
0
4+M
0
0
-M
-M-6
0
0
X3
72(b1)
0
3
1
0
0
-2
0
24
0
X4
64(b2)
0
2
0
1
0
-4
0
32