運籌學課件：第2章 對偶理論

1、Chapter2 對偶理論 ( Duality Theory )單純形法的矩陣描述對偶問題的提出線性規(guī)劃的對偶理論對偶問題的經(jīng)濟解釋影子價格對偶單純形法靈敏度分析(選講)掌握WinQSB軟件求解對偶規(guī)劃本章主要內(nèi)容：學習要點：1. 理解對偶理論，掌握描述一個線性規(guī)劃問題 的對偶問題。 2. 能夠運用對偶單純形法來求解線性規(guī)劃問題。 3. 會用互補松弛條件來考慮一對對偶問題的界。 4. 了解影子價格、靈敏度分析以及用WinQSB求 解對偶規(guī)劃問題。2.1 單純形法矩陣描述0.16-0.120102412x2-0.20.4001207x11.16-3.12100840 x3-1.20003.410

2、00.10010,33012x220-0.51002.5500 x430.8-0.40107.82400 x3000127301001033000 x540010542000 x490001493600 x3x5x4x3x2x1B-1bCBXB每一列的含義？每個表中的B和B-1的查找？B從初表中找，B-1從當前表中找，相當于初表中的I的位置單純形法的矩陣描述單純形法的主要步驟因此，單純形表的主體內(nèi)容是B-1(b,A)CXB-1bB-1AC- CB-1A單純形表的主要結構單純形法的矩陣描述CBCNbXBXNbBNCBCNbXBXNB-1bIB-1N-CBB-1b0CN-CBB-1 N 單純形法的

3、矩陣描述CBCNCS(0)bXBXNXSbBNI0CBCN0CBCNCS(0)bXBXNXSB-1bIB-1NB-1-CBB-1b0CN-CBB-1 N-CBB-1 單純形法的矩陣描述單純形法的矩陣描述2.2 改進單純形法15001/31/311/35X23301-1-2013X500001320j-1001-113X6000-1001-156101/34/304/38X6001x4010 x5000 x606-13218X50513115X40 x3x2x1bXBCB1321/4-1/35/121001X32-5/6-1/61/4-1/31/30-1/21/2-1/4000-20j0015X

4、100103X20P1P1P1思考：P1分別與P1、 P1的關系改進的單純形法231000CBXBbx1x2x3x4x5x60X41513110050X51823-101060X631-11001-j02310003X251/311/31/300150X5310-2-11030X684/304/31/3016-15100-100改進的單純形法231000CBXBbx1x2x3x4x5x63X251/311/31/300150X5310-2-11030X684/304/31/3016j-15100-1000X240112/3-1/3041X1310-2-110-0X640045/3-4/311j

5、-180020-10改進的單純形法設mm系數(shù)矩陣A，求其逆矩陣可以先從第1列開始:以下介紹一種比較簡便的計算方法求解線性規(guī)劃問題的關鍵是計算B-1改進的單純形法以a11為主元素, 進行變換然后構造含有（1）列，而其他列都是單位列的矩陣改進的單純形法可得到：而后以第2列的a22(1) 為主元素，進行變換改進的單純形法然后構造含有（2）列，而其他列都是單位列的矩陣 可得到改進的單純形法重復以上的步驟，直到獲得求單純形表的基矩陣的逆矩陣也可以用這方法。改進的單純形法書上例題自學。2.3 對偶問題的提出 對偶理論是線性規(guī)劃中最重要的理論之一，是深入了解線性規(guī)劃問題結構的重要理論基礎。同時，由于問題提出

6、本身所具有的經(jīng)濟意義，使得它成為對線性規(guī)劃問題系統(tǒng)進行經(jīng)濟分析和敏感性分析的重要工具。那么，對偶問題是怎樣提出的，為什么會產(chǎn)生這樣一種問題呢？對偶問題的提出倆家具制造商間的對話：唉!我想租您的木工和油漆工一用。咋樣？價格嘛好說，肯定不會讓您兄弟吃虧。 王老板做家具賺了大錢，可惜我老李有高科技產(chǎn)品，卻苦于沒有足夠的木工和油漆工咋辦？只有租咯。Hi：王老板，聽說近來家具生意好呀，也幫幫兄弟我哦!家具生意還真賺錢，但是現(xiàn)在的手機生意這么好，不如干脆把我的木工和油漆工租給他，又能收租金又可做生意。價格嘛好商量， 好商量。只是. 王 老 板李 老 板引例1對偶問題的提出王老板的家具生產(chǎn)模型：x1 、 x

7、2是桌、椅生產(chǎn)量。Z是家具銷售總收入（總利潤）。max Z = 50 x1 + 30 x2s.t. 4x1+3x2 120（木工） 2x1+ x2 50 （油漆工） x1，x2 0原始線性規(guī)劃問題，記為（P）王老板的資源出租模型：y1、 y2單位木、漆工出租價格。W是資源出租租金總收入。min W =120y1 + 50y2s.t. 4y1+2y2 50 3y1+ y2 30 y1，y2 0對偶線性規(guī)劃問題，記為（D）所得不得低于生產(chǎn)的獲利（不吃虧原則）要使對方能夠接受 （競爭性原則）兩個原則對偶問題的提出 王老板按（D）的解 y1 、y2出租其擁有的木、漆工資源，既保證了自己不吃虧（出租資源

8、的租金收入并不低于自己生產(chǎn)時的銷售收入），又使得出租價格對李老板有極大的吸引力（李老板所付出的總租金W最少）。按時下最流行的一個詞，叫什么來著對偶問題的提出Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目標函數(shù)約束條件設三種資源的使用單價分別為 y1 , y2 , y3y1 y2 y3生產(chǎn)單位產(chǎn)品A的資源消耗所得不少于單位產(chǎn)品A的獲利生產(chǎn)單位產(chǎn)品B的資源消耗所得不少于單位產(chǎn)品B的獲利y1 +3 y2 40 2y1 + 2 y2 + 2y3 50甲乙資源量A1230B3260C0224單位獲利4050引例2通過使用所有

