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

第六章靜態(tài)線性系統(tǒng)最優(yōu)化模型及求解方法演示文稿目前一頁\總數(shù)二十五頁\編于十八點(diǎn)優(yōu)選第六章靜態(tài)線性系統(tǒng)最優(yōu)化模型及求解方法目前二頁\總數(shù)二十五頁\編于十八點(diǎn)在處理問題時(shí)，經(jīng)常需從不同角度來研究。如某建材廠生產(chǎn)兩種產(chǎn)品，其單位消耗量及單位利潤見表，現(xiàn)欲安排生產(chǎn)計(jì)劃。甲產(chǎn)品乙產(chǎn)品擁有量原料A22.51000原料B0.51600單位利潤250500目前三頁\總數(shù)二十五頁\編于十八點(diǎn)如果從另一個(gè)角度研究，現(xiàn)將原料出售，又不低于產(chǎn)品生產(chǎn)所獲得的利潤，兩種原料出售的最低利潤（在成本的基礎(chǔ)上的加價(jià)）應(yīng)為多少合算？甲產(chǎn)品乙產(chǎn)品擁有量原料A22.51000原料B0.51600單位利潤250500目前四頁\總數(shù)二十五頁\編于十八點(diǎn)在研究問題中，經(jīng)常需要分析某種資源的增加或減少對(duì)目標(biāo)值的影響程度。有些資源的增減并不影響目標(biāo)值，這類資源是長線資源，某些資源的增減對(duì)目標(biāo)值影響很大，這種資源是較稀缺的資源，稱為短線資源。為了確定資源的長短程度，需要一種評(píng)價(jià)方法。目前五頁\總數(shù)二十五頁\編于十八點(diǎn)線性規(guī)劃的對(duì)偶理論目標(biāo)要求變量數(shù)與約束數(shù)C與b系數(shù)矩陣目前六頁\總數(shù)二十五頁\編于十八點(diǎn)原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系原問題（對(duì)偶問題）對(duì)偶問題（原問題）目標(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目前七頁\總數(shù)二十五頁\編于十八點(diǎn)求下述線性規(guī)劃原問題的對(duì)偶問題目前八頁\總數(shù)二十五頁\編于十八點(diǎn)目前九頁\總數(shù)二十五頁\編于十八點(diǎn)區(qū)分基變量XB非基變量等式右端RHSXNXS系數(shù)矩陣檢驗(yàn)數(shù)0矩陣形式描述與單純形表目前十頁\總數(shù)二十五頁\編于十八點(diǎn)原問題目前十一頁\總數(shù)二十五頁\編于十八點(diǎn)對(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)基，則最優(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ì)偶變量一定為零。目前十二頁\總數(shù)二十五頁\編于十八點(diǎn)已知線性規(guī)劃問題目前十三頁\總數(shù)二十五頁\編于十八點(diǎn)maxz=4y1+3y2y1+2y2≤2①y1-y2≤3②2y1+3y2≤5③y1+y2≤2④3y1+y2≤3⑤y1，y2≥0目前十四頁\總數(shù)二十五頁\編于十八點(diǎn)原問題和對(duì)偶問題最優(yōu)解之間的關(guān)系原問題判斷數(shù)行0對(duì)偶問題原問題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問題的一個(gè)基解。目前十五頁\總數(shù)二十五頁\編于十八點(diǎn)設(shè)原問題對(duì)偶問題問題可表示為目前十六頁\總數(shù)二十五頁\編于十八點(diǎn)求得原問題的一個(gè)基解目前十七頁\總數(shù)二十五頁\編于十八點(diǎn)6.6.2影子價(jià)格由單純形法知，目標(biāo)函數(shù)值，當(dāng)b增加一個(gè)單位時(shí)，Z增加，稱為單純形乘子。它體現(xiàn)了資源增加一個(gè)單位時(shí)，目標(biāo)函數(shù)的增長量，起到了資源參考價(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ù)之一。目前十八頁\總數(shù)二十五頁\編于十八點(diǎn)由判斷準(zhǔn)則知，在最優(yōu)基時(shí)只有非基變量所對(duì)應(yīng)的判斷數(shù)才大于零，基變量的判斷數(shù)均為零。因此對(duì)原問題來說，松弛變量不為零，則它一定是基變量，且在基矩陣中，因基變量的判斷數(shù)為零，故根據(jù)對(duì)偶原理，它的影子價(jià)格為零，這種資源增長不會(huì)使目標(biāo)值增加，故它是長線資源。如果松弛變量為非基變量，其值為零，且判斷數(shù)大于零，這說明系統(tǒng)取最優(yōu)解時(shí)，該資源已用盡，其數(shù)量的增加可使目標(biāo)函數(shù)值增加，它的影子價(jià)格就是它所對(duì)應(yīng)的判斷數(shù)。目前十九頁\總數(shù)二十五頁\編于十八點(diǎn)6.6.3對(duì)偶單純形法對(duì)偶單純形法的計(jì)算步驟；（1）將模型標(biāo)準(zhǔn)化目前二十頁\總數(shù)二十五頁\編于十八點(diǎn)（2）求初始基解（判斷數(shù)均大于零的基解，可不是基可行解）目前二十一頁\總數(shù)二十五頁\編于十八點(diǎn)例子：目前二十二頁\總數(shù)二十五頁\編于十八點(diǎn)234000-3-1-2-1100-4[-2]1-30123400出基進(jìn)基目前二十三頁\總數(shù)二十五頁\編于十八點(diǎn)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目前二十四頁\總數(shù)二十五頁\編于十八點(diǎn)回顧運(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