资源预览内容
第1页 / 共35页
第2页 / 共35页
第3页 / 共35页
第4页 / 共35页
第5页 / 共35页
第6页 / 共35页
第7页 / 共35页
第8页 / 共35页
第9页 / 共35页
第10页 / 共35页
亲,该文档总共35页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
4.2两阶段法与大M 法初始可行基的求法求解线性规划的步骤是:1) 已知一个初始基本可行解2) 从初始基本可行解动身,写出单纯型表,求出进基离基变量,做主元消去法,求 出一个新的基本可行解且使目标函数值 得到改善;3) 判定当前基本可行解是否是最优解那末,当观看不出来初始基本可行解时,怎么办?下面介绍的方法是几种求初始基本 可行解的方法4.2.1 两 阶 段 法mincxs.tAxbx 0其中 A 是 mn 矩阵, b 0;如 A 中有 m阶单位矩阵,就初始基本可行解立刻得到;比如, AI m , N,那么xBbxxN0就是一个基本可行解;如A 中不包含 m 阶单位矩阵,就需要用某种方法求出一个基本可行解;介绍两阶段法之前,先引入人工变量的概念;设 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是人为引入的,它的每个重量成为人工变量 ;人变量与前面介绍过的放松变量是两个不同的概念; 放松变量的作用是把不等式约束改写成等式约束, 改写前后的两个问题是等价的;因此,放松变量是“合法”的变量;而人工变量的引 入,转变了原先的约束条件从这个意义上讲,它们是“不合法”的变量;第一阶段 是用单纯形方法消去人工变量(假如可能的话):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.2.4)的目标函数值f0x.eT0Tex0 aa而eT x是目标函数值的最优值,冲突;2. xa0 且 xa的重量都是非基变量;这时,m 个基 变 量 都 是 原 来 的 变 量 , 又 知xx.xa0xx是( 4.2.4)的基本可行解,因此是( 4.2.1)的一个基本可行解;3xa0 且 xa的某些重量是基变量;这时,可用主元消去法把原先变量中的某些非基变量引进基,替换出基变量中的人工变量,再开头两阶段法的其次阶段;应指出,为替换出人工变量而采纳的主元消去,在主元的挑选上,并不要求遵守单纯形法确定离进基变量的规就;其次阶段, 就是从得到的基本可行解动身,用单纯形方法求( 4.2.1)的最优解;例 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-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 下面的列(也可保留, 但人工变量不能再进基) ,把最终的判别数行按原先问题进行修正;其他不变;然后开头其次阶段迭代,即极大化目标函数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,得到以下一阶段问题: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-2120x2x5x4x5x6111x110-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目
收藏 下载该资源
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号