9、資源對外加工所獲得的收益W = 30y1 + 60 y2 + 24y3對偶問題的提出根據(jù)原則2 ，對方能夠接受的價格顯然是越低越好，因此此問題可歸結為以下數(shù)學模型：Min W = 30y1 + 60 y2 + 24y3 y1 + 3y2 402y1 + 2 y2 + 2y3 50y1 , y2 , y3 0s.t目標函數(shù)約束條件原線性規(guī)劃問題稱為原問題，此問題為對偶問題，y1 , y2 , y3為對偶變量，也稱為影子價格對偶問題的提出2.4 線性規(guī)劃的對偶理論Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t原問題（對偶

10、問題）對偶問題（原問題）一、 原問題與對偶問題的對應關系Min W = 30y1 + 60 y2 + 24y3 y1 + 3y2 402y1 + 2 y2 + 2y3 50y1 , y2 , y3 0s.t（y1） （y2）（y3） （x1） 13040（x2）22250306024min max z 3個約束2個變量2個約束 3個變量線性規(guī)劃的對偶理論對偶問題的形式定義 設原線性規(guī)劃問題為 則稱下列線性規(guī)劃問題為其對偶問題，其中yi (i=1,2,m) 稱為對偶變量上述對偶問題稱為對稱型對偶問題原問題簡記為(P)，對偶問題簡記為(D)稱問題(P)和(D )為一對對偶問題線性規(guī)劃的對偶理論對稱

11、型問題的對偶規(guī)則1、給每個原始約束條件定義一個非負對偶變量yi(i=1,2,m)；2、使原問題的目標函數(shù)系數(shù) cj 變?yōu)槠鋵ε紗栴}約束條 件的右端常數(shù)；3、使原問題約束條件的右端常數(shù) bi 變?yōu)槠鋵ε紗栴}目 標函數(shù)的系數(shù)；4、將原問題約束條件的系數(shù)矩陣轉置，得到其對偶問 題約束條件的系數(shù)矩陣；5、改變約束問題不等號的方向，即將“”改為“”；6、原問題為“max”型，對偶問題為“min”型。線性規(guī)劃的對偶理論原始問題Max Z=CXs.t. AXbX 0bACMaxnm對偶問題Min W=Ybs.t.YACY 0MinCATbnmY為行向量線性規(guī)劃的對偶理論當原問題為求極小值時，對偶問題為求極大

12、值。原始問題中目標函數(shù)的系數(shù)變成對偶問題中約束條件的右端；原始問題中約束條件的右端變成對偶問題中目標函數(shù)的系數(shù)。原始問題約束條件系數(shù)矩陣的轉置對應對偶問題中約束條件的系數(shù)矩陣。原始問題的約束條件個數(shù)決定對偶問題變量的個數(shù)；原始問題變量個數(shù)，決定對偶問題的約束個數(shù)。原始問題的約束方程的匹配形式?jīng)Q定對偶問題變量的符號；原始問題決策變量的符號決定所對應對偶問題的約束方程的匹配形式。線性規(guī)劃的對偶理論求線性規(guī)劃問題的對偶規(guī)劃解：由原問題的結構可知為對稱型對偶問題例1線性規(guī)劃的對偶理論求線性規(guī)劃問題的對偶規(guī)劃解：由原問題的結構可知不是對稱型對偶問題，可先化為對稱型，再求其對偶規(guī)劃。例2線性規(guī)劃的對偶理論

13、求線性規(guī)劃問題的對偶規(guī)劃解：由原問題的結構可知不是對稱型對偶問題，可先化為對稱型，再求其對偶規(guī)劃。例3線性規(guī)劃的對偶理論上式已為對稱型對偶問題，故可寫出它的對偶規(guī)劃令則上式化為線性規(guī)劃的對偶理論對偶問題的非對稱形式min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10 x20 x3

14、: unr原始問題變量的個數(shù)(3)等于對偶問題約束條件的個數(shù)(3)； 原始問題約束條件的個數(shù)(4)等于對偶問題變量的個數(shù)(4)。原始問題變量的性質(zhì)影響對偶問題約束條件的性質(zhì)，用 表示 原始問題約束條件的性質(zhì)影響對偶問題變量的性質(zhì)，用 表示線性規(guī)劃的對偶理論1 原問題為“max”，對偶問題為“min”；2 原問題中目標函數(shù)系數(shù) ci 變?yōu)槠鋵ε紗栴}約束條件的右端常數(shù)；3 原問題約束條件的右端常數(shù) bi 變?yōu)槠鋵ε紗栴}目標函數(shù)的系數(shù)；4 原問題約束條件的系數(shù)矩陣轉置，即為其對偶問題的系數(shù)矩陣；5 原問題的變量個數(shù)n等于其對偶問題的約束條件個數(shù)n，原問題 約束條件的個數(shù)m等于其對偶問題變量的個數(shù)m；

15、6 在求極大值的原問題中，“”，“”和“=”的約束條件分別對應其對偶變量“0”，“0”和“無符號限制”；7 在求極大值的原問題中，變量“0”，“0”和“無符號限制”分別對應其對偶約束條件的“”，“”和“=”約束.混合型問題的對偶規(guī)則：線性規(guī)劃的對偶理論原問題（或?qū)ε紗栴}）對偶問題（或原問題）約束條件右端項目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)約束條件右端項目標函數(shù) max目標函數(shù) min約束條件m個m個變量00=無約束變量n個n個約束條件00無約束=線性規(guī)劃的對偶理論 Max Z=40 x1+ 50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0s.ty1y2y3

