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

数学优化在管理中的应用 张弦 2007-11-20 数学优化在管理中的应用领域 优化在金融方面的应用 投资组合优化 贷款组合优化 优化在运营管理方面的应用 生产计划（产量计划、设备分配、工序安排等) 人员排班 设施布局 优化在物流管理方面的应用 物流网络规划(区域、全国、全球） 配送线路优化(快递、零售配送、电子商务送货) 货位/库位优化(仓库、货场、集装箱堆场) 库存优化(单级/多级/网络，单周期/多周期) 优化算法的分类 Mathematic Programming方法 可以证明最终解为全局最优解的优化方法，如线性规划、混合整数规划 Constraint Programming方法 用于解决有限解空间，无法证明结果是全局最优解的有哪些信誉好的足球投注网站方法 Heuristic Programing方法 可以解决无限解空间的问题，无法证明结果是全局最优的有哪些信誉好的足球投注网站方法 Meta-Heuristic方法(禁忌算法、退火算法、遗传算法、神经网络、蚁群算法） 基于数学规划的Heuristic方法（如：拉格朗日松弛） 其他Heuristic方法(针对特定问题，依据经验制定的有哪些信誉好的足球投注网站方法) 为什么不能只依靠MP方法 有些问题无法找到一个可以被证明能够得到最优解的算法 有些问题即使能够通过MP方法得到最优解，但是随着变量数量的增加，约束数量呈爆炸性的增长，计算时间会呈几何级数增长。如，旅行商问题。 什么是好的优化模型？ 易读性vs.模型规模 变量的含义应该更简单还是更复杂 时间复杂度vs.空间复杂度 变量增加增加是否能够换来计算次数的下降 变量数量vs.约束数量 约束和变量是否可以转换，计算速度会有什么变化 分层结构vs.单层结构 主问题和子问题的划分，可能得不到最优解，但是能够简化问题 优化算法的比较 对于特定的模型，不同的算法会有不同的运行效率和不同的运算结果。而算法优劣的比较通常有两种： 同样运算时间下，解的质量的比较 得到最终解（或某水平以上满意解）所花时间的比较 一个经典的优化问题——Traveling Salesman Problem 有N个城市，已知每两个城市之间的距离，一个货郎要从城市1出发，依次经过所有的城市，最后返回城市1。如何走线路最短。 如果把每两个城市之间的路径作为变量，以1代表经过该路径，0代表不经过该路径。则变量个数为N2个。 很显然，每个城市的紧前城市和紧后城市只有一个，则包含约束数量为2N个。 此外，必须保证只有唯一一条成环的路径，且该路径覆盖所有城市，这意味着所有的城市子集内部被选中的路径数量小于城市的数量。则包含约束数量为： 一个经典的优化问题——Traveling Salesman Problem 显然，上述第二类约束数量随着城市数量的增长呈爆炸性的增长，增长速度甚至大于变量数的增长。如8个城市约束数为246，9个城市为501，10个城市为1012，11个城市为2035，12个城市为4082…… 这意味着如果采用数学规划方法，问题的规模会变得非常庞大，运算时间将呈几何级数增长 TSP问题的扩展Vehicle Routing Problem 一个仓库向N个客户配送货物，每个客户都有各自的需求量，总需求量大于单车装载能力。已知仓库到各客户，以及客户之间的运输成本，如何以最少的车辆最少的运输成本满足客户的需求。 VRP问题的进一步扩展 有多个仓库，多种吨位的卡车，向N1个客户送货，同时向N2个客户收货，每个客户要求到达时间在某个时间窗内，不同吨位的卡车所能通行的路段不同，不同时段各路段的平均行驶速度不同，不同客户的卸货速度有所不同。怎样分配不同的卡车到不同的线路，既能满足客户的要求，成本又相对最小。 这样的问题适用于零售连锁企业的配送计划安排，也适用于快递行业的取件和送件计划。 质量和速度的权衡 不同问题对于解的质量和解的速度有不同的要求 对于战略规划层面的优化，如物流网络规划，解的质量可能更为重要 对于运作层面的优化，如日常调度的优化，解的速度可能更为重要 在能够的接受的时间内比较解的质量，可能是选择算法更好的方法 常用的优化软件 ILOG CPLEX/CP(法国) ENGINEST POEM(法国/中国) Xpress-MP(英国) Lindo/Lingo(美国) Matlab Optimization Toolbox(美国) ILOG公司产品线(构件类) ILOG公司产品线(应用类) LogicTool简介 * * 只提供数学规划方法 *