1、1第三章第三章線性規(guī)劃的對偶理論及其應用線性規(guī)劃的對偶理論及其應用書山有路勤為徑，學海無涯苦作舟書山有路勤為徑，學海無涯苦作舟對偶是一種普遍現(xiàn)象對偶是一種普遍現(xiàn)象2假設工廠考慮不進行生產(chǎn)而把全部可利用假設工廠考慮不進行生產(chǎn)而把全部可利用的資源都讓給其他企業(yè)，工廠希望給這些的資源都讓給其他企業(yè)，工廠希望給這些資源定出一個合理的價格，即使別的單位資源定出一個合理的價格，即使別的單位愿意購買，又使本工廠能得到生產(chǎn)這些產(chǎn)愿意購買，又使本工廠能得到生產(chǎn)這些產(chǎn)品所能獲得的最大收益。品所能獲得的最大收益。第一節(jié)第一節(jié) 對偶問題對偶問題一、一、 對偶問題的提出對偶問題的提出實例實例1（典型示例）：（典型示例）

2、： 3 2 利潤利潤 12公斤公斤 4 0 原料原料B 16公斤公斤 0 4 原料原料A 8臺時臺時 2 1 設設 備備資源限量資源限量 II I 產(chǎn)品產(chǎn)品y3y2y1決策變量決策變量12168資源限量資源限量x23402IIx12041I決策決策 變量變量 每臺每臺 收益收益 原料原料B 原料原料A 設備設備資源資源產(chǎn)品產(chǎn)品3 03402204112168min321321321321y,y,yyyyyyy. t . syyyWy3y2y1決策變量決策變量12168資源限量資源限量x23402IIx12041I決策決策 變量變量 每臺每臺 收益收益 原料原料B 原料原料A 設備設備資源資源產(chǎn)

3、品產(chǎn)品 01241648232max21212121x,xxxxx. t . sxxZ4y4y3y2y1200300400600限額限額x330004322Cx240002314Bx120001123A 每臺每臺 收益收益 丁丁 丙丙 乙乙 甲甲材料材料產(chǎn)品產(chǎn)品 0,200423003340022600243:300040002000321321321321321321xxxxxxxxxxxxxxxSTxxxMaxZ假設工廠考慮不進行生產(chǎn)而把假設工廠考慮不進行生產(chǎn)而把全部可利用的資源都讓給其他全部可利用的資源都讓給其他企業(yè)，工廠希望給這些資源定企業(yè)，工廠希望給這些資源定出一個合理的價格，即使別

4、的出一個合理的價格，即使別的單位愿意購買，又使本工廠能單位愿意購買，又使本工廠能得到生產(chǎn)這些產(chǎn)品所能獲得的得到生產(chǎn)這些產(chǎn)品所能獲得的最大收益。最大收益。 0,300043224000234200023:20030040060043214321432143214321yyyyyyyyyyyyyyyySTyyyyMinw實例實例2：5比較上述模型，可以得出兩者之間的一些關系：比較上述模型，可以得出兩者之間的一些關系： 1. 兩個問題，一個是極大化，另一個是極小化；兩個問題，一個是極大化，另一個是極小化； 2. 一個問題的一個問題的變量變量數(shù)等于另一問題的數(shù)等于另一問題的方程方程數(shù)，反數(shù)，反之亦然；

5、之亦然； 3. 一個問題的一個問題的目標目標函數(shù)系數(shù)是另一個問題的約束函數(shù)系數(shù)是另一個問題的約束方程方程右端右端常數(shù)，反之亦然；常數(shù)，反之亦然； 4. 兩個問題的約束方程系數(shù)矩陣互為轉置。兩個問題的約束方程系數(shù)矩陣互為轉置。稱變量稱變量yi為第為第一個一個LP的第的第i個對偶變量，個對偶變量，或第或第一個一個LP的第的第i約束相應的對偶變量約束相應的對偶變量6 對偶問題的提出有其理論依據(jù)，可由對偶問題的提出有其理論依據(jù)，可由“單純單純形法的矩陣描述形法的矩陣描述”加以解釋。加以解釋。 TTTBNBBBTBSBNNBSBNNBBBCYAAYCABCCXXYBCBCYBCNBCCBCXNBCCXB

6、BCCXXbAXCXZ 002001LP00:0:0max11111111的的檢檢驗驗數(shù)數(shù)可可統(tǒng)統(tǒng)一一寫寫成成：、約約束束條條件件）（，由由令令決決策策變變量量）（問問題題如如下下：新新時時，得得最最優(yōu)優(yōu)解解。當當，其其檢檢驗驗數(shù)數(shù)可可表表示示為為：，對對于于 7為為原原問問題題的的對對偶偶問問題題。，問問題題而而后后出出現(xiàn)現(xiàn)的的為為原原問問題題，問問題題稱稱首首先先出出現(xiàn)現(xiàn)的的問問題題可可寫寫成成：新新的的故故義義目目標標函函數(shù)數(shù)取取最最小小才才有有意意的的上上界界為為無無限限大大則則由由目目標標函函數(shù)數(shù)）（0minLP0maxLP0.minLP,)(3TTTTTTTT1TTTT1T YCY

7、AYbWXbAXCXZYCYAtsYbWYCYAZbBCbYYbYbBCYBB8二、二、 對稱對稱LPLP問題問題1. 對稱形式的定義對稱形式的定義必須滿足下列條件：必須滿足下列條件： （1）變量為非負；）變量為非負； （2）約束條件為不等式。）約束條件為不等式。 對于對于max ，約束為，約束為“ ” ； 對于對于min，約束為，約束為“ ”。第一類對稱形式第一類對稱形式第二類對稱形式第二類對稱形式 0.maxXbAXtsCXZ 0.minTTTYCYAtsYbW9), 2 , 1(0), 2 , 1(. .max11njxmibxatsxcZjnjijijnjjj ), 2 , 1(0),

