運籌學(xué)《第二章 線性規(guī)劃的對偶理論與靈敏度分析》

1、運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第二章 對偶理論與靈敏度分析n線性規(guī)劃的對偶問題n對偶問題的基本性質(zhì)n影子價格n對偶單純形法n靈敏度分析運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題例例1 1 美佳公司計劃制造I,II兩種家電產(chǎn)品.已知各制造一件時分別占用的設(shè)備A,B的臺時,調(diào)試時間，調(diào)試工序每天可用于這兩種家電的能力，各售出一件時的獲利情況如下表所示.問該公司應(yīng)制造兩種家電各多少件,使獲利最多。1.1 問題的提出產(chǎn)品I產(chǎn)品II每天可用能力設(shè)備A(h)0515設(shè)備B(h)6224調(diào)試工序(h)1 1

2、5利潤(h)2 1運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題解解: : 設(shè)該公司應(yīng)制造產(chǎn)品設(shè)該公司應(yīng)制造產(chǎn)品I,II分別為分別為x1 1, ,x2 2件件則則, ,目標(biāo)函數(shù)目標(biāo)函數(shù) max z = 2 x1 + x2 約束條件約束條件 5 x2 15 6 x1 + 2 x2 24 x1 + x2 5 x1 0，x20從另一角度提出問題：有一投資公司，欲購買美佳所擁有的資源，如何確定其最低收購價格。1 不吃虧原則 即投資公司希望自己所付出的盡量少，由此形成投資公司的目標(biāo)函數(shù) min w = 15y1+24y2+5y3分析：投資公司欲購買美

3、佳的資源,需給出合理的每種資源(設(shè)備A,設(shè)備B,調(diào)試工序)的價格(假定為y1,y2,y3),該價格需滿足兩個條件：運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析解解: : 設(shè)該公司應(yīng)制造產(chǎn)品設(shè)該公司應(yīng)制造產(chǎn)品I,II分別為分別為x1 1, ,x2 2件件則則, ,目標(biāo)函數(shù)目標(biāo)函數(shù) max z = 2 x1 + x2 約束條件約束條件 5 x2 15 6 x1 + 2 x2 24 x1 + x2 5 x1 0，x20從另一角度提出問題：有一投資公司，欲購買美佳所擁有的資源，如何確定其最低收購價格。分析：投資公司欲購買美佳的資源,需給出合理的每種資源(設(shè)備A,設(shè)備B,調(diào)

4、試工序)的價格(假定為y1,y2,y3),該價格需滿足兩個條件：2 競爭性原則 投資公司為每種資源所付出的資金必須不低于美佳公司利用該資源生產(chǎn)產(chǎn)品所獲得的利潤才可能讓對方同意賣出資源。由此形成約束條件 6y2+y32 5y1+2y2+y3 1 y1, y2 ,y3 0第一節(jié) 線性規(guī)劃的對偶問題產(chǎn)品I產(chǎn)品II每天可用能力設(shè)備A(h)0515設(shè)備B(h)6224調(diào)試工序(h)1 15利潤(h)2 1y1y2y3運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析比較兩模型比較兩模型max z = 2 x1 + x2 5 x2 15 6 x1 + 2 x2 24 x1 + x2

