【正文】 題有可行解，由推論 1，原問題無最優(yōu)解。 20 定理 2（最優(yōu)性準(zhǔn)則） 當(dāng) LP問題目標(biāo)函數(shù)值與其對(duì)偶問題目標(biāo)函數(shù)值相等時(shí)，各自的可行解即為最優(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)解。 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)過一次迭代 初始基 第一輪迭代后的基 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)過一次迭代 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)過一次迭代 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)值相等。 同理，對(duì)于 (D)的任意可行解 Y， 由弱對(duì)偶定理 （推論 2） ， 有 Y b≥CX(0)，所以 Yb在可行域內(nèi)有下界，故 (D)有最優(yōu)解。 AX≤b。 YA≥C。 ??????30 推論： 在用單純形法求解 LP問題 (L)的最優(yōu)單純形表中，松弛變量的檢驗(yàn)數(shù)的相反數(shù)就是其對(duì)偶問題 (D)的最優(yōu)解。 對(duì)偶問題的最優(yōu)解為 Y*=(3/2, 1/8, 0)T 運(yùn)用單純形法計(jì)算得原問題的最終表如下： 32 推論：對(duì)偶問題的最優(yōu)解對(duì)應(yīng)于原問題的最優(yōu)單純型表中松弛變量檢驗(yàn)數(shù)的相反數(shù)或剩余變量的檢驗(yàn)數(shù)。y3 ≤0 ???cj 2 3 0 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 3 x2 2 x1 0 x4 100 250 125 0 1 2 0 1 2 0 1 0 1 0 1 1 0 0 0 1 1 1 1 1 原問題的最優(yōu)單純型表如下所示： 0 0 4 0 1 4+M M Y*=(4, 0, 1)T w*=800 例 34 定理 4（互補(bǔ)松弛定理） 在最優(yōu)情況下，原問題的第 i個(gè)決策變量與其對(duì)偶問題第 i個(gè)約束中的松弛變量的乘積恒為零 。 37 ****1 2 3 42 2 3 2 0 ( 1 )xxxx? ? ? ?* * * *1 2 3 42 3 2 2 0 ( 2 )x x x x? ? ? ?** . . .122 1 2 0 4 1 6 1yy? ? ? ? ?** . . .122 2 4 0 2 2 6 2yy? ? ? ? ?**342 3 2 0xx??**343 2 2 0xx??x1*=x2*=0. 解：由于 y1* 0, y2* 0,由互補(bǔ)松弛性知 解得 x3*= x4*=4. 所以 (L)的最優(yōu)解為 X*=(0,0,4,4)T 因?yàn)? 代入 (1),(2)得 由互補(bǔ)松弛性知， 38 若 X*,Y* 分別為 (L),(D)的最優(yōu)解，那么 CX*=Y*b。 第三節(jié) 對(duì)偶問題的經(jīng)濟(jì)解釋 影子價(jià)格 一、影子價(jià)格 (Shadow Price) 影子價(jià)格是最優(yōu)配置下資源的理想價(jià)格。 39 1 0 0 1/4 0 0 0 2 1/2 1 0 1 1/2 1/8 0 4 4 2 2 x1 0 x5 3 x2 x1 x2 x3 x4 x5 CB XB b 2 3 0 0 0 cj 14 0 0 3/2 1/8 0 例 8 下面是一張 LP問題的最優(yōu)單純形表，其中 x3, x4, x5為松弛變量 則對(duì)偶問題的最優(yōu)解為 Y*=(, , 0)T 40 例 8 X* =(4, 2)T， Z* =14