8、 2 , 1(.min11miynjcyatsybWimijiijmiii 2. 對稱對稱LPLP問題的對偶問題問題的對偶問題)(PP 0.maxXbAXtsCXZ)(DP 0.minYCYAtsYbWTTT)(PP 0.minYCYAtsYbWTTT)(DP 0.maxXbAXtsCXZ10例例3 3：寫出下列：寫出下列LPLP問題的對偶問題問題的對偶問題 0,12416482.32max21212121xxxxxxtsxxZ 0,34224.12168min3213121321yyyyyyytsyyyW對偶對偶對偶變量對偶變量y1y2y3原變量原變量x1x211 0.minYCYAtsYb

9、WTTT推導過程推導過程變形 0.maxXbAXtsCXZ)(PP對偶)(DP 0.maxYCYAtsYbWTTT3. 對偶問題的對偶對偶問題的對偶12對偶)(DP 0)(.)(minXbXAtsXCZTTTT 0.maxXbAXtsCXZ變形 0.maxYCYAtsYbWTTT結論：結論：對偶問題的對偶是原問題。對偶問題的對偶是原問題。13 0,1847433.43min32132132132121xxxxxxxxxxxxtsxxW 0,04 43343.87max321321321321321yyyyyyyyyyyytsyyyZ例例4 4：寫出下列：寫出下列LPLP問題的對偶問題問題的對偶

10、問題解解: : 上述上述LPLP問題的問題的 對偶問題為：對偶問題為：對偶變量對偶變量y1y2y3原變量原變量x1x2x314例例5 5：寫出下列：寫出下列LPLP問題的對偶問題問題的對偶問題 無無約約束束321321321321321, 0, 0221 2 .2maxxxxxxxxxxxxxtsxxxZ并并將將其其化化為為對對稱稱形形式式問問題題，代代入入上上述述用用解解：LPxxxxx 33322, 4.非對稱非對稱LPLP問題的對偶問題問題的對偶問題 0,221 1 2 .2max332133213321332133213321xxxxxxxxxxxxxxxxxxxxtsxxxxZ154

11、332211,yuyyuyu 令令問題變?yōu)椋簡栴}變?yōu)椋簞t上述則上述LP 無無約約束束231321321321321, 0, 0 1 2 12.22minuuuuuuuuuuuutsuuuW問問題題的的對對偶偶問問題題為為：上上述述問問題題的的定定義義，由由對對稱稱形形式式的的LPLP 0, 1 1 2 12 .22min432143214321432143214321yyyyyyyyyyyyyyyyyyyytsyyyyW16 無無約約束束321321321321321, 0, 02212.2maxxxxxxxxxxxxxtsxxxZ 無無約約束束231321321321321, 0, 0121