5、 5 x1 0，x20min w = 15y1+24y2+5y3 6y2+y32 5y1+2y2+y3 1 y1, y2 ,y3 0原問題對偶問題第一節(jié) 線性規(guī)劃的對偶問題運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題原問題原問題1.2 對稱形式下對偶問題的一般形式),.,1(0 max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn對偶問題對偶問題),.,1(0 min221122222112112211112211miycyayayacyayayac

6、yayayaybybybinmmnnnmmmmmm運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題原問題原問題1.2 對稱形式下對偶問題的一般形式),.,1(0 max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn對偶問題對偶問題),.,1(0 min221122222112112211112211miycyayayacyayayacyayayaybybybinmmnnnmmmmmm運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分

7、析第一節(jié) 線性規(guī)劃的對偶問題原問題原問題1.2 對稱形式下對偶問題的一般形式),.,1(0 max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn對偶問題對偶問題),.,1(0 min221122222112112211112211miycyayayacyayayacyayayaybybybinmmnnnmmmmmmAmnAnmT運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題原問題原問題1.2 對稱形式下對偶問題的一般形式),.,1(0 max22112

8、2222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn對偶問題對偶問題),.,1(0 min221122222112112211112211miycyayayacyayayacyayayaybybybinmmnnnmmmmmm運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題原問題原問題1.2 對稱形式下對偶問題的一般形式),.,1(0 max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnn

9、nn對偶問題對偶問題),.,1(0 min221122222112112211112211miycyayayacyayayacyayayaybybybinmmnnnmmmmmm運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題原問題原問題1.2 對稱形式下對偶問題的一般形式),.,1(0 max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn對偶問題對偶問題),.,1(0 min221122222112112211112211miycyayayacyayay

10、acyayayaybybybinmmnnnmmmmmm運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題原問題原問題1.2 對稱形式下對偶問題的一般形式0X maxXbAXCz對偶問題對偶問題0 minYCYAbYTTT運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題原問題原問題練習(xí) 寫出下面規(guī)劃的對偶問題)2 , 1(01241648232 max212121jxxxxxxxzj對偶問題對偶問題) 3 , 2 , 1(03422412168 min3121321iyyyyyyyyi運籌學(xué)運籌

11、學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題例例2 2 寫出下述線性規(guī)劃問題的對偶問題寫出下述線性規(guī)劃問題的對偶問題1.3 非對稱形式下原-對偶問題關(guān)系無約束321321321321321, 0, 04163253234 maxxxxxxxxxxxxxxxxz分析：顯然非對稱形式，將四個不符合對稱形式的地分析：顯然非對稱形式，將四個不符合對稱形式的地方分別化為對稱形式。方分別化為對稱形式。163321xxx44321321xxxxxx運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題例例2 2 寫出

12、下述線性規(guī)劃問題的對偶問題寫出下述線性規(guī)劃問題的對偶問題1.3 非對稱形式下原-對偶問題關(guān)系無約束321321321321321, 0, 04163253234 maxxxxxxxxxxxxxxxxz分析：顯然非對稱形式，將四個不符合對稱形式的地分析：顯然非對稱形式，將四個不符合對稱形式的地方分別化為對稱形式。方分別化為對稱形式。163321xxx44321321xxxxxx運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題例例2 2 寫出下述線性規(guī)劃問題的對偶問題寫出下述線性規(guī)劃問題的對偶問題1.3 非對稱形式下原-對偶問題關(guān)系無約束3213

13、21321321321, 0, 04163253234 maxxxxxxxxxxxxxxxxz分析：顯然非對稱形式，將四個不符合對稱形式的地分析：顯然非對稱形式，將四個不符合對稱形式的地方分別化為對稱形式。方分別化為對稱形式。令x2=-x2163321xxx44321321xxxxxx2532321xxx32134 maxxxxz運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題例例2 2 寫出下述線性規(guī)劃問題的對偶問題寫出下述線性規(guī)劃問題的對偶問題1.3 非對稱形式下原-對偶問題關(guān)系無約束321321321321321, 0, 0416325

14、3234 maxxxxxxxxxxxxxxxxz分析：顯然非對稱形式，將四個不符合對稱形式的地分析：顯然非對稱形式，將四個不符合對稱形式的地方分別化為對稱形式。方分別化為對稱形式。令x3-x3=x31663 3321xxxx44 3321 3321xxxxxxxx25532 3321xxxx 3321334 maxxxxxz運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題例例2 2 寫出下述線性規(guī)劃問題的對偶問題寫出下述線性規(guī)劃問題的對偶問題1.3 非對稱形式下原-對偶問題關(guān)系無約束321321321321321, 0, 0416325323

15、4 maxxxxxxxxxxxxxxxxz分析：顯然非對稱形式，將四個不符合對稱形式的地分析：顯然非對稱形式，將四個不符合對稱形式的地方分別化為對稱形式。方分別化為對稱形式。36536543132 3321 3321 3321 3321yyyyyyyyyyyyyyyy 332144y2 minyyy令-y2=y2,y3=y3-y3,并對約束2兩端乘以-1。1663 3321xxxx44 3321 3321xxxxxxxx25532 3321xxxx 3321334 maxxxxxz運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題例例2 2 寫

16、出下述線性規(guī)劃問題的對偶問題寫出下述線性規(guī)劃問題的對偶問題1.3 非對稱形式下原-對偶問題關(guān)系無約束321321321321321, 0, 04163253234 maxxxxxxxxxxxxxxxxz分析：顯然非對稱形式，將四個不符合對稱形式的地分析：顯然非對稱形式，將四個不符合對稱形式的地方分別化為對稱形式。方分別化為對稱形式。無約束321321321321, 0, 036543132yyyyyyyyyyyy3214y2 minyy 運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題1.3 非對稱形式下原-對偶問題關(guān)系原問題（或?qū)ε紗栴}）原

