《運(yùn)籌學(xué)對(duì)偶問(wèn)題》ppt課件-全文預(yù)覽
【正文】 ??????原問(wèn)題 對(duì)偶問(wèn)題 結(jié)論或繼續(xù)計(jì)算步驟 可行解 可行解 問(wèn)題的最優(yōu)解或最優(yōu)基不變 可行解 非可行解 用單純形法繼續(xù)迭代求最優(yōu)解 非可行解 可行解 用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解 非可行解 非可行解 引進(jìn)人工變量，編制新的單純形表重新計(jì)算 價(jià)值系數(shù) 變化的靈敏度分析 例：在第一章美佳公司的例 1中 （ 1）若產(chǎn)品 I的利潤(rùn)降至 /件，而產(chǎn)品 II的利潤(rùn)增至 2元 /件，美佳公司的最優(yōu)生產(chǎn)計(jì)劃有何改變； （ 2）若產(chǎn)品 I的利潤(rùn)不變，則產(chǎn)品 II的利潤(rùn)在什么范圍變化時(shí)，該公司的最優(yōu)生產(chǎn)計(jì)劃不發(fā)生變化 2 1 0 0 0Cb Xb b x1 x2 x3 x4 x50 x3 7 1/2 0 0 1 2 1/2 7 1/22 x1 3 1/2 1 0 0 1/4 1/21 x2 1 1/2 0 1 0 1/4 1 1/20 0 0 1/4 1/2原最終單純形表 2 0 0 0Cb Xb b x1 x2 x3 x4 x50 x3 7 1/2 0 0 1 1 1/4 7 1/2 6 x1 3 1/2 1 0 0 1/4 1/2 142 x2 1 1/2 0 1 0 1/4 1 1/20 0 0 1/8 2 1/4（ 1）改變后 0 x4 6 0 0 4/5 1 6 x1 2 1 0 1/5 0 12 x2 3 0 1 1/5 0 00 0 1/10 0 1 1/2新的最優(yōu)解為： 0,6,0,3,2 54321 ????? xxxxx最優(yōu)目標(biāo)函數(shù)值為： 9* ?z2 a 0 0 0Cb Xb b x1 x2 x3 x4 x50 x3 7 1/2 0 0 1 2 1/2 7 1/22 x1 3 1/2 1 0 0 1/4 1/2a x2 1 1/2 0 1 0 1/4 1 1/20 0 0 0 .2 5 a 0 .5 1 1 .5 a（ 2）改變后 為使表中的解仍為最優(yōu)解必須 0231,02141 ???? aa因此產(chǎn)品 II的利潤(rùn)變化范圍為 232 ?? a資源常數(shù) 變化的靈敏度分析 例：在第一章美佳公司的例 1中 （ 1）若設(shè)備 A與調(diào)試工序的每天能力不變，而設(shè)備 B每天的能力增加到 32小時(shí)，分析公司最優(yōu)計(jì)劃的變化； （ 2）若設(shè)備 A和 B每天可用能力不變，則調(diào)試工序能力在什么范圍變化時(shí)，問(wèn)題的最優(yōu)基不變 （ 1） b由 (15， 24， 5)T 變?yōu)?(15， 32， 5)T 后，相應(yīng)地最終表中 b列的數(shù)據(jù)變?yōu)? ????????????????????????????????????? ?2/12/112/35532152/34/102/14/102/154/5139。 2． 4對(duì)偶問(wèn)題為 ???????????????????0,06353322232m a x212121212121yyyyyyyyyyyyw由 圖解法 可得對(duì)偶問(wèn)題最優(yōu)解為 .519*。 但對(duì)偶問(wèn)題 第一個(gè)約束條件與非負(fù)約束條件沖突，實(shí)際上，當(dāng) 時(shí)，第一個(gè)約束條件左端非正，因此不可能不小于正數(shù) 1。 。故對(duì)偶問(wèn)題無(wú)可行解。再由于原問(wèn)題最優(yōu)目標(biāo)函數(shù)值等于對(duì)偶問(wèn)題最優(yōu)目標(biāo)函數(shù)值。1故要使最優(yōu)基不變必須 ]6,4[412602360216021545???????????????????????????xxxxxxx利用 Excle求解 LP問(wèn)題，以 (2)為例 變量，已經(jīng)賦了初值 目標(biāo)函數(shù)值 約束條件右端值 其他專業(yè)軟件： Lindo與 Lingo， WinQSB 例如 Lingo，啟動(dòng) Lingo后，按圖中的方式輸入模型，然后點(diǎn)擊求解的圖標(biāo) 。具體計(jì)算公式可以使用 ? 檢查原問(wèn)題是否仍為可行解 ? 檢查對(duì)偶問(wèn)題是否仍為可行解 ? 對(duì)檢查情況按下表進(jìn)行處理 jBjj
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1