16、Min W = 30y1+ 60y2 + 24y3 y1+3y2 + 0y3 402y1+2y2 + 2y3 50 y1 , y2 , y3 0s.tMax W= -30y1- 60y2 - 24y3 y1+3y2 + 0y3 y4 = 402y1+2y2 + 2y3 y5 = 50 y1 , y2 , y3 , y4 , y5 0s.t例4二、 對偶問題的解線性規(guī)劃的對偶理論Max W= -30y1- 60y2 - 24y3 +0(y4 + y5 )-M (y6 + y7 ) y1+3y2 + 0y3 y4 + y6 = 402y1+2y2 + 2y3 y5 + y7 = 50 y1 , y

17、2 , y3 , y4 , y5 0s.tcj-30-60-2400-M-MB-1bcByBy1y2y3y4y5y6y7-My6130-10104040/3-My72220-1015050/2j3M-305M-602M-24-M-M00-90M線性規(guī)劃的對偶理論cj-30-60-2400-M-MB-1bcByBy1y2y3y4y5y6y7-60y21/310-1/301/3040/3-My74/3022/3-1-2/3170/335/3j4M/3-1002M-242M/3+20-M-5M/3+200800-70M/3-60y21/310-1/301/3040/340-24y32/3011/3-

18、1/2-1/31/235/335/2j600-12-12-M+12-M+12-1080-60y201-1/2-1/21/41/2-1/415/2-30y1103/21/2-3/4-1/23/435/2j00-9-15-15/2-M+30-M-15/2-975線性規(guī)劃的對偶理論cj4050000 B-1bcBxBx1x2x3x4x540 x1101/2-1/20150 x5003/2-1/21950 x201-3/41/4015/2j00-35/2-15/20975 Max Z=40 x1+ 50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0s.t x1+2x2

19、 +x3 = 303x1+2x2 +x4 =60 2x2 +x5 = 24 x1 x5 0s.t線性規(guī)劃的對偶理論線性規(guī)劃的對偶理論原問題與其對偶問題的變量與解的對應關系： 在單純形表中，原問題的松弛變量對應對偶問題的變量，對偶問題的剩余變量對應原問題的變量。線性規(guī)劃的對偶理論XBb原問題的變量原問題的松弛變量x1x2x3x4x5x115101/2-1/20 x59003/2-1/21x215/2013/4-1/4000-35/2-15/20YBb對偶問題的變量對偶問題的剩余變量y1y2y3y4y5y215/201-1/2-1/21/4y135/2103/21/2-3/400-9-15-15/

20、2原問題最優(yōu)表對偶問題最優(yōu)表 Max Z=40 x1+ 50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0s.tMin W = 30y1+ 60y2 + 24y3 y1+3y2 + 0y3 402y1+2y2 + 2y3 50 y1 , y2 , y3 0s.t線性規(guī)劃的對偶理論性質(zhì)1 對稱性定理：對偶問題的對偶是原問題 min W= Y bs.t. YA C Y 0max Z=C Xs.t. AXb X 0三、 對偶原理線性規(guī)劃的對偶理論min z= - CXs.t. -AX-bX 0maxw= -Ybs.t. -YA-C Y 0min w=Ybs.t. Y

21、AC Y 0max z=CXs.t. AXb X 0對偶的定義對偶的定義簡要證明：線性規(guī)劃的對偶理論性質(zhì)2 弱對偶原理(弱對偶性)：設 和 分別是問題(P)和(D)的可行解，則必有推論1: 原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之，對偶問題任意可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。證明：(1) 當X和Y為原問題和對偶問題的一個可行解有原問題目標函數(shù)值對偶問題目標函數(shù)值線性規(guī)劃的對偶理論推論2: 在一對對偶問題（P）和（D）中，若其中一個問題可行但目標函數(shù)無界，則另一個問題無可行解；反之不成立。這也是對偶問題的無界性。若（P）為無界解，則（D）無可行解；若（D）為無

22、界解，則（P）無可行解。線性規(guī)劃的對偶理論推論3：在一對對偶問題（P）和（D）中，若一個可行（如P），而另一個不可行（如D），則該可行的問題目標函數(shù)值無界。已知原問題(LP)，試估計它的目標函數(shù)值的界,并驗證弱對偶定理.例5線性規(guī)劃的對偶理論解：問題(LP)的對偶問題(DP)為 (DP)線性規(guī)劃的對偶理論由觀察可知 分別是原問題和對偶問題的可行解。 ，弱對偶定理成立。且由推論1知，對偶問題目標函數(shù)W的下界為10，原問題目標函數(shù)Z的上界為40。且原問題的目標函數(shù)值為對偶問題的目標函數(shù)值為故線性規(guī)劃的對偶理論例：利用對偶性質(zhì)判斷下面問題有無最優(yōu)解例6解：此問題的對偶問題為不能成立，因此對偶問題不可

23、行。故由推論3知原問題無界。為可行解線性規(guī)劃的對偶理論性質(zhì)3 最優(yōu)性定理：如果 是原問題的可行解， 是其對偶問題的可行解，并且:則 是原問題的最優(yōu)解， 是其對偶問題的最優(yōu)解。線性規(guī)劃的對偶理論性質(zhì)4 強(主)對偶性：若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)值相等。還可推出另一結論：若一對對偶問題中的任意一個有最優(yōu)解，則另一個也有最優(yōu)解，且目標函數(shù)最優(yōu)值相等；若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。一對對偶問題的關系，有且僅有下列三種：都有最優(yōu)解，且目標函數(shù)最優(yōu)值相等；兩個都無可行解；一個問題無界，則另一問題無可行解。線性規(guī)劃的對偶理論證明：當X*為原問題的

