模型与软件数学规划软件

模型与软件数学规划软件1第1页，课件共27页，创作于2023年2月线性规划2第2页，课件共27页，创作于2023年2月求解线性规划模型的历史1947年单纯形方法问世，手工计算工作量巨大，第一个有实用价值的线性规划模型只有9个约束，77个变量，花了120人日计算出结果；50年代：出现第一个求解线性规划软件，受计算机限制，只能求解100个变量的线性规划问题；60年代：出现商用线性规划软件，在IBM计算机上可求解上千个变量问题；70年代：许多大型计算机提供商用数学规划软件，如MPS/X，FMPS等，可求解有上万个变量和约束的问题，并有相应的模型数据处理系统，如MG，RG等。3第3页，课件共27页，创作于2023年2月80年代：计算机硬件、软件技术进步加快，求解模型的规模又上升一个数量级内点法问世，新软件出现，如CPLEX，OSL等；出现较完整的模型构造求解系统：GAMS，AMPL等90年代：信息技术时代，运筹学与信息技术的融合出现了基于WINDOWS平台的应用系统IT与OR的集成，出现集信息采集、存储、分析、优化于一体的综合决策支持系统；可求解有上千万变量的超大型数学模型；典型应用：金融、航空、通讯、能源、军事等领域求解线性规划模型的历史4第4页，课件共27页，创作于2023年2月线性规划软件的进步（一）1991年Schultz和Pulleyblank的试验：软件：MPSMPSOSLOSLOSL版本：v1.6v2.0Prim-1Dual-1Dual-2年代：19701988199319931993迭代：3023574885836050114104982时间：5508224114问题：4422约束，6711个变量，110342非零元5第5页，课件共27页，创作于2023年2月线性规划软件的进步（二）2003年Bixby的试验（CPLEX）求解的模型－生产计划模型，有401,640个约束、1,584,000个变量、9,498,000个非零元；求解时间(2.0GHzP4计算机):1988(CPLEX1.0): 29.8days 11997(CPLEX5.0): 1.5hours 1/4802003(CPLEX9.0): 59.1seconds 1/44000……6第6页，课件共27页，创作于2023年2月求解线性规划综合速度的提高1988

2003求解LP的综合速度提高了多少？算法（与计算机无关）: 2360倍计算机（工作站

PCs） 800倍算法×计算机 190万倍摩尔定律预测计算机速度每18个月提高一倍：从1988至2003共15年应提高1024倍；求解前面的生产计划模型1988年需要80年1997年需要24小时2003年需要1分钟7第7页，课件共27页，创作于2023年2月线性规划软件的进步是什么因素使线性规划求解效率有了如此长足的进步呢，著名线性规划软件CPLEX的主要设计者Bixby总结了以下几方面的的进展：处理稀疏矩阵的数据结构线性规划问题的预处理初始基的选择转轴规则的选择：最速边下降法，对偶方法；基的LU分解与乘积形式：分解稳定性，减少非零元素的增长速度，提高计算精度；8第8页，课件共27页，创作于2023年2月单纯形方法的计算效率人们一直试图证明单纯形方法是一种多项式算法；1972年Klee与Minty出人意料的给出一个反例，证明单纯形算法不是多项式算法；该问题共有2n个极点，需要2n-1次迭代才能找到最优解；9第9页，课件共27页，创作于2023年2月求解线性规划的多项式方法单纯形方法是统计意义上的多项式方法1981年Borgwardt在大量实验的基础上指出：单纯形迭代次数的数学期望不会高于O(n4m)前苏联数学家Xachiyan于1979年提出求解“线性严格不等式组”的椭球算法。与求解线性规划问题等价，证明是多项式算法计算效率根本无法与单纯形方法相比美籍印度裔数学家Karmarkar于1984年提出求解线性规划的内点法；可行域内部的搜索方法，计算效率高10第10页，课件共27页，创作于2023年2月单纯形方法与内点法的竞赛美国AT&T贝尔实验室的Monma等人1987年发表实验报告，他们对31个实验问题的求解，所使用的内点算法3倍高于基于单纯形算法的MINOS；Karmarkar1993年发表的实验结果表明对一些大规模的问题内点法比单纯形方法快80-100倍。但有人对Karmarkar的实验结果有异议；单纯形方法和内点法孰优孰劣的争论还没有结束；11第11页，课件共27页，创作于2023年2月整数规划12第12页，课件共27页，创作于2023年2月整数规划典型的整数规划：求解方法：穷举法、割平面法、分支定界法、分支与割平面法13第13页，课件共27页，创作于2023年2月即便求解很小的整数规划也会很困难，求解时间可能以指数增长。如果用穷举法求解，需要的时间如下：