12、2.22minuuuuuuuuuuuutsuuuW)(PP)(DP17對偶關系：對偶關系：一個問題第一個問題第i個變量決定另一問題第個變量決定另一問題第i個約束，個約束，反之亦然。反之亦然。對稱的對應對稱的，非對稱的對應非對稱的對稱的對應對稱的，非對稱的對應非對稱的18直接寫出例直接寫出例5的的LP問題的對偶問題問題的對偶問題 無無約約束束321321321321321, 0, 02 21 2 :2xxxxxxxxxxxxSTxxxMaxZ32122uuuMinW 321uuu 3212uuu 321uuu 12 , 01 u,2無無約約束束u03 u1 :ST19 0 ,0 1 2 1 2

13、:22321321321321321uuuuuuuuuuuuSTuuuMinW無無約約束束3212xxxMaxZ :ST321xxx 321xxx 3212xxx 212, 01 x, 02 x無約束無約束3x 20已知已知LP問題：問題： 0,6002125350.32min212112121xxxxxxxtsxxZ1) 寫出其對偶模型；寫出其對偶模型；2) 如果用大如果用大M法求解原問題，請列出初始法求解原問題，請列出初始單純形表，并用單純形表，并用 標出主元素。標出主元素。補充作業(yè)補充作業(yè)3-1 21的的可可行行解解是是由由于于PP)0(X)0(T)0()0()0(DPPPYbCXYX

14、的的可可行行解解，則則、分分別別為為、若若證證明明：0,)0()0( XbAX所所以以的的可可行行解解是是由由于于DP)0(Y0)0( Y所所以以不不等等式式組組的的兩兩邊邊得得左左乘乘 PP)0(TYbYAXYTT)0()0()0( 第二節(jié)第二節(jié) LPLP問題的對偶理論問題的對偶理論定理定理1 1 弱對偶定理弱對偶定理: : 極大化原問題目標函數(shù)值總是不大極大化原問題目標函數(shù)值總是不大于其對偶問題的目標函數(shù)值。于其對偶問題的目標函數(shù)值。22同同時時轉轉置置得得) 1 ( )0()0()0(YbYAXTTT 0,)0()0( TTTXCYA又又(2) )0()0()0()0(CXCXYAXTT

15、TT 所所以以）得得）、（由由（21)0()0(YbCXT bYAXYTT)0()0()0( 結論：結論：在雙方都是可行解的情況下，極大化問題的在雙方都是可行解的情況下，極大化問題的 目標函數(shù)值總不大于其對偶問題目標函數(shù)值。目標函數(shù)值總不大于其對偶問題目標函數(shù)值。23推論推論1： 若若LP問題有無界解，則其對偶問題無可行解；問題有無界解，則其對偶問題無可行解； 若若LP問題無可行解，則對偶問題或無解或為無界解。問題無可行解，則對偶問題或無解或為無界解。推論推論2 2： 極大化問題的任何一個可行解所對應的目標極大化問題的任何一個可行解所對應的目標函數(shù)值都是其對偶問題的目標函數(shù)值的下界。函數(shù)值都是

16、其對偶問題的目標函數(shù)值的下界。 極小化問題的任何一個可行解所對應的目標極小化問題的任何一個可行解所對應的目標函數(shù)值都是其對偶問題的目標函數(shù)值的上界函數(shù)值都是其對偶問題的目標函數(shù)值的上界。推論推論3 3：)0()0(YbCXT 24例例6 6 考慮下面一對考慮下面一對LPLP問題問題 0,2023220322.432max4321432143214321xxxxxxxxxxxxtsxxxxZ 0,4233322212.2020min212121212121yyyyyyyyyytsyyW問問題題的的可可行行解解、分分別別是是由由于于DPPP)1 ,1(,)1 ,1 ,1 ,1()0()0(TTYX

17、 1040 WZ，所所以以其對偶問題為：其對偶問題為：25)0()0()0(,1YbCXYbCXTT 而而可可知知由由定定理理證明：證明：的的最最優(yōu)優(yōu)解解為為則則PP)0(X)0(CXCX )0()0()0(,1YbCXYbCXTT 而而可可知知由由定定理理的的最最優(yōu)優(yōu)解解為為則則DP)0(YYbYbTT )0(定理定理2 2 最優(yōu)性準則最優(yōu)性準則 當當LPLP問題目標函數(shù)值與其對偶問題問題目標函數(shù)值與其對偶問題目標函數(shù)值相等時，各自的可行解即為最優(yōu)解。目標函數(shù)值相等時，各自的可行解即為最優(yōu)解。若若X(0),Y(0)分別為分別為PP，DP的可行解的可行解, ,且且CTX(0)bTY(0) ，則

18、則X(0),Y(0)分別為分別為PP，DP的最優(yōu)解。的最優(yōu)解。26 0,2023220322:4324321432143214321xxxxxxxxxxxxSTxxxxMaxZ 0,4233322212:2020212121212121yyyyyyyyyySTyyMinW)(PP)(DP例例7 728DPPP)51,56(,)4 , 4 , 0 , 0()0()0(T)0(T)0( YbCXYXT且且的的可可行行解解、是是由由于于的的最最優(yōu)優(yōu)解解、分分別別是是、所所以以，DPPP)0()0(YX27補充作業(yè)補充作業(yè)3-2 。的的應應用用對對偶偶理理論論證證明明不不限限如如下下：已已知知1PP0

19、, 02212.2maxLP*321321321321321 ZxxxxxxxxxxxxtsxxxZ28證明：證明：)0()0(DPPPYX、問問題題的的可可行行解解分分別別為為、設設)0(PPYbCXXT ，有有問問題題的的任任意意可可行行解解對對于于在在可可行行域域內(nèi)內(nèi)有有上上界界所所以以 CX問問題題有有最最優(yōu)優(yōu)解解故故PP)0(DPCXYbYT 有有，問問題題的的任任意意可可行行解解同同理理對對于于在在可可行行域域內(nèi)內(nèi)有有下下界界所所以以YbT問問題題有有最最優(yōu)優(yōu)解解故故DP定理定理3 3 強對偶定理強對偶定理 若若PP，DP均有可行解，則均有可行解，則PP，DP均均有最優(yōu)解，且目標函

20、數(shù)最優(yōu)值相等。有最優(yōu)解，且目標函數(shù)最優(yōu)值相等。29BXXPP所所對對應應的的最最優(yōu)優(yōu)基基為為，的的最最優(yōu)優(yōu)解解為為設設：)1(001*1)0()0()0(bBCXCZbBxxxXXBsNB 可可以以表表示示為為TTBBBACABCCABCABCC ）（則則，的的檢檢驗驗數(shù)數(shù)：則則1110PP 30)2()(DP0)(011111bBCBCbYbWWYBCYIBCCYABCYBTBTTTBBSTTBT ：相相應應的的目目標標函函數(shù)數(shù)值值的的可可行行解解，是是由由此此可可見見，由由令令 YbXCT21 ）知知：）和和（比比較較（:由由最最優(yōu)優(yōu)性性準準則則知知且且目目標標函函數(shù)數(shù)值值相相等等。的的最

21、最優(yōu)優(yōu)解解、分分別別為為、DPPPYX31補充作業(yè)補充作業(yè)3-3 都都存存在在最最優(yōu)優(yōu)解解。和和應應用用對對偶偶理理論論證證明明，如如下下：已已知知DPPP03142342.23maxLP2121212121 xxxxxxxxtsxxZ32證明證明：以以PP是是max為例。為例。當當PP為為max，則，則PP的檢驗數(shù)與的檢驗數(shù)與DP的解之間僅差一個負號；的解之間僅差一個負號；當當PP為為min，則，則PP的檢驗數(shù)與的檢驗數(shù)與DP的解完全相同。的解完全相同。 0.minYCYAtsYbWTTT 0.maxXbAXtsCXZ)(PP)(DP推論：推論： 用單純形求解用單純形求解LP問題時，問題時，

22、PP的檢驗數(shù)對應的檢驗數(shù)對應DP的一的一個解（最優(yōu)時為基可行解，其余為基解）。個解（最優(yōu)時為基可行解，其余為基解）。 330,minDP0,0maxPP),(PP2121 SSTNSTTBSTTSNBSNBSNNBBYYYCYYNCYYBYbWXXXbIXNXBXXXCXCZNBANB可可表表示示為為：相相應應的的改改寫寫成成：則則為為非非基基，且且的的基基，為為設設341111:0:PPPP BCXNBCCXBBCCXbBXBSBNNBBBB的的檢檢驗驗數(shù)數(shù)可可表表示示為為：則則時時得得到到一一個個基基可可行行解解當當?shù)牡慕饨猓涸僭賮韥砜纯纯纯碊P1112211110DP BCYYBCNBC

23、CYCYYNBBCCYCYYBBCYBTTBBNTSTNSTBBTSTBSTBT由由由由由由的的約約束束方方程程根根據(jù)據(jù)令令35 當當PP為為max，在用單純形法求解，在用單純形法求解LP問題問題PP的最優(yōu)單純的最優(yōu)單純形表中松弛變量的檢驗數(shù)的相反數(shù)就是其形表中松弛變量的檢驗數(shù)的相反數(shù)就是其DP的最優(yōu)解；的最優(yōu)解； YTS10XBYTS2CNCBB1 NXNCBB1PP的檢驗數(shù)的檢驗數(shù)YTDP的解的解XSPP的變量的變量PP檢驗數(shù)與檢驗數(shù)與DP解的對應關系表解的對應關系表 當當PP為為min，在用單純形法求解，在用單純形法求解LP問題問題PP的最優(yōu)單純的最優(yōu)單純形表中松弛變量的檢驗數(shù)就是其形表

