優(yōu)化模型與軟件工具數(shù)學(xué)規(guī)劃軟(完整版)
【正文】 ）或減少多少（對求極小化問題）該變量才有可能從零變?yōu)榇笥诹愕臄?shù)。但有人對 Karmarkar的實(shí)驗(yàn)結(jié)果有異議； ? 單純形方法和內(nèi)點(diǎn)法孰優(yōu)孰劣的爭論還沒有結(jié)束； 36 整數(shù)規(guī)劃 37 整數(shù)規(guī)劃 ? 典型的整數(shù)規(guī)劃： ? 求解方法：窮舉法、割平面法、分支定界法、分支與割平面法 i n t e ge ral lors om ejTxuxlbAxtoS u bj e c txcM axi m i z e???38 ? 即便求解很小的整數(shù)規(guī)劃也會很困難 ， 求解時間可能以指數(shù)增長 。 0 ? y ? 10； x 和 y 的上界可以改為 5； ? 5 x + 3 y + z ? 4。B方法在商業(yè)軟件中得到廣泛應(yīng)用； 40 分支定界法 根節(jié)點(diǎn) 整數(shù)解 整數(shù)解 不可行 G A P 下界 上界 求解 LP 松弛問題 : v= (非整數(shù) ) 注意 : (1) GAP = 0 ? 證明已找到最有解 (2) 實(shí)際應(yīng)用 : 經(jīng)常希望能找到足夠好的解就可以了 41 整數(shù)規(guī)劃－ NP難題 ? 一個實(shí)用模型：只有 44個約束， 51個整數(shù)變量，167個非零元； ? 使用最好的 Brench and Cut方法，在用啟發(fā)式方法找到初始整數(shù)解 (2186)和問題的初始上界 (1379)后，繼續(xù)計(jì)算 36小時，搜索了 3200萬節(jié)點(diǎn)，搜索樹占了 ，沒有找到新的整數(shù)解，問題的界也沒有任何改善。 xN = l ? xN = u ? 非基變量的邊際貢獻(xiàn)對目標(biāo)有利 時迫使該變量取其上界 非基變量的邊際貢獻(xiàn)對目標(biāo)不利 時迫該使變量取其下界 ?B = 0 ?N ? 0 (max) ?N ? 0 (min) ?N ? 0 (min) ?N ? 0 (max) 來自 中國最大的資料庫下載 25 變量有界的遞減成本 可變單元格終 遞減 目標(biāo)式 允許的 允許的單元格 名字 值 成本 系數(shù) 增量 減量$B$20 購買數(shù)量 A 55 1$C$20 購買數(shù)量 B 600 50 1E+30$D$20 購買數(shù)量 C 0 61 1E+30 $E$20 購買數(shù)量 D 20 $F$20 購買數(shù)量 E 100 $G$20 購買數(shù)量 F 0 71 1E+30 $H$20 購買數(shù)量 G 450 1 1E+30$I$20 購買數(shù)量 H 0 80 1E+30 26 線性規(guī)劃求解軟件 27 求解線性規(guī)劃模型的努力 ? 1947年求解線性規(guī)劃的單純形方法問世 ? 求解的第一個有實(shí)用價值的線性規(guī)劃模型只有 9個約束， 77個變量，花了 120人日計(jì)算出結(jié)果 ? 第一個求解線性規(guī)劃軟件出現(xiàn)在 50年代，那時受計(jì)算機(jī)限制，只能求解 100個變量的 LP問題； ? 60年代的 IBM商用計(jì)算機(jī)上可求解上千個變量問題； ? 70年代：許多大型計(jì)算機(jī)提供數(shù)學(xué)規(guī)劃軟件，如MPS/X， FMPS等，可求解有上萬個變量和約束的問題，并有相應(yīng)的模型數(shù)據(jù)處理系統(tǒng)，如 MG，RG等。每單位原料的采購成本為 5 元，每小時人工的工資為 10 元。因此也有人稱之為最優(yōu)計(jì)劃價格。 否則計(jì)算 令變量 xk 入基，轉(zhuǎn)到 3； 3. 確定出基變量： i) 若 k?JNl，計(jì)算： ?????????NujNljJjJj 0 0??? ? ? ?? ? jJjjJjkNuNlm a xm a xm a x ??? ?? ?? ,?????????? ??????? 0 jkjkjjJjlaalbm i nB??????????? ??????? 0 jkjkjjJjuaaubm i nB?11 變量有界的單純形算法 ii) 若 k?JNu，計(jì)算： ? = min{? l, ? u, uk lk } 確定出基變量 xr ，轉(zhuǎn)到 4。1 優(yōu)化模型與軟件工具 數(shù)學(xué)規(guī)劃軟件 清華大學(xué)經(jīng)濟(jì)管理學(xué)院 管理科學(xué)與工程系 2 數(shù)學(xué)規(guī)劃軟件 ? 線性規(guī)劃方法的簡單回顧 ? 線性規(guī)劃求解軟件 ? 整數(shù)規(guī)劃 3 線性規(guī)劃方法簡單回顧 4 線性規(guī)劃 ? 線性規(guī)劃是經(jīng)濟(jì)組織中 n 種經(jīng)濟(jì)活動 競爭使用 m種資源 的資源優(yōu)化配置問題； ? 典型的線性規(guī)劃可以表示如下 ? 求解方法：單純形方法、內(nèi)點(diǎn)法 uxlbAxtoS u b j ec txcM i n i m i z eT???5 單純形方法理論發(fā)展歷史 主要研究者 時間1 原始單純形算法 D an t z i g 19472 對偶理論和對偶
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1