Chapter 7 Network Optimization Problems 网络最优化问题 Data model and decisions 数据、模型与决策 第七章 Network Optimization Problems 网络最优化问题 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 Data, Model and Decisions 数据、模型与决策 第七章 Network Optimization Problems 网络最优化问题
本章内容 Topics P241 Chapter 7 Network Optimization Problems 网络最优化问题 Applications of Network optimization 网络最优化模型的应用 与第6章相比: ypes of Network Optimization Problem 有转运点 般不是全连通 网络最优化问题类型 图,所以要画 网络图 7 I Minimum- Cost flow problem最小费用流间题.在B用 72/7.3 Maximum flow problem最大流问题 阵 3.约束条件中用 7.4 Shortest path Problem 最短路问题 净流量 补充:最短路问题的另一个实际应用一货郎担问题 补充:最短路问题的另一个实际应用一中国邮路问题 7.5 Minimum Spanning Tree Problem最小支撑树问题 案例72资金的运作(最小费用流问题) RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 本章内容 Topics P241 Applications of Network Optimization 网络最优化模型的应用 Types of Network Optimization Problem 网络最优化问题类型 7.1 Minimum-Cost Flow Problem 最小费用流问题 7.2/7.3 Maximum Flow Problem 最大流问题 7.4 Shortest Path Problem 最短路问题 补充：最短路问题的另一个实际应用－货郎担问题 补充：最短路问题的另一个实际应用－中国邮路问题 7.5 Minimum Spanning Tree Problem 最小支撑树问题 案例7.2 资金的运作（最小费用流问题） 与第6章相比： 1. 有转运点，一 般不是全连通 图，所以要画 网络图 2. 在Excel中用 弧表示稀疏矩 阵 3. 约束条件中用 净流量
Chapter 7 Network Optimization Problems Applications of network Optimizatio络最优化问题 网络最优化模型的应用P241 网络在各种实际背景问题中以各种各样的形式存在。交 通、电子和通讯网络遍及我们日常生活的各个方面, 络规划也广泛用于解决不同领域中的备种问题,如生 分配、项自计划、广址选择、资源管理和财务策划等 等。 网络规划为描述系统各组成部分之间的关系提供了非常 有效的真观和概禽上的帮助,广泛应用于科学、社会和 近些年来,管理科学中一个振奋人心的发展是它的网络 最优化问题的方法论和应用方面都取得了不同寻常的飞 速发展。 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 Applications of Network Optimization 网络最优化模型的应用 P241 网络在各种实际背景问题中以各种各样的形式存在。交 通、电子和通讯网络遍及我们日常生活的各个方面，网 络规划也广泛用于解决不同领域中的各种问题，如生产 、分配、项目计划、厂址选择、资源管理和财务策划等 等。 网络规划为描述系统各组成部分之间的关系提供了非常 有效的直观和概念上的帮助，广泛应用于科学、社会和 经济活动的每个领域中。 近些年来，管理科学中一个振奋人心的发展是它的网络 最优化问题的方法论和应用方面都取得了不同寻常的飞 速发展
Chapter 7 Network Optimization Problems 网络最优化问题 Types of Network Optimization Problem 网络最优化问题类型P242 Minimum-Cost flow Problem 最小费用流问题 Maximum flow problem 最大流问题 Shortest path problem 最短路问题 Minimum Spanning Tree Problem 最小支撑树问题一唯一不是线性规划问题 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 Types of Network Optimization Problem 网络最优化问题类型P242 ▪ Minimum-Cost Flow Problem 最小费用流问题 ▪ Maximum Flow Problem 最大流问题 ▪ Shortest Path Problem 最短路问题 ▪ Minimum Spanning Tree Problem 最小支撑树问题 －唯一不是线性规划问题
7. 1 Minimum-Cost flow problem Chapter 7 最小费用流间题P242 Network Optimization Problems 网络最优化问题 例子:无限配送公司的问题(网络配送问题 是网络最小费用流问题的另外一个名称) 无限配送公司有两个工厂生产产品,这些产品需 要运送到两个仓库里。 配送网络图(网络模型) 80 units F 60ums目标是 1 produced needed通过配 送网络 DC 的运输 成本最 70 units F2 W2)90 units produced needed 小 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 F 1 D C F 2 W2 W1 80 units produced 70 units produced 60 units needed 90 units needed 7. 1 Minimum-Cost Flow Problem 最小费用流问题 P242 例子：无限配送公司的问题（网络配送问题 是网络最小费用流问题的另外一个名称） • 无限配送公司有两个工厂生产产品，这些产品需 要运送到两个仓库里。 • 配送网络图 （网络模型） 目标是 通过配 送网络 的运输 成本最 小