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

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,线性规划,1,线性规划1,求解线性规划模型的历史,1947,年单纯形方法问世，手工计算工作量巨大，第一个有实用价值的线性规划模型只有,9,个约束，,77,个变量，花了,120,人日计算出结果；,50,年代：出现第一个求解线性规划软件，受计算机限制，只能求解,100,个变量的线性规划问题；,60,年代：出现商用线性规划软件，在,IBM,计算机上可求解上千个变量问题；,70,年代：许多大型计算机提供商用数学规划软件，如,MPS/X,，,FMPS,等，可求解有上万个变量和约束的问题，并有相应的模型数据处理系统，如,MG,，,RG,等。,2,求解线性规划模型的历史1947年单纯形方法问世，手工计算工作,80,年代：,计算机硬件、软件技术进步加快，求解模型的规模又上升一个数量级,内点法问世，新软件出现，如,CPLEX,，,OSL,等；,出现较完整的模型构造求解系统：,GAMS,，,AMPL,等,90,年代：信息技术时代，运筹学与信息技术的融合,出现了基于,WINDOWS,平台的应用系统,IT,与,OR,的集成，出现集信息采集、存储、分析、优化于一体的综合决策支持系统；,可求解有上千万变量的超大型数学模型；,典型应用：金融、航空、通讯、能源、军事等领域,求解线性规划模型的历史,3,80年代：计算机硬件、软件技术进步加快，求解模型的规模又上,线性规划软件的进步（一）,1991,年,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,非零元,4,线性规划软件的进步（一）1991年Schultz和Pulle,线性规划软件的进步（二）,2003,年,Bixby,的试验（,CPLEX,）,求解的模型 生产计划模型，有,401,640,个约束、,1,584,000,个变量、,9,498,000,个非零元；,求解时间,(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,5,线性规划软件的进步（二）2003年 Bixby的试验（CPL,求解线性规划综合速度的提高,1988,2003,求解,LP,的综合速度提高了多少？,算法（与计算机无关）,:2360,倍,计算机（工作站,PCs,）,800,倍,算法,计算机,190,万倍,摩尔定律预测计算机速度每,18,个月提高一倍：从,1988,至,2003,共,15,年应提高,1024,倍；,求解前面的生产计划模型,1988,年需要,80,年,1997,年需要,24,小时,2003,年需要,1,分钟,6,求解线性规划综合速度的提高1988 2003 求解LP的,线性规划软件的进步,是什么因素使线性规划求解效率有了如此长足的进步呢，著名线性规划软件,CPLEX,的主要设计者,Bixby,总结了以下几方面的的进展：,处理稀疏矩阵的数据结构,线性规划问题的预处理,初始基的选择,转轴规则的选择：最速边下降法，对偶方法；,基的,LU,分解与乘积形式：分解稳定性，减少非零元素的增长速度，提高计算精度；,7,线性规划软件的进步是什么因素使线性规划求解效率有了如此长足的,单纯形方法的计算效率,人们一直试图证明单纯形方法是一种多项式算法；,1972,年,Klee,与,Minty,出人意料的给出一个反例，证明单纯形算法不是多项式算法；,该问题共有,2,n,个极点，需要,2,n,-1,次迭代才能找到最优解；,8,单纯形方法的计算效率人们一直试图证明单纯形方法是一种多项式算,求解线性规划的多项式方法,单纯形方法是统计意义上的多项式方法,1981年Borgwardt在大量实验的基础上指出：单纯形迭代次数的数学期望不会高于,O,(,n,4,m,),前苏联数学家Xachiyan 于1979年提出求解“线性严格不等式组”的椭球算法。,与求解线性规划问题等价，证明是多项式算法,计算效率根本无法与单纯形方法相比,美籍印度裔数学家Karmarkar 于1984年,提出求解线性规划的内点法；,可行域内部的搜索方法，计算效率高,9,求解线性规划的多项式方法单纯形方法是统计意义上的多项式方法9,单纯形方法与内点法的竞赛,美国AT&T贝尔实验室的Monma等人1987年发表实验报告，他们对31个实验问题的求解，所使用的内点算法3倍高于基于单纯形算法的MINOS；,Karmarkar 1993年发表的实验结果表明对一些大规模的问题内点法比单纯形方法快80-100倍。但有人对Karmarkar的实验结果有异议；,单纯形方法和内点法孰优孰劣的争论还没有结束；,10,单纯形方法与内点法的竞赛美国AT&T贝尔实验室的Monma等,整数规划,11,整数规划11,整数规划,典型的整数规划：,求解方法：穷举法、割平面法、分支定界法、分支与割平面法,12,整数规划典型的整数规划：12,即便求解很小的整数规划也会很困难，求解时间可能以指数增长。如果用穷举法求解，需要的时间如下：,n,解的数量求解时间,101.02,10,3,1.02,10,-3,秒,201.05,10,6,1.05,秒,301.07,10,9,18,分钟,401.10,10,12,13,天,501.73,10,15,36,年,1001.27,10,30,4,亿亿,年,整数规划求解难度,13,即便求解很小的整数规划也会很困难，求解时间可能以指数增长。如,整数规划求解史：19501998,割平面方法,（,Cutting Plane,）,:,1954 Dantzig,Fulkerson,Johnson:,使用割平面方法求解有,42,个城市的旅行推销商问题（,TSP,）；,1957,年,Gomory,完成了割平面方法的理论研究；,分支定界法,（,Branch-and-Bound,）：,1960 Land,Doig;1965 Dakin;,商业软件,：,MPSX/370,：,1971,年由,Benichou,等开发；,UMPIRE,：,1972,年,Forrest,Hirst,Tomlin,等开发；,1972 1998,：各种先进的,B&B,方法在商业软件中得到广泛应用；,14,整数规划求解史：19501998割平面方法（Cuttin,分支定界法,根节点,v,3,v,4,整数解,x,2,x,3,y,0,y,1,z,0,z,1,整数解,不可行,z,0,z,1,G,A,P,下界,上界,求解,LP,松弛问题,:,v=3.5(,非整数,),注意,:,(1)GAP=0,证明已找到最有解,(2),实际应用,:,经常希望能找到足够好的解就可以了,15,分支定界法根节点v 3v 4 整数解x 2x,整数规划NP难题,一个实用模型：只有44个约束，51个整数变量，167个非零元；,使用最好的Branch and Cut方法，在用启发式方法找到初始整数解(-2186)和问题的初始上界(-1379)后，继续计算36小时，搜索了3200万节点，搜索树占了5.5G内存，没有找到新的整数解，问题的界也没有任何改善。,问题出在哪里？糟糕的模型构造方法；,16,整数规划NP难题一个实用模型：只有44个约束，51个整数变,线性规划求解速度也可能是瓶颈,SGM:Schedule Generation Model,，,157,323,约束，,182,812,变量，,6,348,437,非零元；,求解线性规划松弛问题用了,18,个小时,使用,Branch and Cut,方法,:,搜索了,368,个节点，找到了很好的解；,所用时间：,14,天,整数规划问题并不困难，线性规划的求解速度是求解的障碍；,如果线性规划求解速度可以再提高,1000,倍，情况会如何？,17,线性规划求解速度也可能是瓶颈SGM:Schedule G,整数规划求解方法进展,线性规划的进展：更稳定、快捷的对偶算法,变量节点选择：受旅行推销商问题的影响,启发式算法：,8,种不同的方法；,节点的预评估：借鉴约束规划的思想,对问题进行预处理：如约束的改写,x,j,(,u,j,),y,y,=0/1,x,j,u,j,y,(for all,j,),割平面方法（,Cutting planes,）,18,整数规划求解方法进展线性规划的进展：更稳定、快捷的对偶算法1,预处理,缩减问题的尺寸：,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,为,0-1,变量，,将约束改为：,4,x,+3,y,+,z,4,19,预处理缩减问题的尺寸：19,节点选择方法,在解的可行性和最优性间权衡,深度优先：更易找到整数可行解,广度优先：搜索树会很大；,最好优先：追踪最好的解；,节点预估法：预估在该节点下发现最好的整数解的值；,=integer feasible,20,节点选择方法在解的可行性和最优性间权衡=integer f,割平面法,y,x,可行域,割平面,更好的割平面,(,整数解多面体的表面,),21,割平面法yx可行域割平面更好的割平面(整数解多面体的表面),整数规划求解方法进展,CPLEX,公司选择了,108,个整数规划模型，分别用,5.0,和,8.0,版本求解，试图评估最有效的改进技术：,5.0,版本无法求解全部问题，,8.0,版本少于,1000,秒求解全部问题；,Cuts53.7x,Presolve10.8x,CPLEX 5.0 presolve 3.1x,CPLEX 5.0 var.selection 2.9x,Heuristics 1.4x,Node presolve 1.3x,22,整数规划求解方法进展CPLEX公司选择了108个整数规划模型,一个求解实例,求解有,7,万个约束，,23,万个整数变量的超大型整数规划,使用,CPLEX6.0,版本 没有任何希望；,使用,CPLEX9.0,版本：,只用了,76,秒钟，在根节点发现最优解；,割平面法使松弛问题变得更紧；,使用启发式方法找到最优解；,23,一个求解实例求解有7万个约束，23万个整数变量的超大型整数规,其它方法带来的改善,24,其它方法带来的改善24,求解技术改进带来的好处,建立更大，更精确的模型：一些供应链优化模型有,1000,万约束，,2000,万变量，求解只需要,1.5,小时；,建立全局（,global,）优化模型，以前可能需要分开求解，如航空公司的模型；,建立长期（,long-term,）优化模型，如制造业模型，更准确反映实际需要；,25,求解技术改进带来的好处建立更大，更精确的模型：一些供应链优化,运筹模型技术的应用前景,运筹优化模型技术在以下方面的进展,算法和软件技术,计算机硬件技术,信息技术保证了数据的可获得性,模型的表达与实现技术,优化技术已经为现实应用展现了广阔的前景,What is possible today could only have been dreamed of even 10 years ago,。,26,运筹模型技术的应用前景运筹优化模型技术在以下方面的进展26,