第六章靜態(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對偶規(guī)劃及影子價格應(yīng)用線性規(guī)劃處理問題經(jīng)常出現(xiàn)以下情況：所建模型變量不多，但約束卻很多。求解這類問題時，由于引入松弛變量和人工變量，導(dǎo)致矩陣A的規(guī)模急驟增大。如兩個變量，10個約束的線性規(guī)劃 模型，如果都是大于等于約束，則引入松弛變量和人工變量20個，是矩陣A的階次由102增大為1022，使計算工作量增大。在處理問題時，經(jīng)常需從不同角度來研究。如某建材廠生產(chǎn)兩種產(chǎn)品

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

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

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

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

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

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

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

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

10、xxxxxxxxxxxxw0,43232432min5432153214321321xxxxxxxxxxxxxxxxw234000-3-1-2-1100-4-21-30123400jcBCBXb1x4x3x2x5xjjzc 4x5x出基。行）選（2,0min4rbbbiir12234,22min0mincaaccjjjS進基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對偶問題的最優(yōu)解為：，故問題的最優(yōu)解為列非負，檢驗數(shù)全為正回顧運輸問題平衡型運輸問題設(shè)有m個供應(yīng)地，n個需求地，現(xiàn)需求編制產(chǎn)品調(diào)運計劃，使產(chǎn)品運輸費用最省。 需求地供應(yīng)地12.n擁有量1c11c12.c1na12c21c22.c2na2.mcm1cm2.cmnam需求量b1b2bniiba的運費。個需求地供應(yīng)單位產(chǎn)品個生產(chǎn)地向第為第個需求地的需求量；為第個生產(chǎn)地的生產(chǎn)量；為第量；個需求地運輸?shù)漠a(chǎn)品數(shù)個生產(chǎn)地向第為第jicjbiajixijjiij 0,2, 1,2, 1.min1111ijnjiijmijijminjijijxmiaxnjbxtsxcz這就是運輸問題的數(shù)學(xué)模型。它包含mn個變量，(m+n)個約束方程。其系數(shù)矩陣的結(jié)構(gòu)比較松散，且特殊。 行行nmvvvuuuxxxxxxxxxnmmnmmnn1111111111111111112121212222111211位勢法檢驗設(shè)u1，u2，um；v1，v2，vn是對應(yīng)運輸問題的m+n個約束條件的對偶變量。B是含有一個人工變量xa的(m+n)(m+n)初始基矩陣。人工變量xa在目標函數(shù)中的系數(shù)ca=0，從線性規(guī)劃的對偶理論可