17、問題（或?qū)ε紗栴}）對偶問題（或原問題）對偶問題（或原問題）目標(biāo)函數(shù)目標(biāo)函數(shù) max z目標(biāo)函數(shù)目標(biāo)函數(shù) min w決決策策變變量量n個個約約束束條條件件n個個00無約束無約束=約約束束條條件件m個個決決策策變變量量m個個00=無約束無約束約束條件右端項約束條件右端項目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項約束條件右端項運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題原問題原問題練習(xí)1 寫出下面規(guī)劃的對偶問題無約束321321321321321, 0, 04163253234 maxxxxxxxxx

18、xxxxxxxz對偶問題對偶問題無約束321321321321321, 0, 03654313242 minyyyyyyyyyyyyyyy運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題原問題原問題練習(xí)1 寫出下面規(guī)劃的對偶問題對偶問題對偶問題無約束321321321321321, 0, 03654313242 minyyyyyyyyyyyyyyy無約束321321321321321, 0, 04163253234 maxxxxxxxxxxxxxxxxz運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃

19、的對偶問題原問題原問題練習(xí)2 寫出下面規(guī)劃的對偶問題對偶問題對偶問題123max 43zyyy12312312313123min 242313430,0,wxxxxxxxxxxxxxx無約束2y1+3y2+y3 23y1- y2 1 y1+ y2+y3 -4y1 y2 y300無約束運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第一節(jié) 線性規(guī)劃的對偶問題練習(xí)3 寫出下面規(guī)劃的對偶問題123452345123413412345max 375883416233222252105250,0,zxxxxxxxxxxxxxxxxxxxxx 無約束123452345123413

20、412345max 375883416233222252105250,0,zxxxxxxxxxxxxxxxxxxxxx 無約束變換1234523451234134112212345max 375883416233222251022550,0,0,zxxxxxxxxxxxxxxxxxxxxxxxxx 無約束，無約束12345672345126712312311234567min -162510225523373253228480,0,0,wyyyyyyyyyyyyyyyyyyyyyyyyyyyyy 無約束，0,0,0運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第二節(jié)

21、 對偶問題的基本性質(zhì)2.1 單純形法的矩陣描述cjc1c2c3c4c5000CBXBbx1x2x3x4x5x6x7x80 x6b1a11a12a13a14a151000 x7b2a21a22a23a24a250100 x8b3a31a32a33a34a35001cj-zjc1c2c3c4c5000cjc1c2c3c4c5000CBXBbx1x2x3x4x5x6x7x8c1x1b1100a14a15111213c2x2b2010a24a25212223c3x3b3001a34a35313233cj-zj000c4-z4c5 z50-z60-z70-z8初初始始表表過過程程表表運籌學(xué)運籌學(xué)-線性規(guī)

22、劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第二節(jié) 對偶問題的基本性質(zhì)2.1 單純形法的矩陣描述cjc1c2c3c4c5000CBXBbx1x2x3x4x5x6x7x80 x6b1a11a12a13a14a151000 x7b2a21a22a23a24a250100 x8b3a31a32a33a34a35001cj-zjc1c2c3c4c5000cjc1c2c3c4c5000CBXBbx1x2x3x4x5x6x7x8c1x1b1100a14a15111213c2x2b2010a24a25212223c3x3b3001a34a35313233cj-zj000c4-z4c5 z50-z6

