文档介绍：Data, Model and Decisions
数据、模型与决策
Session 5
Network Optimization Problems
网络最优化问题
Session Topics
Phillips Petroleum Vehicle Replacement Planning
飞利浦石油公司运输工具替换计划
Applications work Optimization
网络最优化模型的应用
Types work Optimization Problem
网络最优化问题类型
Minimum work 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 work Optimization
网络最优化模型的应用
网络在交通、电子和通讯网络遍及我们日常生活的
各个方面,网络规划也广泛用于解决不同领域中的
各种问题,如生产、分配、项目计划、厂址选择、
资源管理和财务策划等等。
网络规划为描述系统各组成部分之间的关系提供了
非常有效直观和概念上的帮助,广泛应用于科学、
社会和经济活动的每个领域中
Network representation
网络表述
这种描述还有其他应用吗?
想想看!
Types work Optimization Problem
网络最优化问题类型
Minimum work Flow Model
最小费用流问题
Maximum Flow Problems
最大流问题
Shortest Path Problem
最短路问题
Minimum Spanning Tree Problem
最小支撑树问题
Minimum work Flow Model
最小费用流问题
最小费用流问题的构成:
节点(nodes)(供应点、需求点、转运点)
弧(arcs)
目标: 通过网络满足需求提供供应,
最小化流的总成本
Assumptions of Minimum Cost
Network Flow
最小费用流问题的假设
至少一个供应点一个需求点剩下都是转运点
通过弧的流只允许沿着箭头方向流动,通过弧的
最大流量取决于该弧的容量
网络中有足够的弧提供足够容量,使得所有在供
应点中产生的流都能够到达需求点
在流的单位成本已知前提下,通过每一条弧的流
的成本和流量成正比