数学规划在管理中的应用.ppt

《数学规划在管理中的应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学优化在管理中的应用张弦2007-11-20数学优化在管理中的应用领域优化在金融方面的应用投资组合优化贷款组合优化优化在运营管理方面的应用生产计划（产量计划、设备分配、工序安排等)人员排班设施布局优化在物流管理方面的应用物流网络规划(区域、全国、全球）配送线路优化(快递、零售配送、电子商务送货)货位/库位优化(仓库、货场、集装箱堆场)库存优化(单级/多级/网络，单周期/多周期)优化算法的分类MathematicProgramming方法可以证明最终解为全局最优解的优化方法，如线性规划、混合整数规划ConstraintProgramming方法用于解决有限解空间，无法

2、证明结果是全局最优解的搜索方法HeuristicPrograming方法可以解决无限解空间的问题，无法证明结果是全局最优的搜索方法Meta-Heuristic方法(禁忌算法、退火算法、遗传算法、神经网络、蚁群算法）基于数学规划的Heuristic方法（如：拉格朗日松弛）其他Heuristic方法(针对特定问题，依据经验制定的搜索方法)为什么不能只依靠MP方法有些问题无法找到一个可以被证明能够得到最优解的算法有些问题即使能够通过MP方法得到最优解，但是随着变量数量的增加，约束数量呈爆炸性的增长，计算时间会呈几何级数增长。如，旅行商问题。什么是好的优化模型？易读性vs.模

3、型规模变量的含义应该更简单还是更复杂时间复杂度vs.空间复杂度变量增加增加是否能够换来计算次数的下降变量数量vs.约束数量约束和变量是否可以转换，计算速度会有什么变化分层结构vs.单层结构主问题和子问题的划分，可能得不到最优解，但是能够简化问题优化算法的比较对于特定的模型，不同的算法会有不同的运行效率和不同的运算结果。而算法优劣的比较通常有两种：同样运算时间下，解的质量的比较得到最终解（或某水平以上满意解）所花时间的比较一个经典的优化问题——TravelingSalesmanProblem有N个城市，已知每两个城市之间的距离，一个货郎要从城市1出发，依次经过所有的城市

4、，最后返回城市1。如何走线路最短。如果把每两个城市之间的路径作为变量，以1代表经过该路径，0代表不经过该路径。则变量个数为N2个。很显然，每个城市的紧前城市和紧后城市只有一个，则包含约束数量为2N个。此外，必须保证只有唯一一条成环的路径，且该路径覆盖所有城市，这意味着所有的城市子集内部被选中的路径数量小于城市的数量。则包含约束数量为：一个经典的优化问题——TravelingSalesmanProblem显然，上述第二类约束数量随着城市数量的增长呈爆炸性的增长，增长速度甚至大于变量数的增长。如8个城市约束数为246，9个城市为501，10个城市为1012，11个城市为2

5、035，12个城市为4082……这意味着如果采用数学规划方法，问题的规模会变得非常庞大，运算时间将呈几何级数增长TSP问题的扩展VehicleRoutingProblem一个仓库向N个客户配送货物，每个客户都有各自的需求量，总需求量大于单车装载能力。已知仓库到各客户，以及客户之间的运输成本，如何以最少的车辆最少的运输成本满足客户的需求。VRP问题的进一步扩展有多个仓库，多种吨位的卡车，向N1个客户送货，同时向N2个客户收货，每个客户要求到达时间在某个时间窗内，不同吨位的卡车所能通行的路段不同，不同时段各路段的平均行驶速度不同，不同客户的卸货速度有所不同。怎样分配不同的

6、卡车到不同的线路，既能满足客户的要求，成本又相对最小。这样的问题适用于零售连锁企业的配送计划安排，也适用于快递行业的取件和送件计划。质量和速度的权衡不同问题对于解的质量和解的速度有不同的要求对于战略规划层面的优化，如物流网络规划，解的质量可能更为重要对于运作层面的优化，如日常调度的优化，解的速度可能更为重要在能够的接受的时间内比较解的质量，可能是选择算法更好的方法常用的优化软件ILOGCPLEX/CP(法国)ENGINESTPOEM(法国/中国)Xpress-MP(英国)Lindo/Lingo(美国)MatlabOptimizationToolbox(美国)只提供数学

7、规划方法ILOG公司产品线(构件类)ILOG公司产品线(应用类)LogicTool简介优越的性价比POEMSolutionBuilder世界上唯一的集逻辑，优化及搜索规则为一体的支持业务逻辑建模和复杂问题求解的智能描述型语言。NCL语言简洁的脚本用于管理(地图、时间等)可视化和“WhatIf...”(如果...会怎样)式的交互。VisualScriptGoogle:NCLConstraintLanguage不仅是一个开发工具而且是一个部件化的应用平台。在培训、管理、部署和维护上均显优越性。逻辑+运筹学算法+搜索规则+图形界面POEM支持模块化的解决方