·线性规划原问题与对偶问题的对应关系归纳于表3-3。对于任意一个线性规划问题可以按照表3-3原问题与对偶问题的对应关系，直接构造其对偶问题·例如，根据表3-3的对应关系，对例3可以直接构造其对偶问题：Min W =20y;+10y2+5y3s.t. 3yi+4y2+y3 ≥42y1-3y2+y3 =5yi≥0，y,≤0,Y符号不限
• 线性规划原问题与对偶问题的对应关系归 纳于表3-3。对于任意一个线性规划问题， 可以按照表3-3原问题与对偶问题的对应关 系，直接构造其对偶问题。 • 例如，根据表3-3的对应关系，对例3可以 直接构造其对偶问题： • Min W =20y1+10y2+5y3 s.t. 3y1+4y2+y3 ≥4 2y1 -3y2+y3 =5 y1 ≥0 ，y2≤0 ,y3符号不限
第二节对偶理论、单纯形法的矩阵表示一z=CX+CXmaxz = CXmaxs.t.AX+IX, =bAX ≤bs.t.X,X, ≥0X≥0XBXnmax z=[CB,C,C][X.XB[B,N,I]X=bs.t.LXIXB,XN,X, ≥0
第二节 对偶理论 • 一、单纯形法的矩阵表示 , , 0 . . [ , , ] max [ , , ] = = B N I I N B I N B B N I X X X b X X X st B N I X X X z C C C , 0 . . max + = = + I I I I X X st AX IX b z CX C X 0 . . max = X s t AX b z CX
max z=CXβ+CX +CXBXB + NX +IX, = bs.t.XB,XN,X, ≥0max z=CXβ+CyX+CXX=B'b-B'NX-B'IXs.t.XB,XN,X, ≥0max z=C,B"b+(C -C,B'M)X +(C -C,B'D)Xs.t. Xβ+B'NX +B'IX, =B'bXB,X,X, ≥0
, , 0 . . max + + = = + + B N I B N I B B N N I I X X X st BX NX IX b z C X C X C X , , 0 . max 1 1 1 = - - = + + - - - B N I B N I B B N N I I X X X st X B b B NX B IX z C X C X C X , , 0 . . max ( ) ( ) 1 1 1 1 1 1 + + = = + - + - - - - - - - B N I B N I B N B N I B I X X X st X B NX B IX B b z C B b C C B N X C C B I X
表3-4 矩阵形式的初始单纯形表非基变量基变量初始单纯形表基XBXIXnbB1NCXi0CB-C,BCn-C,NCj=Cj-Zi口表3-5经选代后矩阵形式的单纯形表基变量非基变量最优单纯形表基XBXIXNB-1IB-INCXβB-Ib0Cr-CB B-1Cn-CB B-1 NC=C;-Zi
初始单纯形表 非基变量 基变量 基 XB XN XI CI XI b B N I Cj=cj -zi CB-CIB CN-CIN 0 最优单纯形表 基变量 非基变量 基 XB XN XI CB XB B-1 b I B-1N B-1 Cj=cj -zi 0 CN-CB B-1 N CI -CB B-1 表3-4 矩阵形式的初始单纯形表 表3-5 经迭代后矩阵形式的单纯形表
[例4]第二章第三节的例6中表2-3、表2-4、表2-5给出了单纯形法的迭代过程，表2-3为初始单纯形表，表2-5为最终单纯形表，试依据表3-4、表3-5的依存关系指出B，B-1，B-1 b，CB-lb，-CB-1003025CjCBb0X1X2X3X4XB021044020X3002130[3] 10→X400Ci2530个Z=Cb × b=001253/8-1/415/2X210530-1/41/2X1C00-15/8-35/4Z=337.5
[例4]第二章第三节的例6中表2-3、表2-4、表2-5给 出了单纯形法的迭代过程，表2-3为初始单纯形表， 表2-5为最终单纯形表，试依据表3-4、表3-5的依 存关系指出Ｂ，B-1 ，B-1ｂ，CBB-1b，-CBB-1 CB cj 30 25 0 0 b θ x1 x2 x3 x4 0 x3 2 4 1 0 40 20 0 x4 [3] 2 0 1 30 10→ Cj 30↑ 25 0 0 Z=CB×b=0 25 x2 0 1 3/8 -1/4 15/2 30 x1 1 0 -1/4 1/2 5 Cj 0 0 -15/8 -35/4 Z=337.5 XB Xj