§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