24、中松弛變量的檢驗數(shù)就是其DP的最優(yōu)解。的最優(yōu)解。36解：化為標準型：化為標準型 5 ,4 ,3,2,1,01241648232max524132121jxxxxxxxxxxZj例例8 8 求下列問題對偶問題的最優(yōu)解求下列問題對偶問題的最優(yōu)解 0,12416482.32max21212121xxxxxxtsxxZ37 X(0) (0,0,8,16,12)T以以1為主元素進行旋轉運算，為主元素進行旋轉運算，x1為換入變量，為換入變量， x3為換出變量為換出變量 0 q qi 3 0 0 x5 x2 x3 x40 x4 x3XB b j 0 x1CB 2 cj x1 cj x2 x3 x4 x5 1

25、 4 0 2 0 4 1 0 0 0 1 0 0 0 1 2 3 0 0 0 b816 12 XB x3 x4 x5 CB 0 0 0以以4為主元素進行旋轉運算，為主元素進行旋轉運算，x2為換入變量，為換入變量，x5為換出變量為換出變量 j 2 3 0 0 0 q qi 8/2 12/44 x2 3 0 0 0 1/43 1 4 0 1 016 0 0 1 1 0 -1/22X(1) (0,3,2,16,0)T 2 0 0 -3/4 016/4 2/1 1Y(0) (0,0,0,-2,-3)TY(1) (0,0,3/4,-2,0)T38此時達到最優(yōu)解。此時達到最優(yōu)解。X*=(4,2), max

26、 Z=14。 0 q qi 3 0 0 x5 x2 x3 x40 x4 x23 XB b j x1CB 2 cj 0 q qi 3 0 0 x5 x2 x3 x4x23 x1XB b j 2 x1CB 2 cj 0 0 0 1/43 10 -2 0 1/4 0 x1 2 0 1 1 0 -1/22 2 0-4 128 08/2 12 x50 0 -2 1/2 14 0 1 0 1/4 04 0 1/2 -1/8 0 02 10 -3/2 -1/8 0 0X(3) (4,2,0,0,4)TX(2) (2,3,0,8,0)T以以2為主元素進行旋轉運算，為主元素進行旋轉運算，x5為為換入變量，換入變

27、量，x4為換出變量為換出變量Y(2) (2,0,-1/4,0,0)TY(3) (3/2,1/8,0,0,0)T39重要提示：重要提示： 由上述實例可以看出：在用單純形法求解由上述實例可以看出：在用單純形法求解LP問問題時，題時，PP沒有得到最優(yōu)解之前，每迭代一步得到一沒有得到最優(yōu)解之前，每迭代一步得到一個基可行解，此時個基可行解，此時DP得到的是一個基解；而當?shù)玫降氖且粋€基解；而當PP得到最優(yōu)解時，得到最優(yōu)解時，DP才得到一個基可行解。根據(jù)才得到一個基可行解。根據(jù)強對強對偶定理偶定理，DP得到的這個基可行解一定是得到的這個基可行解一定是DP的最優(yōu)的最優(yōu)解。解。40 miliillCyax1)0

