[所有分类]Session05网络最优化问题.ppt

Aetna School of Management,S.J.T.U. All Rights Reserved,Ren Jian Biao.,2001 Session5 Network Optimization Problems 网络最优化问题 renjb@ Data, Model and Decisions 数据、模型与决策 Session 5 Network Optimization Problems 网络最优化问题 Session Topics Phillips Petroleum Vehicle Replacement Planning 飞利浦石油公司运输工具替换计划 Applications of Network Optimization 网络最优化模型的应用 Types of Network Optimization Problem 网络最优化问题类型 Minimum Cost Network Flow Model 最小费用流问题 Session Topics Maximum Flow Problems 最大流问题 Shortest Path Problem 最短路问题 Minimum Spanning Tree Problem 最小支撑树问题 飞利浦石油（Phillips Petroleum）应用最短路问题模型对各种高速公路运输车、卡车和货车运输路线的优化来降低成本提高竞争力 Planning Vehicle Replacement at Phillips Petroleum 飞利浦石油的运输工具替换计划 经典应用 Waddell (1983) Jul-Aug Interfaces article, “A Model for Equipment Replacement Decisions and Policies” 有1500辆卡车和3800辆货车 用最短路模型建立替换战略(20年时间跨度) 每次为每一类运输工具求解模型 考虑成本有维护和运营成本、租赁成本、购买成本、 政府授权费用路税和其他税收（投资税、折旧） 开始做lease-or-buy决策，然后做替换战略，目前扩展到了其他的设备（非运输工具） Planning Vehicle Replacement at Phillips Petroleum 飞利浦石油的运输工具替换计划 经典应用 Applications of Network Optimization 网络最优化模型的应用 网络在交通、电子和通讯网络遍及我们日常生活的 各个方面，网络规划也广泛用于解决不同领域中的 各种问题，如生产、分配、项目计划、厂址选择、 资源管理和财务策划等等。 网络规划为描述系统各组成部分之间的关系提供了 非常有效直观和概念上的帮助，广泛应用于科学、 社会和经济活动的每个领域中 Network representation 网络表述 这种描述还有其他应用吗？ 想想看！ Types of Network Optimization Problem 网络最优化问题类型 Minimum Cost Network Flow Model 最小费用流问题 Maximum Flow Problems 最大流问题 Shortest Path Problem 最短路问题 Minimum Spanning Tree Problem 最小支撑树问题 Minimum Cost Network Flow Model 最小费用流问题 最小费用流问题的构成： 节点(nodes)（供应点 、需求点 、转运点） 弧（arcs） 目标: 通过网络满足需求提供供应， 最小化流的总成本 Assumptions of Minimum Cost Network Flow 最小费用流问题的假设 至少一个供应点一个需求点剩下都是转运点 通过弧的流只允许沿着箭头方向流动，通过弧的 最大流量取决于该弧的容量 网络中有足够的弧提供足够容量，使得所有在供 应点中产生的流都能够到达需求点 在流的单位成本已知前提下，通过每一条弧的流 的成本和流量成正比 Characteristic of Solution 解的特征 具有可行解的特征：在以上的假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解 具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解 Distribution Unlimited Co. 无限配送公司 无限配送公司的最小成本流问题的电子表格模型 实际举例 Network Sim