《高等数学》课程PPT教学课件（章节知识点）7.3 两阶段法

§73两阶段法 建立人造基对应的单纯形矩阵 设有线性规划问题 (I) minS=CiX+C2x2+.+ c1x1+a122 +…+a1xn=b xt aox 211 2 2 …+a 2n S·t amIx1+ am2x2+. amrrn=bmy 0(j=1 其中b≥0(j=1,2,…,m)

§ 7.3 两 阶 段 法 一、建立人造基对应的单纯形矩阵 设有线性规划问题 (Ⅰ) minS = c1x1 + c2x2 + ··· + cnxn a11x1 + a12x2 + ··· +a1nxn = b1 , a21x1 + a22x2 + ··· + a2nxn = b2 , ······ am1x1 + am2x2 + ··· + amnxn = bm, xj≥0 ( j = 1, 2, ···, n). 其中 bj≥0 ( j =1, 2, ···, m )          s t

引入辅助线性规划问题 (Ⅱ) mmx=y1+y2+…+ym s-C 212 y+a1ux1+a12x2+…+ S·t y2+a21x1+a2x72+… ym+amgx1+am2x2+…+a mnn x≥0(=1,2,…,n)2y≥>0(=1,2,…,m)

引入 辅助线性规划问题 (Ⅱ) min z = y1+ y2+ ··· + ym S- c1x1- c2x2 - ··· - cnxn= 0 y1+ a11x1+ a12x2 + ··· + a1nxn= b1 y2+ a21x1+ a22x2 + ··· + a2nxn = b2 ym + am1x1+ am2x2+ ··· + amnxn= bm xi≥0 (i =1,2, ···, n), yj≥0 (j =1, 2,···, m)           s t   

000 12 In b 0bbb∶b 000….1an1an2 C=(0,1,1,1,0,0 显然问题(Ⅱ)有一现成的可行基 01 B 00:0 称为人造基) 00

. 0 . 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 3 2 1 1 2 2 1 2 2 2 1 1 1 2 1 1 2                     =                 − − − = m m m m n n n n b b b b a a a a a a a a a c c c                 A b C=(0,1,1, ···,1,0,0, ···, 0) （称为人造基） 0 0 0 1 0 1 0 0 1 0 0 0               =        B 显然,问题(Ⅱ)有一现成的可行基

00 LP=01…0a1…anb(问题(Ⅱ)的简化增广矩阵 ∑an∑a2…∑an∑ 0…0 (1)+(2)+…+(m) T(B m2 mn (问题(Ⅱ)对应基B的单纯形矩阵)

( ) 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 ( ) 1 2 1 1 1 2 1 1 1 2 1 1 1 2 1 1 (1) (2) ( ) 1 1 1 1 1 1 T B L P =                   − − − ⎯⎯⎯⎯⎯→                 − − − − =     = = = = + + + m m m n m n n m i i m i i n m i i m i i m m m n m n n a a a b a a a b c c c a a a b a a b a a b c c                               (问题(Ⅱ)的简化增广矩阵) (问题(Ⅱ)对应基B的单纯形矩阵)

从人造基B开始,应用单纯形法,必可求得问 题(Ⅱ)最优基B对应的单纯形矩阵 m+1 m+n+1 m+1 m+n+1 S (B)=6b 1,m+101,m+2 dn Lmtn+1 m2 m m1,m+2 m1,m+n+1 辅助问题最优基确定的目标函数值与求解原 问题的关系

从人造基B开始,应用单纯形法,必可求得问 题(Ⅱ)最优基 对应的单纯形矩阵 二、辅助问题最优基确定的目标函数值与求解原 问题的关系. ( ) . 1 2 , 1 , 2 , 1 1 1 1 2 1, 1 1, 2 1, 1 1 1 2 1 2 1 0 1 2 1 2 1 0                   = + + + + + + + + + + + + + + + + m m m m m m m m n m m m m n m m m n m m m n b b b b b d b b b b b d s z                         T B B

情形1若=minz=0,且问题(Ⅱ)的最优基B中不 含人工变量列,则B就是原问题I)的可行基这时,只要 在T(B中去掉S,yy2mn所在列及第一行,便得原问 题(I)关于B的单纯形矩阵,再应用单纯形方法,即可求 解原问题(I 例1求解线性规划问题 min S=-x+ 2x2+ x3 2x1-x2+x3>-4 Sx1+2x2=6 3>0

情形1 若z0 = minz = 0,且问题(Ⅱ)的最优基 中不 含人工变量列, 则 就是原问题(Ⅰ)的可行基.这时,只要 在T( )中去掉 S, y1 ,y2 ,…,ym 所在列及第一行, 便得原问 题(Ⅰ)关于 的单纯形矩阵,再应用单纯形方法, 即可求 解原问题(Ⅰ). 例1 求解线性规划问题 min S = - x1+ 2x2+ x3 2x1 - x2 + x3≥ -4 x1+ 2x2 = 6 x1 , x2 , x3 ≥0 B B B      s t B

解引进松弛变量x将问题化为标准形式 (I) min S=-x+ 2x2+ x3 2x1+x2-x3+x4=4 stx1+2x2=6 1,x2,x3,x4>0

解 引进松弛变量 x4 , 将问题化为标准形式 (Ⅰ) min S = - x1+ 2x2+ x3 - 2x1+ x2 - x3+ x4 = 4 x1+ 2x2 = 6 x1 , x2 , x3 , x4≥0      s t

由于没有现成的可行基,故引入辅助问题 minz=V1+y2 +x1-2x2-x3=0 2x1+x 2-x3+x4=4 S·t +x1+2x x≥0,y≥0(i=1,2,3,4;j=1,2

由于没有现成的可行基, 故引入辅助问题. (Ⅱ) min z = y1+ y2 S + x1－2x2－x3 = 0 y1 －2x1 + x2 －x3 + x4 = 4 y2 + x1 + 2x2 = 6 xi≥0, yj≥0 ( i = 1, 2, 3, 4; j = 1, 2 )        s t

001-2-10 A=010-21-11人造基B=(P,P2P3) 0-1-100000 1001-2-100 (LP) 010-21-1 4 00112006

              − − − − − − = =           − − − − = 0 0 1 1 2 0 0 6 0 1 0 2 1 1 1 4 1 0 0 1 2 1 0 0 0 1 1 0 0 0 0 0 ( ) ( , , ) 0 0 1 1 2 0 0 0 1 0 2 1 1 1 1 0 0 1 2 1 0 0 1 2 3 L P A 人造基B P P P

000-13-1110 001-2-100 (1)+(3)+(4) 010-211,-B)=T(P,P,P) 00112006 000 -106 T(B)=T(P1,P2,P3) 1003

( ) ( , , ) 1 0 0 3 2 1 2 1 0 0 0 1 1 1 2 5 2 1 0 1 1 0 1 2 0 1 0 6 0 1 1 1 2 5 2 3 0 0 ( ) ( , , ) 0 0 1 1 2 0 0 6 0 1 0 2 1 1 1 4 1 0 0 1 2 1 0 0 0 0 0 1 3 1 1 10 1 1 2 5 0 1 2 3 (1) (3) (4) T B T P P P T B T P P P = =                   − − − − − − − ⎯⎯⎯⎯→ = =               − − − − − − ⎯⎯+ ⎯+ ⎯→