《最优化教案》由会员分享，可在线阅读，更多相关《最优化教案（35页珍藏版）》请在金锄头文库上搜索。
1、 4.2两阶段法与大M 法初始可行基的求法求解线性规划的步骤是：1） 已知一个初始基本可行解2） 从初始基本可行解动身，写出单纯型表，求出进基离基变量，做主元消去法，求 出一个新的基本可行解且使目标函数值 得到改善；3） 判定当前基本可行解是否是最优解那末，当观看不出来初始基本可行解时，怎么办？下面介绍的方法是几种求初始基本 可行解的方法4.2.1 两 阶 段 法mincxs.tAxbx 0其中 A 是 mn 矩阵， b 0；如 A 中有 m阶单位矩阵，就初始基本可行解立刻得到；比如， AI m , N，那么xBbxxN0就是一个基本可行解；如A 中不包含 m 阶单位矩阵，就需要用某种方法求出
2、一个基本可行解；介绍两阶段法之前，先引入人工变量的概念；设 A 中不包含 m 阶单位矩阵， 为使约束方程的系数矩阵中含有m 阶单位矩阵，把每个方程增加一个非负变量，令Axxab（ 4.2.2）x 0，即xxa 0 A,I m bxa（ 4.2.3）x 0，xa 0明显，x0xab是（ 4.2.3） 的一个基本可行解；向量 xa 0是人为引入的，它的每个重量成为人工变量 ；人变量与前面介绍过的放松变量是两个不同的概念； 放松变量的作用是把不等式约束改写成等式约束， 改写前后的两个问题是等价的；因此，放松变量是“合法”的变量；而人工变量的引 入，转变了原先的约束条件从这个意义上讲，它们是“不合法”
3、的变量；第一阶段 是用单纯形方法消去人工变量（假如可能的话）：mins.teT xaAxxb（ 4.2.4）x 0， xa 0其中 e1,1,1T是重量全是1 的 m维列向量，xa xn1 , xnTm是 人 工 变量构成的 m 维列向量；由于 x0, xab 是（ 4.2.4）的一个基本可行解，目标函数值在可行域上有下界，因此问题（ 4.2.4）必存在最优基本可行解；求解（ 4.2.4），设得到的最优基本可行解是 xT, xTa T，此时必有以下三种情形之一：1. xa0 这时（ 4.2.1）无可行解；由于假如（ 4.2.1）存在可行解x. 就xx.xa0是（ 4.2.4）的可行解；在此点，
4、问题（4.2.4）的目标函数值f0x.eT0Tex0 aa而eT x是目标函数值的最优值，冲突；2. xa0 且 xa的重量都是非基变量；这时，m 个基 变 量 都 是 原 来 的 变 量 ， 又 知xx.xa0xx是（ 4.2.4）的基本可行解，因此是（ 4.2.1）的一个基本可行解；3xa0 且 xa的某些重量是基变量；这时，可用主元消去法把原先变量中的某些非基变量引进基，替换出基变量中的人工变量，再开头两阶段法的其次阶段；应指出，为替换出人工变量而采纳的主元消去，在主元的挑选上，并不要求遵守单纯形法确定离进基变量的规就；其次阶段， 就是从得到的基本可行解动身，用单纯形方法求（ 4.2.1
5、）的最优解；例 4.2.1用两阶段法求以下问题的最优解max2x1x2s.tx1x2 2x1x2 1x1 3x1, x2 0先引进放松变量x4 ,x5 , x6，把问题化成标准形式；由于此标准形式中约束方程的系数矩阵并不包含3阶单位矩阵，因此仍引进人工变量x6 , x7；下面先求解一阶段问题：minx6x7s.tx1x2x3+ x6=2x1x2x4x7 =1x1x5=3x j 0j1,7仍旧用主元消去法， 主元用框号标出； 迭代p1过程如下：1zjcjcBBjcjcB yjcjfcB xBcB BbcBbx1x2x3x4x5x6x7x611-1001021-10-10011100110020-
6、1-10003x7x53x602-1101-11x11x50011-10-100101102-1100-2-1211x20111101-222221x113100-102221x50021111322122200000-1-10由于全部判别数zjc j 0，因此达到最优解； 在一阶段问题的最优解中，人工变量量；这样，我们得到初始基本可行解x6 , x7都是非基变 x1,x2 ,x3 ,x4 ,x5 3 ,21 ,0,0, 223第一阶段终止后，修改最终的单纯形表；去掉人工变量 x6 和x7 下面的列（也可保留， 但人工变量不能再进基） ，把最终的判别数行按原先问题进行修正；其他不变；然后开头其
7、次阶段迭代，即极大化目标函数f2x1x2 ；迭代过程如下：x1x2x3x4x5x2111012202x1101103222x511300221213052220002-110111-10020-1101103-20040101121000130-11011010026x4x1x5x4x1x3得到（ 4.2.5）的最优解（x1 ，x2 ） =（ 3， 0），目标函数最优值f max6例 4.2.2用两阶段法求解以下问题mins.tx1x2x12x2x3 24x14x2x3 =4x1x1,x2 ,x3 =0x3 0引进放松变量x4 ，把上述问题化成标准形式，再引进人工变量x5 , x6，得到以下一
8、阶段问题：mins.tx5x6x12x24x14x2x3 x3+x4=2x5=4x1x3+x6 =0x j 0j1 ， 6先用单纯形法解一阶段问题，迭代如下：zjcjcBBjcjcB yjcjpfcB xBcB BbcBb1其中 cB是目标函数中基变量的系数构成的维行向量， y j是上表中的第 j 列， b 是上表中的右端列；x1x2x3x4x5x6x4-1211002x5-44-10104x610-10010-34-2000411x2211001221x5-20-3-21000-100100-4-2000x61-1x6 ，取主元y311，经元消去得到下表：x1x2x301020200-5-2
9、120x2x5x4x5x6111x110-10010再以y235 为主元，进行主元消法，得到x1x2x3x4x5x6100100x21102021x3205x12151255013550这样， 基变量均为原先的变量，得到原先的问题的一个基本可行解 x1 ,x2 ,x3 ,x4 0,1,0,0再把表中人工变量对应的列去掉（也可保留， 但人工变量不能再进基） ，并把判别数行增加进去；正如前面曾经指出过的那样， 初表中的判别数和目标函数值p1利用定义来运算，即zjcjcBBjcjcB yjcjfcB xBcB BbcBb1其中 cB是目标函数中基变量的系数构成的维行向量， y j是上表中的第 j 列， b 是上表中的右端列；其次阶段的初表如下：x1x2x2x3x4101021x32001502x110050000此表已是最优表；最优解是1-110 x1 ,x2 ,x3 0,1,0目