24、一個最優(yōu)解，B為相應的最優(yōu)基，通過引入松弛變量Xs，將問題(P)轉化為標準型令CCBCN0解基系數(shù)基變量XBXNXsCBXBIB-1NB-1B-1b0CN -CBB-1N -CBB-1CBB-1bCXAC-CBB-1A說明Y*可行線性規(guī)劃的對偶理論問題:（1）由性質(zhì)4可知，對偶問題最優(yōu)解的表達式 Y*=?（2）求 Y*是否有必要重新求解(D)?不必。可以從原問題（P）的單純形終表獲得。CCBCN0解基系數(shù)基變量XBXNXsCBXBIB-1NB-1B-1b0CN -CBB-1N -CBB-1CBB-1b線性規(guī)劃的對偶理論性質(zhì)5 互補松弛性：設X0和Y0分別是P問題 和 D問題 的可行解，則它們分

25、別是最優(yōu)解的充要條件是：其中：Xs、Ys為松弛變量。在線性規(guī)劃問題的最優(yōu)解中，若對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；另一方面，如果約束條件取嚴格不等式，則其對應的變量一定為零。緊約束與松約束線性規(guī)劃的對偶理論一個約束稱為緊約束，如果該約束在所有最優(yōu)解上的值使左右取等號。 即我們把嚴格等式約束稱為緊約束（或起作用約束）. 不是緊約束的約束稱為松約束。 即把某一最優(yōu)解處取嚴格不等式的約束稱為松約束（或不起作用約束）。對于最優(yōu)解X*和Y*而言，松約束的對偶約束是緊約束.以上關系稱為對偶問題的互補松弛關系或松緊關系。在計算上，若已知一個問題的最優(yōu)解，則可利用互補松弛條件求另一個

26、問題的最優(yōu)解.緊約束與松約束松緊關系非常重要線性規(guī)劃的對偶理論證: (必要性）原問題 對偶問題線性規(guī)劃的對偶理論 y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 對偶問題的變量 對偶問題的松弛變量 原始問題的變量 原始問題的松弛變量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一對變量中，其中一個大于0，另一個一定等于0線性規(guī)劃的對偶理論性質(zhì)5的應用：該性質(zhì)給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)解的方法，即已知Y求X或已知X求Y互補松弛條件由于變量都非負，要使求和式等于零，則必定每一分量為零，因而有下列關系： 若Y0，則

27、Xs必為0；若X0，則Ys必為0利用上述關系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。線性規(guī)劃的對偶理論 已知線性規(guī)劃的最優(yōu)解是X=(6,2,0)T,求其對偶問題的最優(yōu)解Y。解：寫出原問題的對偶問題，即標準化例7線性規(guī)劃的對偶理論設對偶問題最優(yōu)解為Y(y1，y2),由互補松弛性定理可知，X和 Y滿足：即：因為x10，x20，所以對偶問題的第一、二個約束的松弛變量等于零，即y30，y40，帶入方程中：解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為：Y=(1,1)，最優(yōu)值w=26。線性規(guī)劃的對偶理論 已知線性規(guī)劃 的對偶問題的最優(yōu)解為Y=(0,-2)，求原問題的

28、最優(yōu)解。解: 對偶問題是標準化例8線性規(guī)劃的對偶理論設原問題最優(yōu)解為X(x1，x2 ，x3)T ,由互補松弛性定理知，X和 Y滿足：將Y帶入由方程可知，y3y50，y41。y2=-20 x50又y4=10 x20將x2，x5分別帶入原問題約束方程中，得：解方程組得：x1=-5,x3=-1, 所以原問題的最優(yōu)解為X=(-5,0,-1)，最優(yōu)值z=-12線性規(guī)劃的對偶理論試用對偶原理求解線性規(guī)劃問題已知其對偶規(guī)劃的最優(yōu)解為練習線性規(guī)劃的對偶理論解：該問題的對偶規(guī)劃為線性規(guī)劃的對偶理論利用松緊關系，代入對偶規(guī)劃的約束條件得下列約束是松約束，將最優(yōu)解松約束緊約束其對偶約束是緊約束線性規(guī)劃的對偶理論設原

29、問題的最優(yōu)解為緊約束線性規(guī)劃的對偶理論 對偶規(guī)劃可以用線性規(guī)劃的單純形法求解。由對偶原理可見，原問題與對偶問題之間有緊密聯(lián)系，因此我們能夠通過求解原問題來找出對偶問題的解，反之依然?；パa松弛條件就可以解決由原問題的最優(yōu)解直接求出對偶問題的最優(yōu)解。對偶問題解的求法線性規(guī)劃的對偶理論原問題與對偶問題解的對應關系小結對應關系原問題最優(yōu)解無界解無可行解對偶問題最優(yōu)解(Y,Y)(N,N)無界解(Y,Y)無可行解(Y,Y)無法判斷線性規(guī)劃的對偶理論思考題判斷下列結論是否正確，如果不正確，應該怎樣改正？1）任何線性規(guī)劃都存在一個對應的對偶線性規(guī)劃.2）原問題第i個約束是“”約束，則對偶變量yi0.3）互為對

