第八章-图与网络模型应用运筹学

1、第6章 Network Analysis图与网络模型,1Introduction to Networks 基本概念 2 Shortest Path Problems 最短路问题 3Minimum spanning tree 最小生成树问题 4 Maximum Flow Problems 最大流问题 5Minimum-Cost Flow Problems 最小费用最大流问题,1,实例一: Seervada Park P266 黙登公司,图中线上数据表示道路的距离， O 表示入口，子母表示站点（控制点）三个问题：(1)从入口O到最美景点T 的最短路？OT smallest total distan

2、ce (2) 需要在所有站点安装电话线保证通信联系，需要在那些道路下铺设电话线，使总电话最少? A minimum total number of miles of telephone line installed; (3) 公园在每条道路上安排了电车，每条道路车辆的运能有一定限制，问如何安排道路上的车次，使从入口到景点T 的运能最大？How to route the various trips to maximize the number of trips that can be per day without violating the limits on any individual r

3、oad.,图 6-1,二、哥尼斯堡七桥问题,东普鲁士的哥尼斯堡城中，有一条普莱格尔河，河中有两个岛屿（奈佛夫岛），河上建有七座桥，将岛与两岸陆地相连（图6-2）。当地居民喜欢散步，并提出这样一个问题：若从岸或岛上任一处陆地出发，能否通过每座桥正好一次而回到原地。,图 6-2 a,A,B,C,D,尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图6-2b所示图形的一笔画问题。,欧拉在他的论文中证明了这是不可能的:不存在从某个点出发，经过每座桥一次且只能一次，最终回到原出发地的方案,图6-2b,三、四色问题,四色问题的提出来自英国，1852年，毕业于伦敦大学的格思里(F

4、rancis Guthrie)来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”这个结论能不能从数学上加以严格证明呢？他与在大学念书的弟弟决心试一试。兄弟二人为证明这一问题使用了一大叠稿纸，可研究工作没有任何进展。1852年10月23日，他的弟弟拿这个问题请教他的老师、著名数学家德摩尔根(Augustus de Morgan)，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密尔顿爵士(Sir William Hamilton)请教。但直到1865年哈密尔顿逝世为止，这个问题也没有得到解决

5、。,1878年6月13日，英国当时著名的数学家凯利(Arthur Cayley)正式向伦敦数学学会提出这个问题，之后，四色猜想开始成了世界数学界关注的问题。许多一流的数学家纷纷加入研究，1879年，著名的律师兼数学家肯普(Alfred Bray Kempe)提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此解决了。11年后，即1890年，数学家赫伍德(Percy John Heawood)以自己的精确计算指出肯普的证明是错误的，但该方法经补救后可用来证明五色定理。后来，越来越多的数学家虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马(

6、Fermat)猜想相媲美的难题。,进入20世纪以后，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。美国数学家富兰克林(Franklin)于1922年证明了25国以下的地图都可以用四色着色，1926年，结果推进到27国，1938年，推进到31国，1940年，推进到35国，1970年，推进到40国，随后又推进到了96国。后来，由于计算机性能的迅速提高，以及人机对话的出现，大大加快了四色猜想证明的进程。1976年6月，美国数学家阿佩尔(Kenneth Appel)与哈肯(Wolfgang Haken)经过整整4年的紧张工作，在伊利诺斯大学的两台不同计算机上，花费了1200个小时，作了100亿

7、个判断，终于完成了四色定理的证明。,四色猜想的计算机证明，轰动了世界。它不仅解决了一个历时100多年的难题，而且有可能成为数学史上一系列新思维的起点。不过也有一些数学家并不满足于计算机取得的成就，他们仍在寻找着简捷明快的纯数学证明方法。1995年，中国学者李宏棋给出了一个数学证明，收录于中国科学技术文库数理科学和化学卷。,1图与网络的基本概念,图论中图是由点和边构成，可以反映一些对象之间的关系。 例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图6-3就是一个表示这种关系的图。,(v1) 赵,(v2)钱,(v3)孙,(v4)李,(v5) 周,(v6)吴,(v7)陈,e2,e1,e3,

