2.3对偶单纯形法 对偶单纯形法是求解对偶规划的一种方法 对偶单纯形法:利用对偶理论得到的一个 求解线性规划问题的方法
对偶单纯形法是求解对偶规划的一种方法 × 对偶单纯形法：利用对偶理论得到的一个 求解线性规划问题的方法
单纯形法(原始单纯形法)的两个条件: 1、问题为标准型 2、有初始基本可行解 求minz=2x1+x 2 标准型为 3x1+x,≥3 maxZ′=-2 4x1+3x2≥6 3x1+x2-x3=3 s.t. x1+2x,≤3 4x1+3x2-x 6 s t x1+2x2+x5=3 引进人工变量x,x7 x12x2x32x4,x5≥0 max Z=-2x-x-Mx Mx 2 6 7 3x +x=3 用单纯形 4x1+3x2-x4+x7=6 法求解 s.t. x,+2x,+x=3 x,,x,,x2x1.x。≥0
单纯形法（原始单纯形法）的两个条件： 1、问题为标准型 2、有初始基本可行解 + + + = + , 0 2 3 4 3 6 3 3 . min 2 1 2 1 2 1 2 1 2 1 2 x x x x x x x x st 求 Z x x + + = + − = + − = = − − , , , , 0 2 3 4 3 6 3 3 . max 2 1 2 3 4 5 1 2 5 1 2 4 1 2 3 1 2 x x x x x x x x x x x x x x st Z x x 标准型为 + + = + − + = + − + = = − − − − , , , , 0 2 3 4 3 6 3 3 . max 2 1 2 3 4 5 1 2 5 1 2 4 7 1 2 3 6 1 2 6 7 6 7 x x x x x x x x x x x x x x x x st Z x x Mx Mx 引进人工变量x ，x 用单纯形 法求解
对偶单纯形法的优点: 1、不需要人工变量; 2、当变量多于约束时,用对偶单 纯形法可减少迭代次数; 3、在灵敏度分析中,有时需要用对 偶单纯形法处理简化
对偶单纯形法的优点： 1、不需要人工变量； 2、当变量多于约束时，用对偶单 纯形法可减少迭代次数； 3、在灵敏度分析中，有时需要用对 偶单纯形法处理简化
原始单纯形法的基本思路: 对标准型maxz=CX A=B N AX=b B st Ⅹ≥0.b≥0 C=(CB CN) (P P P)设B=(PP2…P)是可行基 于是X=b◆→(BM|=b←BXB+NXx=b N B可逆 X=B 6-B NXN 且Z=(CCN BB +C,Ⅹ X CB(B b-B NXN)+CNXN B Bb+(CM-C BBN DX
于是AX = b ( ) b X X B N N B = BX B + NX N = b B 可逆 X B B b B NX N −1 −1 = − ( ) = N B B N X X 且Z C C = CB XB +CN X N = CB B b − B NX N +CN X N − − ( ) 1 1 CB B b CN CB B N X N ( ) −1 −1 = + − 0, 0 . max = = X b st AX b 对标准型 z CX ( ) A P1 P2 Pm Pm+1 Pn = 设B = (P1 P2 Pm )是可行基 A = (B,N) = N B X X X 原始单纯形法的基本思路： ( ) C = CB CN
对问题maxz= CX max Z=CBb+(C-CBN)XN s t AX=b A=B-b-B-INX X≥0 Xn≥0,Xx≥0 取可行基 检验数 关于可行基B的典则形式 B=(Pp 令xN=0得YB=Bb≥0得基本可行解X1=(Bb,0 1、若所有的检验数C-BN≤0,则x为最优解 2、检验数CN-CBN中存在一个分量>0,且该分量对应的列 向量中所有的分量0,且该分量对应 的列向量中至少有一个分量>0,则存在更好的基本可行解 做换基迭代:在迭代过程中,始终保持对应的基本解可行 即XB=Bb≥0 并使检验数C-C。B-N中>0的分量 个数越来越少,最终CN-CBN≤0
0 . max = = X s t AX b 对问题 z CX ( ) B = P1 P2 Pm 取可行基 Z CB B b CN CB B N X N max ( ) − 1 − 1 = + − X B B b B NX N − 1 − 1 = − XB 0 , X N 0 关于可行基 B的典则形式 检验数 令X N = 0 0 1 = − 得X B B b ( ) = − ,0 1 得基本可行解X1 B b 1 0 1 − − 、若所有的检验数 C N B N , 则X 1为最优解 的列向量中至少有一个分量 则存在更好的基本可行解 、若检验数 中至少有一个分量 且该分量对应 0, 3 0, 1 − − CN CB B N 向量中所有的分量 则目标函数值在可行解域内无上界 、检验数 中存在一个分量 且该分量对应的列 0, 2 0, 1 − − CN CB B N 做换基迭代:在迭代过程中，始终保持对应的基本解可行 0 1 = − 即XB B b 0 0 1 1 − − − −C C B N C C B NN B N B 个数越来越少，最终 并使检验数 中 的分量
原始单纯形法的迭代过程: 取可行基 对问题maxz=CXB=(PP2…P) st AX=b 令XN=0得X=B-b≥0 X≥0 得基本可行解x1=(Bb10) maxZ=CbBb+(CN-CBBNXN 0.XR+(CN-CRBNX=Z-CrBb X=B6-B NX X+BX=B b X≥0,X≥0 初始单纯形表: 若CN-BN≤0,X1为最优解 常数项 否则,选定入基、出基变量 检验行0 CN-CBBIN<0Z.:-对该单纯形表做行变换 E B-IN Bb≥0直至CN=B1N≤0 得最优单纯形表 最优单纯形表的充要条件:CN-BN≤0
0 . max = = X st AX b 对问题 z CX ( ) B = P1 P2 Pm 取可行基 B CN CB B N X N max Z C B b ( ) −1 −1 = + − X B B b B NX N −1 −1 = − XB 0, X N 0 X C C B N X Z C B b B N B N B 1 1 0 ( ) − − + − = − X B B NX N B b −1 −1 + = 令X N = 0 0 1 = − 得XB B b 若CN − B −1 N 0，X1 为最优解 XB XN 常数项 检验行 0 CN- CBB-1N Z- CBB-1b XB E B-1N B-1b 初始单纯形表： 0 原始单纯形法的迭代过程： ( ) = − ,0 1 得基本可行解X1 B b ? 0 否则，选定入基、出基变量 对该单纯形表做行变换 直至CN − B −1 N 0， 得最优单纯形表 最优单纯形表的充要条件：CN − B −1 N 0
对偶单纯形法的基本思路: 对maxz=CX maxZ=CBBb+(CN-CBB NXN .t aX= b X=B 6-B NX Ⅹ≥0 X,≥0.X,≥0 取基B=(PP 令X=0得XB=Bb 若Bb≥0,X为最优角 得基本解X1=(B b0 否则,换基迭代 若C-C,B1N≤0 选定入基、出基变量 作对偶单纯形表: 对该单纯形表做行变换 Xp X B 常数项(始终保持C-BN≤0 检验行0 CN-CBB-N≤OzCB直至Bb≥0, B E B-IN Bb≥0得最优对偶单纯形表 最优对偶单纯形表的充要条件:B1b≥0
0 . max = = X st AX b 对 z CX ( ) 取基B = P1 P2 Pm B CN CB B N X N max Z C B b ( ) −1 −1 = + − X B B b B NX N −1 −1 = − XB 0, X N 0 对偶单纯形法的基本思路： = 0 令X N X B b B −1 得 = ( ) = − ,0 1 得基本解X1 B b 0 : 1 − − 若CN CB B N XB XN 常数项 检验行 0 CN- CBB-1N Z- CBB-1b XB E B-1N B-1b 作对偶单纯形表： 0 ?0 , X1 为最优解 否则，换基迭代 对该单纯形表做行变换 直至B −1 b 0， 得最优对偶单纯形表 0 1 − 若B b (始终保持CN − B −1 N 0） 选定入基、出基变量 最优对偶单纯形表的充要条件： 0 1 − B b
例:求minZ=2x1+x 3x1+x2≥3 取基B=(P3,P4,P5) 4x1+3x,≥6 基本解X=(00,-3,-63) s.t. x1+2x,≤3 XIX2X3X4X5 检验行 检-2-b000Z 不 X.x 解:标准型为 ≤0 1100|-3 max Z 2x1 X1-4-30 3x 2 3 S基B的典则形式 分析: 2x42x5≥O 若X3或X4所在的行的a均 即mnxz=-2x1-x2 非负, 3x1-x,+x 则问题一定无可行解 x +X st< x1+2x2 否则,做换基迭代 x x1,x2,x2,x4,x≥0
+ + + = + , 0 2 3 4 3 6 3 3 . min 2 1 2 1 2 1 2 1 2 1 2 x x x x x x x x st 例：求 Z x x + + = + − = + − = = − − , , , , 0 2 3 4 3 6 3 3 . max 2 1 2 3 4 5 1 2 5 1 2 4 1 2 3 1 2 x x x x x x x x x x x x x x st Z x x 解：标准型为 + + = − − + = − − − + = − , , , , 0 2 3 4 3 6 3 3 . 1 2 3 4 5 1 2 5 1 2 4 1 2 3 x x x x x x x x x x x x x x st max 2 1 2 即 Z = − x − x ( ) 3 4 5 取基B = P ,P ,P 基本解X = (0，0，− 3，− 6，3) 基B的典则形式 X1 X2 X3 X4 X5 检 -2 -1 0 0 0 Z X3 -3 -1 1 0 0 -3 X4 -4 -3 0 1 0 -6 X5 1 2 0 0 1 3 不 可 行 检验行 ≤0 分析： 若X3或X4所在的行的aij均 非负， 则问题一定无可行解 否则，做换基迭代
X1X,Ⅹ2X1X 确定出基变量: 检 1000|Z X3|-3|-1100-3 设bn=min{b;|b1<0} X4-4-3)0 则取b所在行的基变量 X5120013 为出基变量 1/ 21/3 即取X4为出基变量 XⅩ3XⅩ 4 检-2/300-1/30Z+2 2、确定入基变量: X3-5/301-1/30|-1 原 则: X24/310-1/302 保持检验行系数<0 X5(5/3002/31-1 设 mIn lari<o X X 00-3/5-2/5Z+12/5 日则取x为入基变量 x3001-1-10 最优解X=(,-,0,0,0) 101/54/56/5 X11 00-2/5-3/53/5 最优值Z=-12
X1 X2 X3 X4 X5 检 -2 -1 0 0 0 Z X3 -3 -1 1 0 0 -3 X4 -4 -3 0 1 0 -6 X5 1 2 0 0 1 3 1、确定出基变量： 设br =min{bi | bi <0} 则取br所在行的基变量 为出基变量 即取X4为出基变量 2、确定入基变量： 原则： 保持检验行系数≤0 0 0 min | 0 ri i ri ri i a a a = 设 则取xi 0 为入基变量 1 3 X1 X2 X3 X4 X5 检 X3 X2 X5 1 2 X1 X2 X3 X4 X5 检 X3 X2 X1 最优解 （ ，，0，0，0） 5 6 5 3 X = 5 最优值Z = −12 -2/3 0 0 -1/3 0 Z+2 -5/3 0 1 -1/3 0 -1 4/3 1 0 -1/3 0 2 -5/3 0 0 2/3 1 -1 0 0 0 -3/5 -2/5 Z+12/5 0 0 1 -1 -1 0 0 1 0 1/5 4/5 6/5 1 0 0 -2/5 -3/5 3/5
例:求mnZ=2x1+x2解:标准型为 3x1+x,≥3 maX 2 4x1+3x2≥6 3x1+x2-x3=3 s t 4x1+3x2-x4=6 x1+2x2≤3 +2x,+ x1,x2≥0 1 2 4255 所求问题的最优解最优解X 36 ,0,0,0 36 55 最优值z12 最优值Z
（ ，） 所求问题的最优解 5 6 5 3 X = 5 12 最优值Z = + + + = + , 0 2 3 4 3 6 3 3 . min 2 1 2 1 2 1 2 1 2 1 2 x x x x x x x x st 例：求 Z x x + + = + − = + − = = − − , , , , 0 2 3 4 3 6 3 3 . max 2 1 2 3 4 5 1 2 5 1 2 4 1 2 3 1 2 x x x x x x x x x x x x x x st Z x x 解：标准型为 最优解 （ ，，0，0，0） 5 6 5 3 X = 5 最优值Z = −12