28、()0(, 0 則則若若0,)0(1)0( lmiliilxCya則則若若 njkjkjkbxay1)0()0(, 0 則則若若0,)0(1)0( knjkjkjybxa則則若若0PP)2)(1(* XYYSS之之間間的的關關系系。即即方方程程中中的的變變量量與與相相應應的的對對偶偶為為0PP)4)(3(* SSXYX。即。即的對偶變量之間的關系的對偶變量之間的關系與相應與相應方程中的方程中的為為定理定理4 互補松弛定理互補松弛定理 在最優(yōu)情況下，在最優(yōu)情況下，PP的第的第i個決策變量與其個決策變量與其DP的第的第i個約束中的松弛變量的乘積恒為零個約束中的松弛變量的乘積恒為零。反之亦然。反之亦

29、然。 (2)(1)(3)(4)設設X(0),Y(0)分別為分別為PP,DP的的可行解，則可行解，則X(0),Y(0)分別為分別為PP,DP的最優(yōu)的最優(yōu)解的充要條件為解的充要條件為 , ,有有)1 ,1(,nlmklk 41 0,2023220322:432max4321432143214321xxxxxxxxxxxxSTxxxxZ 0,4233322212:2020min212121212121yyyyyyyyyySTyyW)(PP)(DP例例9 9 考慮下面問題考慮下面問題的最優(yōu)解的最優(yōu)解用互補松弛定理求出用互補松弛定理求出的最優(yōu)解為的最優(yōu)解為已知已知)()51,56()(*PPYDP 42

30、解:0000, 421*2*1 ssxxyy、，、由由定定理理形形式式：的的約約束束可可以以簡簡化化成成如如下下則則PP)1(20322*4*3*2*1 xxxx)2(20232*4*3*2*1 xxxx016 . 14 . 02 . 121*2*1 syyy026 . 22 . 04 . 222*2*1 syyy2032*4*3 xx2023*4*3 xx4*4*3 xx則則，問問題題的的最最優(yōu)優(yōu)解解為為所所以以 PPTX)4,4,0,0(* 則，得得：、代代入入)2()1(,0*2*1 xx43已知已知LP原問題為：原問題為： 0,166623.3315min543215242132121

31、xxxxxxxxxxxxxtsxxZ已知原問題用兩階段已知原問題用兩階段法求得最優(yōu)單純形表法求得最優(yōu)單純形表如下，試用對偶理論如下，試用對偶理論寫出其對偶問題的最寫出其對偶問題的最優(yōu)解。優(yōu)解。-230-50 0 -33 0 0 x5 x2 x3 x4-1/3001100002/3-13-214/31-15 x1 x2-33 x4 XBb0 j 03 0 x1CB -15 cj補充作業(yè)補充作業(yè)3-4 44第三節(jié)第三節(jié) 對偶問題的經(jīng)濟學解釋對偶問題的經(jīng)濟學解釋影子價格影子價格 0.maxXbAXtsCXZ 0,.0maxSSSXXbIXAXtsXCXZ標準化標準化)(PP)(PP，則則松松弛弛變變

32、量量的的檢檢驗驗數(shù)數(shù)若若最最優(yōu)優(yōu)基基為為 B得得到到的的最最優(yōu)優(yōu)單單純純形形表表中中用用單單純純形形法法求求解解PP110 BCIBCBBS STY *所所以以一、對偶最優(yōu)解的經(jīng)濟解釋：資源的影子價格一、對偶最優(yōu)解的經(jīng)濟解釋：資源的影子價格45*YbWCXZT 由由于于是是變變化化的的，則則假假設設mbbb,211、 y*i的數(shù)學含義的數(shù)學含義mmbZybZybZy *2*21*1,的的變變化化量量。問問題題的的最最優(yōu)優(yōu)目目標標函函數(shù)數(shù)值值單單位位時時，變變化化可可以以理理解解成成當當資資源源PP1*iyi*22*11*mmybybybZ 所所以以4610例例最最優(yōu)優(yōu)單單純純形形表表問問題題的

33、的右右面面是是該該 LPTY)0 ,125. 0 , 5 . 1(* 則則對對偶偶問問題題的的最最優(yōu)優(yōu)解解為為 0 q qi 3 0 0 x5 x2 x3 x40 x5x23 x1XB b j 2 x1CB 2 cj 0 -2 1/2 14 0 1 0 1/4 04 0 1/2 -1/8 0 02 10 -3/2 -1/8 0 0 0,12416482. .32max21212121xxxxxxtsxxZ 5 , 4 , 3 , 2 , 1, 01241648232max352241132121jxyxxyxxyxxxxxZj對對偶偶變變量量標準化標準化47 做目標函數(shù)做目標函數(shù)2x1+3x2

34、的等值線，與陰影部的等值線，與陰影部分的邊界相交于分的邊界相交于Q(4,2)點，表明最優(yōu)點，表明最優(yōu)生產(chǎn)計劃為：生產(chǎn)生產(chǎn)計劃為：生產(chǎn)I產(chǎn)品產(chǎn)品4件，生產(chǎn)件，生產(chǎn)II產(chǎn)產(chǎn)品品2件。件。Q(4,2)x1x24x1=164x2=12x1+2x2=844083Z=14Q(4.25,1.875)Z=14.125Q(4,2.5)Z=15.5Q(4,2)Z=140,125.0,5 .1*3*2*1 yyy則則沒沒有有變變化化。個個單單位位，則則變變化化；變變化化個個單單位位，則則變變化化；變變化化個個單單位位，則則變變化化表表明明：根根據(jù)據(jù)影影子子價價格格的的含含義義，*3*2*11125.015 .11Z

35、bZbZb48 (1)對偶問題的最優(yōu)解對偶問題的最優(yōu)解買主的最低出價。買主的最低出價。 (2)原問題資源的影子價格原問題資源的影子價格當該資源增加當該資源增加1單位時引起單位時引起的總收入的增量的總收入的增量賣主的內(nèi)控價格。賣主的內(nèi)控價格。 (3)代表在資源最優(yōu)利用條件下對單位第代表在資源最優(yōu)利用條件下對單位第i種資源的估價，種資源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在最優(yōu)生產(chǎn)配置這種估價不是資源的市場價格，而是根據(jù)資源在最優(yōu)生產(chǎn)配置中作出的貢獻而作的估價，為區(qū)別起見，稱為影子價格中作出的貢獻而作的估價，為區(qū)別起見，稱為影子價格（shadow price)。 資源影子價格資源影子價

36、格資源市場價格資源市場價格 資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而它的影子價資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而它的影子價格則有賴于資源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務、格則有賴于資源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務、產(chǎn)品結構等情況發(fā)生變化，資源的影子價格也隨之改變。產(chǎn)品結構等情況發(fā)生變化，資源的影子價格也隨之改變。即：市場價格由市場確定；影子價格由生產(chǎn)企業(yè)確定。即：市場價格由市場確定；影子價格由生產(chǎn)企業(yè)確定。2、 y*i的經(jīng)濟學含義的經(jīng)濟學含義49(4)影子價格反映了資源的稀缺性，影子價格越高，則越稀缺。影子價格反映了資源的稀缺性，影子價格越高，則越稀缺。(5) 影子價格是

37、一種邊際價格。影子價格是一種邊際價格。(6)資源的影子價格實際上又是一種機會成本。資源的影子價格實際上又是一種機會成本。 在完全市場經(jīng)濟條件下在完全市場經(jīng)濟條件下,當：當： 資源的市場價格資源的市場價格影子價格，應賣出這種資源影子價格，應賣出這種資源 隨著資源的買進賣出，它的影子價格也將隨之發(fā)生變化，隨著資源的買進賣出，它的影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。503、 影子價格在企業(yè)管理中的作用影子價格在企業(yè)管理中的作用 (1)告訴管理者增加何種資源對企業(yè)更有利；告訴管理者增加何種資源對企業(yè)更

38、有利； (2)告訴管理者花多大代價購買進資源或賣出資源是合適的；告訴管理者花多大代價購買進資源或賣出資源是合適的； (3)為新產(chǎn)品定價提供依據(jù)。為新產(chǎn)品定價提供依據(jù)。51二、對偶約束的經(jīng)濟解釋二、對偶約束的經(jīng)濟解釋產(chǎn)品的機會成本產(chǎn)品的機會成本 n,j ,xbxaxaxaxabxaxaxaxabxaxaxaxa. t . sxcxcxcxcZjmnmnjmjmmnnjjnnjjnnjj210max221122222212111121211122111y2ymy機會機會(隱含隱含)成本：成本：jmmjjjPYyayayaT2211 表示減少一件第表示減少一件第j種產(chǎn)品生產(chǎn)所節(jié)省的資源量可以增加的利

39、潤或產(chǎn)值。種產(chǎn)品生產(chǎn)所節(jié)省的資源量可以增加的利潤或產(chǎn)值。52三、對偶松弛變量的經(jīng)濟解釋三、對偶松弛變量的經(jīng)濟解釋產(chǎn)品的差額成本產(chǎn)品的差額成本 m,i ,ycyyayayacyyayayacyyayaya. t . sybybybybWinnmmmnnnmmmmmmmmii210min22112222221121112211112211機會成本機會成本jjjjmmjjjjmcPYcyayayay T2211)(差額成本差額成本=機會成本利潤或產(chǎn)值機會成本利潤或產(chǎn)值差額成本差額成本利潤或產(chǎn)值利潤或產(chǎn)值53jjjjmmjjjjmcPYcyayayay T2211)(從對偶松弛變量從對偶松弛變量ym+

40、j看：看： 差額成本差額成本(ym+j)=機會成本利潤或產(chǎn)值機會成本利潤或產(chǎn)值從檢驗數(shù)從檢驗數(shù)j看：看： 第第j種產(chǎn)品的相對價值系數(shù)種產(chǎn)品的相對價值系數(shù)(j)=利潤或產(chǎn)值機會成本利潤或產(chǎn)值機會成本 當產(chǎn)品利潤或產(chǎn)值當產(chǎn)品利潤或產(chǎn)值=機會機會(隱含隱含)成本，可生產(chǎn)該產(chǎn)品；否則，不安排生成本，可生產(chǎn)該產(chǎn)品；否則，不安排生產(chǎn)。產(chǎn)。檢驗數(shù)的經(jīng)濟意義。檢驗數(shù)的經(jīng)濟意義。54ijijijijbx ay y ,bx anjiinj 1100時時，當當時時當當這表明在利潤最大化的生產(chǎn)計劃中，如果某種資源這表明在利潤最大化的生產(chǎn)計劃中，如果某種資源bi未得到充未得到充分利用時，該種資源的影子價格為零；又當資源

41、的影子價格不分利用時，該種資源的影子價格為零；又當資源的影子價格不為零時，表明該種資源在生產(chǎn)中已耗費完畢，反映了資源的稀為零時，表明該種資源在生產(chǎn)中已耗費完畢，反映了資源的稀缺性。由此總結：缺性。由此總結： (1)影子價格大于影子價格大于0的資源沒有剩余；的資源沒有剩余； (2)有剩余的資源影子價格等于有剩余的資源影子價格等于0； (3)安排生產(chǎn)的產(chǎn)品機會成本等于利潤；安排生產(chǎn)的產(chǎn)品機會成本等于利潤； (4)機會成本大于利潤的產(chǎn)品不安排生產(chǎn)。機會成本大于利潤的產(chǎn)品不安排生產(chǎn)。四、互補松弛定理的經(jīng)濟解釋四、互補松弛定理的經(jīng)濟解釋55 5,4,3,2,1,01241648232max5241321

42、21jxxxxxxxxxxZj 0342241216851531421321y,yyyyyyy. t . syyyWmin對偶對偶典型示例分析：典型示例分析：1y2y3y1x2xX* (4,2,0,0,4)TY* (3/2,1/8,0,0,0)T031 *xy042 *xy053 *xy014 *xy025 *xy56第四節(jié)第四節(jié) 對偶單純形法對偶單純形法一、基本思想一、基本思想 由單純形法的原理可知：在用單純形法求解由單純形法的原理可知：在用單純形法求解LP問題時，問題時，PP沒有得到最優(yōu)解之前，每迭代一步得到?jīng)]有得到最優(yōu)解之前，每迭代一步得到一個基可行解，此時一個基可行解，此時DP得到的是

