图与网络分析---最大流问题

1、图和网络分析、赵芳玲、图论是运筹学的重要分支，它是建构和处理离散数学模型的重要工具。 说明性的方法往往有助于解决人们用其他方法难以解决的问题。 图论的发展可以追溯到1736年欧拉发表的解决著名“哥白尼堡七桥问题”的论文。 由于这种数学模型和方法的直观形象，具有启发性和趣味性，深受人们的欢迎。 迄今为止，已广泛应用于系统工程科学、通信工程、计算机科学、经济领域。 传统的物理、化学、生命学也广泛使用图理论的模型方法。 设定图和网络分析、图的基本知识、最短问题、树和最小生成树、最大流问题、最小费用最大流问题、四、最大流问题(一)、基本概念1、网络：赋予权利的有向图D=(V，a ) 在d的各弧(vi，

2、vj)A中，有非负的cij，称为弧的容量。 这样的图d称为容量网络，简称为网络，记载为D=(V、a、c、Vs、Vt )。 2、产水量、可执行流、径流量、流入量： (1)产水量：在网络d上的各弧形定义的函数中，f(vi，vj)=fij称为弧形(vi，vj )上的产水量。 (2)可能的流程：将满足以下条件的流程称为可能的流程：1)容量制约：每个弧(vi，vj)A有0 fij cij。 2 )保存条件：关于使用的中间点，将顶点vi的流入量、顶点vi的径流量、f称为d上的可能的流。 其产水量v(f )将(起点vs )、(终点vt )、(5)零流电弧： fij0的电弧称为零流电弧。 (6)零以外的流动的

3、弧： fij0的弧是零以外的流动的弧。 (3)饱和弧：在可能的流程中将fijcij的弧称为饱和弧。 (4)非饱和弧：在可能的流程中将fijcij的弧称为非饱和弧。 例6下图示出了可能的流程，其中(容量限制，保存条件)，图中的零流圆弧，其馀为非饱和圆弧和零流圆弧。例7下图将一个可执行的流程、产水量v(f )=8、最大的流程、网络上的最大的可执行的流程称为最大的流程，所谓最大的流程问题是求出给定的网络的最大的流程，(2)最大的流程的算法、1、图制作计程仪程序、2， 用lingo8.0软件求最大流动，例8现在城市s的石油需要通过管道输送到城市t，中间有4个中转台v1，v2的v3和v4，城市和中转台的

4、连接和管道的容量求从城市s到城市t的最大流动，如下图所示。 模型3360集：节点/s、1、2、3、4、t/； arcs (节点，节点)/s，1 s，2.1，2，1，3，4，3，2，t 4，3，4，t/:c，f； endsets data: c=8 7 5 9 9 2 5 6 10； 数据最大值=流量； 大小(大小) 3360和(大小) -和(大小) 3360 f，大小(大小)=0； 求和，求和，求和，求和，求和； 法(arcs : bnd (0，f，c ) )； END、计程仪柱结构1、定径套定义部(setsendsets)2、数据输入部(dataenddata)3、其他部分(最优化目标和制约

5、) 全球最佳溶解热定检测at迭代：对象：00000可变性valuereductionflow 1.4.000000.000000 c (s1)8. 0000000. 000000 c (s1) 2 )7. 000000 c (1，2 )5. 000000 c (1，3 )9. 000000 c (2，4 )9. 000000 c (3)2. 000000 c (3，t )5. 000000 c (4，3 )6. 000000 c (4，3 ) 1 )7. 000000 f (s2)7. 000000.000000 f (1，2 )2. 000000 f (1，3 )5. 000000 f (2

6、，4 )9. 000000 f (3，2 )0. 000000 f (3)5. 00000 f (3) 5 t ) 9.000000全局最佳溶解热检测迭代：对象3360.00000可变数值流1.4.000000.000000 f (s1) 7.0000000 2 )7. 000000 f (1，2 )2. 000000 f (1，3 )5. 000000 f (2，4 )9. 000000-1.000000 f (3)2)0. 000000 f (3，t )5. 000000-1.000000 f (3，t ) sets :节点/s、1、2、3、t/； arcs (节点，节点)/s，1 s，2

