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

第六章靜態(tài)線性系統(tǒng)最優(yōu)化模型及求解方法演示文稿當(dāng)前1頁(yè)，總共25頁(yè)。優(yōu)選第六章靜態(tài)線性系統(tǒng)最優(yōu)化模型及求解方法當(dāng)前2頁(yè)，總共25頁(yè)。在處理問(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當(dāng)前3頁(yè)，總共25頁(yè)。如果從另一個(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當(dāng)前4頁(yè)，總共25頁(yè)。在研究問(wèn)題中，經(jīng)常需要分析某種資源的增加或減少對(duì)目標(biāo)值的影響程度。有些資源的增減并不影響目標(biāo)值，這類(lèi)資源是長(zhǎng)線資源，某些資源的增減對(duì)目標(biāo)值影響很大，這種資源是較稀缺的資源，稱(chēng)為短線資源。為了確定資源的長(zhǎng)短程度，需要一種評(píng)價(jià)方法。當(dāng)前5頁(yè)，總共25頁(yè)。線性規(guī)劃的對(duì)偶理論目標(biāo)要求變量數(shù)與約束數(shù)C與b系數(shù)矩陣當(dāng)前6頁(yè)，總共25頁(yè)。原問(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當(dāng)前7頁(yè)，總共25頁(yè)。求下述線性規(guī)劃原問(wèn)題的對(duì)偶問(wèn)題當(dāng)前8頁(yè)，總共25頁(yè)。當(dāng)前9頁(yè)，總共25頁(yè)。區(qū)分基變量XB非基變量等式右端RHSXNXS系數(shù)矩陣檢驗(yàn)數(shù)0矩陣形式描述與單純形表當(dāng)前10頁(yè)，總共25頁(yè)。原問(wèn)題當(dāng)前11頁(yè)，總共25頁(yè)。對(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ì)偶變量一定為零。當(dāng)前12頁(yè)，總共25頁(yè)。已知線性規(guī)劃問(wèn)題當(dāng)前13頁(yè)，總共25頁(yè)。maxz=4y1+3y2y1+2y2≤2①y1-y2≤3②2y1+3y2≤5③y1+y2≤2④3y1+y2≤3⑤y1，y2≥0當(dāng)前14頁(yè)，總共25頁(yè)。原問(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è)基解。當(dāng)前15頁(yè)，總共25頁(yè)。設(shè)原問(wèn)題對(duì)偶問(wèn)題問(wèn)題可表示為當(dāng)前16頁(yè)，總共25頁(yè)。求得原問(wèn)題的一個(gè)基解當(dāng)前17頁(yè)，總共25頁(yè)。6.6.2影子價(jià)格由單純形法知，目標(biāo)函數(shù)值，當(dāng)b增加一個(gè)單位時(shí)，Z增加，稱(chēng)為單純形乘子。它體現(xiàn)了資源增加一個(gè)單位時(shí)，目標(biāo)函數(shù)的增長(zhǎng)量，起到了資源參考價(jià)格的作用，因此又稱(chēng)為影子價(jià)格。又稱(chēng)為機(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ù)之一。當(dāng)前18頁(yè)，總共25頁(yè)。由判斷準(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ù)。當(dāng)前19頁(yè)，總共25頁(yè)。6.6.3對(duì)偶單純形法對(duì)偶單純形法的計(jì)算步驟；（1）將模型標(biāo)準(zhǔn)化當(dāng)前20頁(yè)，總共25頁(yè)。（2）求初始基解（判斷數(shù)均大于零的基解，可不是基可行解）當(dāng)前21頁(yè)，總共25頁(yè)。例子：當(dāng)前22頁(yè)，總共25頁(yè)。234000-3-1-2-1100-4[-2]1-30123400出基進(jìn)基當(dāng)前23頁(yè)，總共25頁(yè)。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當(dāng)前24頁(yè)，總共25頁(yè)?；仡欉\(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