【正文】 由于 X(0) =(1,1,1,1)T, Y(0)=(1,1)T分別為(L),(D)的可行解， Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 ≤20 . 2x1+ x2+3x3+2x4 ≤20 x1,x2,x3,x4 ≥0 ??? Min W = 20y1+20y2 y1+2y2 ≥ 1 2y1+ y2 ≥ 2 . 2y1+3y2 ≥ 3 3y1+2y2 ≥ 4 y1,y2≥0 ???????Z(0)=10 W(0)=40 W≥10 推論 2 Z≤40 推論 3 故 Z≤40,W≥10. 19 例 121 2 31 2 31 2 3m ax221, , 0z x xx x xx x xx x x??? ? ? ?? ? ? ?? 試用對(duì)偶理論證明上述線性規(guī)劃問(wèn)題無(wú)最優(yōu)解 證明：首先看到該問(wèn)題存在可行解，如 X=(0,0,0) 上述問(wèn)題的對(duì)偶問(wèn)題為 1212121212m i n 22110,0 w y yyyyyyyyy??? ? ??????由第一約束條件知對(duì)偶問(wèn)題無(wú)可行解，因原問(wèn)題有可行解，由推論 1，原問(wèn)題無(wú)最優(yōu)解。 若 LP問(wèn)題無(wú)可行解， 則對(duì)偶問(wèn)題或有無(wú)界解 或無(wú)可行解。 20 定理 2（最優(yōu)性準(zhǔn)則） 當(dāng) LP問(wèn)題目標(biāo)函數(shù)值與其對(duì)偶問(wèn)題目標(biāo)函數(shù)值相等時(shí)，各自的可行解即為最優(yōu)解。 (P57) 若 X(0),Y(0)分別為 (L)， (D)的可行解 ,且 CX(0)＝ Y(0)b, 則 X(0),Y(0)分別為 (L)， (D)的最優(yōu)解。 證明： 由定理 1可知，對(duì)于 (L)的任意可行解 X，有 CX ≤ Y(0)b 由于 CX(0) =Y(0)b， CX ≤CX(0) ， 故 X(0)為 (L) 的最優(yōu)解； 同理， 由定理 1可知， 對(duì)于 (D)的任意可行解 Y，有Yb≥CX(0)， 由于 CX(0) =Y(0)b， Yb≥Y(0)b， Y(0)為 (D)的最優(yōu)解。 21 例 5 ()DMax Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 ≤20 . 2x1+ x2+3x3+2x4 ≤20 x1,x2,x3,x4 ≥0 ??? Min W = 20y1+20y2 y1+2y2 ≥ 1 2y1+ y2 ≥ 2 . 2y1+3y2 ≥ 3 3y1+2y2 ≥ 4 y1,y2≥0 ???????由于 X(0)=(0,0,4,4)T, Y(0)=(6/5,1/5)T是 (L)， (D)的 可行解且 CX(0)=bTY(0)=28，所以 X(0),Y(0)分別為 (L)， (D)的最優(yōu)解。 22 線性規(guī)劃的矩陣表示 Max Z=CX . AX ≤b X≥0 ???令 A=(B,N), X= XB ,C=(CB,CN) XN ??????由 AX+IXs=b (B,N,I) XB =b BXB+NXN+IXs=b BXB=bNXNIXs XN Xs XB=B1bB1NXN B1Xs (1) 將 (1)式代入目標(biāo)函數(shù)得 Z=CX = (CB,CN) XB =CBXB+CNXN= CB (B1bB1NXN B1Xs)+CNXN XN = CBB1b+(CNCBB1N)XN CB B1Xs (2) ????????????Max Z=CX+0Xs . AX+IXs=b X, Xs≥0 ???用非基變量表示基變量 用非基變量表示目標(biāo)函數(shù) 23 σ=(0, CNCBB1N, CB B1) =(CCBB1A, CB B1) (CCBB1A, CB B1)= (CCBB1(B,N), CB B1) =(CBCBB1B, CNCBB1N, CB B1) =(0, CNCBB1N, CB B1) 若 CNCBB1N≤0, CB B1≤0,則 Z為最優(yōu)解 令 XN=0, Xs=0， 可以得到基 B的基可行解和目標(biāo)函數(shù)值 XB=B1bB1NXN B1Xs Z= CBB1b+(CNCBB1N)XN CB B1Xs X=(XB, XN, Xs)=(B1b,0,0) Z= CBB1b 24 C CB XB b XB XN XS Z CB XB B1b CB CN 0 I CNCBB1N B1N B1 0 CBB1 CBB1b 25 初始單純形表 cj CB XB b x1 x2 x3 x4 x5 σj ?cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 0 x4 3 x2 2 16 3 [1] 0 1 0 1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 σj 9 2 0 0 0 3/4 0 x3 0 x4 0 x5 2 3 0 0 0 8 16 12 1 2 1 0 0 4 0 0 1 0 0 [4] 0 0 1 2 3 0 0 0 0 4 3 經(jīng)過(guò)一次迭代 初始基 第一輪迭代后的基 P3 P4 P5 1 0 0 0 1 0 0 0 1 B= P3 P4 P2 1 0 2 0 1 0 0 0 4 B’= 1 0 1/2 0 1 0 0 0 1/4 B’1= 26 初始單純形表 cj CB XB b x1 x2 x3 x4 x5 σj ?cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 0 x4 3 x2 2 16 3 [1] 0 1 0 1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 σj 9 2 0 0 0 3/4 0 x3 0 x4 0 x5 2 3 0 0 0 8 16 12 1 2 1 0 0 4 0 0 1 0 0 [4] 0 0 1 2 3 0 0 0 0 4 3 經(jīng)過(guò)一次迭代 1 0 1/2 0 1 0 0 0 1/4 B’1= B’1 b= 1 0 1/2 0 1 0 0 0 1/4 8 16 12 2 16 3 = Z= CBB’1b=9 27 初始單純形表 cj CB XB b x1 x2 x3 x4 x5 σj ?cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 0 x4 3 x2 2 16 3 [1] 0 1 0 1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 σj 9 2 0 0 0 3/4 0 x3 0 x4 0 x5 2 3 0 0 0 8 16 12 1 2 1 0 0 4 0 0 1 0 0 [4] 0 0 1 2 3 0 0 0 0 4 3 經(jīng)過(guò)一次迭代 1 0 1/2 0 1 0 0 0 1/4 B’1= B’1A= CBB1 =(0, 0, 3/4) A’ 28 定理 3（強(qiáng)對(duì)偶定理） 若 (L)， (D)均有可行解，則 (L)， (D)均有最優(yōu)解， 且目標(biāo)函數(shù)最優(yōu)值相等。 證明： 設(shè) X(0),Y(0)分別為 (L)， (D)的可行解 ,由弱對(duì)偶定理(推論 3)，對(duì)于 (L)的任意可行解 X，有 CX ≤ Y(0)b，所以CX在可行域內(nèi)有上界，故 (L)有最優(yōu)解。 同理，對(duì)于 (D)的任意可行解 Y， 由弱對(duì)偶定理 （推論 2） ， 有 Y b≥CX(0)，所以 Yb在可行域內(nèi)有下界，故 (D)有最優(yōu)解。 設(shè) (L)的最優(yōu)解為 X(0)，且 X(0)所對(duì)應(yīng)的最優(yōu)基為 B， X(0)可以表示為 X(0) = XB(0) = B1b XN(0) 0 ????????????max z=CX。 AX≤b。 X≥0……(L) min w=Yb。 YA≥C。 Y≥0……(D) 29 則 (σA,σS)= (C,0) –CBB1(A, I)=(C –CBB1A, –CBB1)≤0 由于 C–CBB1A≤0， 所以 CBB1A ≥C (1) 又 –CBB1≤0， 故 CBB1≥0. (2) 令