n 解的数量 求解时间 10 1.02

103 1.0210-3秒 20 1.05

106 1.05秒 30 1.07

109 18分钟 40 1.10

1012 13天 50 1.73

1015 36年 100 1.27

1030 4亿亿

年整数规划求解难度14第14页，课件共27页，创作于2023年2月整数规划求解史：1950－1998割平面方法（CuttingPlane）

:1954Dantzig,Fulkerson,Johnson:使用割平面方法求解有42个城市的旅行推销商问题（TSP）；1957年Gomory完成了割平面方法的理论研究；分支定界法（Branch-and-Bound）：1960Land,Doig;1965Dakin;商业软件：MPSX/370：1971年由Benichou等开发；UMPIRE：1972年Forrest,Hirst,Tomlin等开发；1972–1998：各种先进的B&B方法在商业软件中得到广泛应用；15第15页，课件共27页，创作于2023年2月分支定界法根节点v3v

4

整数解x2x

3

y0y

1

z0z

1

整数解不可行z0z

1

GAP下界上界求解LP松弛问题:v=3.5(非整数)注意:(1)GAP=0证明已找到最有解(2)实际应用:经常希望能找到足够好的解就可以了16第16页，课件共27页，创作于2023年2月整数规划－NP难题一个实用模型：只有44个约束，51个整数变量，167个非零元；使用最好的BranchandCut方法，在用启发式方法找到初始整数解(-2186)和问题的初始上界(-1379)后，继续计算36小时，搜索了3200万节点，搜索树占了5.5G内存，没有找到新的整数解，问题的界也没有任何改善。问题出在哪里？糟糕的模型构造方法；17第17页，课件共27页，创作于2023年2月线性规划求解速度也可能是瓶颈SGM:ScheduleGenerationModel，157,323约束，182,812变量，6,348,437非零元；求解线性规划松弛问题用了18个小时使用BranchandCut方法:搜索了368个节点，找到了很好的解；所用时间：14天整数规划问题并不困难，线性规划的求解速度是求解的障碍；如果线性规划求解速度可以再提高1000倍，情况会如何？18第18页，课件共27页，创作于2023年2月整数规划求解方法进展线性规划的进展：更稳定、快捷的对偶算法变量节点选择：受旅行推销商问题的影响启发式算法：8种不同的方法；节点的预评估：借鉴约束规划的思想对问题进行预处理：如约束的改写

xj

(

uj)y,y=0/1

xj

ujy(forallj)割平面方法（Cuttingplanes）19第19页，课件共27页，创作于2023年2月预处理缩减问题的尺寸：x+y

3，x1，y1 x+y

3可以删去缩紧约束（Tightenformulation）x+y

5;0x10;0y10；

x和y的上界可以改为5；5x+3y+z

4;x,y,z为0-1变量， 将约束改为：4x+3y+z

420第20页，课件共27页，创作于2023年2月节点选择方法在解的可行性和最优性间权衡深度优先：更易找到整数可行解广度优先：搜索树会很大；最好优先：追踪最好的解；节点预估法：预估在该节点下发现最好的整数解的值；

……=integerfeasible21第21页，课件共27页，创作于2023年2月割平面法yx可行域割平面更好的割平面(整数解多面体的表面)22第22页，课件共27页，创作于2023年2月整数规划求解方法进展CPLEX公司选择了108个整数规划模型，分别用5.0和8.0版本求解，试图评估最有效的改进技术：5.0版本无法求解全部问题，8.0版本少于1000秒求解全部问题；Cuts 53.7xPresolve 10.8xCPLEX5.0presolve 3.1xCPLEX5.0var.selection 2.9xHeuristics 1.4xNodepresolve 1.3x23第23页，课件共27页，创作于2023年2月一个求解实例求解有7万个约束，23万个整数变量的超大型整数规划使用CPLEX6.0版本－没有任何希望；使用CPLEX9.0版本：只用了76秒钟，在根节点发现最优解；割平面法使松弛问题变得更紧；使用启发式方法找到最优解；24第24页，课件共27页，创作于2023年2月其它方法带来的改善25第25页，课件共27页，创作于2023年2月求解技术改进带来的好处建立更大，更精确的模型：一些供应链优化模型有1000万约束，2000万变量，求解只需要1.5小时；建立全局（global）优化模型，以前可能需要分开求解，如航空公司的模型；建立