23、0-z70-z8初初始始表表過過程程表表CBCNXBXNXSBNICBCN000XSbCBCNXBXNXSIB-1NB-10CN-CB B-1N00- CB B-1CBXBB-1b推導(dǎo)推導(dǎo)運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第二節(jié) 對偶問題的基本性質(zhì)2.1 單純形法的矩陣描述cjc1c2c3c4c5000CBXBbx1x2x3x4x5x6x7x80 x6b1a11a12a13a14a151000 x7b2a21a22a23a24a250100 x8b3a31a32a33a34a35001cj-zjc1c2c3c4c5000cjc1c2c3c4c5000CB

24、XBbx1x2x3x4x5x6x7x8c1x1b1100a14a15111213c2x2b2010a24a25212223c3x3b3001a34a35313233cj-zj000c4-z4c5 z50-z60-z70-z8初初始始表表過過程程表表CBCNXBXNXSBNICBCN000XSbCBCNXBXNXSIB-1NB-10CN-CB B-1N00- CB B-1CBXBB-1b運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析cj23000CBXBbx1x2x3x4x50 x381210040 x41640010-0 x512040013cj-zj230002x

25、121010-0.5-0 x4800-41243x2301001/412cj-zj00-200.25B=(p1,p4,p2)102410004B-1=(p3,p4,p5)100.5412001/41100.582412168001/4123B bb 運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析0CN-CB B-1N0- CB B-1CB-CB B-1B=C-CB B-1A- CB B-1C-CBB-1A0-CBB-1 0令YT=CBB-1（單純形乘子)，代入上式及目標(biāo)函數(shù)YTAC ATY CTYT 0 Y 0z= CBB-1b = YTb=即原問題松弛變量檢驗數(shù)的

26、相反數(shù)對應(yīng)其對偶問題的可行解推導(dǎo)若基B為最優(yōu)基運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析例例3 30524261550002 max5214213254321jxxxxxxxxxxxxxxz0125260052415 min532143254321iyyyyyyyyyyyyy運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析原問題變量松弛變量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2cj-zj000-1/4-1/2對偶問題剩余變量對偶問題變量y4y5y1y2y3對偶問

27、題變量對偶問題剩余變量y1y2y3y4y5y21/4-5/411-1/41/4y31/215/2011/2-3/2cj-zj15/2007/23/2原問題松弛變量原問題變量x3x4x5x1x2原問題松弛變量檢驗數(shù)的相反數(shù)對應(yīng)其對偶問題的可行解對偶問題剩余變量的檢驗數(shù)是原問題的可行解運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析原問題變量松弛變量x1x2x3x4x5x315/20015/4-15/2x27/21001/4-1/2x13/2010-1/43/2cj-zj000-1/4-1/2對偶問題剩余變量對偶問題變量y4x5y1y2y3對偶問題變量對偶問題剩余變量y1

28、y2y3y4x5y21/4-5/411-1/41/4y31/215/2011/2-3/2cj-zj15/2007/23/2原問題松弛變量原問題變量x3x4x5x1x2原問題松弛變量檢驗數(shù)的相反數(shù)對應(yīng)其對偶問題的可行解對偶問題剩余變量的檢驗數(shù)是原問題的可行解運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析練習(xí)練習(xí) 已知線性規(guī)劃問題：已知線性規(guī)劃問題：121212112max 2222730zxxxxxxxxx，的最終單純形表：的最終單純形表：（1 1）寫出其對偶規(guī)劃）寫出其對偶規(guī)劃（2 2）解出對偶問題最優(yōu)解）解出對偶問題最優(yōu)解（3 3）寫出最優(yōu)基矩陣）寫出最優(yōu)基矩陣B

