第六章靜態(tài)線性系統(tǒng)最優(yōu)化模型及求解方法7

1、徐曉鳴Guangdong Ocean University Engineering CollegeE-mail:第第6 6章靜態(tài)線性系統(tǒng)最優(yōu)化模型及求解方法章靜態(tài)線性系統(tǒng)最優(yōu)化模型及求解方法Optimization Model6.6對(duì)偶規(guī)劃及影子價(jià)格應(yīng)用線性規(guī)劃處理問題經(jīng)常出現(xiàn)以下情況：所建模型變量不多，但約束卻很多。求解這類問題時(shí)，由于引入松弛變量和人工變量，導(dǎo)致矩陣A的規(guī)模急驟增大。如兩個(gè)變量，10個(gè)約束的線性規(guī)劃 模型，如果都是大于等于約束，則引入松弛變量和人工變量20個(gè)，是矩陣A的階次由102增大為1022，使計(jì)算工作量增大。在處理問題時(shí)，經(jīng)常需從不同角度來研究。如某建材廠生產(chǎn)兩種產(chǎn)品

2、，其單位消耗量及單位利潤見表，現(xiàn)欲安排生產(chǎn)計(jì)劃。甲產(chǎn)品乙產(chǎn)品擁有量原料A22.51000原料B0.51600單位利潤2505000,6005 . 010005 . 22. .500250max21212121xxxxxxtsxxZ如果從另一個(gè)角度研究，現(xiàn)將原料出售，又不低于產(chǎn)品生產(chǎn)所獲得的利潤，兩種原料出售的最低利潤（在成本的基礎(chǔ)上的加價(jià)）應(yīng)為多少合算？0,5005 . 22505 . 02. .6001000min2121212121yyyyyytsyySyy為兩種原料的最低利潤、設(shè)：甲產(chǎn)品乙產(chǎn)品擁有量原料A22.51000原料B0.51600單位利潤250500在研究問題中，經(jīng)常需要分析某

3、種資源的增加或減少對(duì)目標(biāo)值的影響程度。有些資源的增減并不影響目標(biāo)值，這類資源是長線資源，某些資源的增減對(duì)目標(biāo)值影響很大，這種資源是較稀缺的資源，稱為短線資源。為了確定資源的長短程度，需要一種評(píng)價(jià)方法。6.6.1線性規(guī)劃的對(duì)偶理論0,6005 . 010005 . 22. .500250max21212121xxxxxxtsxxZ0,5005 . 22505 . 02. .6001000min21212121yyyyyytsyyS目標(biāo)要求變量數(shù)與約束數(shù)C與b系數(shù)矩陣原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系原問題（對(duì)偶問題）對(duì)偶問題（原問題）目標(biāo)函數(shù)minZ目標(biāo)函數(shù)maxZ約束條件約束條件數(shù)為m變量對(duì)偶變量數(shù)為

4、m個(gè)約束條件為對(duì)偶變量為yj0約束條件為對(duì)偶變量yj0約束條件為=對(duì)偶變量yj為自由變量變量變量數(shù)為n個(gè)約束條件約束條件為n個(gè)變量xi為自由變量約束條件為=變量xi0約束條件為變量xi0約束條件為約束的系數(shù)矩陣為A約束的系數(shù)矩陣為AT約束常數(shù)項(xiàng)為b約束常數(shù)項(xiàng)為C指標(biāo)因素為C指標(biāo)因素為b求下述線性規(guī)劃原問題的對(duì)偶問題 無約束432134322431143214321, 0, 0362422153532minxxxxyxxxyxxxyxxxxxxxxz無約束3213213213121321001523322645y,y,yyyyyyyyyyyyyyzmax0maxXbAXCXZ約束條件：目標(biāo)函數(shù)：

5、區(qū)分基變量XB非基變量等式右端RHSXNXS系數(shù)矩陣檢驗(yàn)數(shù)0IBB1NB1NBCCBN11B1BCBbB1bBCB1矩陣形式描述與單純形表011ABCCABCCBNBN基變量的系數(shù)均為零是非基變量的系數(shù)，CYAAYC001ABCCB01BCYB令zbBCbYbBCYBB11兩邊同時(shí)乘以只能存在最小值無限大）（表示bYYBCYB010minYCYAbYw0maxXbAXCXZ原問題 對(duì)偶理論一對(duì)對(duì)偶問題，是一個(gè)問題的兩個(gè)側(cè)面，其目標(biāo)是一致的，若原問題有最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等；若原問題解無界，對(duì)偶問題無可行解。原問題的檢驗(yàn)數(shù) ，對(duì)應(yīng)于對(duì)偶問題的一組基解，基矩陣B為最優(yōu)基，

6、則最優(yōu)基下的檢驗(yàn)數(shù)對(duì)應(yīng)于對(duì)偶問題的最優(yōu)解。對(duì)偶問題的最優(yōu)解是原問題的最優(yōu)基下的檢驗(yàn)數(shù)。在線性規(guī)劃最優(yōu)解中，若對(duì)應(yīng)的某一約束條件的對(duì)偶變量值非零，則該約束條件取嚴(yán)格等式，如果約束條件取嚴(yán)格不等式，則對(duì)應(yīng)的對(duì)偶變量一定為零。ABCCB1已知線性規(guī)劃問題求其原問題的最優(yōu)解。解為已知其對(duì)偶問題的最優(yōu)5,53,540,43243232532min*2*154321543215432154321zyyxxxxxxxxxxxxxxxxxxxxwmax z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20原問題和對(duì)偶問題最優(yōu)解之間的關(guān)系原問題判斷數(shù)行0對(duì)

