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

1、1线性规划线性规划2求解线性规划模型的历史求解线性规划模型的历史w 1947年单纯形方法问世，手工计算工作量巨大，年单纯形方法问世，手工计算工作量巨大，第第一个有实用价值的线性规划模型只有一个有实用价值的线性规划模型只有9个约束，个约束，77个个变量，花了变量，花了120人日计算出结果；人日计算出结果；w 50年代：出现第一个求解线性规划软件，受计算机年代：出现第一个求解线性规划软件，受计算机限制，只能求解限制，只能求解100个变量的线性规划问题；个变量的线性规划问题；w 60年代：出现商用线性规划软件，在年代：出现商用线性规划软件，在IBM计算机上可计算机上可求解上千个变量问题；求解上千个变

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

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

4、验：的试验：软件：软件： 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线性规划软件的进步（二）线性规划软件的进步（二）w 2003年年 Bixby的试验（的试验（CPLEX） 求解的模型求解的模型 生产计划模型，有生产计划模型，有401, 640个约束、个约束、1, 584,

5、 000个变量、个变量、9, 498, 000个非零元；个非零元；w 求解时间求解时间 ( 2.0 GHz P4 计算机计算机 ): 1988 (CPLEX 1.0): 29.8 days 1 1997 (CPLEX 5.0): 1.5 hours 1/480 2003 (CPLEX 9.0): 59.1 seconds 1/44000 6求解线性规划综合速度的提高求解线性规划综合速度的提高w 1988 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 人们一直试图证明单纯形方法是一种多项式算法；人们一直试图证明单纯形方法是一种多项式算法；w 1972年年Klee与与Minty出人意料的给出一个反例，证明出人意料的给出一个反例，证明单纯形算法不是多项式算法；单纯形