8、e4,e5,图6-3,2,图论中所考察的图不同于以往几何学与分析学中的图形，这里的图只考虑点与点之间由线连接的关系。至于画成直线还是曲线，画得长些还是短些，画在这儿还是那儿，都无关紧要。也就是说，点线位置可随意安排，线长不代表实际长度。,1图与网络的基本概念,无向图： 由点和边构成的图，记作G=（V，E）。 有向图： 由点和弧构成的图，记作D=（V，A）。,5,Graph (Network ) G = (V, E) Node set (Vertex set) V = v1, v2 , v3 , v4 , v5 顶点集 弧集 Arc Set E =(v1, v2), (v1, v4 ), (v2

9、, v3 ), (v2, v4 ), (v3, v4 ), (v3, v5 ), (v4, v5 ), (Edge set) (边集) 有向弧Directed Arc 无向弧(边)Undirected Arc P54,中文书中称赋权的图为网络,v2,v3,v1,v4,v5,v2,v3,v1,v4,v5,图6-4,图 6-5,一条链是(A Path)某些点与(连接这些点)的边的交替序列。无重复顶点和重复边的链称为初等链 图 6-5 中v1 v2 v3v4 v5 为一条链，且为一条初等链， 而v1 v4v2 v3v4 v5 不是初等链 两个顶点相同的边称为环， e22 为环 两个顶点之间的边数2时

10、,叫多重边。 v1 ，v2 之间有多重边 有多重边的图称为多重图，无环且无多重边的图称为简单图。这里，主要研究简单图 圈Cycle: 起点和终点相同 的链称为圈。 图6-6中 v1 v2 v4v3 v1为一个圈 简单圈：如果一个圈中所含的边 均不相同 初等圈：除起点和终点外链中所 含的点 均不相同的圈；,点的次为以顶点为端点的边的条数。记为d(v)或deg(v)。 当d(v) = 0，称顶点v为孤立点；当d(v)1，称顶点v为悬挂点； 当d(v)为奇（偶）数，称顶点v为奇（偶）点。 赋权图：对一个无向图G的每一条边(vi, vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,

11、vj)上的权。 连通图：对无向图G，若任何两个不同的点之间，至少存在一条链则G为连通图。 网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。,弧容量arc capacity (cij) : The maximum amount of flow allowed through an arc is referred to as the capacity of that arc. Each node where the net amount of flow generated (outflow minus infl

12、ow流出量流入量0) is a fixed positive number is a supply node（供应节点） Each node where the net amount of flow generated is a fixed negative 负数number is a demand node(需求节点) Any node where the net amount of flow generated is fixed at zero is a transshipment node（转运节点）. Having the amount of flow out of the node

13、equal the amount of flow into the node is referred to as conservation of flow 流量守恒,欧拉圈Eulerian cycle ：连通图中经过每一条狐(边)一次且一次的圈 a closed path that passes through each arc exactly once 必要条件：每个顶点均为偶点。因为除了起始点，每个顶点的次等于2顶点在圈中出现的次数 Necessary condition: each node has an even degree.Why necessary? The degree of

14、a node j is twice the number of times j appears on the path (except for the initial and final node of the walk.) 定理. 一个连通图存在欧拉圈当且仅当图中每个顶点均为偶点 A graph has an eulerian cycle if and only if the graph is connected and every node has even degree. 欧拉链：经过每一条狐(边)一次且一次的一条（非封闭）链Eulerian path: a path that is n

15、ot closed and passes through each arc exactly once 定理.一个连通图存在欧拉链当且仅当图中除两个顶点外，其它顶点均为偶点。 A graph has an eulerianpath if and only if exactly two nodes have odd degree and the graph is connected.,殴拉圈的应用Eulerian cycles and extensions are used in practice 邮递路程Mail Carrier routes: 以最少时间参观城市每个街区一次visit each

16、 city block at least once minimize travel time other constraints in practice? 废物回收路径Trash pickup routes visit each city block at least once minimize travel time other constraints in practice?,2最短路问题,最短路问题：对一个赋权的有向图D中的指定的两个点vs和vt找到一条从 vs 到 vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从vs到vt的最短路。这条路上所有弧的权数的总和被称为从vs