30、偶問題，或者同時都有最優(yōu)解，或者同時都無最優(yōu)解.4）對偶問題有可行解，則原問題也有可行解.5）原問題有多重解，對偶問題也有多重解.6）對偶問題有可行解，原問題無可行解，則對偶問題具有無界解.7）原問題無最優(yōu)解，則對偶問題無可行解.8）對偶問題不可行，原問題可能無界解.9）原問題與對偶問題都可行，則都有最優(yōu)解.10）原問題具有無界解，則對偶問題不可行.11）對偶問題具有無界解，則原問題無最優(yōu)解.12）若X*、Y*是原問題與對偶問題的最優(yōu)解，則X*=Y*.線性規(guī)劃的對偶理論2.5 影子價格單位產(chǎn)品消耗的資源(噸/件)原始問題是利潤最大化的生產(chǎn)計劃問題總利潤(元)產(chǎn)品產(chǎn)量(件)單位產(chǎn)品的利潤(元/件

31、)消耗的資源(噸)剩余的資源(噸)資源限量(噸)影子價格對偶問題資源定價問題對偶問題是資源定價問題，對偶問題的最優(yōu)解y1、y2、.、ym稱為m種資源的影子價格（Shadow Price）原始和對偶問題都取得最優(yōu)解時，最大利潤 Max z=Min w總利潤(元)資源限量(噸)資源價格(元/噸)影子價格在一對 P 和 D 中，若 P 的某個約束條件的右端項常數(shù) bi （第 i 種資源的擁有量）增加一個單位時，所引起目標函數(shù)最優(yōu)值z* 的改變量稱為第 i 種資源的影子價格，其值等于D問題中對偶變量 yi*。由對偶問題得基本性質(zhì)可得：1. 影子價格的數(shù)學分析：影子價格2. 影子價格的經(jīng)濟意義1）影子價

32、格是一種邊際價格在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標函數(shù)最優(yōu)值的變化。即對偶變量yi 就是第 i 種資源的影子價格。即： 影子價格影子價格是針對某一具體約束條件而言,因此影子價格可理解為目標函數(shù)最優(yōu)值對資源的一階偏導數(shù) 資源影子價格的性質(zhì)影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于0影子價格0X2X1X= (15,7.5) Z=975X= (15.5,7.25) Z=982.5X= (14.5,8.25) Z=992.5Max Z=40X1+ 50X2 X1+2X2 303X1+2X2

33、60 2X2 24 X1 , X2 0s.t0X2X1X= (15,7.5) Z=975Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t0X2X1X= (15,7.5) Z=975X= (14.5,8.25) Z=992.5Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t0X2X1X= (15,7.5) Z=975X= (15.5,7.25) Z=982.5Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t

34、0X2X1X= (15,7.5) Z=975Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t0X2X1X= (15,7.5) Z=975X= (15.5,7.25) Z=982.5X= (14.5,8.25) Z=992.5Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0s.t2）影子價格是一種機會成本影子價格是在資源最優(yōu)利用條件下對單位資源的估價，這種估價不是資源實際的市場價格。因此，從另一個角度說，它是一種機會成本。若第i 種資源的單位市場價格為mi ，則有當yi* m

35、i 時，企業(yè)愿意購進這種資源，單位純利為yi*mi ，則有利可圖；當yi* mi 則購進資源 i，可獲單位純利yi*mi ； 若yi* 0，則xn+i =0如果xn+i 0，則yi =0影子價格大于0的資源，在最優(yōu)生產(chǎn)計劃條件下沒有剩余ym+jxj=0如果ym+j 0，則xj =0如果xj 0，則ym+j =0最優(yōu)生產(chǎn)計劃條件下有剩余的資源，其影子價格等于0差額成本大于0（機會成本大于利潤）的產(chǎn)品，不安排生產(chǎn)安排生產(chǎn)的產(chǎn)品，差額成本等于0（機會成本等于利潤）互補松弛關系經(jīng)濟解釋影子價格4）影子價格對單純形表計算的解釋單純形表中的檢驗數(shù)其中cj表示第j種產(chǎn)品的價格; 表示生產(chǎn)該種產(chǎn)品所消耗的各項

36、資源的影子價格的總和，即產(chǎn)品的隱含成本。當產(chǎn)值大于隱含成本時，即 ，表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排；否則 ，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。影子價格2.6 對偶單純形法 對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據(jù)對偶原理和單純形法原理而設計出來的，因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形法。對偶單純形法原理對偶單純形法基本思路： 找出一個對偶問題的可行基，保持對偶問題為可行解的條件下，判斷XB是否可行（XB為非負），若否，通過變換基解，直到找到原問題基可行解（即XB為非負），這時原問題與對偶問題同時達到可行解，由定理4可得最優(yōu)解。對偶單純形

37、法找出一個DP的可行基LP是否可行（XB 0）保持DP為可行解情況下轉移到LP的另一個基本解最優(yōu)解是否循環(huán)結束對偶單純形法先回顧一下單純形算法：它是從線性規(guī)劃的一個基可行解迭代到另一個基可行解的過程，在迭代過程中，保持基解的可行性，逐步消除基解的檢驗數(shù)的非負性，即為了求解線性規(guī)劃，我們也可以從線性規(guī)劃的一個基解迭代到另一個基解，在迭代過程中，保持基解的檢驗數(shù)的非正性，逐步消除基解的不可行性，即對偶單純形法 如果原問題(P)的一個基本解X與對偶問題(D)的基可 行解Y對應的檢驗數(shù)向量滿足條件 則稱X為原問題(P)的一個正則解。求解原問題(P)時，可以從(P)的一個正則解開始，迭代到另一個正則解，

38、使目標函數(shù)值增加，當?shù)秸齽t解滿足原始可行性條件(即xi0)時，就找到了原問題(P)的最優(yōu)解。 這一方法稱為對偶單純形法對偶單純形法定義原始單純形法對偶單純形法前提條件所有bi 0所有檢驗數(shù)0最優(yōu)性檢驗所有檢驗數(shù)0？所有bi 0？換入、出基變量的確定先確定換入基變量后確定換出基變量先確定換出基變量后確定換入基變量原始基本解的進化可行最優(yōu)（對偶問題的解從不可行到可行）非可行可行（最優(yōu)）（原問題的解從不可行到可行）對偶單純形法原問題解空間對偶問題解空間可行解可行解基本解基本解正則解正則解基可行解基可行解最優(yōu)解對偶單純形法對偶單純法的迭代步驟：（1）找一個正則基B和初始正則解X(0)，將問題（P）

