文档介绍：§ 初始解
:(1)(2)
1、阶段法
设原问题为
( )
不妨假设,(如果某一个元素小于0,该方程两边乘于-1后则可以使右端数变成正数) 为什么要这样假设?
两阶段法的基本思想
第一阶段:判定LP问题是否有可行解。若有,则求出一个初始的基本可行解。
第二阶段:从初始解出发,用单纯形方法求解原问题。
考虑辅助问题(在( ) 中增加个人工变量)
()
其中,。
分析()与()的关系:
(1)
即或
(2)是()的最优解
(3)是()的基本可行解是()的最优基本可行解。
分析()的特点:
<1> , <2>
所以,问题()必有最优解。
三种情形:(设()的最优基本可行解为)
<1>. 且为非基变量,则此时是问题()的基本可行解,且基变量不变。
<2>.,则原问题没有可行解。
<3>. 但中有部分变量为基变量,此时是问题()的基本可行解,不同的是基变量会有些改变。
当情形1出现时,在最优基可行解的单纯形表里删除对应的列,同时计算出检验数就可以得到原问题的单纯形表。有时为了方便,在第一阶段开始时就同时用两个检验行。
当情形3出现时,设第一阶段的最优单纯形表为
…
…
…
…
RHS
…
…
…
0
…
0
0
…
…
1
0
不防设,基变量是人工变量,则(?)。考查第所在的这一行的前个元素,即。
(1)若它们不全为0,设
则为非基变量(?)。以为转轴元进行一次旋转(注意此时不要求?)。由于,所以。所以的最小值仍为0。只是将取零值的非基变量
变成了基变量,代替了取零值的人工变量。
(2)若它们全为0
则秩. 所以秩。这表明第所在的这一行是多余的,将它删去即可。
因此,可以去掉前几节要求的两个假设:
<1> <2> 秩

解: 首先引入人工变量和,考虑辅助问题
以和为基变量可得其第一个基可行解, 其对应的单纯形表为
RHS
-5
0
-21
0
0
0
0
0
0
0
0
0
0
-1
-1
0
1
-1
6
-1
0
1
0
2
1
1
2
0
-1
0
1
1
首先,把所在一行变为检验行。
RHS
-5
0
-21
0
0
0
0
0
2
0
8
-1
-1
0
0
3
1
-1
6
-1
0
1
0
2
1
1
2
0
-1
0
1
1
RHS
-3/2
-7/2
0
-7/2
0
21/6
0
7
2/3
4/3
0
1/3
-1
-4/3
0
1/3
1/6
-1/6
1
-1/6
0
1/6
0
1/3
2/3
4/3
0
1/3
-1
-1/3
1
1/3
RHS
1/4
0
0
-21/8
-21/8
21/8
21/8
63/8
0
0
0
0
0
-1
-1
0
1/4
0