模型与软件3数学规划软件.ppt

《模型与软件3数学规划软件.ppt》由会员分享，可在线阅读，更多相关《模型与软件3数学规划软件.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、优化模型与软件工具数学规划软件清华大学经济管理学院清华大学经济管理学院管理科学与工程系管理科学与工程系1线性规划线性规划2求解线性规划模型的历史求解线性规划模型的历史w1947年单纯形方法问世，手工计算工作量巨大，第一年单纯形方法问世，手工计算工作量巨大，第一个有实用价值的线性规划模型只有个有实用价值的线性规划模型只有9个约束，个约束，77个变个变量，花了量，花了120人日计算出结果；人日计算出结果；w50年代：出现第一个求解线性规划软件，受计算机限年代：出现第一个求解线性规划软件，受计算机限制，只能求解制，只能求解100个变量的线性规划问题；个变量的线性规划问题；w60年代：出现商用线性规划

2、软件，在年代：出现商用线性规划软件，在IBM计算机上可计算机上可求解上千个变量问题；求解上千个变量问题；w70年代：许多大型计算机提供商用数学规划软件，如年代：许多大型计算机提供商用数学规划软件，如MPS/X，FMPS等，可求解有上万个变量和约束的问等，可求解有上万个变量和约束的问题，并有相应的模型数据处理系统，如题，并有相应的模型数据处理系统，如MG，RG等。等。3w 80年代：年代：计算机硬件、软件技术进步加快，求解模型的计算机硬件、软件技术进步加快，求解模型的规模又上升一个数量级规模又上升一个数量级内点法问世，新软件出现，如内点法问世，新软件出现，如CPLEX，OSL等；等；出现较完整的

3、模型构造求解系统：出现较完整的模型构造求解系统：GAMS，AMPL等等w 90年代：信息技术时代，运筹学与信息技术的融合年代：信息技术时代，运筹学与信息技术的融合出现了基于出现了基于WINDOWS平台的应用系统平台的应用系统IT与与OR的集成，出现集信息采集、存储、分析、优化的集成，出现集信息采集、存储、分析、优化于一体的综合决策支持系统；于一体的综合决策支持系统；可求解有上千万变量的超大型数学模型；可求解有上千万变量的超大型数学模型；典型应用：金融、航空、通讯、能源、军事等领域典型应用：金融、航空、通讯、能源、军事等领域求解线性规划模型的历史求解线性规划模型的历史4线性规划软件的进步（一）线

4、性规划软件的进步（一）w1991年年Schultz和和Pulleyblank的试验：的试验：软件：软件：MPS MPS OSL OSL OSL版本：版本：v1.6 v2.0 Prim-1 Dual-1 Dual-2年代：年代：1970 1988 1993 1993 1993迭代：迭代：302357 48858 36050 11410 4982时间：时间：550 82 24 11 4问题：问题：4422约束，约束，6711个变量，个变量，110342非零元非零元5线性规划软件的进步（二）线性规划软件的进步（二）w2003年年 Bixby的试验（的试验（CPLEX）求解的模型求解的模型 生产计划模

5、型，有生产计划模型，有401,640个约束、个约束、1,584,000个变量、个变量、9,498,000个非零元；个非零元；w求解时间求解时间(2.0 GHz P4 计算机计算机):1988(CPLEX 1.0):29.8 days 11997(CPLEX 5.0):1.5 hours 1/4802003(CPLEX 9.0):59.1 seconds 1/440006求解线性规划综合速度的提高求解线性规划综合速度的提高w1988 2003 求解求解LP的综合速度提高了多少？的综合速度提高了多少？算法（与计算机无关）算法（与计算机无关）:2360倍倍计算机（工作站计算机（工作站 PCs）800

6、倍倍算法算法 计算机计算机 190万倍万倍摩尔定律预测计算机速度每摩尔定律预测计算机速度每18个月提高一倍：从个月提高一倍：从1988至至2003共共15年应提高年应提高1024倍；倍；w求解前面的生产计划模型求解前面的生产计划模型1988年需要年需要 80 年年1997年需要年需要 24 小时小时2003年需要年需要 1 分钟分钟7线性规划软件的进步线性规划软件的进步w是什么因素使线性规划求解效率有了如此长足的进步呢，是什么因素使线性规划求解效率有了如此长足的进步呢，著名线性规划软件著名线性规划软件CPLEX的主要设计者的主要设计者Bixby总结了以总结了以下几方面的的进展：下几方面的的进展

7、：处理稀疏矩阵的数据结构处理稀疏矩阵的数据结构线性规划问题的预处理线性规划问题的预处理初始基的选择初始基的选择转轴规则的选择：最速边下降法，对偶方法；转轴规则的选择：最速边下降法，对偶方法；基的基的LU分解与乘积形式：分解稳定性，减少非零分解与乘积形式：分解稳定性，减少非零元素的增长速度，提高计算精度；元素的增长速度，提高计算精度；8单纯形方法的计算效率单纯形方法的计算效率w人们一直试图证明单纯形方法是一种多项式算法；人们一直试图证明单纯形方法是一种多项式算法；w1972年年Klee与与Minty出人意料的给出一个反例，证明出人意料的给出一个反例，证明单纯形算法不是多项式算法；单纯形算法不是多

