第六章靜態(tài)線性系統(tǒng)最優(yōu)化模型及求解方法第一頁(yè)，共二十七頁(yè)，編輯于2023年，星期一6.6對(duì)偶規(guī)劃及影子價(jià)格應(yīng)用線性規(guī)劃處理問(wèn)題經(jīng)常出現(xiàn)以下情況：所建模型變量不多，但約束卻很多。求解這類問(wèn)題時(shí)，由于引入松弛變量和人工變量，導(dǎo)致矩陣A的規(guī)模急驟增大。如兩個(gè)變量，10個(gè)約束的線性規(guī)劃模型，如果都是大于等于約束，則引入松弛變量和人工變量20個(gè)，是矩陣A的階次由10×2增大為10×22，使計(jì)算工作量增大。第二頁(yè)，共二十七頁(yè)，編輯于2023年，星期一在處理問(wèn)題時(shí)，經(jīng)常需從不同角度來(lái)研究。如某建材廠生產(chǎn)兩種產(chǎn)品，其單位消耗量及單位利潤(rùn)見(jiàn)表，現(xiàn)欲安排生產(chǎn)計(jì)劃。甲產(chǎn)品乙產(chǎn)品擁有量原料A22.51000原料B0.51600單位利潤(rùn)250500第三頁(yè)，共二十七頁(yè)，編輯于2023年，星期一如果從另一個(gè)角度研究，現(xiàn)將原料出售，又不低于產(chǎn)品生產(chǎn)所獲得的利潤(rùn)，兩種原料出售的最低利潤(rùn)（在成本的基礎(chǔ)上的加價(jià)）應(yīng)為多少合算？甲產(chǎn)品乙產(chǎn)品擁有量原料A22.51000原料B0.51600單位利潤(rùn)250500第四頁(yè)，共二十七頁(yè)，編輯于2023年，星期一在研究問(wèn)題中，經(jīng)常需要分析某種資源的增加或減少對(duì)目標(biāo)值的影響程度。有些資源的增減并不影響目標(biāo)值，這類資源是長(zhǎng)線資源，某些資源的增減對(duì)目標(biāo)值影響很大，這種資源是較稀缺的資源，稱為短線資源。為了確定資源的長(zhǎng)短程度，需要一種評(píng)價(jià)方法。第五頁(yè)，共二十七頁(yè)，編輯于2023年，星期一6.6.1線性規(guī)劃的對(duì)偶理論目標(biāo)要求變量數(shù)與約束數(shù)C與b系數(shù)矩陣第六頁(yè)，共二十七頁(yè)，編輯于2023年，星期一原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）目標(biāo)函數(shù)minZ目標(biāo)函數(shù)maxZ約束條件約束條件數(shù)為m變量對(duì)偶變量數(shù)為m個(gè)約束條件為≥對(duì)偶變量為yj≥0約束條件為≤對(duì)偶變量yj≤0約束條件為=對(duì)偶變量yj為自由變量變量變量數(shù)為n個(gè)約束條件約束條件為n個(gè)變量xi為自由變量約束條件為=變量xi≥0約束條件為≤變量xi≤0約束條件為≥約束的系數(shù)矩陣為A約束的系數(shù)矩陣為AT約束常數(shù)項(xiàng)為b約束常數(shù)項(xiàng)為C指標(biāo)因素為C指標(biāo)因素為b第七頁(yè)，共二十七頁(yè)，編輯于2023年，星期一求下述線性規(guī)劃原問(wèn)題的對(duì)偶問(wèn)題第八頁(yè)，共二十七頁(yè)，編輯于2023年，星期一第九頁(yè)，共二十七頁(yè)，編輯于2023年，星期一區(qū)分基變量XB非基變量等式右端RHSXNXS系數(shù)矩陣檢驗(yàn)數(shù)0矩陣形式描述與單純形表第十頁(yè)，共二十七頁(yè)，編輯于2023年，星期一原問(wèn)題第十一頁(yè)，共二十七頁(yè)，編輯于2023年，星期一對(duì)偶理論一對(duì)對(duì)偶問(wèn)題，是一個(gè)問(wèn)題的兩個(gè)側(cè)面，其目標(biāo)是一致的，若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解，且目標(biāo)函數(shù)值相等；若原問(wèn)題解無(wú)界，對(duì)偶問(wèn)題無(wú)可行解。原問(wèn)題的檢驗(yàn)數(shù)，對(duì)應(yīng)于對(duì)偶問(wèn)題的一組基解，基矩陣B為最優(yōu)基，則最優(yōu)基下的檢驗(yàn)數(shù)對(duì)應(yīng)于對(duì)偶問(wèn)題的最優(yōu)解。對(duì)偶問(wèn)題的最優(yōu)解是原問(wèn)題的最優(yōu)基下的檢驗(yàn)數(shù)。在線性規(guī)劃最優(yōu)解中，若對(duì)應(yīng)的某一約束條件的對(duì)偶變量值非零，則該約束條件取嚴(yán)格等式，如果約束條件取嚴(yán)格不等式，則對(duì)應(yīng)的對(duì)偶變量一定為零。第十二頁(yè)，共二十七頁(yè)，編輯于2023年，星期一已知線性規(guī)劃問(wèn)題第十三頁(yè)，共二十七頁(yè)，編輯于2023年，星期一maxz=4y1+3y2y1+2y2≤2①y1-y2≤3②2y1+3y2≤5③y1+y2≤2④3y1+y2≤3⑤y1，y2≥0第十四頁(yè)，共二十七頁(yè)，編輯于2023年，星期一原問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解之間的關(guān)系原問(wèn)題判斷數(shù)行0對(duì)偶問(wèn)題原問(wèn)題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問(wèn)題的一個(gè)基解。第十五頁(yè)，共二十七頁(yè)，編輯于2023年，星期一設(shè)原問(wèn)題對(duì)偶問(wèn)題問(wèn)題可表示為第十六頁(yè)，共二十七頁(yè)，編輯于2023年，星期一求得原問(wèn)題的一個(gè)基解第十七頁(yè)，共二十七頁(yè)，編輯于2023年，星期一6.6.2影子價(jià)格由單純形法知，目標(biāo)函數(shù)值，當(dāng)b增加一個(gè)單位時(shí)，Z增加，稱為單純形乘子。它體現(xiàn)了資源增加一個(gè)單位時(shí)，目標(biāo)函數(shù)的增長(zhǎng)量，起到了資源參考價(jià)格的作用，因此又稱為影子價(jià)格。又稱為機(jī)會(huì)成本、會(huì)計(jì)價(jià)格、隱含價(jià)格、最優(yōu)計(jì)劃價(jià)格、完全競(jìng)爭(zhēng)條件下的市場(chǎng)價(jià)格以及最優(yōu)分工協(xié)作方案的實(shí)現(xiàn)價(jià)格等。是經(jīng)濟(jì)管理中相當(dāng)重要的參數(shù)之一。第十八頁(yè)，共二十七頁(yè)，編輯于2023年，星期一由判斷準(zhǔn)則知，在最優(yōu)基時(shí)只有非基變量所對(duì)應(yīng)的判斷數(shù)才大于零，基變量的判斷數(shù)均為零。因此對(duì)原問(wèn)題來(lái)說(shuō)，松弛變量不為零，則它一定是基變量，且在基矩陣中，因基變量的判斷數(shù)為零，故根據(jù)對(duì)偶原理，它的影子價(jià)格為零，這種資源增長(zhǎng)不會(huì)使目標(biāo)值增加，故它是長(zhǎng)線資源。如果松弛變量為非基變量，其值為零，且判斷數(shù)大于零，這說(shuō)明系統(tǒng)取最優(yōu)解時(shí)，該資源已用盡，其數(shù)量的增加可使目標(biāo)函數(shù)值增加，它的影子價(jià)格就是它所對(duì)應(yīng)的判斷數(shù)。第十九頁(yè)，共二十七頁(yè)，編輯于2023年，星期一6.6.3對(duì)偶單純形法對(duì)偶單純形法的計(jì)算步驟；（1）將模型標(biāo)準(zhǔn)化第二十頁(yè)，共二十七頁(yè)，編輯于2023年，星期一（2）求初始基解（判斷數(shù)均大于零的基解，可不是基可行解）第二十一頁(yè)，共二十七頁(yè)，編輯于2023年，星期一例子：第二十二頁(yè)，共二十七頁(yè)，編輯于2023年，星期一234000-3-1-2-1100-4[-2]1-30123400出基進(jìn)基第二十三頁(yè)，共二十七頁(yè)，編輯于2023年，星期一234000-10[-5/2]1/21-1/2221-1/23/20-1/2041012340002/501-1/5-2/51/5211/5107/5-1/5-2/5009/58/51/5第二十四頁(yè)，共二十七頁(yè)，編輯于2023年，星期一回顧運(yùn)輸問(wèn)題平衡型運(yùn)輸問(wè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需求