中国人民大学信息学院：《运筹学》课程教学资源（PPT课件讲稿）第七章 网络最优化问题

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 例子：无限配送公司的问题（网络配送问题 是网络最小费用流问题的另外一个名称） • 无限配送公司有两个工厂生产产品，这些产品需 要运送到两个仓库里。 • 配送网络图 （网络模型） 目标是 通过配 送网络 的运输 成本最 小

Chapter 7 Network Optimization Problems 7.1 Minimun- Cost flow Problen网络最优化间题 最小费用流问题一术语P244 最小费用流问题的构成(网络表示): 1节点 nodes)(供应点净流量为正、需求点净流量为负 转运点净流量为零) 2弧(arcs):可行的运输线路(节点j>节点j), 经常有最大流量(容量)的限制 3决策变量:x;-通过弧(节点>节点j)的流量 RuC Information School, Ye Xiang 2007

Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 7. 1 Minimum-Cost Flow Problem 最小费用流问题－术语 P244 最小费用流问题的构成（网络表示）： 1.节点(nodes)（供应点-净流量为正 、需求点-净流量为负 、转运点-净流量为零 ） 2.弧（arcs）：可行的运输线路（节点i->节点j）， 经常有最大流量（容量）的限制 3.决策变量：xij－通过弧（节点i->节点j）的流量

Chapter 7 Network Optimization Problems Assumptions of Minimum Cost Flow Problem 最小费用流问题的假设P244 网络最优化问题 1.至少一个供应点 2.至少一个需求点 3.剩下都是转运点 通过弧的流只允许沿着箭头方向流动,通过弧的最大 流量取决于该弧的容量 5.网络中有足够的弧提供足够容量,使得所有在供应点 中产生的流都能够到达需求点 6.在流的单位成本已知前提下,通过每一条弧的流的成 本和流量成正比(目标函数是线性的) 7.最小费用流问题的目标在满足给定需求条件下,使得 通过网络配送的总成本最小(或总利润最大化) RuC Information School, Ye Xiang 2007

Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 Assumptions of Minimum Cost Flow Problem 最小费用流问题的假设 P244 1. 至少一个供应点 2. 至少一个需求点 3. 剩下都是转运点 4. 通过弧的流只允许沿着箭头方向流动，通过弧的最大 流量取决于该弧的容量 5. 网络中有足够的弧提供足够容量，使得所有在供应点 中产生的流都能够到达需求点 6. 在流的单位成本已知前提下，通过每一条弧的流的成 本和流量成正比（目标函数是线性的） 7. 最小费用流问题的目标在满足给定需求条件下，使得 通过网络配送的总成本最小（或总利润最大化）

Chapter 7 Network Optimization Problems Characteristic of solution 网络最优化问题 解的特征P244 具有可行解的特征:在以上的假设下,当且仅 当供应点所提供的流量总和等于需求点所需要 的流量总和时,最小费用流问题有可行解(平 衡条件)。 具有整数解的特征:只要其所有的供应量、需 求量和弧的容量都是整数值,那么任何最小费 用流问题的可行解就一定有所有流量都是整数 的最优解。 RuC Information School, Ye Xiang 2007

Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 Characteristic of Solution 解的特征 P244 ▪ 具有可行解的特征：在以上的假设下，当且仅 当供应点所提供的流量总和等于需求点所需要 的流量总和时，最小费用流问题有可行解（平 衡条件） 。 ▪ 具有整数解的特征：只要其所有的供应量、需 求量和弧的容量都是整数值，那么任何最小费 用流问题的可行解就一定有所有流量都是整数 的最优解

Chapter 7 Network Optimization Problems 无限配送公司的最小费用流问题网络最优化问题 的线性规划数学模型(补充) 决策变量xn:通过弧(节点1到节点的流量 总运输成本最小化 Min cost=S700xmw+S300xm1DC+ S200xpCwI+$400 pC- w2+ $400F2-DC+S900xF2-w2 约束条件(节点净流量、弧的容量限制,非负) (由于80+70=60+90,即总供应=总需求,平衡) 供应点F1:xH1w1+xDc=80 供应点F2 e2 -dc +m2- w2=70 转运点DC:xpcw1+xpCw2-(xm1DC+x2Dc)=0 需求点W1 tx DC-W1 需求点W2:xDCw2+x2w2=90 弧的容量限制:xH1DC、xpCw1、xDcw2、xpDc≤50 且 x:≥0 RuC Information School, Ye Xiang 2007

Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 无限配送公司的最小费用流问题 的线性规划数学模型（补充） 决策变量xij：通过弧(节点i到节点j)的流量 总运输成本 最小化 Min Cost = $700xF1-W1 + $300xF1-DC + $200xDC-W1 + $400xDC-W2 + $400xF2-DC + $900xF2-W2 约束条件(节点净流量、弧的容量限制，非负） （由于80＋70＝60＋90，即总供应＝总需求，平衡） 供应点 F1: xF1-W1 + xF1-DC = 80 供应点 F2: xF2-DC + xF2-W2 = 70 转运点 DC: xDC-W1 + xDC-W2 - (xF1-DC + xF2-DC ) = 0 需求点 W1: xF1-W1 + xDC-W1 = 60 需求点 W2: xDC-W2 + xF2-W2 = 90 弧的容量限制： xF1-DC 、 xDC-W1 、 xDC-W2 、xF2-DC 50 且 xij  0

无限配送公司的最小费用流问题 Chapter 7 的电子表格模型P245 Network Optimization Problems 网络最优化问题 列出了网络中的弧和各弧所对应的容量、单位流量成本 决策变量(可变单元格)为通过弧的流量x 目标单元格:计算流量的总成本 每个节点的净流量(总流出一总流入)为约束条件。供应点的净 流量为正,需求点的净流量为负,而转运点的净流量为0 窍门:用两个SUMF函数的差来计算每个节点的净流量(快捷且 不容易犯错) Distribution unlimited co minimum cost Flow Problem 2P246无限配送公司的最小费用流问题 决策变量:通过孤节点到节点的流量 从 流量对 容量单位成本 节点净流量供应/需求 678 F1 5700 80 80 7 F1DC 300 70 70 0000 <=50 5200 DC 0 DCW2 50 400 F2 5400 W2 -9 11F2W2 590 总成本5110000 RuC Information School, Ye Xiang 2007

Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 无限配送公司的最小费用流问题 的电子表格模型P245 • 列出了网络中的弧和各弧所对应的容量、单位流量成本 • 决策变量（可变单元格）为通过弧的流量xij • 目标单元格：计算流量的总成本 • 每个节点的净流量（总流出－总流入）为约束条件。供应点的净 流量为正，需求点的净流量为负，而转运点的净流量为0 • 窍门：用两个SUMIF函数的差来计算每个节点的净流量（快捷且 不容易犯错）