《的使用方法学习.pptx》由会员分享,可在线阅读,更多相关《的使用方法学习.pptx(67页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、它是如何工作的?优化是一个可应用于特定问题的一个过程。这样逻辑上第一步是对要解决问题的一个清晰的描述。随后的步骤如下:为你的问题构造一个模型将数据加入模型中利用数学优化引擎分析该模型以找到最好的可能解当优化模型嵌入到实际应用中时,计划人员和运作管理者可以进行分析,并可以比较各种方案1第1页/共67页下面的图表说明了优化需要处理的一些信息类型,下面的图表说明了优化需要处理的一些信息类型,和优化过程所产生的结果。和优化过程所产生的结果。2第2页/共67页3第3页/共67页数学优化在管理中的应用领域优化在金融方面的应用投资组合优化贷款组合优化优化在运营管理方面的应用生产计划(产量计划、设备分配、工序
2、安排等)人员排班设施布局优化在物流管理方面的应用物流网络规划(区域、全国、全球)配送线路优化(快递、零售配送、电子商务送货)货位/库位优化(仓库、货场、集装箱堆场)库存优化(单级/多级/网络,单周期/多周期)4第4页/共67页优化算法的分类Mathematic Programming方法可以证明最终解为全局最优解的优化方法,如线性规划、混合整数规划Constraint Programming方法用于解决有限解空间,无法证明结果是全局最优解的搜索方法Heuristic Programing方法可以解决无限解空间的问题,无法证明结果是全局最优的搜索方法Meta-Heuristic方法(禁忌算法、退
3、火算法、遗传算法、神经网络、蚁群算法)基于数学规划的Heuristic方法(如:拉格朗日松弛)其他Heuristic方法(针对特定问题,依据经验制定的搜索方法)5第5页/共67页为什么不能只依靠MP方法有些问题无法找到一个可以被证明能够得到最优解的算法有些问题即使能够通过MP方法得到最优解,但是随着变量数量的增加,约束数量呈爆炸性的增长,计算时间会呈几何级数增长。如,旅行商问题。6第6页/共67页什么是好的优化模型?易读性vs.模型规模变量的含义应该更简单还是更复杂时间复杂度vs.空间复杂度变量增加增加是否能够换来计算次数的下降变量数量vs.约束数量约束和变量是否可以转换,计算速度会有什么变化
4、分层结构vs.单层结构主问题和子问题的划分,可能得不到最优解,但是能够简化问题7第7页/共67页优化算法的比较对于特定的模型,不同的算法会有不同的运行效率和不同的运算结果。而算法优劣的比较通常有两种:同样运算时间下,解的质量的比较得到最终解(或某水平以上满意解)所花时间的比较8第8页/共67页一个经典的优化问题Traveling Salesman Problem 有N个城市,已知每两个城市之间的距离,一个货郎要从城市1出发,依次经过所有的城市,最后返回城市1。如何走线路最短。如果把每两个城市之间的路径作为变量,以1代表经过该路径,0代表不经过该路径。则变量个数为N2个。很显然,每个城市的紧前城
5、市和紧后城市只有一个,则包含约束数量为2N个。此外,必须保证只有唯一一条成环的路径,且该路径覆盖所有城市,这意味着所有的城市子集内部被选中的路径数量小于城市的数量。则包含约束数量为:9第9页/共67页一个经典的优化问题Traveling Salesman Problem显然,上述第二类约束数量随着城市数量的增长呈爆炸性的增长,增长速度甚至大于变量数的增长。如8个城市约束数为246,9个城市为501,10个城市为1012,11个城市为2035,12个城市为4082这意味着如果采用数学规划方法,问题的规模会变得非常庞大,运算时间将呈几何级数增长10第10页/共67页TSP问题的扩展Vehicle
6、Routing Problem一个仓库向N个客户配送货物,每个客户都有各自的需求量,总需求量大于单车装载能力。已知仓库到各客户,以及客户之间的运输成本,如何以最少的车辆最少的运输成本满足客户的需求。11第11页/共67页VRP问题的进一步扩展有多个仓库,多种吨位的卡车,向N1个客户送货,同时向N2个客户收货,每个客户要求到达时间在某个时间窗内,不同吨位的卡车所能通行的路段不同,不同时段各路段的平均行驶速度不同,不同客户的卸货速度有所不同。怎样分配不同的卡车到不同的线路,既能满足客户的要求,成本又相对最小。这样的问题适用于零售连锁企业的配送计划安排,也适用于快递行业的取件和送件计划。12第12页
7、/共67页质量和速度的权衡不同问题对于解的质量和解的速度有不同的要求对于战略规划层面的优化,如物流网络规划,解的质量可能更为重要对于运作层面的优化,如日常调度的优化,解的速度可能更为重要在能够的接受的时间内比较解的质量,可能是选择算法更好的方法13第13页/共67页下图说明了开发时间下图说明了开发时间/计划类型和在多数情计划类型和在多数情况下应用所使用的恰当技术之间的关系况下应用所使用的恰当技术之间的关系14第14页/共67页在优化中用到的主要的规划技术线性规划(LP)整数规划(IP)二次规划(QP)约束规划(CP)实际中,许多整数规划都含有浮点计算,因此混合整数规划(MIP)的应用要多于纯I
8、P15第15页/共67页OPL 可以描述下面类型的规划问题:16OPL没法处理非线性问题没法处理非线性问题第16页/共67页OPL 和优化:总体介绍OPL 开发环境是ILOG 全部优化解决方案组件中的一个。下面表示了ILOG 优化工具的组成,它可以分成两类:ILOG PowerOps:全面,预先建立的应用,它们利用了超过15 年的经验,这些经验为在制造业和运输业中的一些特殊领域中的工作提供了优化技术。ODMS:优化决策管理系统,开发定制模型的一个成熟系统,是基于ILOG 的、经过工业验证的、优化引擎的应用。17第17页/共67页ODMS 中的OPLILOG OPL 开发环境是优化决策管理系统(
9、ODMS)中的一个组成成分。ODMS 是一套工具组件,包括ILOG 优化引擎,它可以用来开发定制模型和应用你可以利用OPL 开发环境来设计定制模型,用来解决你的商业或机构中的特定问题,这个过程并不需要低级开发语言。你可以利用OPL 集成开发环境(IDE)来进行这一过程18第18页/共67页它为用户提供了一个图形用户界面,从而为模型的开发提供了直观的工具这些模型可以直接和ILOG 优化决策管理器(ODM)一起集成到开发的应用中,从而是商业用户可以进行what-if 分析,并且比较各种方案数据与模型是相互独立的,这样你开发的原型就具有了可重用性OPL的优势的优势19第19页/共67页ILOG OP
10、L的文件介绍项目文件(.prj)包含了相应的各种文件和与一个问题相关的参数。它组织相关的模型和数据文件,并提供一种方便的方法来维护相关文件和运行选择之间的关系。在项目中:模型文件(.mod)声明了数据项目,但是并不需要初始化它们;数据文件(.dat)包含了在模型中声明的数据的初始化;设置文件(.ops)当你决定改变一个或多个数学规划和其他选择的缺省值是,该文件保存用户定义的值;20第20页/共67页运行配置并不是一个文件类型,而是为了运行的目的而设置项目变化。一个运行配置组合了一个模型文件和一个或多个数据文件,考虑到内容和/或设置,它们与项目中原始的模型和数据是不同的,但是是针对同一个数学问题
11、。在一个项目中,你可以根据自己的需要定义多个运行配置。21第21页/共67页一个最小的项目有:一个模型文件对于同一模型文件的一个缺省的运行配置一个典型的项目有:一个或多个模型文件;任意数量的数据文件(或者没有数据文件)一个或多个设置文件一个或多个运行配置,设置这些模型,数据和设置文件的不同组合.22第22页/共67页一个生产计划问题作为一个例子,现在研究一个典型的生产计划案例。下面的表格列出了一般的要求,它是用商业术语来描述的,如同它们在OPL 开发环境中的声明。23第23页/共67页24第24页/共67页程序的说明25第25页/共67页26第26页/共67页27第27页/共67页28第28页
12、/共67页OPL解决线性规划问题29第29页/共67页Maximizesum(p in Products)profitp*productionpsubject to forall(c in Components)sum(p in Products)demandp,c*productionp=subc30第30页/共67页实例某公司根据市场需求计划加工生产三种产品,各产品的原材料消耗定额、工时定额、单位利润和最高资源限制如表1。现要求安排三种产品的产量X1,X2,X3,满足在资源限制条件下使得总利润为最大 31第31页/共67页项目项目甲产品甲产品X1乙产品乙产品X2丙产品丙产品X3资源限制资源
13、限制材料材料1(kg/件)件)324600kg材料材料2(kg/件)件)5861030kg材料材料3(kg/件)件)253688kg加工能力(工时加工能力(工时/件)件)232495工时工时单位利润(元单位利润(元/件)件)8010910532第32页/共67页数学模型33第33页/共67页程序的建立在ILOG OPL Studio 中新建一个prj,命名为product1.prj,在product1.prj下面的product1.mod中输入以下命令:34第34页/共67页数据类型定义与变量的申明Enum Products.;enum Components.;float+demandProd
14、ucts,Components=.;float+profitProducts=.;float+subComponents=.;var float+productionProducts;35第35页/共67页目标函数和约束maximize sum(p in Products)profitp*productionpsubject to forall(c in Components)sum(p in Products)demandp,c*productionp=subc;36第36页/共67页在product1.prj下面的product1.data中输入以下数据:Products=X1,X2,X3
15、;Components=materialone,materialtwo,materialthree,time;demand=3,5,2,2,2,8,5,3,4,6,3,2;profit=80,109,105;sub=600,1030,688,495;数据文件data37第37页/共67页程序结果运行程序,可以得到以下结果:Optimal Solution with Objective Value:17219.0000productionX1=0.0000productionX2=26.0000productionX3=137.000038第38页/共67页39DemandSubProfitSo
16、lution第39页/共67页 销地产地B1B2.Bn产量A1x11 c11x12 c12.x1n c1na1A2x21 c21x22 c22.x2n c2na2.Amxm1 cm1xm2cm2.xmn cmnam销量b1b2.bnOPL解决运输规划问题40第40页/共67页41数学模型西北角法、最小元素法、Vogel法用闭回路法、位势法来做最优性检验第41页/共67页Trans.modenum CitiesA.;enum CitiesB.;float+capacity=.;float+supplyCitiesA=.;float+demandCitiesB=.;assert sum(o in
17、CitiesA)supplyo=sum(d in CitiesB)demandd;float+costCitiesA,CitiesB=.;var float+transCitiesA,CitiesB;42第42页/共67页minimize sum(o in CitiesA&d in CitiesB)costo,d*transo,dsubject to forall(o in CitiesA)sum(d in CitiesB)transo,d=supplyo;forall(d in CitiesB)sum(o in CitiesA)transo,d=demandd;forall(o in Cit
18、iesA&d in CitiesB)transo,d=capacity;display trans;43第43页/共67页实例演示CityFRA DETLAN WIN STLFRELAFGARY 301081011716CLEV 227107218213PITT1911121025831544第44页/共67页Trans.data CitiesA=GARY CLEV PITT;CitiesB=FRA DET LAN WIN STL FRE LAF;capacity =625;supply=400 700 800;demand=300 300 100 75 650 225 250;cost=30
19、 10 8 10 11 71 6 22 7 10 7 21 82 13 19 11 12 10 25 83 15 ;45第45页/共67页46第46页/共67页OPL 解决作业车间调度问题47第47页/共67页下面应用ILOG解决一个典型问题FT10的最短调度时间,来说明ILOG解决调度问题的过程 一个调度问题可以建立成混合整数规划模型和约束规划模型.不同的是约束规划模型的建立依赖于基于约束规划技术的软件所提供的建模语言和建模结构。ILOG能对这两种模型求解,但它对约束规划模型的表述和求解,更能体现它对车间调度问题的强大建模能力和解决能力。48第48页/共67页ILOG解决调度问题的基本过程I
20、LOG解决调度问题的基本过程是:充分了解所要解决的问题,了解问题具有的约束及其使用资源的性质;建立问题的模型,包括设计已知变量、决策变量,实现各种约束的表达,评估模型,然后应用优化设计语言(OPL)进行程序实现49第49页/共67页同时发现问题,对建立的模型进行的修改例如去除不必要的约束等等,将文件保存为:mod文件;最后将要运行的数据写入*.dat文件,与*.mod形成一个project,运行程序得到调度结果。50第50页/共67页Jsp.modint nbMachines=.;range Machines 1.nbMachines;int nbJobs=.;range Jobs 1.nbJ
21、obs;int nbTasks=.;range Tasks 1.nbTasks;Machines resourceJobs,Tasks=.;int+durationJobs,Tasks=.;int totalDuration=sum(j in Jobs,t in Tasks)durationj,t;51第51页/共67页scheduleHorizon=totalDuration;Activity taskj in Jobs,t in Tasks(durationj,t);Activity makespan(0);UnaryResource toolMachines;minimize makes
22、pan.endsubject to forall(j in Jobs)taskj,nbTasks precedes makespan;52CP Model第52页/共67页 forall(j in Jobs)forall(t in 1.nbTasks-1)taskj,t precedes taskj,t+1;forall(j in Jobs)forall(t in Tasks)taskj,t requires toolresourcej,t;53第53页/共67页Jsp.datnbMachines=10;nbJobs=10;nbTasks=10;resource=1,2,3,4,5,6,7,8
23、,9,10 ,1,3,5,10,4,2,7,6,8,9 ,2,1,4,3,9,6,8,7,10,5 ,2,3,1,5,7,9,8,4,10,6 ,3,1,2,6,4,5,9,8,10,7 ,3,2,6,4,9,10,1,7,5,8 ,2,1,4,3,7,6,10,9,8,5 ,3,1,2,6,5,7,9,10,8,4 ,1,2,4,6,3,10,7,8,5,9 ,2,1,3,7,9,10,6,4,5,8 ;54第54页/共67页duration=29,78,9,36,49,11,62,56,44,21 ,43,90,75,11,69,28,46,46,72,30 ,91,85,39,74,90
24、,10,12,89,45,33 ,81,95,71,99,9,52,85,98,22,43 ,14,6,22,61,26,69,21,49,72,53 ,84,2,52,95,48,72,47,65,6,25 ,46,37,61,13,32,21,32,89,30,55 ,31,86,46,74,32,88,19,48,36,79 ,76,69,76,51,85,11,40,89,26,74 ,85,13,61,7,64,76,47,52,90,45 ;55第55页/共67页结果表述然后运行搜索策略,运行程序,利用ILOG SolverILOG Scheduler可以得到调度甘特图,最优解为9
25、30。56第56页/共67页调度甘特图57第57页/共67页小结优化是一种基于数学的技术,它针对最大的运作效益来分配资源,它可应用于许多种工业和商业情况中。OPL 开发环境是ILOG 优化决策管理系统(ODMS)的一个组成成分,ODMS 是一个工具组件,包括ILOG 优化引擎,它可以用来开发定制模型和应用。OPL 开发环境主要用户是优化建模专家,他们用来为一个商业行为或机构的具体问题设计定制解决方案,这个过程不需要低级的编程语言。58第58页/共67页小结OPL 开发环境提供一个集成的开发环境(IDE),它允许你使用直观的图形界面进行建模。模型可以集成到由ILOG 优化决策管理器(ODM)开发的应用中,允许用户执行what-if分析,比较不同方案。数据与模型独立,因此模型是可重用的。如何应用OPL 开发环境来构建一个简单的、可重用的模型,并使用不同的数据。59第59页/共67页60第60页/共67页61第61页/共67页62第62页/共67页63第63页/共67页64第64页/共67页65第65页/共67页END66第66页/共67页67感谢您的观看!第67页/共67页
限制150内