原始单纯形法的迭代过程: 取可行基 对问题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均 非负， 则问题一定无可行解 否则，做换基迭代