29、 B及其逆矩陣及其逆矩陣B B-1-1cj21000CBXBbx1x2x3x4x52x250101/21/21x13100010 x33001-1/23/2cj-zj000-1-2運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第二節(jié) 對偶問題的基本性質(zhì)2.2 對偶問題的基本性質(zhì)1.1.弱對偶性弱對偶性若 是原問題的可行解， 是其對偶問題的可行解，則恒有 ),.,1(njxj),.,1(miyimiiinjjjybxc111）原問題任一可行解的目標(biāo)函數(shù)是其對偶問題目標(biāo)函數(shù)值的下界；反之對偶問題任一可行解的目標(biāo)函數(shù)是其原問題的上界。2）若原問題有無界解，則其對偶問題無可

30、行解；反之若對偶問題有無界解，則原問題無可行解。3）若原問題有可行解而對偶問題無可行解則原問題目標(biāo)函數(shù)值無界；反之若對偶問題有可行解而原問題無可行解則對偶問題目標(biāo)函數(shù)值無界。無界解無可行解無可行解無界解無可行解運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第二節(jié) 對偶問題的基本性質(zhì)2.2 對偶問題的基本性質(zhì)2.2.最優(yōu)性最優(yōu)性若 是原問題的可行解，是其對偶問題的可行解，當(dāng)C = Tb時， ， 是最優(yōu)解。 XYXYXY3.3.強(qiáng)對偶性強(qiáng)對偶性若原問題與其對偶問題均有可行解，則兩者均有最優(yōu)解，且最優(yōu)值相等。 4.4.互補(bǔ)松弛性互補(bǔ)松弛性若 是原問題的可行解，是其對偶問題

31、的可行解，那么 TXS=0 和YS T =0，當(dāng)且僅當(dāng)兩者均為最優(yōu)解。 XYYX運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析原問題變量松弛變量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2cj-zj000-1/4-1/2對偶問題剩余變量對偶問題變量y4y5y1y2y3對偶問題變量對偶問題剩余變量y1y2y3y4y5y21/4-5/411-1/41/4y31/215/2011/2-3/2cj-zj15/2007/23/2原問題松弛變量原問題變量x3x4x5x1x20524261550002 max5

32、214213254321jxxxxxxxxxxxxxxz0125260052415 min532143254321iyyyyyyyyyyyyy*(7/2,3/2),(0,0)(15/2,0,0),(0,1/4,1/2)TsTSXYXY運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析練習(xí)已知線性規(guī)劃問題如下，利用對偶理論證明該問題已知線性規(guī)劃問題如下，利用對偶理論證明該問題無最優(yōu)解。無最優(yōu)解。0,122 max32132132121xxxxxxxxxxxz證明：該問題對偶問題如下，易驗證原問 題有可行解，對偶 問題約束1顯示該問 題無可行解，故由弱 對偶性推論3可得,原

33、 問題有無界解，即無 最優(yōu)解。 0,01122 min2121212121yyyyyyyyyy3）若原問題有可行解而對偶問題無可行解則原問題目標(biāo)函數(shù)值無界；反之若對偶問題有可行解而原問題無可行解則對偶問題目標(biāo)函數(shù)值無界。運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析練習(xí)已知線性規(guī)劃問題如下，其對偶問題最優(yōu)解為已知線性規(guī)劃問題如下，其對偶問題最優(yōu)解為y y1 1* *=4/5,y=4/5,y2 2* *=3/5;z=5,=3/5;z=5,用對偶理論找出原問題最優(yōu)解。用對偶理論找出原問題最優(yōu)解。)5,.,1(0354324534232532 min32132154321

34、jxxxxxxxxxxxxxxxxj運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析)5,.,1(033243232532 min543215432154321jxxxxxxxxxxxxxxxxj解:原問題對偶問題為0,3325323223yy4 max21212121212121yyyyyyyyyyyyz解解: :將將y y1 1* *=4/5,y=4/5,y2 2* *=3/5=3/5代入對偶規(guī)劃得代入對偶規(guī)劃得(1)4/5+6/5=2(1)4/5+6/5=2(2)4/5-3/5=1/53(2)4/5-3/5=1/53(3)8/5+9/5=17/55(3)8/5+

35、9/5=17/55(4)4/5+3/5=7/52(4)4/5+3/5=7/50;0;由互補(bǔ)松弛性由互補(bǔ)松弛性定理定理: :對于原問題的最優(yōu)解對于原問題的最優(yōu)解X=(xX=(x1 1* *,x,x2 2* *,x,x3 3* *,x,x4 4* *,x,x5 5* *) )T T, ,成立下式成立下式Y(jié) YS SX=0,X=0,即即y y3 3x x1 1* *=y=y4 4x x2 2* *=y=y5 5x x3 3* *=y=y6 6x x4 4* *=y=y7 7x x5 5* *=0=0因為因為y y4 4, y, y5 5, y, y6 60,0,則有則有x x2 2* *=x=x3

36、3* *=x=x4 4* *=0;=0;又又Y Y* *X XS S=0(y=0(y1 1* *,y,y2 2* *0,0,則則x x6 6=x=x7 7=0).=0).則則x x1 1+3x+3x5 5 =4 2x=4 2x1 1+x+x5 5=3=3解得解得: :x x1 1=1,x=1,x5 5=1=1故原問題最優(yōu)解為(1,0,0,0,1)T最優(yōu)值為w=2*1+3*1=5運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析練習(xí)已知線性規(guī)劃問題如下，其最優(yōu)解為已知線性規(guī)劃問題如下，其最優(yōu)解為X X* *=2,2,4,0=2,2,4,0T T, ,用對偶理論找出對偶問題

37、最優(yōu)解。用對偶理論找出對偶問題最優(yōu)解。123412412123234max 243826960(1,.,4)jzxxxxxxxxxxxxxxxxj最優(yōu)解為最優(yōu)解為X X* *=2,2,4,0=2,2,4,0T T123412412123234max 243826960(1,.,4)jzxxxxxxxxxxxxxxxxj解：原問題的對偶問題為：解：原問題的對偶問題為：123412312343414min 86962234110(1,.,4)jwyyyyyyyyyyyyyyyyj將將X X* *代入原問題可得：代入原問題可得：x5=0,x6=0,x70,x8=0.x5=0,x6=0,x70,x8=

38、0.由互補(bǔ)松弛性定理由互補(bǔ)松弛性定理 可得：可得：同樣由同樣由 可得：可得：即即: :*30y *TSY X =0T*sY X =05670,0,0yyy123123434142234110(1,.,4)jyyyyyyyyyyyyj將將 代入得代入得*30y 12124422341yyyyyyY Y* *=(4/5,3/5,0,1)=(4/5,3/5,0,1)T T運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第三節(jié) 影子價格回憶第一節(jié)所提出的問題回憶第一節(jié)所提出的問題max z = 2 x1 + x2 5 x2 15 6 x1 + 2 x2 24 x1 + x2

39、5 x1 0，x20min w = 15y1+24y2+5y3 6y2+y32 5y1+2y2+y3 1 y1, y2 ,y3 0原問題對偶問題美佳公司計劃制造I,II兩種家電產(chǎn)品.已知各制造一件時分別占用的設(shè)備A,B的臺時,調(diào)試時間，調(diào)試工序每天可用于這兩種家電的能力，各售出一件時的獲利情況如下表所示.問該公司應(yīng)制造兩種家電各多少件,使獲利最多有一投資公司，欲購買美佳所擁有的資源，如何確定其最低收購價格影子價格Shadow price運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析影子價格的定義n聯(lián)合國工業(yè)發(fā)展組織的有關(guān)文獻(xiàn)中對影子價格的含義解釋聯(lián)合國工業(yè)發(fā)展組織的

40、有關(guān)文獻(xiàn)中對影子價格的含義解釋 ：“影子價格是商品或生產(chǎn)要素可得性的任何變化所帶來的福利影子價格是商品或生產(chǎn)要素可得性的任何變化所帶來的福利增加增加”，其實質(zhì)是說明影子價格是反映資源合理配置的資源價格。，其實質(zhì)是說明影子價格是反映資源合理配置的資源價格。n國家計委在國家計委在建設(shè)項目經(jīng)濟(jì)評價方法與參數(shù)建設(shè)項目經(jīng)濟(jì)評價方法與參數(shù)中對影子價格解釋中對影子價格解釋：“影子價格是為消除價格扭曲對投資決策的影響，合理度量資源、影子價格是為消除價格扭曲對投資決策的影響，合理度量資源、貨物與服務(wù)的經(jīng)濟(jì)價值而測定的，比財務(wù)價格更為合理的價格貨物與服務(wù)的經(jīng)濟(jì)價值而測定的，比財務(wù)價格更為合理的價格”。并進(jìn)一步闡明

41、：并進(jìn)一步闡明：“所謂合理，從定價原則看應(yīng)能更好的反映產(chǎn)品的所謂合理，從定價原則看應(yīng)能更好的反映產(chǎn)品的價值，反映市場供求情況，反映資源稀缺程度。從價格產(chǎn)生的效價值，反映市場供求情況，反映資源稀缺程度。從價格產(chǎn)生的效果看，應(yīng)能使資源配置向優(yōu)化方向發(fā)展。果看，應(yīng)能使資源配置向優(yōu)化方向發(fā)展?！边\籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第三節(jié) 影子價格資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而其影子價格依賴于資源的利用情況，是未知數(shù)。影子價格是一種邊際價格。影子價格的說明設(shè)對偶問題目標(biāo)函數(shù)最優(yōu)值為w=y1*b1+ y2*b2+ ym*bm并假定w為bi的函數(shù)，則有yi*=

42、 ，因此 yi*可以理解為 w對bi的變化率，即當(dāng)僅bi變化一個單位， w的變化量。這即是經(jīng)濟(jì)學(xué)中邊際價格的含義。ib運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第三節(jié) 影子價格3.資源的影子價格是一種機(jī)會成本。影子價格的說明機(jī)會成本當(dāng)具有多種用途的稀缺資源使經(jīng)濟(jì)主體需要選擇時，選擇會帶來成本，選擇的成本我們稱為機(jī)會成本，當(dāng)把一定資源用于生產(chǎn)某種產(chǎn)品時所放棄的另一各產(chǎn)品的數(shù)量就是機(jī)會成本，它是作出一次決策時所放棄的其他可供選擇的最好用途。運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第三節(jié) 影子價格3.資源的影子價格是一種機(jī)會成本。影子

43、價格的說明理論上，在完全市場經(jīng)濟(jì)條件下，資源的影子價格高于市場價格時，應(yīng)購入該資源；反之，則應(yīng)售出該資源。4. 在生產(chǎn)過程中，若某種資源未被完全利用，則該資源的影子價格為0；當(dāng)該資源的影子價格不為零時則表明該資源在生產(chǎn)過程中已使用完畢。某種資源未被完全利用，表明若繼續(xù)增加該種資源的數(shù)量，問題的最優(yōu)解也不會變化，即目標(biāo)函數(shù)相對于該種資源的變化率為0，根據(jù)影子價格的說明2，則該資源的影子價格為0。也可以用互補(bǔ)松弛性定理來解釋。設(shè)有n種資源，由互補(bǔ)松弛性定理：若資源i未用完，則有 ,由即第i種資源的影子價格為零。*0TsYX *123123(,.,.)(,.,.,)0Tinssssisnyyyyyx

44、xxxx0six *0,0isiiy xy得到運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第三節(jié) 影子價格5.資源的影子價格與檢驗數(shù)。影子價格的說明111,mTjjBjjjjijiimijijicC B PcY Pca ya yjc原問題的檢驗數(shù)這里可以理解為生產(chǎn)產(chǎn)品的隱含成本， 為該產(chǎn)品的價格，若價格大于隱含成本，即檢驗數(shù)大于零，表明還可以繼續(xù)利用這些資源增加該產(chǎn)品的生產(chǎn)，否則表明沒必要增加該產(chǎn)品數(shù)量。即檢驗數(shù)小于零表明已經(jīng)達(dá)到最優(yōu)解。運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第三節(jié) 影子價格6. 原問題的目的在于確定資源的最優(yōu)分

45、配方案，而對偶問題的目的在于確定資源的恰當(dāng)估價。影子價格的說明運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第四節(jié) 對偶單純形法回顧單純形法的基本步驟回顧單純形法的基本步驟4.1 基本思路cj23000CBXBbx1x2x3x4x52x141000.2500 x5400-20.513x22010.5-1/80cj-zj00-1.5-1/80該列值非負(fù)且不含非零人工變量該行值非正+運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第四節(jié) 對偶單純形法回顧線性規(guī)劃原問題與對偶問題解的關(guān)系回顧線性規(guī)劃原問題與對偶問題解的關(guān)系4.1 基本思路cj23

46、000CBXBbx1x2x3x4x52x141000.2500 x5400-20.513x22010.5-1/80cj-zj00-1.5-1/80原問題的基可行解對偶問題的基解，若對偶問題與原問題同時為可行解，則同時達(dá)到最優(yōu)解運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析對偶性質(zhì)對偶性質(zhì)若原問題;,0Sb X XSmaxz=CX;AX+X對偶問題min; ,0SSwYb YA YC Y Y則原問題單純形表的檢驗數(shù)行對應(yīng)其對偶問題的一個基解。運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析第四節(jié) 對偶單純形法1.1.列出初始單純形表。檢查列出

47、初始單純形表。檢查b b列的數(shù)字，若都為非負(fù)，檢驗數(shù)都為列的數(shù)字，若都為非負(fù)，檢驗數(shù)都為非正，則已經(jīng)得到最優(yōu)解，停止計算。若檢查非正，則已經(jīng)得到最優(yōu)解，停止計算。若檢查b b列的數(shù)字時，至少列的數(shù)字時，至少有一個負(fù)分量，檢驗數(shù)保持非正，則轉(zhuǎn)入步驟有一個負(fù)分量，檢驗數(shù)保持非正，則轉(zhuǎn)入步驟2 2。2.2.確定換出變量確定換出變量 按照按照3.3.確定換入變量確定換入變量在單純形表中檢查在單純形表中檢查xl所在行的系數(shù)所在行的系數(shù)alj（j=1,2,n）.若所有alj0,則無可行解無可行解,停止計算。若存在停止計算。若存在alj12, 即最優(yōu)解不滿足該約束。將該約束增加松弛變量為3x1+2x2+x6

48、=12 , 代入原最終表cj210000CB XB bx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x612320001cj-zj000-1/4-1/20由于x1,x2為基變量，故其對應(yīng)向量應(yīng)為單位向量.運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析cj210000CB XB bx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x6-3/2000-1/4-3/21cj-zj000-1/4-1/

49、20原問題不可行，用對偶單純形法求解.1 1/3運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析cj210000CB XB bx1x2x3x4x5x60 x3150015/20-52x141001/30-1/31x20010-1/2010 x510001/61-2/3cj-zj000-1/60-1/3最優(yōu)解為生產(chǎn)家電最優(yōu)解為生產(chǎn)家電I 4I 4件件. .運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析練習(xí)1 已知某廠生產(chǎn)兩種產(chǎn)品的最優(yōu)單純形表。其中x1,x2為兩種產(chǎn)品的產(chǎn)量，x3,x4,x5為三種資源(設(shè)備臺時,原材料A,B)的松弛變量。求解

50、下列問題：(1)若該廠欲生產(chǎn)一種新產(chǎn)品，每件消耗三種資源分別為2， 6，3，獲利5，是否值得生產(chǎn)？(2)若該廠從別處抽出4臺時用于生產(chǎn)，求最優(yōu)生產(chǎn)計劃。cj23000CB XB bx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80cj-zj00-1/2-1/80運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析cj23000CB XB bx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80cj-zj00-1/2-1/80解: 1T666x62cYP5(1/2,1/8,0) 613/403 設(shè)新增產(chǎn)品量為因此生產(chǎn)該產(chǎn)品可以獲利。運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析cj23000CB XB bx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80cj-zj00-1/2-1/80解:21101/4048bB b21/214161/21/8021201/408+444bB b21/2116-41/21/80124bb 由增加 臺時，則將b反映到最終單純表中，用對偶單純型法繼續(xù)迭代運籌學(xué)運籌學(xué)-線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的