優(yōu)化模型與軟件工具數(shù)學(xué)規(guī)劃軟-資料下載頁(yè)
2025-05-22 22:14本頁(yè)面
【導(dǎo)讀】線性規(guī)劃方法的簡(jiǎn)單回顧。線性規(guī)劃是經(jīng)濟(jì)組織中n種經(jīng)濟(jì)活動(dòng)競(jìng)爭(zhēng)。使用m種資源的資源優(yōu)化配置問(wèn)題；典型的線性規(guī)劃可以表示如下。x=是一個(gè)基本可行解。cN-cBB-1N被稱為檢驗(yàn)向量。j=cj-cBB-1pj，被稱為檢驗(yàn)數(shù)或遞減成。非基變量有在下界和上界兩種狀態(tài)，量在下界的矩陣，Nu對(duì)應(yīng)非基變量在上界部分。令JNl表示在下界的非基變量的下標(biāo)集合，JNu. 變量有上下界的典則方程可以寫為：。-若滿足已找到最優(yōu)解，停止計(jì)算。令變量xk入基，轉(zhuǎn)到3；確定出基變量xr，轉(zhuǎn)到4。其置于下界，并計(jì)算基變量的相應(yīng)變化。影子價(jià)格是對(duì)偶解十分形象的名稱，它既表明對(duì)。因此也有人稱之為最優(yōu)計(jì)劃價(jià)格。系統(tǒng)內(nèi)資源數(shù)量和價(jià)格的變化都會(huì)引起影子價(jià)。格的變化，因此它是一種動(dòng)態(tài)價(jià)格體系。資源的供應(yīng)不會(huì)給系統(tǒng)目標(biāo)帶來(lái)任何改善。元，B產(chǎn)品售價(jià)40元。產(chǎn)的原料為25個(gè)單位和15小時(shí)人工。
【正文】 S. Johnson: 使用割平面方法求解有 42個(gè)城市的旅行推銷商問(wèn)題（ TSP）； ? 割平面方法 : 1957年 Gomory完成了割平面方法的理論研究； ? 分支定界法（ Branchandbound） ： 1960 Land, Doig。 1965 Dakin。 ? MPSX/370： 1971年由 Benichou等人開(kāi)發(fā)； ? UMPIRE： 1972年 Forrest, Hirst, Tomlin等； ? 1972 – 1998：各種先進(jìn)的 Bamp。B方法在商業(yè)軟件中得到廣泛應(yīng)用； 40 分支定界法 根節(jié)點(diǎn) 整數(shù)解 整數(shù)解 不可行 G A P 下界 上界 求解 LP 松弛問(wèn)題 : v= (非整數(shù) ) 注意 : (1) GAP = 0 ? 證明已找到最有解 (2) 實(shí)際應(yīng)用 : 經(jīng)常希望能找到足夠好的解就可以了 41 整數(shù)規(guī)劃－ NP難題 ? 一個(gè)實(shí)用模型：只有 44個(gè)約束， 51個(gè)整數(shù)變量，167個(gè)非零元； ? 使用最好的 Brench and Cut方法，在用啟發(fā)式方法找到初始整數(shù)解 (2186)和問(wèn)題的初始上界 (1379)后，繼續(xù)計(jì)算 36小時(shí)，搜索了 3200萬(wàn)節(jié)點(diǎn)，搜索樹(shù)占了 ，沒(méi)有找到新的整數(shù)解，問(wèn)題的界也沒(méi)有任何改善。 ? 問(wèn)題出在哪里？糟糕的模型構(gòu)造方法 。 42 線性規(guī)劃求解速度也可能是瓶頸 ? SGM: Schedule Generation Model， 157,323約束， 182,812變量， 6,348,437非零元； ? 求解線性規(guī)劃松弛問(wèn)題用了 18個(gè)小時(shí) ? 使用 Branchandcut方法 : ? 搜索了 368個(gè)節(jié)點(diǎn)，找到了很好的解； ? 所用時(shí)間： 14天 ? 整數(shù)規(guī)劃問(wèn)題似乎并不困難，但 線性規(guī)劃的求解速度是求解的障礙 ； ? 如果線性規(guī)劃求解速度可以提高 1000倍，情況會(huì)如何？ 43 整數(shù)規(guī)劃求解方法進(jìn)展 ? 線性規(guī)劃的進(jìn)展：更穩(wěn)定、快捷的對(duì)偶算法 ? 變量節(jié)點(diǎn)選擇：受旅行推銷商問(wèn)題的影響 ? 啟發(fā)式算法： 8 種不同的方法； ? 節(jié)點(diǎn)的預(yù)評(píng)估：借鑒約束規(guī)劃的思想 ? 對(duì)問(wèn)題進(jìn)行預(yù)處理：如約束的改寫 ? xj ? (? uj) y, y = 0/1 ? xj ? ujy (for all j) ? 割平面方法（ Cutting planes） 44 預(yù)處理 ? 縮減問(wèn)題的尺寸： ? x + y ? 3， x ? 1， y ? 1 x + y ? 3可以刪去 ? 縮緊約束（ Tighten formulation） ? x + y ? 5。 0 ? x ? 10。 0 ? y ? 10； x 和 y 的上界可以改為 5； ? 5 x + 3 y + z ? 4。 x, y, z 為 01變量， 將約束改為： 4 x + 3 y + z ? 4 45 節(jié)點(diǎn)選擇方法 ? 在解的可行性和最優(yōu)性間權(quán)衡 ? 深度優(yōu)先：更易找到整數(shù)可行解； ? 廣度優(yōu)先：搜索樹(shù)會(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秒求解全部問(wèn)題； ? Cuts ? Presolve ? CPLEX presolve ? CPLEX var. selection ? Heuristics ? Node presolve 48 一個(gè)求解實(shí)例 ? 求解有 7萬(wàn)個(gè)約束， 23萬(wàn)個(gè)整數(shù)變量的超大型整數(shù)規(guī)劃 ? 使用 － 沒(méi)有任何希望； ? 使用 ： ? 只用了 76秒鐘，在根節(jié)點(diǎn)發(fā)現(xiàn)最優(yōu)解； ? 割平面法使松弛問(wèn)題變得更緊； ? 使用啟發(fā)式方法找到最優(yōu)解； 49 求解技術(shù)改進(jìn)帶來(lái)的好處 ? 建立更大，更精確的模型：一些供應(yīng)鏈優(yōu)化模型有 1000萬(wàn)約束， 20xx萬(wàn)變量，求解只需要 小時(shí)； ? 建立全局（ global）優(yōu)化模型，以前可能需要分開(kāi)求解，如航空公司的模型； ? 建立長(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。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1