8、项式算法；w该问题共有该问题共有2n个极点，需要个极点，需要2n-1次迭代才能找到最优次迭代才能找到最优解；解；9求解线性规划的多项式方法求解线性规划的多项式方法w单纯形方法是统计意义上的多项式方法单纯形方法是统计意义上的多项式方法1981年年Borgwardt在大量实验的基础上指出：单在大量实验的基础上指出：单纯形迭代次数的数学期望不会高于纯形迭代次数的数学期望不会高于O(n4m)w前苏联数学家前苏联数学家Xachiyan 于于1979年提出求解年提出求解“线性严线性严格不等式组格不等式组”的椭球算法。的椭球算法。与求解线性规划问题等价，证明是多项式算法与求解线性规划问题等价，证明是多项式算

9、法计算效率根本无法与单纯形方法相比计算效率根本无法与单纯形方法相比w美籍印度裔数学家美籍印度裔数学家Karmarkar 于于1984年年提出求解线提出求解线性规划的内点法；性规划的内点法；可行域内部的搜索方法，计算效率高可行域内部的搜索方法，计算效率高10单纯形方法与内点法的竞赛单纯形方法与内点法的竞赛w美国美国AT&T贝尔实验室的贝尔实验室的Monma等人等人1987年发表实年发表实验报告，他们对验报告，他们对31个实验问题的求解，所使用的内个实验问题的求解，所使用的内点算法点算法3倍高于基于单纯形算法的倍高于基于单纯形算法的MINOS；wKarmarkar 1993年发表的实验结果表明对一

10、些大规年发表的实验结果表明对一些大规模的问题内点法比单纯形方法快模的问题内点法比单纯形方法快80-100倍。但有人倍。但有人对对Karmarkar的实验结果有异议；的实验结果有异议；w单纯形方法和内点法孰优孰劣的争论还没有结束；单纯形方法和内点法孰优孰劣的争论还没有结束；11整数规划整数规划12整数规划整数规划w典型的整数规划：典型的整数规划：w求解方法：穷举法、割平面法、分支定界求解方法：穷举法、割平面法、分支定界法、分支与割平面法法、分支与割平面法13w即即便便求求解解很很小小的的整整数数规规划划也也会会很很困困难难，求求解解时时间间可可能能以以指指数数增增长长。如如果果用用穷穷举举法法求

11、求解解，需需要要的的时时间间如如下：下：n 解的数量解的数量求解时间求解时间101.02 103 1.02 10-3 秒秒201.05 106 1.05 秒秒301.07 109 18 分钟分钟401.10 1012 13 天天501.73 1015 36 年年 1001.27 1030 4 亿亿亿亿 年年整数规划求解难度整数规划求解难度 14整数规划求解史：整数规划求解史：19501998w割平面方法割平面方法（Cutting Plane）:1954 Dantzig,Fulkerson,Johnson:使用割平面方使用割平面方法求解有法求解有42个城市的旅行推销商问题（个城市的旅行推销商问题

12、（TSP）；）；1957年年Gomory完成了割平面方法的理论研究；完成了割平面方法的理论研究；w分支定界法分支定界法（Branch-and-Bound）：）：1960 Land,Doig;1965 Dakin;w商业软件商业软件：MPSX/370：1971年由年由Benichou等开发；等开发；UMPIRE：1972年年Forrest,Hirst,Tomlin等开发；等开发；1972 1998：各种先进的：各种先进的B&B方法在商业软件中方法在商业软件中得到广泛应用；得到广泛应用；15分支定界法分支定界法根节点根节点v 3v 4 整数解整数解x 2x 3 y 0y 1 z 0z 1 整数解整

