運(yùn)籌學(xué)建模ppt課件-資料下載頁
2025-05-03 18:35本頁面
【正文】 變化。或者，當(dāng)運(yùn)用線性規(guī)劃編制完生產(chǎn)計(jì)劃并即將付諸應(yīng)用時(shí)，又發(fā)生了新的情況，某些原來未加限制的資源現(xiàn)在有了限制，從而出現(xiàn)一個(gè)新的追加約束條件?；蛘?，企業(yè)準(zhǔn)備增加新產(chǎn)品，使工廠的生產(chǎn)計(jì)劃發(fā)生整個(gè)變化。 靈敏度分析 ? 從而，我們面臨這樣的問題：上述種種情況的發(fā)生，將對已求得的最優(yōu)解產(chǎn)生什么影響 ?或者說，我們?nèi)绾卧谠械淖顑?yōu)單純形表的基礎(chǔ)上用最少的計(jì)算量，去獲得修改后的線性規(guī)劃問題的最優(yōu)解 ?這就是我們要討論的 靈敏度分析（ Sensitivity Analysis） 問題。 靈敏度分析 ? 一般分下面 5個(gè)問題來進(jìn)行靈敏度分析： ? 1．變量 xj的目標(biāo)函數(shù)系數(shù) cj在何范圍內(nèi)變動(dòng)，問題(LP)的最優(yōu)基 (最優(yōu)解 )不變 ?如果超出這個(gè)范圍，如何求最優(yōu)解 ? ? 2．第 s種資源 bs在何范圍內(nèi)變動(dòng)，最優(yōu)基不變 ?如果 bs超出這個(gè)范圍，如何求最優(yōu)解 ? ? 3．變量 xj在矩陣 A中的系數(shù)列向量發(fā)生變化，如何求新問題的最優(yōu)解 ? ? 4．追加新的約束條件，如何求新的線性規(guī)劃的最優(yōu)解 ? ? 5．增加新的變量 xj，如何求新問題的最優(yōu)解 ? 特殊規(guī)劃－運(yùn)輸問題 一般模型： m個(gè)物資產(chǎn)地 （ 發(fā)點(diǎn) ） A1, A2,… , Am，n個(gè)物資銷地 （ 收點(diǎn) ） B1, B2, … , Bn， ai為 發(fā)點(diǎn) Ai的物資供應(yīng)量 （ 發(fā)量 ） ， bj為收點(diǎn) Bj對物資的需求量 （ 收量 ） ， cij表示把物資從 Ai運(yùn)到 Bj的單位運(yùn)價(jià) ， xij表示把物資從 Ai運(yùn)到 Bj的運(yùn)輸量 ， 問應(yīng)如何運(yùn)輸才能使運(yùn)費(fèi)最小 ？（ 假定收發(fā)平衡 ） 特殊規(guī)劃－運(yùn)輸問題 Ai Bj B1 … Bj … Bn ai A1 c11 … c1j … c1n a1 … … … … … Ai ci1 … cij … cin ai … … … … … Am cm1 … cmj … cmn am bj b1 … bj … bn 運(yùn)輸收發(fā)平衡單位運(yùn)價(jià)表（簡稱運(yùn)輸表格） 特殊規(guī)劃－運(yùn)輸問題 稱之為 運(yùn)輸問題的標(biāo)準(zhǔn)模型 ， 此為 產(chǎn)銷平衡模型 ， 產(chǎn)銷不平衡時(shí) ， 增加虛擬的收點(diǎn)和發(fā)點(diǎn) （ 松弛變量 ） 即可達(dá)到產(chǎn)銷平衡 。 1111m i n..0mnij ijijnij ijmij jiijf c xxas t x bx??????????????? ????????特殊規(guī)劃－運(yùn)輸問題 ? 求解方法：線性規(guī)劃的解法也適用運(yùn)輸問題，但是針對運(yùn)輸問題的特殊性有其特殊解法 —— 表上作業(yè)法（詳見有關(guān)書籍）。 ? 一些名詞：閉回路，孤立點(diǎn)，尋找初始基本可行解方法（西北角法，最小元素法），計(jì)算檢驗(yàn)數(shù)方法（位勢法） 一般模型有：平衡運(yùn)輸問題，不平衡運(yùn)輸問題，有界發(fā)量運(yùn)輸問題，運(yùn)量有界的運(yùn)輸問題，轉(zhuǎn)運(yùn)問題，多品種物資運(yùn)輸問題，空車調(diào)度問題 特殊規(guī)劃－整數(shù)規(guī)劃 ? 決策變量為整數(shù)時(shí)的線性規(guī)劃稱為整數(shù)規(guī)劃 ，如： 1212121214 9 51. . 6 3 1,0Mi n f x xxxs t x xxx? ? ?????? ? ??? ?? 整數(shù)? 去掉整數(shù)要求后的最優(yōu)解為（ , ）是否通過作舍入處理，就可得到最優(yōu)解？ 特殊規(guī)劃－整數(shù)規(guī)劃 ? 我們發(fā)現(xiàn)（ 2, 3） ,（ 1, 3） ,（ 2, 4） ,（ 1, 4）都不是，其實(shí)（ 2, 2）或（ 3, 1）才是。另一方面，這種舍入的計(jì)算量也是相當(dāng)大的（多大？） ? 由此可見，整數(shù)規(guī)劃有其自己獨(dú)到的一些解法！割平面法，柯莫力割，柯莫力割平面法 ,分支定界法（隱式枚舉法） ? 整數(shù)規(guī)劃含純整數(shù)規(guī)劃（ AIP）、混合整數(shù)規(guī)劃（ MIP）和 0－ 1規(guī)劃（ BIP）
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1