39、化為關于基B的典式，列初始對偶單純形表.設正則解的典式為：對偶單純形法將上面的典式轉換成前面所學習過的單純形表：（2）若, 則迭代停止，已求得原問題（P）的最優(yōu)解;否則轉下一步。對偶單純形法則迭代停止，原問題無解；否則轉下一步。為換出變量。若（3）確定換出變量：若則取相應的變量對偶單純形法（4）確定換入變量：若則取x l 為換入變量。以正則解，返回（2）。為主元進行換基運算得到新的對偶單純形法用對偶單純形法計算解：為了便于尋找初始正則解，將問題變形為：取x4,x5為初始正則解，列單純形表如下：例9對偶單純形法-2-3-400XBbx1x2x3x4x5x4-3-1-2-110 x5-4-21-3

40、010-2-3-4由于初始正則解有負分量，于是取min-3,-4=-4x5為換出變量，取x1為換入變量，得新基x4,x1 ，51= -2為主元對偶單純形法基變換的過程：主元變?yōu)?，即用-2去除單純形表中基變量x5所在的行；主元所在列的其它元變?yōu)?，消去非基變量x1所在的列的其余元-1，-2；得新基x4,x1的單純形表-2-3-400XBbx1x2x3x4x5x4-3-1-2-110 x5-4-21-3010-2-3-4對偶單純形法基變換的過程：-2-3-4XBbx1x2x3x4x5x4x1-2-3-400XBbx1x2x3x4x5x4-3-1-2-110 x5-4-21-3010-2-3-42

41、1-1/23/20-1/2-10-5/21/21-1/240-4-10-1對偶單純形法-2-3-4XBbx1x2x3x4x5x4x121-1/23/20-1/2-10-5/21/21-1/240-4-10-1可見正則解的有負分量，由于x4=1 , 所以取x4為換出變量，取x2為換入變量，得新基x2,x1 ，42=-5/2為主元對偶單純形法-2-3-4XBbx1x2x3x4x5x22/501-1/5-2/51/5x111/5107/5-1/5-2/528/500-3/5-8/5-1/5此時正則解是可行解，也是最優(yōu)解。 X*=(11/5，2/5，0，0，0)；z*=-28/5進行基變換，得新正則解

42、的單純形表：對偶單純形法例10cjB-1b-120-5000cByBy1y2y3y40y3-50-4-2100y4-30-3-101j0-120-5000-120/-4-50/-2-50y22521-1/200y4-5-10-1/21j-1250-200-2502050-50y21501-3/22-120y15101/2-1j-135000-15-20例11cjB-1b23-5-M0cBxBx1x2x3x4x5-Mx471111070 x5-10-25-101j-7MM+2M+3M-5003x27111100 x5-45-70-6-51j21-10-7-M-301/77/6(M+3)/53x2

43、4/7011/72/71/72x145/7106/75/7-1/7j102/700-50/7-(M+16)/7-1/7例12cj3-1-100-MB-1bcBxBx1x2x3x4x5x60 x41-2110011110 x54-1-2010-3-Mx6-20100111j-6M+3-1M-1000-Mcj3-1-100-MB-1bcBxBx1x2x3x4x5x60 x43-2010-1100 x50-10012-1-1x3-2010011j1-1000-M+1-1cj3-1-100-MB-1bcBxBx1x2x3x4x5x63x11001/3-2/3-5/34-1x20100-1-21-1x3

44、0012/3-4/3-7/39j000-1/3-1/3-M+2/32cj3-1-100-MB-1bcBxBx1x2x3x4x5x60 x43001-2-512-1x20100-1-21-1x3-2010011j1000-1-M-1-2對偶單純形法的迭代步驟中,如何找一個初始正則解？初始正則解的確定標準形線性規(guī)劃問題選定的基B，不妨設對偶單純形法可行基B的典式為右端常數(shù)中有負數(shù)，而檢驗數(shù)全非正，則基B為正則基，相應的 解為初始正則解，就可用對偶單純形法求解。否則，若出現(xiàn)正檢驗數(shù)，X(0)就不是正則解。為此，求初始正則基和初始正則解，可增加一個約束條件：原問題(P)的典式擴充為下列問題:擴充問題：

45、對偶單純形法非基變量充分大數(shù)擴充問題的一個正則基和正則解是不難得到的。對偶單純形法擴充問題的兩種可能結果：（1）若擴充問題無可行解，則原問題(P)也無可行解。（2）若擴充問題有最優(yōu)解且目標函數(shù)最優(yōu)值與 M 無關,則有必為原問題(P)的最優(yōu)解。則把 x0 作為換出變量，xk 作為換入變量，經(jīng)過一次迭代，就可得到一個正則解：具體計算可以在單純形表上實現(xiàn).證明:則 一定是擴充問題的可行解，與假設矛盾。令對偶單純形法（1）若擴充問題無可行解，則原問題(P)也無可行解。事實上，若原問題如果有可行解：由于所以則 是擴充問題的可行解，又因擴充問題與原問題的目標函數(shù)相同，且都與 無關,所以必有 這與 是擴充問

46、題的最優(yōu)解矛盾。 對偶單純形法（2）若擴充問題有最優(yōu)解且目標函數(shù)最優(yōu)值與 M 無關,則有必為原問題(P)的最優(yōu)解。事實上，如果原問題有可行解對偶單純形法的理論解釋對偶單純形法所使用的表格與原單純形法一樣，可將典式中的數(shù)據(jù)放在原單純形表上，即得到對偶單純形表，所不同的是這里保證在整個過程中不保證,即右端常數(shù)中可以出現(xiàn)負數(shù)。對偶單純形法先定換出變量，再定換入變量。從本章起，不強調(diào)右端常數(shù)非負這個條件。設正則基 的典式為：對偶單純形法對偶單純形表對偶單純形法的迭代方式與原單純形法基本一致.所不同的是：先定換出變量，再定換入變量，決定主元并作基變換得到一個新的正則解X(1),從而完成一次迭代.算法的后