7、偶問題BX1SYNXNBNABCC12SYSX1BCBY原問題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問題的一個(gè)基解。設(shè)原問題0maxXbAXCXZ0,max;SNBSNBNNBBXXXbIXNXBXXCXCZNBAB原問題可以改寫為：于是，是原問題的一個(gè)可行基設(shè)0,min2121SSNSBSYYYCYYNCYYBYbw對(duì)偶問題問題可表示為0minYCYAbYw求得原問題的一個(gè)基解)(0122111111NBCCYCYYNYCYYBBCYBCNBCCbBXBNSNSSBSBBBNB得出代入得出代入令。與其相應(yīng)的檢驗(yàn)數(shù)為6.6.2影子價(jià)格由單純形法知，目標(biāo)函數(shù)值 ，當(dāng)b增加一個(gè)單位時(shí)，Z增加 ， 稱為單純形

8、乘子。它體現(xiàn)了資源增加一個(gè)單位時(shí)，目標(biāo)函數(shù)的增長量，起到了資源參考價(jià)格的作用，因此又稱為影子價(jià)格。又稱為機(jī)會(huì)成本、會(huì)計(jì)價(jià)格、隱含價(jià)格、最優(yōu)計(jì)劃價(jià)格、完全競爭條件下的市場(chǎng)價(jià)格以及最優(yōu)分工協(xié)作方案的實(shí)現(xiàn)價(jià)格等。是經(jīng)濟(jì)管理中相當(dāng)重要的參數(shù)之一。bBCB11BCB1BCB由判斷準(zhǔn)則 知，在最優(yōu)基時(shí)只有非基變量所對(duì)應(yīng)的判斷數(shù)才大于零，基變量的判斷數(shù)均為零。因此對(duì)原問題來說，松弛變量不為零，則它一定是基變量，且在基矩陣中，因基變量的判斷數(shù)為零，故根據(jù)對(duì)偶原理，它的影子價(jià)格為零，這種資源增長不會(huì)使目標(biāo)值增加，故它是長線資源。如果松弛變量為非基變量，其值為零，且判斷數(shù)大于零，這說明系統(tǒng)取最優(yōu)解時(shí)，該資源已用盡

9、，其數(shù)量的增加可使目標(biāo)函數(shù)值增加，它的影子價(jià)格就是它所對(duì)應(yīng)的判斷數(shù)。01ABCCB6.6.3對(duì)偶單純形法對(duì)偶單純形法的計(jì)算步驟；（1）將模型標(biāo)準(zhǔn)化0minXbAXCXZ（2）求初始基解（判斷數(shù)均大于零的基解，可不是基可行解）。）進(jìn)行旋轉(zhuǎn)變換，轉(zhuǎn)（。列，得旋轉(zhuǎn)中心）選（）；（則問題解無解，否則轉(zhuǎn)）如果所有（行。）選（）。束，否則轉(zhuǎn)（則得最優(yōu)解，計(jì)算就結(jié)如果370min66, 050min44, 0)3(rsrjrjjSrjiiriaaaccabbbb例子：0,43232432min321321321321xxxxxxxxxxxxw0,43232432min5432153214321321xxxx

10、xxxxxxxxxxxxw0,43232432min5432153214321321xxxxxxxxxxxxxxxxw234000-3-1-2-1100-4-21-30123400jcBCBXb1x4x3x2x5xjjzc 4x5x出基。行）選（2,0min4rbbbiir12234,22min0mincaaccjjjS進(jìn)基234000-10-5/21/21-1/2221-1/23/20-1/204101jcBCBXb1x4x3x2x5xjjzc 4x1x2340002/501-1/5-2/51/5211/5107/5-1/5-2/5009/58/51/5jcBCBXb1x4x3x2x5xjj

11、zc 2x1x)5/1 , 5/8()0 , 0 , 0 , 5/2 , 5/11(YXb對(duì)偶問題的最優(yōu)解為：，故問題的最優(yōu)解為列非負(fù)，檢驗(yàn)數(shù)全為正回顧運(yùn)輸問題平衡型運(yùn)輸問題設(shè)有m個(gè)供應(yīng)地，n個(gè)需求地，現(xiàn)需求編制產(chǎn)品調(diào)運(yùn)計(jì)劃，使產(chǎn)品運(yùn)輸費(fèi)用最省。 需求地供應(yīng)地12.n擁有量1c11c12.c1na12c21c22.c2na2.mcm1cm2.cmnam需求量b1b2bniiba的運(yùn)費(fèi)。個(gè)需求地供應(yīng)單位產(chǎn)品個(gè)生產(chǎn)地向第為第個(gè)需求地的需求量；為第個(gè)生產(chǎn)地的生產(chǎn)量；為第量；個(gè)需求地運(yùn)輸?shù)漠a(chǎn)品數(shù)個(gè)生產(chǎn)地向第為第jicjbiajixijjiij 0,2, 1,2, 1.min1111ijnjiijmijijminjijijxmiaxnjbxtsxcz這就是運(yùn)輸問題的數(shù)學(xué)模型。它包含mn個(gè)變量，(m+n)個(gè)約束方程。其系數(shù)矩陣的結(jié)構(gòu)比較松散，且特殊。 行行nmvvvuuuxxxxxxxxxnmmnmmnn1111111111111111112121212222111211位勢(shì)法檢驗(yàn)設(shè)u1，u2，um；v1，v2，vn是對(duì)應(yīng)運(yùn)輸問題的m+n個(gè)約束條件的對(duì)偶變量。B是含有一個(gè)人工變量xa的(m+n)(m+n)初始基矩陣。人工變量xa在目標(biāo)函數(shù)中的系數(shù)ca=0，從線性規(guī)劃的對(duì)偶理論可