文档介绍：Data, Model and Decisions
数据、模型与决策
Session 5
Network Optimization Problems
网络最优化问题
Types work Optimization Problem
网络最优化问题类型
Minimum work Flow Model
最小费用流问题
Maximum Flow Problems
最大流问题
Shortest Path Problem
最短路问题
Minimum Spanning Tree Problem
最小支撑树问题
一、基本概念
1. 发点和收点(源和汇)
设点 v 是有向图 D 的一个顶点
•发点:如果不存在以v为终点的弧,则称v是D的一个发点(源)
•收点:如果不存在以v为始点的弧,则称v是D的一个收点(汇)
2. 容量和流量
•容量:网络中某条弧(vi,vj)的最大通过能力称为该弧的
容量,记做 cij 。
•流量:通过弧(vi,vj)的某种流的实际数量称为该弧的
流量,记做 fij 。
3. 可行流和最大流
发点 vs 流出的流量为 f ,则汇入收点vt 的流量为-f
满足下述条件的流称为可行流
(1)可行性条件:对每一条弧(vi,vj)∈ A ,均应有
0 ≤ fij ≤ cij
即网络的每条弧上的流量均为非负值,且不超过容量。
(2)平衡条件:
流入任何一个中间点的流量必等于流出该顶点的流量
对vi ≠ vs , vt ∑ f ij −∑ f ji = 0
j j
发点 vs 流出与流入量之差为发点的流量
f − f = f
对发点 vs ∑ sj ∑ js
j j
收点 vt 流出与流入量之差为发点的流量的负值
对收点 vt ∑ f tj −∑ f jt = − f
j j
实际上即表示收点 vt 的接收量等于发点 vs 的流出量。
f 叫做可行流的流量。
v2 5,3 v3
4
,
2,
2 4
, 1
7 1
,
2
5,4 8,2
v1 v4 v5
弧旁第一个数字为容量,第二个数字为流量,即 cij,fij
满足可行条件和平衡条件,因而为一可行流。f = 6
显然,零流 fij= 0 是一个可行流。
因而可行流总是存在的。
流量最大的可行流叫做网络的最大流。
实际上最大流问题是一个线性规划问题,可描述为
max f
0 ≤ f ij ≤ cij
⎧ f v = v
⎪ i s
∑ f ij −∑ f ji = ⎨ 0 vi ≠ v s ,vt
j j
⎩⎪− f vi = vt
Applications work Optimization
网络最优化模型的应用
网络在交通、电子和通讯网络遍及我们日常生活的
各个方面,网络规划也广泛用于解决不同领域中的
各种问题,如生产、分配、项目计划、厂址选择、
资源管理和财务策划等等。
网络规划为描述系统各组成部分之间的关系提供了
非常有效直观和概念上的帮助,广泛应用于科学、
社会和经济活动的每个领域中
无限配送公司的问题
无限配送公司有两个工厂生产产品,这些产品
,工
厂2生产70个单位,
库2需要90个单位,工厂1和仓库1之间以及工
厂2和仓库2之间有一条铁路运输轨道,卡车司机
总共可以从工厂运输50个单位到配送中心,然后
可以从配送中心运输50个单位到仓库.
问题:每条路线运送多少单位的产品?
Network representation
网络表述
80 units F1 W1 60 units
produced needed
DC
70 units F2 W2 90 units
produced needed
这种描述还有其他应用吗?
想想看!