47、半部分與原單純形法完全一致.對偶單純形法 (2)再選進基變量:假定xk為進基變量, 我們分析一下xk 應滿足什么條件,才能使迭代后得到的解仍為問題(P)的正則解. (1)先選出基變量:若 則取與 相對應的基變量 xr 為出基變量. 因為 ,而換基運算的第一步是用主元 去除第r 行中的各元素,為了使變換后 為正數(shù),所以主元 必須從第r 行的負元素中選取,即 . 設主元處在第 k 列,于是換基運算后,各檢驗數(shù)變?yōu)?因為要求迭代后得到的解仍為正則解,于是 又因為 于是當 時,不等式(1)自然成立;由此則取與之相對應的非基變量 為換入變量。 否則,當 時,要使不等式(1)成立,必須 又因為 于是當 時

48、,不等式(1)自然成立;對偶單純形法最后證明對應于新的正則解X(1),對偶問題(D)的目標函數(shù)值將得到改善.這樣,上述求極大值問題(P)的迭代過程,實質(zhì)上是在對對偶問題(D)求極小值,所以目標函數(shù)越小就越接近最優(yōu)解.直到得到對偶問題(D)的最小值,相應地也就求出了原問題(P)的最大值. 出基變量 與進基變量 xk 確定以后,以 為主元進行換基運算(方法與原單純形法相同)即可得新的正則解X(1) . 這是因為 ,故和原始單純形法一樣,若對偶問題是非退化的(即對偶問題的每一個基可行解都是非退化的,或者說,對于原問題的每一個正則解，都有 ,則每迭代一次,目標函數(shù)都將嚴格減小,從而一定能在有限次迭代后

49、得到原問題的最優(yōu)解,或者判定它無解.容易證明:若 ,且所有的 ,則原問題(P)無解(自己證明). 用對偶單純形法求解線性規(guī)劃問題時，當約束條件為“”時，不必引進人工變量，使計算簡化。當線性規(guī)劃問題中變量多于約束條件時，用對偶單純形法計算可以減少工作量。對偶單純形法應用于主要應用于靈敏度分析及整數(shù)規(guī)劃等有關章節(jié)中。對偶單純形法的局限性主要是：對大多數(shù)線性規(guī)劃問題，很難找到一個初始正則解。因此對偶單純形法一般不單獨使用。對偶單純形法的優(yōu)缺點：對偶單純形法2.7 靈敏度分析靈敏度分析=對于市場的變化，我們的決策究竟怎樣變化 （不需要將它當成一個新問題）靈敏度分析的重要性在于：1. 向決策者提供線性規(guī)

50、劃問題的最優(yōu)解所能適應的環(huán)境條件變化的范圍；2. 環(huán)境條件變化時可能對經(jīng)營狀況帶來何種影響；3. 產(chǎn)生影響后的解決途徑。靈敏度分析靈敏度分析的類型：1. 模型中各個參數(shù)在什么范圍變化時，最優(yōu)基不發(fā)生改變。2. 模型中參數(shù)變化已經(jīng)超出上述范圍時，如何快速確定新的最優(yōu)基和最優(yōu)解新的最優(yōu)決策方案。模型中參數(shù)變化主要指：1. 目標函數(shù)的系數(shù)變化；2. 約束條件右邊的值變化；3. 約束條件中aij 的變化；4. 可決策變量增減的變化；5. 約束條件增減的變化。 靈敏度分析靈敏度分析的任務：1.當系數(shù)A、b、C中的某個發(fā)生變化時,目前的最優(yōu)基是否仍最優(yōu)（即目前的最優(yōu)生產(chǎn)方案是否要變化）?(稱為模型參數(shù)的靈

51、敏度分析)2.增加一個變量或增加一個約束條件時，目前的最優(yōu)基是否仍最優(yōu)（即目前的最優(yōu)生產(chǎn)方案是否要變化）？(稱為模型結構的靈敏度分析) 靈敏度分析線性規(guī)劃問題 I 表與 B 表的關系對給定符合典式的線性規(guī)劃問題中，初始基矩陣為 I ，基變量為 XS ，即松弛變量。其對應的初始單純形表如下： I 表（初始表）對初始單純形表進行迭代之后得到 B 為最優(yōu)基矩陣，最終典式所對應的單純形表： B 表（最終表）基解 X XSXSb A Ij C 0 基解 XB XN XSXBB -1b I B -1N B -1 j 0 CN CB B -1N - CB B -1 靈敏度分析原問題對偶問題結論或繼續(xù)計算的步

52、驟可行解可行解非可行解非可行解可行解非可行解可行解非可行解問題的最優(yōu)解或最優(yōu)基不變可以用單純形法繼續(xù)迭代求最優(yōu)解可以用對偶單純形法繼續(xù)迭代求最優(yōu)解引進人工變量，編制新的單純形表重新計算線性規(guī)劃原問題單純形法對應的 I 表中參數(shù)的變化將引起B(yǎng) 表中對應參數(shù)的變化情況如下：靈敏度分析基解X XSXSbA Ij C 0 基解XB XN XSXBB -1b I B -1N B -1 j 0 CN CB B -1N - CB B -1 I 表（初始表）B 表（最終表）靈敏度分析的方法： 靈敏度分析方法的關鍵是從單純形法對應的 I 表中參數(shù)的變化來分析B 表中對應參數(shù)的變化情況來回答決策者所關心問題。 靈

53、敏度分析的方法是在目前最優(yōu)基B下進行的。即當參數(shù)A、b、c中的某一個或幾個發(fā)生變化時，考察是否影響以下兩式的成立？ 靈敏度分析1. 對于參數(shù)b的靈敏度分析基解 XB XN XSXSb B N I j CB CN 0基解 XB XN XSXBB-1b I B -1N B -1j 0 CN CB B -1 - CB B -1I 表B 表當I 表中b變化為b時，在B 表中將只有解列 B-1b發(fā)生變化。靈敏度分析bXXBB-1bB-1AZC BB-1bC-C BB-1Ab變化的時候，僅對B-1b有影響僅關心B-1b0?若新的B-1b不滿足0，最優(yōu)基發(fā)生變化，此時需用對偶單純形法進行計算，調(diào)整可行性可能

54、當B-1b0時，最優(yōu)基不變（即生產(chǎn)產(chǎn)品的品種不變，但數(shù)量及最優(yōu)值會變化），此時可以簡單求出新最優(yōu)解。所以，b的變化只影響最優(yōu)解的變化和最優(yōu)值的變化。靈敏度分析若B-1b0，其是一個不等式組，從中可以解得b的變化范圍（此時，需保證當前最優(yōu)基變化后仍為最優(yōu)基）若B-1b中有小于0的分量，則需用對偶單純形法迭代，以求出新的最優(yōu)方案。（此時，基變量不變，因為基變量只需要相應的B可逆就可以了）bXXBB-1bB-1AZC BB-1bC-C BB-1A靈敏度分析I 表Cj21000CB基解X1X2X3X4X50X315051000X424620100X5511001檢驗數(shù)j21000B 表Cj21000C

55、B基解X1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2檢驗數(shù)j000-1/4-1/2靈敏度分析若b2增加到30，最優(yōu)解如何變化？最優(yōu)基不變，最優(yōu)解變?yōu)椋?，0，15，0，0）。靈敏度分析I 表Cj21000CB基解X1X2X3X4X50X315051000X424620100X5511001檢驗數(shù)j21000B 表Cj21000CB基解X1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2檢驗數(shù)j000-1/4-1/2靈敏度分析若b2增加到32，最優(yōu)解如何變