17、到vt的距离。 一、求解最短路的Dijkstra算法(双标号法永久与临时标号) 步骤： 1.给出点v1以永久标号(d(v1)0, v1),第一个数0表示v1到自己的距离(以后第一个数d(v)表示起点到这个标号点v的最短距离，第二坐标表示前趋点，为了便于用计算机计算，可以用顶点的下标1表示。算法将顶点分成永久标号点集合P和其他点集合J 2.找出最新已永久标号的点的集合IP，临时标号和没标号点的集合J以及与新永久标号点想连的弧的集合,如果上述弧的集合是空集，则计算结束。如果vt已标号 (d(vt),vk )，则 vs 到vt的距离为d(vt)，而从vs 到vt的最短路径，则可以从vk 反向追踪到起

18、点vs 而得到。 如果vt 未标号，则尚未找到从vs 到vt 的最短路。如果上述的弧的集合不是空集，则转下一步。 3. 假定vi是新标号的点，考察以vi为起点的所有弧(vi,vj)(vjJ)，计算数值 lijd(vi)wij 。令新的d(vi)=min lij, d(vj) ，根据需要修改前趋点。 在所有的d(vj)(vjJ) ， d(vu)=min d(vj),vjJ , 对顶点vu进行永久标号,vu为新永久标号点vu P, 返回步骤2。,例一求 SEERVADA 公园O到T的最短路,(0, O),(2, O),(5, O),(4, O),(4, A),(7, O),(9, A),7=min

19、4+3, 4+4,(8, B ),B E,(14, E),(13, D),O到T的最短路为：O A BD T 和O A B ED T 路长d(O,T) = 13,可用表格表示上述迭代,例二，用Dijkstra算法求下图16的最短路,记d(i )为从1到i 路径的长度Suppose that d(i) is the length of some path from node 1 to node i. wij 为(i, j)的长度弧Suppose that there is an arc (i, j) of length wij. 因此，从1 到j 的路长至多等于d(i) + wij 。Then

20、there is a path from node 1 to node j of length at most d(i) + wij.,图6-7,A Key Procedure in Shortest Path Algorithms,在每次迭代中，记d(i )为从1到i 路径的长度，如果不存在路径，记d(j) = 。At each iteration d(j) is the length of some path from node 1 to node j. (If no path is known, then d(j) = ) 更新标号 (i) 对于每条弧 For each (i, j) A

21、(i)， 若d(j) d(i) + wij ，则记新的d(j) : = d(i) + wij 前趋点为pred(j):=i;,在上图中, 原来d(j) =78，当找到从1到i的路P的路长为72时，需要修改d(j) 为72 。the best path from 1 to j has length 78 But P, (i, j) is a path from 1 to j of length 72.,迭代Initialize,Solved node 1,LIST = 2, 3 d(2)=2, d(2)= 4,Solved node 2,2,Min 2,4= 2,将顶点2 永久标号,LIST 3

22、, 4, 5 d( ) = 3, 6, 4,Solved node 3,Min 3,4,6= 3，将顶点3 永久标号,Solved node 5,LIST 4, 6 d( ) = 6, 6,Trace back the path from node 6 to node 1 using the predecessors.1到6的最短路12 5 6，路长d(6)=6,The shortest path from node 1 to node 6,从1到各点的最短路如下The shortest path from node 1 to node i,最短路问题一个应用,例3 设备更新问题。某公司使用一

23、台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。 已知：设备每年年初的价格表 p236 设备维修费如下表,11,例3的解： 将问题转化为最短路问题，如图6-8： 用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的 设备一直使用到第j年年初。 把所有弧的权数计算如下表：,59,41,12+5+6 =23,12,11+5+6 =22,第1年初购买费加两年维护

24、费,第4年初购买费加两年维护费,图6-8,11+5+6+8=30,(继上页) 把权数赋到图中，再用Dijkstra算法求最短路。 最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1 v3 v6和 v1 v4 v6,13,3最小生成树问题,树是图论中的重要概念，所谓树就是一个无圈的连通图。,图6-9中，(a)就是一个树，而(b)因为图中有圈所以就不是树， (c)因为不连通所以也不是树。,14,给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图6-10中，(b)和(c)都是(a)的生成子图。 如果图G的一

25、个生成子图还是一个树，则称这个生成子图为生成树，在图6-10中，(c)就是(a)的生成树。 最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。,(a),(b),(c),15,简单的算法 The Simple Algorithm 1、避圈算法,选择第一条边：选择成本最低的备选边 选择下一条边：在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边（不能有圈） 重复第二个步骤，直到所有的节点都有一条边（可能会有多于一条边）与其相连 此时就得到了最优解（最小支撑树）,2、求解最小生成树的破圈算法。算法的步骤： 在给定的赋

26、权的连通图上任找一个圈。 在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。 如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。,用避圈法求公园图的最小生成树首先选择最小边,Application of Algorithm to Modern Corp.: Second Link,Application of Algorithm to Modern Corp.: Third Link,Application of Algorithm to Modern Corp.: Fourth Link,Application o

27、f Algorithm to Modern Corp.: Fifth Link,Application of Algorithm to Modern Corp.: Final Link,生成树很多，我们需要找出最小的生成树,最小生成树一些实际应用,Design of telecommunication networks (computer networks, lease-line telephone networks, cable television networks, etc.) Design of a lightly-used transportation network to mini

28、mize the total cost of providing the links (rail lines, roads, etc.) Design of a network of high-voltage electrical power transmission lines. Design of a network of wiring on electrical equipment (e.g., a digital computer system) to minimize the total length of the wire. Design of a network of pipel

29、ines to connect a number of locations.,电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计 低负荷运输网络的设计，使得网络中提供链接的部分（如铁路、公路等 等）的总成本最小 高压输电线路网络的设计 电器设备线路网络（如数字计算机系统）的设计，使得线路总长度最短 连接多个场所的管道网络设计,4 最大流问题 Maximum Flow Problems,定义9 设一个赋权有向图D=（V,A）,在V中指定一个发点vs和一个收点vt ,其它的点叫做中间点。对于D中的每一个弧(vi ,vj) A,都有一个非负数cij叫做弧的容量。我们把这样的图D叫做一个网

30、络系统，常记做D=（V，A，C）(三元组表示）。 网络D上任一弧(vi ,vj)上有流量fij，称函数F = f(vi ,vj) = fjj 为网络D的一个流。,定义10 网络上的一个流F叫做可行流，如果F 满足以下条件 （1）容量条件：对于每一个弧（vi ,vj）A,有 0 fij cij . （2）平衡条件：,对于发点vs,有,对于收点vt,有,对于中间点vk ，有,v(F) 称为可行流F的流量,下图网络图中F是可行流，,( v1, v3) 是非饱和弧； ( v4, v3) 是饱和弧； u1: vs v1 v3 vt 是一条增广链；u2: vs v2 v4 v1 v3 vt 也是一条增广链

31、, 对于u2，( v4, v1) 是反向弧,通过配送网络的流量最大 从供应商到加工设施的流量最大 输油管道系统的油的流量最大 输水管道流量最大 运输网络中车流量最大.,目标是使从发点到收点的总流量最大，这个流量可用发点发出流量总和或流入收点的总流量来衡量 The objective is to maximize the total amount of flow from the source to the sink. This amount is measured in either of two equivalent ways, namely, either the amount leavi

32、ng the source or the amount entering the sink.,求最大流可用线性规划来表示,主要目标与约束为,例六 The BMZ Distribution Network,鹿特丹,斯图加特,里斯本,波尔多,纽约,新奥尔良,洛杉矶,A Network Model for BMZ,s.t. fSR= fRN fSB= f BNY + f BNO fSL= f LN f BNY + fRN = fNYA f BNO + f LN = fNOA f NOA + fNYA = fSR + fSB + fSL fSR50； fSB 70； fSL 40； fRN 60；f

33、LN 30； f BNY 40； f BNO 50； fNYA 80 ；fNOA 70 f ij0,4最大流问题,最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。 一、最大流的数学模型 例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？,19,4最大流问题,我们可以为此例题建立线

34、性规划数学模型： 设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：,20,在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0fij cij。我们把满足守恒条件及流量可行条件的一组网络流 fij称之为可行流,(即线性规划的可行解)，可行流中一组流量最大(也即发出点总流出量最大)的称之为最大流（即线性规划的最优解）。 我们把例6的

35、数据代入以上线性规划模型，用软件得到以下的结果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最优值（最大流量）=10。,21,求最大流的标号方法（增广链算法）,标号法用一个二维数组（vi , l(vj)）对点进行标号，第一个标号表示这个标号是从那一点得到的。以便找出增广链。第二个标号是为了 用来确定增广链上的调整量。从发点第vs 开始标号，通过查号过程寻找增广链L，如果存在增广链L，就沿着增广链L调整流量以增加流量。然后重新标号和查号，寻找下一条增广链，如果不存在增广链，则找到最大流 一、标号过程，设 为可

36、行流 1 . 给发点vs 标号（0，+） 2 .选择一个已标号的点vi，对于vi一切未标号的邻接点vj，按下列规则处理： (1) 如果在弧（vi ,vj）上，fij cij,那么给vj 标号 (vi ,l(vj) 。 其中 l(vj) = min l(vi), cij fij。这时vj 成为标号未检查的点。,(2) 如果在弧（vj ,vi）上，fji 0,那么给vj 标号(vi , l(vj). 其中 l (vj) = min l(vi), fji 。 这时vj 成为标号未检查点。 3 重复步骤（2），直到vt被标号或标号过程无法进行下去，既不再有顶点可标号，则标号法结束。 若收点vt被标号，

37、则存在一条增广链，转调整过程 二、调整过程 （1）以 vt 标号中第二个数l (vt) 为调整量，进行调整，令,（2）去掉所有 标号，回到第一步，对可行流 重新标号,在运筹学导论的求最大流的增广链算法An augmenting path algorithm中，每次找到增广链进行流量调整时，将原来容量调整为剩余容量(原容量新增流量)，而不采用标号的方法。当某条弧的剩余容量为0时，这条弧为饱和弧，流量无法增大，(无法对右端点进行标号)管理运筹学也采用同样方法。,Min7,5,6=5,Step 1,Step 2,(O, 7 ),(B, 5 ),(E, 5 ),A,O,2,3,B,D,2,5,E,C,

38、4,T,0,1,0,0,4,0,0,0,2,4,0,5,1,1,5,6,3,0,3,(0,),(O,5),Min5,3,9=3,(A,3),(D,3),Min2,3,5=2,Min4,4,1,3=1,A,O,1,4,B,D,0,7,E,C,1,T,3,0,0,1,0,4,0,2,1,4,0,0,6,1,8,1,3,(0,),(O,1),1,3,(C,1),(-E,4),(A,1),4求最大流的增广链算法An augmenting path algorithm,二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图: (a)和 (b)、(c)和(d)的意义相同。 用以

39、上方法对例6的图的容量标号作改进，得下图,22,求最大流的基本算法 （1）找出一条从发点到收点的路，在这条路上的每一条弧顺流和方向的容量都大于零。如果不存在这样的路，则已经求得最大流。 （2）找出这条路上各条弧的最小的顺流的容量fp，通过这条路增加网络的流量fp 。 （3）在这条路上，减少每一条弧的顺流容量fp ，同时增加这些弧的逆流容量fp ，返回步骤（1）。 用此方法对例6求解： 第一次迭代：选择路为v1 v4 v7 。弧（ v4 , v7 ）的顺流容量为2， 决定了fp =2，改进的网络流量图如下图：,P245,23,第二次迭代：选择路为v1 v2 v5 v7 。弧（ v2 , v5 ）

40、的顺流容量为 3，决定了fp =3，改进的网络流量图如下图： 第三次迭代：选择路为v1 v4 v6 v7 。弧（ v4 , v6 ）的顺流容量为 1，决定了fp =1，改进的网络流量图如下图：,v4,24,第四次迭代：选择路为v1v4 v3 v6 v7 。弧（ v3 , v6 ）的顺流容 量为2，决定了fp = 2，改进的网络流量图如下图： 第五次迭代：选择路为v1 v2 v3 v5 v7 。弧（ v2 , v3 ）的顺流容 量为2，决定了fp =2，改进的网络流量图如下图：,25,经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为1

41、0。 最大流量图如下图：,26,最大流流量,在求解过程中寻找的从发点到收点的简单链称为增广链，增广链满足的条件：正向弧（与链方向相同）是非饱和弧（ 0 fij cij 非饱和弧的作用是增大流量），逆向弧（与链方向相反）是非零流弧（ 0 fij cij非零流弧的作用是可以减少流量），当不存在增广链时，就找到最大流,BMZ with Multiple Supply and Demand Points,BMZ has a second, smaller factory in Berlin. The distribution center in Seattle has the capability o

42、f supplying parts to the customers of the distribution center in Los Angeles when shortages occur at the latter center. Question: How many units should be sent through each shipping lane to maximize the total units flowing from Stuttgart and Berlin to Los Angeles and Seattle?,Excel求解最大流问题,BMZ案例研究的电子

43、表格求解BMZ Case Study,BMZ案例求解,案例研究,节点净流量,最小费用流问题的假设 Assumptions of a Minimum-Cost Flow Problem,网络是有向和连通的 至少有一个供应点At least one of the nodes is a supply node. 至少有一个需求点At least one of the other nodes is a demand node. 余下节点为转运点 通过弧的流量只允许沿着箭头方向流动，其最大流量有弧的容量给出 网络中有足够提供充分容量的弧，使得供应点产生的所有流量都能够到达所有的需求节点需求点 通过每条弧

44、的流的成本与流量成正比 最小费用流的目标是在满足给定需求的条件下，使得通过网络供应的总成本最小,5 最小费用流问题Minimum-Cost Flow Problem,最小费用流问题的线性规划模型,Any minimum cost flow model consists of a set of nodes: 供应点S的供应量si ,Supply node(s), with supply si 需求点的需求量di Demand node(s), with demand di 转运点Transshipment nodes A set of arcs from node i to node j 从节点

45、i流向节点j 的弧集 单位流量的成本为bij with cost bij 容量限制kij some with limited capacity kij 线性规划模型 LP Formulation:,Let xij = 从节点i流到节点j 的流量flow from i to jMinimize Cost = ij bij xijsubject to Capacity: xij kij and xij 0.,Properties of Minimum-Cost Flow Problems,The Feasible Solutions Property:可行解性质 最小费用流量问题有可行解的必要条件

46、为供应点所产生的流量总和等于需求点吸收流量总和 The Integer Solutions Property:整数解性质 As long as all the supplies, demands, and arc capacities have integer values, any minimum-cost flow problem with feasible solutions is guaranteed to have an optimal solution with integer values for all its flow quantities.只有当所有点的供应量、需求量和容量

47、为整数时,如果已经求出最大流为 则求最小费用最大流的线性规划模型为,xij kij and xij 0.,Typical Applications of Minimum-Cost Flow Problems,无限配送公司的问题 P242,x1,x2,x3,x4,x5,x6,Minimize Cost = 700 x1 +300 x2 + 400 x3 +900 x4 +200 x5 + 400 x6 subject to x1 +x2 =80, x3 +x4 =70 , x2 +x3 = x5 +x6 , x1 +x5 =60 , x4 +x6 =90 , x2 50, x3 50 ， x5

48、50, x6 50,无限配送公司的最小成本流问题的电子表格模型,使用 SUMIF 函数,The net outflow (flow out flow in) from node x is then =SUMIF(“From labels”, x, “Flow”) SUMIF(“To labels”, x, “Flow”),流出F1的量流进F1的量,最小费用流求最短路问题,Let xij = 从节点i流到节点j 的流量flow from i to jMinimize ij bij xijsubject to xij 0.,例12最短路里特城消防站Littletown Fire Station,里

49、特城的消防站道路系统 的网络表述如下：,求O点到T点的最短路,x2,x1,x3,x4,x5,x6,x9,x7,x8,x10,x11,x12,x13,x14,x15,x16,x17,x18,x5,x6,x11,x16,x19,x18,线性规划模型,Min 3 x1 +6x2 + 4 x3 + 6 x4 +x5 + 2 x6 + 4 x7 +5x8 + 7 x9 + 8 x10 +3x11 + 6x12 + 5 x13 +4x14 + 4x15 + 5 x16 +4x17 + 2x18 + 7x19 s.t. x1 + x2 + x3 1 O点 x1 + x5 x4x5 = 0 A点 x2 + x

50、5 + x6 x5 x7x6 x8 = 0 B点 x3+ x6 x6 x9 = 0 C点 x4 + x7 + x11 x10 x11 = 0 D点 x8 + x9 + x11 + x6 x5 x7x6 x8 = 0 E点 x10 + x12 + x16 x16x15 = 0 F点 x13 + x16 + x18 x16 x17x18 = 0 G点 x14 + x18 x18 x19 = 0 H点 x15+ x17 + x19 = 1 T点 xi (i =1,19) 0, x5, x6, x11, x16, x18 0，,电子表格模型,最短路线为： OA B E F T,5最小费用最大流问题,最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi,vj），除了给出容量cij 外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总运送费用最小。 一、最小费用最大流的数学模型 例7 由于输油管道的长短不一，所以在例6中每段管道（ vi,vj ）除了有不同的流量限制cij外，还有不同的单位流量的费用bij ，cij的单位为万 加仑/小时， bij的单位为百元/万加仑。如图。从采地 v1向销地 v7运送石 油，怎样运送才能运送最多的石油并使得总的运送费用