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,且该分量对应的列 向量中所有的分量<O,则目标函数值在可行解域内无上界 3、若检验数CM-CBN中至少有一个分量>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 个数越来越少，最终 并使检验数 中 的分量