13、数解不可行不可行z 0z 1 GAP下界下界上界上界求解求解 LP LP 松弛问题松弛问题:v=3.5(v=3.5(非整数非整数)注意注意:(1)GAP=0 (1)GAP=0 证明已找到最有解证明已找到最有解 (2)(2)实际应用实际应用:经常希望能找到足够好的解就可以了经常希望能找到足够好的解就可以了16整数规划整数规划NP难题难题w一个实用模型：只有一个实用模型：只有44个约束，个约束，51个整数变量，个整数变量，167个非零元；个非零元；w使用最好的使用最好的Branch and Cut方法，在用启发式方法方法，在用启发式方法找到初始整数解找到初始整数解(-2186)和问题的初始上界和问

14、题的初始上界(-1379)后，后，继续计算继续计算36小时，搜索了小时，搜索了3200万节点，搜索树占了万节点，搜索树占了5.5G内存，没有找到新的整数解，问题的界也没有内存，没有找到新的整数解，问题的界也没有任何改善。任何改善。w问题出在哪里？糟糕的模型构造方法；问题出在哪里？糟糕的模型构造方法；17线性规划求解速度也可能是瓶颈线性规划求解速度也可能是瓶颈wSGM:Schedule Generation Model，157,323约束，约束，182,812变量，变量，6,348,437非零元；非零元；w求解线性规划松弛问题用了求解线性规划松弛问题用了18个小时个小时w使用使用Branch a

15、nd Cut方法方法:搜索了搜索了368个节点，找到了很好的解；个节点，找到了很好的解；所用时间：所用时间：14天天w整数规划问题并不困难，线性规划的求解速度是求整数规划问题并不困难，线性规划的求解速度是求解的障碍；解的障碍；如果线性规划求解速度可以再提高如果线性规划求解速度可以再提高1000倍，情况会如倍，情况会如何？何？18整数规划求解方法进展整数规划求解方法进展w线性规划的进展：更稳定、快捷的对偶算法线性规划的进展：更稳定、快捷的对偶算法w变量节点选择：受旅行推销商问题的影响变量节点选择：受旅行推销商问题的影响w启发式算法：启发式算法：8 种不同的方法；种不同的方法；w节点的预评估：借鉴

16、约束规划的思想节点的预评估：借鉴约束规划的思想w对问题进行预处理：如约束的改写对问题进行预处理：如约束的改写 xj (uj)y,y=0/1 xj ujy (for all j)w割平面方法（割平面方法（Cutting planes）19预处理预处理w缩减问题的尺寸：缩减问题的尺寸：x+y 3，x 1，y 1x+y 3可以删去可以删去w缩紧约束（缩紧约束（Tighten formulation）x+y 5;0 x 10;0 y 10；x 和和 y 的上界可以改为的上界可以改为 5；5 x+3 y+z 4;x,y,z 为为0-1变量，变量，将约束改为：将约束改为：4 x+3 y+z 420节点选择

17、方法节点选择方法w在解的可行性和最优性间权衡在解的可行性和最优性间权衡深度优先：更易找到整数可行解深度优先：更易找到整数可行解广度优先：搜索树会很大；广度优先：搜索树会很大；最好优先：追踪最好的解；最好优先：追踪最好的解；节点预估法：预估在该节点下发节点预估法：预估在该节点下发现最好的整数解的值；现最好的整数解的值；=integer feasible21割平面法割平面法yx可行域可行域割平面割平面更好的割平面更好的割平面(整整数解多面体的表面数解多面体的表面)22整数规划求解方法进展整数规划求解方法进展wCPLEX公司选择了公司选择了108个整数规划模型，分别用个整数规划模型，分别用5.0和和

18、8.0版本求解，试图评估最有效的改进技术：版本求解，试图评估最有效的改进技术：w5.0版本无法求解全部问题，版本无法求解全部问题，8.0 版本少于版本少于1000秒求解全秒求解全部问题；部问题；Cuts53.7xPresolve10.8xCPLEX 5.0 presolve 3.1xCPLEX 5.0 var.selection 2.9xHeuristics 1.4xNode presolve 1.3x23一个求解实例一个求解实例w求解有求解有7万个约束，万个约束，23万个整数变量的超大型整数万个整数变量的超大型整数规划规划w使用使用CPLEX6.0版本版本 没有任何希望；没有任何希望；w使用

19、使用CPLEX9.0版本：版本：只用了只用了76秒钟，在根节点发现最优解；秒钟，在根节点发现最优解；割平面法使松弛问题变得更紧；割平面法使松弛问题变得更紧；使用启发式方法找到最优解；使用启发式方法找到最优解；24其它方法带来的改善其它方法带来的改善25求解技术改进带来的好处求解技术改进带来的好处w建立更大，更精确的模型：一些供应链优化模型有建立更大，更精确的模型：一些供应链优化模型有1000万约束，万约束，2000万变量，求解只需要万变量，求解只需要1.5小时；小时；w建立全局（建立全局（global）优化模型，以前可能需要分开求）优化模型，以前可能需要分开求解，如航空公司的模型；解，如航空公

20、司的模型；w建立长期（建立长期（long-term）优化模型，如制造业模型，）优化模型，如制造业模型，更准确反映实际需要；更准确反映实际需要；26运筹模型技术的应用前景运筹模型技术的应用前景w运筹优化模型技术在以下方面的进展运筹优化模型技术在以下方面的进展算法和软件技术算法和软件技术计算机硬件技术计算机硬件技术信息技术保证了数据的可获得性信息技术保证了数据的可获得性模型的表达与实现技术模型的表达与实现技术w优化技术已经为现实应用展现了广阔的前景优化技术已经为现实应用展现了广阔的前景 What is possible today could only have been dreamed of even 10 years ago。27