7、 s，3.1，2，t 2，3，t 3，t/:c，f； endsets data: c=5 7 8 5 7 4 6 7； 数据最大值=流量； 大小(大小) 3360和(大小) -和(大小) 3360 f，大小(大小)=0； 求和，求和，求和，求和，求和； 法(arcs : bnd (0，f，c ) )； 电影结束， globaloptionolsolutionsolutionsolutionalsolutitytectity 33605 objectivedvalue 3360.00000 virverviralvaluerededcostflow 1.8.00000 . 5.00000 c (

8、s，2)7.000000c(s，3 )8. 000000 c (1，2 )5. 000000 c (1，t )7. 000000 c (2)3)4. 000000 c (2，t )6. 000000 1) 5.000000 -1.000000 F(S，2 )6. 000000 f (s3)7. 000000.00000 f (1，2 )0. 000000 f (1，t )5. 000000 f (2，3 )0. 000000 f (2， t )6. 000000-1.000000 f (3)7. 000000-1.000000，F(S，1) 5.000000 -1.00000 F(S，2)6.

9、000000f(s，3)7.0000000.00000f(1， 2 )0. 000000 f (1)5. 000000.000000 f (2，3 )0. 000000 f (2，T) 6.000000 -1.000000 F(3，T) 7.000000 -1.000000，流程18.00000，例如如图7-18所示，运输系统v1和v2是两个中转台。 显示的数字是线路的最大运输能力。 求出从产地到销售地的最大运输量。 解这是多发点的网络。为了用前面介绍的算法求出最大的流程，需要形成只有一个起点和一个终点的网络。 这并不难。 网络中的一个起点vs、一个终点vt、从vs到s1、s2的弧、从t1、t

10、2、t3到vt的弧、sets: nodes/vs、s1、s2、v1、v2、t1、t2、t3、vt/； arcs (节点、节点)/vs、s1 vs、s2 s1、t1 s1、v2 s2、v2 s2、t3 v1、t1v2、t2 v2、t3 t1、vt t2、vt t3、vt/:c、f； end sets data : c=272751212661822； 数据最大值=流量； 大小(大小) 3360和(大小) -和(大小) 3360 f，大小(大小)=0； 求和，求和，求和，求和，求和； 法(arcs : bnd (0，f，c ) )； 电影结束， globaloptionolsolutionsolu

11、tionsolutionfortheationrectity : objectivedvalue 33346.00000 virverviralvaluerededcostflow 4.6.00000 . 19.00000 f (vs，S2) 27.00000 0.000000 F(S1，T1) 10.00000 -1.000000 F(S1，V1) 5.000000 -1.000000 F(S1， v2)4. 000000. 000000 f (s2) v2) 15.000000. 000000 f (s 2，T3) 12.00000 0.000000 F(V1，t1)8.000000f(v

12、1，t2)0.000000f(v2， v1)3. 000000-1.000000 f (v2) t2)6. 000000-1.000000 f (v 2，t3) 10.000000f (t 1，vt ) 18.00000 f (t 2，vt)6.000000f(t3，vt )6. 000000 f VT) 22.00000 -1.000000，该运输系统的最大运输量为：练习：求出下图的网络最大流、最大流的产水量和最小截尾。 图中弧形旁边的数字是弧形的容量。 图c、设置3360节点/v 1、v2、v3、v4、v5、v6、v7/； arcs (节点、节点)/v 1、v2 v1、v3 v2、v5 v2、v4、v5 v4、v6 v5、v7 v6、v7/:c、f； 结束设置数据： c=1395554910； 数据最大值=流量； 大小(大小) 3360和(大小) -和(大小) 3360 f，大小(大小)=0； 求和，求和，求和，求和，求和； 法(arcs : bnd (0，f，c ) )； 13 (11 )，9 (9)，4 (0)，5 (5)，6(6)，5 (4)，5 (