Management Operations Research 管理运筹学
主讲教师 曹翠珍
山西财经大学工商管理学院
§4 最大流问题
由一个生动的自编案例引入课题
突如其来的SARS的肆虐，明显地暴露出了我们对突发公共卫生事件应急处理能力的严重不足、应急反应的行动迟缓、手段匮乏。更重要的是给我国正在发展中的公共卫生事业敲响了警钟：建立一个反应灵敏、运转有效的应急反应机制刻不容缓。那么，如何才能真正做到反应灵敏、运转有效？
《突发公共卫生事件应急条例》在不到一个月的时间内应时而生了。《条例》的第五条明确规定： 突发事件应急工作，应当遵循预防为主、常备不懈的方针，贯彻统一领导、分级负责、反应及时、措施果断、依靠科学、加强合作的原则。利用最大流问题就可以找到一个使病人得到及时救治的最佳方案。
我们假设A城市有一个定点接收医院、一个急救中心、一些指定发烧门诊和若干救护车。当急救中心接到呼救时，首先派出救护车将病人送到指定的发烧门诊进行初诊，然后根据初诊结果，将病人分为“非典”病人、疑似病人、其它病人。如果是前两种，就要送到指定医院去进行及时抢救、隔离治疗。如果是后一种，送入其它医院进行治疗。那么问题是如何利用这些有限的资源，最大限度地输送、接收病人，使他们得到及时诊断、抢救、隔离、治疗？
Example: 非典病人的问题
如图所示：
S1——急救中心
S2——定点接收医院
S3——其它医院
T1、T2、T3——三个发烧门诊
箭头——输送路线
方括号内数字——对应路线上最多可输送的病人量
问题：确定通过每条路线输送多少病人，使得一天内输送、接收病人量最大？
Example: 非典病人的问题
·
[30]
[10]
[30]
S2
[40]
[50]
[15]
S1
T1
T2
T3
S3
[20]
[20]
[50]
Maximum Flow Problem
最大流的问题
最大流问题：
最大流问题是管理科学中网络最优化问题的一个特殊类型。最大流问题是解决怎样使得配送网络中流量最大的问题。
应用：
通过从供应商到公司供应网络的流量最大。
通过管道运输系统的油的流量最大。
最大化通过输水系统的水的流量。
通过交通网络的车辆的流量最大。
最大流问题的一些术语
[30]
[10]
[30]
S2
[40]
[50]
[15]
S1
T1
T2
T3
S3
[20]
[20]
[50]
最大流问题可以用网络模型表示。
网络中的圆圈叫做节点（nodes）。
最大流问题的网络中所有流起源于一个节点，这个节点叫做源 （source），所有的流终止于另一个节点，这个节点叫做收点（sink）。中间的节点叫做转运点。 最大流问题的变形通常可以有多个源和收点。
网络中的箭头称为弧(arcs)。
允许通过某一条弧的最大流量称为该弧的容量(capacity)。
最大流问题的基本假设
1、通过每一个弧的流只允许沿着弧的箭头所指方向流动。由源发出的所有弧背向源，而所有终结于收点的弧指向收点。
2、所有节点产生的净流量=流出—流入。
3、转运点（transshipment node）产生的净流量为零。
4、最大流问题的目标是使得从源到收点的流量最大。这个流量的大小可以用两种等价的方法来衡量，分别叫做从源点出发的流量和进入收点的流量。
步骤1：定义问题、收集数据。
步骤2：绘制网络图形，构建数学模型。
步骤3：用计算机程序进行求解。
步骤4：测试模型并在必要时进行修正。
步骤5：应用模型分析问题并提出建议， 进行 辅助管理决策。
解决问题的方法步骤
如图所示：
S1——急救中心
S2——定点接收医院
S3——其它医院
T1、T2、T3——三个发烧门诊
箭头——输送路线
方括号内数字——对应路线上最多可输送的病人量
问题：确定通过每条路线输送多少病人，使得一天内输送、接收病人量最大？
Example: 非典病人的问题
·
[30]
[10]
[30]
S2
[40]
[50]
[15]
S1
T1
T2
T3
S3
[20]
[20]
[50]
建立数学模型
设9个决策变量分别为：
=急救中心到发烧门 诊i 输送量 i=1，2，3
=发烧门诊1到定点接收医院输送量
=发烧门诊2到定点接收医院输送量
=发烧门诊3到定点接收医院输送量
=发烧门诊1到其它医院输送量
=发烧门诊2到其它医院输送量
=发烧门诊3到其它医院输送量
MAX 总输送量 =
[30]
[10]
[30]
S2
[40]
[50]
[15]
S1
T1
T2
T3
S3
[20]
[20]
[50]
约束条件：
[30]
[10]
[30]
S2
[40]
[50]
[15]
S1
T1
T2
T3
S3
[20]
[20]
[50]
用EXCEL求解
[30]
[10]
[30]
S2
[40]
[50]
[15]
S1
T1
T2
T3
S3
[20]
[20]
[50]
可行解方案
约束条件
决策报告
50
45
100
最大输送量
10
20
—
—
—
发烧门诊3
40
10
—
—
—
发烧门诊2
5
15
—
—
—
发烧门诊1
—
—
30
50
20
急救中心
其它医院
定点接收医院
发烧门诊3
发烧门诊2
发烧门诊1
目的地
出发地
根据这一具体的决策方案，不仅可以最大限度地利用有限的稀缺资源，采取有效、及时地紧急措施。从而达到最大限度地输送病人，使病人得到最及时地治疗和隔离，对有效控制病情起到非常重要的作用。 而且可以结合当时的病情变化及医疗卫生条件的不断改善，分析和预测今后的调度指挥方案是否需要调整和怎样调整。真可谓“夫运筹帷幄之中，决胜于千里之外”。
分析
Summary
要点
最大流问题
最大流问题的概念及术语：
网络模型、节点、转运点、弧、容量、源
最大流问题的假设
单方向
净流量=流出—流入、转运点的净流量=零
目标：流量最大
建模与求解
最大流问题的应用
例1 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？
v5
6
3
5
2
2
2
4
1
2
6
3
v1
v2
v7
v4
v3
v6
图2
设弧(vi,vj)上流量为fij，
网络上的总的流量为F，则有：
v5
6
3
5
2
2
2
4
1
2
6
3
v1
v2
v7
v4
v3
v6
图2
从源点出发的流量
=进入收点的流量
转运点的净流量=零
在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件：
中间点它的总流入量必须等于总流出量；
发点的流出量必须等于收点的总流入量。
其后面两个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0≤fij≤ cij。
最大流问题的应用
求解
我们把满足守恒条件及流量可行条件的一组网络流 {fij}称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。
用“管理运筹学软件”求解
我们把例2的数据代入以上线性规划模型，用“管理运筹学软件”，马上得到以下的结果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。
最优值（最大流量）=10万加仑/小时。
在求解网络中最大流问题时,我们常常还考虑“费用”多少的问题。
——最小费用最大流问题
§5 最小费用最大流问题
(4,4)
(6,6)
(3,4)
(5,7)
(2,5)
(2,4)
（2,3）
(1,3)
(2,8)
（3,2）
v1
v2
v5
v7
v4
v3
v6
(6,3)
如下图： 给了一个带收发点的网络，对每一条弧（Vi,vj），除了给出容量Cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总运送费用最小。
举例
例2 由于输油管道的长短不一，所以在例1中每段管道（ vi,vj ）除了有不同的流量限制cij外，还有不同的单位流量的费用bij ，cij的单位为万加仑/小时， bij的单位为百元/万加仑。从采地 v1向销地 v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。
这个最小费用最大流问题可以分两步走来解决：
第一步，先求出此网络图中的最大流量F，这已在例1中建立了模型，并通过管理运筹学软件已经获得结果。
第二步，在最大流量F的所有解中，找出一个最小费用的解。即：只要在例1的约束条件上，再加上总流量必须等于F的约束条件：f12=f14=F,即可。
设弧（vi,vj）上的流量为fij，这时已知网络中最大流量为F，目标函数显然是求其流量的最小费用。
由此得到线性规划模型如下：
最小费用最大流问题的建模
用管理运筹学软件，可求得如下结果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。
其最优值(最小费用)=145百元。
如果我们把例2的问题改为：每小时运送6万加仑的石油从采地v1到销地v7最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。
想到什么？
一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij的网络中，求一个给定值f的流量的最小费用，这个给定值f的流量应小于等于最大流量F，否则无解。
求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可。在例2中只要把f12+f14=F改为f12+f14=f=6得到了最小费用流的线性规划的模型了。
Summary
要点
最大流问题
最大流问题的概念及术语：
网络模型、节点、转运点、弧、容量、源
最大流问题的假设
单方向
净流量=流出—流入、转运点的净流量=零
目标：流量最大
最小费用大流问题
可以看作最大流问题的一个扩展（费用最小）
可以看作运输问题中的转运问题
作业
1、P254
习题4 、习题5
2、上机练习求解
