優(yōu)化模型與軟件工具數(shù)學(xué)規(guī)劃軟-文庫(kù)吧在線文庫(kù)
【正文】 x ? ? 0 ? ? 0 min ? ? 0 ? ? 0 24 變量有界問題的遞減成本 ? 變量有界的 LP問題： max {cx | Ax ? b, l ? x ? u} 下界 = l 上界 = u 變量取值 xB ? 基變量可以在上下界之間自由活動(dòng)，最優(yōu)時(shí)對(duì)目標(biāo)函數(shù)的邊際貢獻(xiàn)應(yīng)為零。 ? MPSX/370： 1971年由 Benichou等人開發(fā)； ? UMPIRE： 1972年 Forrest, Hirst, Tomlin等； ? 1972 – 1998：各種先進(jìn)的 Bamp。 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)化模型，以前可能需要分開求解，如航空公司的模型； ? 建立長(zhǎng)期（ 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。 如果用窮舉法求解 ， 需要的時(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。 22 檢驗(yàn)數(shù)（遞減成本）的特點(diǎn) ? 變量的檢驗(yàn)數(shù) ? = cN cBB1N 與約束的影子價(jià)格相似，是系統(tǒng)達(dá)到最優(yōu)時(shí)的邊際值。 A 產(chǎn)品需消耗 2個(gè)單位的原料和 1 小時(shí)人工； B 產(chǎn)品需消耗 3 個(gè)單位的原料和 2 小時(shí)人工。 ?影子價(jià)格是對(duì)偶解十分形象的名稱，它既表明對(duì)偶解是對(duì)資源的一種客觀估價(jià)，又表明它是虛擬而不是真實(shí)的價(jià)格。 ? 令 JNl表示在下界的非基變量的下標(biāo)集合， JNu表示在上界的非基變量的下標(biāo)集合。 8 變量有上下界的單純形方法 考慮下述線性規(guī)劃問題： max: z = cx . Ax = b l ? x ? u ? 非基變量有在下界和上界兩種狀態(tài)， ? A矩陣可分為： A = (B, Nl, Nu)， Nl對(duì)應(yīng)非基變量在下界的矩陣， Nu對(duì)應(yīng)非基變量在上界部分。 ?目標(biāo)函數(shù)值通常用價(jià)值量衡量，對(duì)偶解也具有價(jià)值內(nèi)涵，被稱為影子價(jià)格。 影子價(jià)格的特點(diǎn) 17 某企業(yè)生產(chǎn) A , B 兩種產(chǎn)品。 ? 檢驗(yàn)數(shù)在很多計(jì)算機(jī)軟件中被稱為 遞減成本(reduced cost)，其含義為該變量所對(duì)應(yīng)的目標(biāo)函數(shù)系數(shù)應(yīng)該增加多少（對(duì)求極大化問題
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1