43、一個基解；而當?shù)玫降氖且粋€基解；而當PP得到最優(yōu)解時，得到最優(yōu)解時，DP才得到一個基可行解。根據(jù)才得到一個基可行解。根據(jù)強對偶定理強對偶定理，DP得到的這個基可行解一定是得到的這個基可行解一定是DP的的最優(yōu)解。最優(yōu)解。 根據(jù)對偶問題的對稱性，也可始終保持根據(jù)對偶問題的對稱性，也可始終保持DP為基為基可行解，可行解， PP從基解開始迭代，當從基解開始迭代，當PP得到基可行解時，得到基可行解時，表明表明PP和和DP都得到最優(yōu)解。都得到最優(yōu)解。57 為了始終保持為了始終保持DP為基可行解，對于為基可行解，對于最大化最大化的的PP問題，其檢驗數(shù)必須保持非正；對于問題，其檢驗數(shù)必須保持非正；對于最小化最

44、小化的的PP問題，其檢驗數(shù)必須保持非負。問題，其檢驗數(shù)必須保持非負。 由于由于PP可以從基解開始迭代，因此可以從基解開始迭代，因此PP約束條件約束條件的右端常數(shù)項可以為非正。的右端常數(shù)項可以為非正。58二、步驟二、步驟(以最大化為例以最大化為例):為為換換出出變變量量；所所對對應應的的基基變變量量選選取取否否則則，令令停停止止計計算算；，則則最最優(yōu)優(yōu)解解已已經(jīng)經(jīng)達達到到，所所有有常常數(shù)數(shù)項項若若所所有有法法求求解解；，則則不不能能用用對對偶偶單單純純形形若若存存在在）（liiilijjbbbbb,0|min0002 ;DPPP0,0|min)3(為為無無界界解解無無可可行行解解，為為換換入入變

45、變量量；若若所所有有所所對對應應的的非非基基變變量量選選取取計計算算 ljkljljjjkaaaq q q q轉轉第第二二步步算算作作為為主主元元素素進進行行旋旋轉轉運運以以,)4(lka建建立立初初始始表表；，形形式式，且且引引入入松松弛弛變變量量問問題題的的約約束束條條件件為為化化 LP)1(59建初始表建初始表是否最優(yōu)？是否最優(yōu)？ 結束結束選出換出和換入選出換出和換入變量進行運算變量進行運算YN60例例11 0,2 82 4 :32min32132321321321xxxxxxxxxxxSTxxxZ 0,2 824 :32max32132321321321xxxxxxxxxxxSTxxx

46、Z 0,2 8 2 4 :32max65432163253214321321xxxxxxxxxxxxxxxxxSTxxxZ用對偶單純形法求解下列用對偶單純形法求解下列LPLP問題問題解：原問題變形為解：原問題變形為6101021180000101-10-201000-11-1-40b-3-2-1 0 1 1 1 2 0 4 0 0 0 0 1 0 1 -1 0 -2 0 -1 0 0 0 1 -1 1 4-1 b -3 -2 -1jc1x2x3x4x4x5xj 5x6x6xBCBX0 -1 -2 -3 0 0 0jc1x2x3x4x1x5xj 5x6x6xBCBX 4 0 -3 -2 -1 0

47、 06221130000000-10-1102-2-10-100016-1b-3-2-110026* ZXT），（故故jc1x2x3x4x1x5x5x6x2xBCBX 10 0 0 -5 -1 0 -3j 注意：注意：對偶單純形法不可理解成是求解對偶問題的單對偶單純形法不可理解成是求解對偶問題的單純形法，而是根據(jù)對偶理論，允許原問題從初始非可純形法，而是根據(jù)對偶理論，允許原問題從初始非可行基開始迭代求解原問題的單純形法。行基開始迭代求解原問題的單純形法。 63三、幾個問題的討論三、幾個問題的討論無無界界解解為為無無可可行行解解、若若最最小小比比值值規(guī)規(guī)則則失失效效DP,PP,2問題問題具有正則

48、解的具有正則解的、對偶單純形法只適用、對偶單純形法只適用LP 1的的創(chuàng)創(chuàng)新新思思想想、對對偶偶單單純純形形法法所所包包含含3問問題題的的正正則則解解稱稱為為則則（對對于于極極大大化化問問題題），均均驗驗數(shù)數(shù)且且對對應應于于此此基基本本解解的的檢檢問問題題存存在在基基本本解解若若正正則則解解的的定定義義：LP0,LPXX 64第五節(jié)第五節(jié) 靈敏度分析靈敏度分析 模型中的參數(shù)模型中的參數(shù)AbC一般是預測估計的確定值，而一般是預測估計的確定值，而在計劃實施時，這些值一般不可能正好是事先估計的在計劃實施時，這些值一般不可能正好是事先估計的值，因此有必要在求解后，分析這些參數(shù)值在將來可值，因此有必要在求

49、解后，分析這些參數(shù)值在將來可能變化后對最優(yōu)性的影響。能變化后對最優(yōu)性的影響。靈敏度分析就是計算為保靈敏度分析就是計算為保持原最優(yōu)性質(zhì)不變，模型中某一個參數(shù)（持原最優(yōu)性質(zhì)不變，模型中某一個參數(shù)（Cj或或bi或或aij）單獨變化的允許范圍。單獨變化的允許范圍。 問問題題當當LP 0:maxXbAXSTCXZ一、定義一、定義65011 jBjjPBCC 、021* bBXB、二、靈敏度分析常用的兩個公式二、靈敏度分析常用的兩個公式最優(yōu)性最優(yōu)性(最優(yōu)基最優(yōu)基)不變的條件：不變的條件： 1.1.可行條件：可行條件：XB 02.2.最優(yōu)條件：最優(yōu)條件： j0（maxmax） 靈敏度分析就是求出在上述兩個最

50、優(yōu)條件仍成立靈敏度分析就是求出在上述兩個最優(yōu)條件仍成立的情況下，參數(shù)的情況下，參數(shù)bicjaij的變化范圍。這需要將上述的變化范圍。這需要將上述兩式寫成含有參數(shù)的表達式。兩式寫成含有參數(shù)的表達式。 66三、靈敏度分析的幾種結果三、靈敏度分析的幾種結果可行條件：可行條件：XB =B-1b0。當。當bi發(fā)生變化時，只影響可行性。發(fā)生變化時，只影響可行性。用用XB =B-1b0 求出求出bi的變化量，此時的變化量，此時最優(yōu)基不變最優(yōu)基不變（XB中中的基變量名稱沒有變，但數(shù)值一般會改變）。的基變量名稱沒有變，但數(shù)值一般會改變）。 最優(yōu)條件：最優(yōu)條件： j0。當。當cj發(fā)生變化時，只影響最優(yōu)性，用發(fā)生變

51、化時，只影響最優(yōu)性，用 j0( j=cj-ciaij=cj-CBPj )求出求出cj的變化量，此時只是的變化量，此時只是Z值值會改變，而會改變，而最優(yōu)解不變最優(yōu)解不變（最優(yōu)基和基變量值均不變）。（最優(yōu)基和基變量值均不變）。1.最優(yōu)基不變，最優(yōu)解保持不變，最優(yōu)目標值可能改變。最優(yōu)基不變，最優(yōu)解保持不變，最優(yōu)目標值可能改變。2.最優(yōu)基不變，最優(yōu)解改變，最優(yōu)目標值改變。最優(yōu)基不變，最優(yōu)解改變，最優(yōu)目標值改變。3.最優(yōu)基改變，最優(yōu)解改變，最優(yōu)目標值改變。最優(yōu)基改變，最優(yōu)解改變，最優(yōu)目標值改變。67最優(yōu)基不變，最優(yōu)解有可能變化，不需處理最優(yōu)基不變，最優(yōu)解有可能變化，不需處理可行解可行解可行解可行解最優(yōu)基

52、改變，用單純形法繼續(xù)迭代求最優(yōu)最優(yōu)基改變，用單純形法繼續(xù)迭代求最優(yōu)非可行解非可行解可行解可行解非可行解非可行解可行解可行解DP最優(yōu)基改變，引進人工變量，編制新單純形表，最優(yōu)基改變，引進人工變量，編制新單純形表，求最優(yōu)求最優(yōu)最優(yōu)基改變，用對偶單純形法繼續(xù)迭代求最優(yōu)最優(yōu)基改變，用對偶單純形法繼續(xù)迭代求最優(yōu)結果及處理方法結果及處理方法非可行解非可行解非可行解非可行解PP靈敏度分析的幾種結果及相應處理方法靈敏度分析的幾種結果及相應處理方法681)1( B用用線線性性代代數(shù)數(shù)法法求求1)2( B直直接接用用最最優(yōu)優(yōu)單單純純形形表表求求（初初始始表表）由由bIXAXbAXS 得得兩兩邊邊左左乘乘1 B)(

53、111最最優(yōu)優(yōu)表表bBXBAXBS 的的求求法法、11 B四、常數(shù)項四、常數(shù)項bi改變的靈敏度分析改變的靈敏度分析69純純形形表表如如下下初初始始單單純純形形表表和和最最優(yōu)優(yōu)單單例例12 0,12416 48 2.32max21212121xxxxxxtsxxZ其單純形表如下所示其單純形表如下所示70 0125. 05 . 015 . 02025. 001B最最優(yōu)優(yōu)單單純純形形表表10.5-2004x50000 x50-0.1250.5102x23-0.1250.25x40-1.500-140014x12x3x2x1bXBCB032cj0100416x40010 x50004012x5000

54、x40032 1218x30 x3x2x1bXBCB032cj初始單純形表初始單純形表71公公式式推推導導、2發(fā)發(fā)生生了了變變化化假假設設只只有有一一個個常常數(shù)數(shù)項項rb)(1bbBbbbrrr 則則即即bBbB 11 0011rbBbB 00),(11rmrbbB 72 rmrmririrrrrbbbbbbbbB 1110 解解不不等等式式組組得得：0 riribb 即即，irirbb 則則，iririrbb 時時，當當0iririrbb 時時，當當0),2,1(mi 73）（）（0|min0|max iririririribbb 的的變變化化范范圍圍是是：即即，rb 注：注：優(yōu)解發(fā)生改變優(yōu)

55、解發(fā)生改變此時最優(yōu)基不變，但最此時最優(yōu)基不變，但最)1(改改變變只只能能有有一一個個常常數(shù)數(shù)項項發(fā)發(fā)生生)2(列列。中中第第除除以以用用迭迭代代后后的的的的變變化化范范圍圍的的方方法法：個個常常數(shù)數(shù)項項計計算算第第rBbbrr1 ，計計算算公公式式不不變變。為為若若minLP740010 x6000223130 x60001x5012583150 x7071x4700 x70154648120 x50 x3x2x1bxBCB154 cj基不變。基不變。的變化范圍，使原最優(yōu)的變化范圍，使原最優(yōu)求求和最優(yōu)單純形表和最優(yōu)單純形表問題的初始單純形表問題的初始單純形表下面是求解同一下面是求解同一321,

56、LPbbb例例 13:初始單純形表初始單純形表75-52/15-13/158/15-1/15x600-1/1512/34/308x47-1/15-4/152/15x50105/313/3092x7000 x4700 x70-19/3-17/302/31/3114x14x3x2x1bxBcB154 cj最優(yōu)單純形表最優(yōu)單純形表76 11513154015815101511521B解：解：)92,8,14( Tb) 1513,158,151(2 T )154,151,152(1 T )1 ,0,0(3 T 77)15492,1518min()15214max(1 b1201051 b即即，1313

57、8015,2 b即即392b )151392,15114min()1588max(2 b)92,8,14( Tb) 1513,158,151(2 T )154,151,152(1 T )1 ,0,0(3 T ）（）（由由0|min0|max iririririribbb 781-12102x23-33x40-1-1x50-300-8 -1011x12x3x2x1bxBcB132 cj 11*bbbb代代替替，其其中中被被假假設設原原來來的的 使使原原最最優(yōu)優(yōu)基基仍仍為為最最優(yōu)優(yōu)基基的的取取值值范范圍圍求求,)1( 為為松松弛弛變變量量問問題題的的最最終終單單純純形形表表下下面面是是某某例例54

58、,LP14xx大大基基不不變變而而目目標標函函數(shù)數(shù)值值最最為為何何值值時時，使使得得原原最最優(yōu)優(yōu)求求 )2(問問題題：79解解：)1 ( 11131B1bB )(*1bbB 11BbB 111321 22410 141 所所以以，)2(1*bBCZB )(*1bbBCB 11BCbBCBB 28 ，達到最大，達到最大時，時，當當101* Z *BX )1 ,3(21)3,2(801-12102x23-1-1x50-33x40-300-1011x12x3x2x1bXBCB132 cj的的改改變變非非基基變變量量目目標標函函數(shù)數(shù)系系數(shù)數(shù))1(改改變變基基變變量量目目標標函函數(shù)數(shù)系系數(shù)數(shù)的的)2(例

59、例4:4:下面是一張下面是一張LPLP問題的最優(yōu)單純形表問題的最優(yōu)單純形表, ,觀觀察其基變量、非基變量目標函數(shù)系數(shù)的改察其基變量、非基變量目標函數(shù)系數(shù)的改變對檢驗數(shù)的影響變對檢驗數(shù)的影響五、五、C的改變的改變81jjc jjjjcccc 變變?yōu)闉橄迪禂?shù)數(shù)若若非非基基變變量量的的目目標標函函數(shù)數(shù)jjx 的的檢檢驗驗數(shù)數(shù)則則，原原最最優(yōu)優(yōu)解解不不變變即即原原最最優(yōu)優(yōu)解解不不變變?nèi)羧鬸jjjjjccc 0原原最最優(yōu)優(yōu)解解改改變變?nèi)羧?0jjjc 討論：討論：最最優(yōu)優(yōu)解解不不變變即即431, 333 cc最最優(yōu)優(yōu)解解不不變變即即330, 3 44 cc的的改改變變非非基基變變量量目目標標函函數(shù)數(shù)系系

60、數(shù)數(shù))1(最最優(yōu)優(yōu)解解不不變變即即110, 155 ccjBjjjBjjPBCccPBCc11 :本本例例中中原原最最優(yōu)優(yōu)解解不不變變即即則則正正好好相相反反。，為為若若注注意意： minLPjjc 82改變改變基變量目標函數(shù)系數(shù)的基變量目標函數(shù)系數(shù)的)2(kkkBBBccc 若若jBBBBBjjPBccccccmkk1),(21 jBBBBBjPBcccccckmk1)0 , 0(),(21 kjBjBjacPCck kjBjack 0 0|min0|max kjkjjBkjkjjaacaak jkjBack 即，即，行行的的相相應應元元素素。除除以以迭迭代代后后的的第第用用檢檢驗驗數(shù)數(shù)行行