優(yōu)化模型與軟件工具數(shù)學(xué)規(guī)劃軟(參考版)
2025-05-27 22:14本頁面
【正文】 x, y, z 為 01變量， 將約束改為： 4 x + 3 y + z ? 4 45 節(jié)點(diǎn)選擇方法 ? 在解的可行性和最優(yōu)性間權(quán)衡 ? 深度優(yōu)先：更易找到整數(shù)可行解； ? 廣度優(yōu)先：搜索樹會(huì)很大； ? 最好優(yōu)先：追蹤最好的解； ? 節(jié)點(diǎn)預(yù)估法：預(yù)估在該節(jié)點(diǎn)下發(fā)現(xiàn)最好的整數(shù)解的值； …… = integer feasible 46 割平面法 y x 可行域 割平面 更好的割平面 (整數(shù)解多面體的表面 ) 47 整數(shù)規(guī)劃求解方法進(jìn)展 ? CPLEX公司選擇了 108個(gè)整數(shù)規(guī)劃模型，分別用 和 ，試圖評(píng)估最有效的改進(jìn)技術(shù)： ? , 1000秒求解全部問題； ? Cuts ? Presolve ? CPLEX presolve ? CPLEX var. selection ? Heuristics ? Node presolve 48 一個(gè)求解實(shí)例 ? 求解有 7萬個(gè)約束， 23萬個(gè)整數(shù)變量的超大型整數(shù)規(guī)劃 ? 使用 － 沒有任何希望； ? 使用 ： ? 只用了 76秒鐘，在根節(jié)點(diǎn)發(fā)現(xiàn)最優(yōu)解； ? 割平面法使松弛問題變得更緊； ? 使用啟發(fā)式方法找到最優(yōu)解； 49 求解技術(shù)改進(jìn)帶來的好處 ? 建立更大，更精確的模型：一些供應(yīng)鏈優(yōu)化模型有 1000萬約束， 20xx萬變量，求解只需要 小時(shí)； ? 建立全局（ global）優(yōu)化模型，以前可能需要分開求解，如航空公司的模型； ? 建立長期（ longterm ）優(yōu)化模型，如制造業(yè)模型，更準(zhǔn)確反映實(shí)際需要； 50 運(yùn)籌模型技術(shù)的應(yīng)用前景 ? 運(yùn)籌優(yōu)化模型技術(shù)在以下方面的進(jìn)展 ? 算法和軟件技術(shù) ? 計(jì)算機(jī)硬件技術(shù) ? 信息技術(shù)保證了數(shù)據(jù)的可獲得性 ? 模型的表達(dá)與實(shí)現(xiàn)技術(shù) ? 優(yōu)化技術(shù)已經(jīng)為現(xiàn)實(shí)應(yīng)用展現(xiàn)了廣闊的前景 － What is possible today could only have been dreamed of even 10 years ago。 0 ? x ? 10。 ? 問題出在哪里？糟糕的模型構(gòu)造方法 。 ? MPSX/370： 1971年由 Benichou等人開發(fā)； ? UMPIRE： 1972年 Forrest, Hirst, Tomlin等； ? 1972 – 1998：各種先進(jìn)的 Bamp。 如果用窮舉法求解 ， 需要的時(shí)間如下： n 解的數(shù)量 求解時(shí)間 10 ?103 ?103 秒 20 ?106 秒 30 ?109 18 分鐘 40 ?1012 13 天 50 ?1015 36 年 100 ?1030 4 億億 年 整數(shù)規(guī)劃求解難度 39 整數(shù)規(guī)劃求解史： 1950－ 1998 ? 1954 Dantzig, Fulkerson, S. Johnson: 使用割平面方法求解有 42個(gè)城市的旅行推銷商問題（ TSP）； ? 割平面方法 : 1957年 Gomory完成了割平面方法的理論研究； ? 分支定界法（ Branchandbound） ： 1960 Land, Doig。T貝爾實(shí)驗(yàn)室的 Monma等人 1987年發(fā)表實(shí)驗(yàn)報(bào)告，他們對(duì) 31個(gè)實(shí)驗(yàn)問題的求解，所使用的內(nèi)點(diǎn)算法 3倍高于基于單純形算法的MINOS； ? Karmarkar1993年發(fā)表的實(shí)驗(yàn)結(jié)果表明對(duì)一些大規(guī)模的問題內(nèi)點(diǎn)法比單純形方法快 80100倍。 28 ? 80年代： ? 計(jì)算機(jī)硬件、軟件技術(shù)進(jìn)步加快，求解模型的規(guī)模又上升一個(gè)數(shù)量級(jí) ? 內(nèi)點(diǎn)法問世，新軟件出現(xiàn)，如 CPLEX， OSL等； ? 出現(xiàn)較完整的模型求解系統(tǒng)： GAMS， AMPL等。 ? ?j 還可表示為： ?j = cj cBB1pj = cj ypj y 是影子價(jià)格， pj 是消耗系數(shù)，則 ypj 為按影子價(jià)格計(jì)算的影子成本；檢驗(yàn)數(shù)是價(jià)格 cj 和影子成本 ypj的差值； ? 變量非負(fù)約束的影子價(jià)格 = 變量的遞減成本； 23 檢驗(yàn)數(shù)（遞減成本）的特點(diǎn) ? 檢驗(yàn)數(shù)與每一個(gè)變量相對(duì)應(yīng) ? 基變量的檢驗(yàn)數(shù)一定為零（為什么）； ? 非基變量的檢驗(yàn)數(shù)才可能取非零值； ? 變量有上、下界約束的檢驗(yàn)數(shù)符號(hào)： 問題類型 變量在下界 變量在上界 max ? ? 0 ? ? 0 min ? ? 0 ? ? 0 24 變量有界問題的遞減成本 ? 變量有界的 LP問題： max {cx | Ax ? b, l ? x ? u} 下界 = l 上界 = u 變量取值 xB ? 基變量可以在上下界之間自由活動(dòng)，最
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1