8、算法不是多项式算法；w 该问题共有该问题共有2n个极点，需要个极点，需要2n-1次迭代才能找到最优次迭代才能找到最优解；解；0 1 10102 10221jjjij)ij(jnjj)jn(xn,.jxx. t .sx:max9求解线性规划的多项式方法求解线性规划的多项式方法w 单纯形方法是统计意义上的多项式方法单纯形方法是统计意义上的多项式方法 1981年年Borgwardt在大量实验的基础上指出：单在大量实验的基础上指出：单纯形迭代次数的数学期望不会高于纯形迭代次数的数学期望不会高于O(n4m)w 前苏联数学家前苏联数学家Xachiyan 于于1979年提出求解年提出求解“线性严线性严格不等

9、式组格不等式组”的椭球算法。的椭球算法。 与求解线性规划问题等价，证明是多项式算法与求解线性规划问题等价，证明是多项式算法 计算效率根本无法与单纯形方法相比计算效率根本无法与单纯形方法相比w 美籍印度裔数学家美籍印度裔数学家Karmarkar 于于1984年提出求解线年提出求解线性规划的内点法；性规划的内点法； 可行域内部的搜索方法，计算效率高可行域内部的搜索方法，计算效率高10单纯形方法与内点法的竞赛单纯形方法与内点法的竞赛w 美国美国AT&T贝尔实验室的贝尔实验室的Monma等人等人1987年发表实年发表实验报告，他们对验报告，他们对31个实验问题的求解，所使用的内个实验问题的求解，所使用

10、的内点算法点算法3倍高于基于单纯形算法的倍高于基于单纯形算法的MINOS；w Karmarkar 1993年发表的实验结果表明对一些大规年发表的实验结果表明对一些大规模的问题内点法比单纯形方法快模的问题内点法比单纯形方法快80-100倍。但有人倍。但有人对对Karmarkar的实验结果有异议；的实验结果有异议；w 单纯形方法和内点法孰优孰劣的争论还没有结束；单纯形方法和内点法孰优孰劣的争论还没有结束；11整数规划整数规划12整数规划整数规划w 典型的整数规划：典型的整数规划：w 求解方法：穷举法、割平面法、分支定界求解方法：穷举法、割平面法、分支定界法、分支与割平面法法、分支与割平面法inte

11、gerallorsomejTxuxlbAxtoSubjectxcMaximize13w 即便求解很小的整数规划也会很困难，求解时间即便求解很小的整数规划也会很困难，求解时间可能以指数增长。如果用穷举法求解，需要的时可能以指数增长。如果用穷举法求解，需要的时间如下：间如下： 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整数规划求解史：整数

12、规划求解史：19501998w 割平面方法割平面方法（ Cutting Plane ） : 1954 Dantzig, Fulkerson, Johnson: 使用割平面方使用割平面方法求解有法求解有42个城市的旅行推销商问题（个城市的旅行推销商问题（TSP）；）； 1957年年Gomory完成了割平面方法的理论研究；完成了割平面方法的理论研究；w 分支定界法分支定界法（Branch-and-Bound）：）： 1960 Land, Doig; 1965 Dakin;w 商业软件商业软件： MPSX/370：1971年由年由Benichou等开发；等开发； UMPIRE：1972年年Forre

13、st, Hirst, Tomlin等开发；等开发； 1972 1998：各种先进的：各种先进的B&B方法在商业软件中方法在商业软件中得到广泛应用；得到广泛应用；15分支定界法分支定界法根节点根节点v 3v 4 整数解整数解x 2x 3 y 0y 1 z 0z 1 整数解整数解不可行不可行z 0z 1 GAP下界下界上界上界求解求解 LP LP 松弛问题松弛问题: : v=3.5 ( v=3.5 (非整数非整数) )注意注意: : (1) GAP = 0 (1) GAP = 0 证明已找到最有解证明已找到最有解 (2) (2) 实际应用实际应用: : 经常希望能找到足够好的解就可以了经常希望能找

14、到足够好的解就可以了16整数规划整数规划NP难题难题w 一个实用模型：只有一个实用模型：只有44个约束，个约束，51个整数变量，个整数变量，167个非零元；个非零元；w 使用最好的使用最好的Branch and Cut方法，在用启发式方法方法，在用启发式方法找到初始整数解找到初始整数解(-2186)和问题的初始上界和问题的初始上界(-1379)后，后，继续计算继续计算36小时，搜索了小时，搜索了3200万节点，搜索树占了万节点，搜索树占了5.5G内存，没有找到新的整数解，问题的界也没有内存，没有找到新的整数解，问题的界也没有任何改善。任何改善。w 问题出在哪里？糟糕的模型构造方法；问题出在哪里

15、？糟糕的模型构造方法；17线性规划求解速度也可能是瓶颈线性规划求解速度也可能是瓶颈w SGM: Schedule Generation Model，157,323约束，约束，182,812变量，变量，6,348,437非零元；非零元；w 求解线性规划松弛问题用了求解线性规划松弛问题用了18个小时个小时w 使用使用Branch and Cut方法方法: 搜索了搜索了368个节点，找到了很好的解；个节点，找到了很好的解； 所用时间：所用时间：14天天w 整数规划问题并不困难，线性规划的求解速度是求整数规划问题并不困难，线性规划的求解速度是求解的障碍；解的障碍； 如果线性规划求解速度可以再提高如果线

16、性规划求解速度可以再提高1000倍，情况会如倍，情况会如何？何？18整数规划求解方法进展整数规划求解方法进展w 线性规划的进展：更稳定、快捷的对偶算法线性规划的进展：更稳定、快捷的对偶算法w 变量节点选择：受旅行推销商问题的影响变量节点选择：受旅行推销商问题的影响w 启发式算法：启发式算法：8 种不同的方法；种不同的方法；w 节点的预评估：借鉴约束规划的思想节点的预评估：借鉴约束规划的思想w 对问题进行预处理：如约束的改写对问题进行预处理：如约束的改写 xj ( uj) y, y = 0/1 xj ujy (for all j)w 割平面方法（割平面方法（Cutting planes）19预处

17、理预处理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节点选择方法节点选择方法w 在解的可行性和最优性间权衡在解的可行性和最优性间权衡 深度优先：更易找到整数可行解深度优先：更易找到整数可行解 广度优先：搜索树会很大；广度优先：搜索树会很大； 最好优

18、先：追踪最好的解；最好优先：追踪最好的解； 节点预估法：预估在该节点下发节点预估法：预估在该节点下发现最好的整数解的值；现最好的整数解的值；= integer feasible21割平面法割平面法yx可行域可行域割平面割平面更好的割平面更好的割平面 (整整数解多面体的表面数解多面体的表面)22整数规划求解方法进展整数规划求解方法进展w CPLEX公司选择了公司选择了108个整数规划模型，分别用个整数规划模型，分别用5.0和和8.0版本求解，试图评估最有效的改进技术：版本求解，试图评估最有效的改进技术：w 5.0版本无法求解全部问题，版本无法求解全部问题，8.0 版本少于版本少于1000秒求解全

19、秒求解全部问题；部问题； Cuts53.7x Presolve10.8x CPLEX 5.0 presolve 3.1x CPLEX 5.0 var. selection 2.9x Heuristics 1.4x Node presolve 1.3x23一个求解实例一个求解实例w 求解有求解有7万个约束，万个约束，23万个整数变量的超大型整数万个整数变量的超大型整数规划规划w 使用使用CPLEX6.0版本版本 没有任何希望；没有任何希望；w 使用使用CPLEX9.0版本：版本： 只用了只用了76秒钟，在根节点发现最优解；秒钟，在根节点发现最优解； 割平面法使松弛问题变得更紧；割平面法使松弛问题

20、变得更紧； 使用启发式方法找到最优解；使用启发式方法找到最优解；24其它方法带来的改善其它方法带来的改善25求解技术改进带来的好处求解技术改进带来的好处w 建立更大，更精确的模型：一些供应链优化模型有建立更大，更精确的模型：一些供应链优化模型有1000万约束，万约束，2000万变量，求解只需要万变量，求解只需要1.5小时；小时；w 建立全局（建立全局（global）优化模型，以前可能需要分开求）优化模型，以前可能需要分开求解，如航空公司的模型；解，如航空公司的模型；w 建立长期（建立长期（ long-term ）优化模型，如制造业模型，）优化模型，如制造业模型，更准确反映实际需要；更准确反映实际需要；26运筹模型技术的应用前景运筹模型技术的应用前景w 运筹优化模型技术在以下方面的进展运筹优化模型技术在以下方面的进展 算法和软件技术算法和软件技术 计算机硬件技术计算机硬件技术 信息技术保证了数据的可获得性信息技术保证了数据的可获得性 模型的表达与实现技术模型的表达与实现技术w 优化技术已经为现实应用展现了广阔的前景优化技术已经为现实应用展现了广阔的前景 What is possible today could only have been dreamed of even 10 years ago。