56、化？最優(yōu)基發(fā)生變化，用對偶單純形法求解。靈敏度分析B 表Cj21000CB基解X1X2X3X4X50X315051002X15110010X420-401-6檢驗數(shù)j0-100-2B 表Cj21000CB基解X1X2X3X4X50X335/20015/4-15/22X111/21001/4-1/21X2-1/2010-1/43/2檢驗數(shù)j000-1/4-1/2靈敏度分析 已知某生產(chǎn)計劃問題的數(shù)學模型，為使最優(yōu)方案不變，試討論第二個約束條件b2的變化范圍。 cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0

57、0 1/5 6/5 解：生產(chǎn)計劃問題的數(shù)學模型和最優(yōu)單純形表為：靈敏度分析從矩陣形式的單純形表中可知，b2的變化只影響解的可行性B-1b0，因此，為使最優(yōu)解不變，只需變化以后的B-1b0即可。由解得：當數(shù)據(jù)量十分大的時候，十分麻煩寫為B-1(24,26)+B-1b靈敏度分析若b2變化超過范圍，則需用對偶單純形法進行求解。如b2=6，則 cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x112-6 0 1 3/5 -2/5 1 0 -2/5 3/5 Z12 0 0 1/5 6/5 將上述數(shù)字替換最優(yōu)單純形表中相應位置的數(shù)據(jù)得：靈敏度分析 cj 4 3 0 0 CBXBb x1

58、x2 x3 x4 30 x2x3315 3/2 1 0 1/2 -5/2 0 1 -3/2 Z9 1/2 0 0 3/2 用對偶單純形法迭代，求出的最優(yōu)單純形表如下：得到新的最優(yōu)解為：x1=0，x2=3; max z=9靈敏度分析當 Cj 是非基變量 X 的目標系數(shù)時，若要保持最優(yōu)解（或基）不變，則必須滿足：CN CB B -1N 0基解 XB XN XSXSb B N Ij CB CN 0基解 XB XN XSXBB -1b I B -1N B -1j 0 CN CB B -1N - CB B -1I 表B 表2.對價值系數(shù)Cj變化的分析(1)當 Cj 變化使得非基變量的Cj Zj 0，即最

59、優(yōu)解（或基）發(fā)生變化，則在原單純形表的基礎上，繼續(xù)求解模型。靈敏度分析max z = 2x1 + x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x1 ，x2 0I 表Cj21000CB基解X1X2X3X4X50X315051000X424620100X5511001檢驗數(shù)j21000靈敏度分析B 表Cj21000CB基解X1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2檢驗數(shù)j000-1/4-1/2B 表CjC11000CB基解X1X2X3X4X50X315/20015/4-15/2C1X17/2

60、1001/4-1/21X23/2010-1/43/2檢驗數(shù)j0001/4-C1/4C1/2-3/2若要使最優(yōu)解保持不變，求x1的價值系數(shù)變化范圍。靈敏度分析因此：當CN（非基變量的目標函數(shù)系數(shù)）中某個Cj發(fā)生變化時，只影響到非基變量xj的檢驗數(shù) 最優(yōu)解改變，需要用單純形法重新進行迭代，以求得新的最優(yōu)解。最優(yōu)解不變（最小值）靈敏度分析 對于下列線性規(guī)劃模型,為使最優(yōu)解不變，討論非基變量y1的目標函數(shù)系數(shù)c3的變化范圍。用單純形法求得其最優(yōu)表為： cj 4 3 2 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 -1/5 3/5 -2/5 1 0 4/5 -2/5 3/