優(yōu)化模型與軟件工具數(shù)學(xué)規(guī)劃軟-預(yù)覽頁
【正文】 可求解有上千萬變量的超大型數(shù)學(xué)模型； ? 出現(xiàn)了基于 WINDOWS平臺的應(yīng)用系統(tǒng) ? IT與 OR的集成，出現(xiàn)集信息采集、存儲、分析、優(yōu)化于一體的綜合決策支持系統(tǒng)； 求解線性規(guī)劃模型的努力 29 線性規(guī)劃軟件的進步（一） ? 1991年 Schultz和 Pulleyblank的試驗： 軟件： MPS MPS OSL OSL OSL 版本： Prim1 Dual1 Dual2 年代： 1970 1988 1993 1993 1993 迭代： 302357 48858 36050 11410 4982 時間： 550 82 24 11 4 問題： 4422約束， 6711個變量， 110342非零元 30 線性規(guī)劃軟件的進步（二） ? 20xx年 Bixby的試驗（ CPLEX） ? 求解的模型 － 生產(chǎn)計劃模型，有 401, 640個約束、 1, 584, 000個變量、 9, 498, 000個非零元； ? 求解時間 ( GHz P4 計算機 ): ? 1988 (CPLEX ): days 1x ? 1997 (CPLEX ): hours 480x ? 20xx (CPLEX ): seconds 44000x 31 線性規(guī)劃軟件的進步 ? 1988 ? 20xx 求解 LP的綜合速度提高了多少？ ? 算法（與計算機無關(guān)） : 2360x ? 計算機（工作站 ? PCs） 800x ? 算法 計算機 1900000x ? 摩爾定律預(yù)測計算機速度每 18個月提高一倍：從 1988至 20xx共 15年應(yīng)提高 1024倍； ? 在當(dāng)時條件下求解前面的問題 ? 1988年需要 80 年 ? 1997年需要 24 小時 ? 20xx年需要 1 分鐘 32 線性規(guī)劃軟件的進步 ? 是什么因素使線性規(guī)劃求解效率有了如此長足的進步呢，著名線性規(guī)劃軟件 CPLEX的主要設(shè)計者 Bixby總結(jié)了以下幾方面的的進展： ? 處理稀疏矩陣的數(shù)據(jù)結(jié)構(gòu) ? 線性規(guī)劃問題的預(yù)處理 ? 初始基的選擇 ? 轉(zhuǎn)軸規(guī)則的選擇：最速邊下降法，對偶方法； ? 基的 LU分解與乘積形式：分解穩(wěn)定性，減少非零元素的增長速度，提高計算精度； 33 單純形方法的計算效率 ? 人們一直試圖證明單純形方法是一種多項式算法； ? 1972年 Klee與 Minty出人意料的給出一個反例，證明單純形算法不是多項式算法； ? 該問題共有 2n個極點，需要 2n1次迭代才能找到最優(yōu)解； 0 1 10102 10221???????????jjjij)ij(jnjj)jn(xn,...x:m ax34 單純形方法的計算效率 ? 人們又試圖從統(tǒng)計意義上研究單純形算法的復(fù)雜性， 1981年 Bwardt在大量實驗的基礎(chǔ)上指出：單純形迭代次數(shù)的數(shù)學(xué)期望不會高于O(n4m) ? 1979年 Xachiyan提出求解線性規(guī)劃的橢球法（多項式算法）； ? 1984年 Karmarkar提出求解線性規(guī)劃的內(nèi)點法； 35 單純形方法與內(nèi)點法的競賽 ? 美國 ATamp。 1965 Dakin。 42 線性規(guī)劃求解速度也可能是瓶頸 ? SGM: Schedule Generation Model， 157,323約束， 182,812變量， 6,348,437非零元； ? 求解線性規(guī)劃松弛問題用了 18個小時 ? 使用 Branchandcut方法 : ? 搜索了 368個節(jié)點，找到了很好的解； ? 所用時間： 14天 ? 整數(shù)規(guī)劃問題似乎并不困難，但 線性規(guī)劃的求解速度是求解的障礙 ； ? 如果線性規(guī)劃求解速度可以提高 1000倍，情況會如何？ 43 整數(shù)規(guī)劃求解方法進展 ? 線性規(guī)劃的進展：更穩(wěn)定、快捷的對偶算法 ? 變量節(jié)點選擇：受旅行推銷商問題的影響 ? 啟發(fā)式算法： 8 種不同的方法； ? 節(jié)點的預(yù)評估：借鑒約束規(guī)劃的思想 ? 對問題進行預(yù)處理：如約束的改寫 ? xj ? (? uj) y, y = 0/1 ? xj ? ujy (for all j) ? 割平面方法（ Cutting planes） 44 預(yù)處理 ? 縮減問題的尺寸： ? x + y ? 3， x ? 1， y ? 1 x + y ? 3可以刪去 ? 縮緊約束（ Tighten formulation） ? x + y ? 5。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1