第5章-图论与网络规划模型分析课件.ppt

1、第第5 5章章 图论与网络规划模型图论与网络规划模型v图论作为离散数学的一个重要分支，在工图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中许多方面程技术、自然科学和经济管理中许多方面都能提供有力的数学模型来解决实际问题。都能提供有力的数学模型来解决实际问题。v比如，哥尼斯堡七桥问题、中国邮递员问题、比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问中的重要方法。许多难题由于归结为图论问题被巧妙地解决。题被巧妙地解决。第第5 5章章 图论与网络规划模型图论与网络规划模型v5.1

2、 5.1 图的基本概念图的基本概念v5.2 5.2 最短路问题与最大流问题最短路问题与最大流问题v5.3 5.3 最优连线问题与旅行商问题最优连线问题与旅行商问题 5.1.1 5.1.1 图的定义图的定义5.1 5.1 图的基本概念图的基本概念 图图G是一个偶对（是一个偶对（V,E），其中），其中V(G)=v1,v2,vn为图的为图的 顶点集（顶点集（vertex set），），E(G)=e1,e2,en 为图的边集为图的边集（edge set）或弧集（常用）或弧集（常用A表示）表示）,记记ek=(vi,vj)(k=1,2,m)。若若ek是无序对，则称是无序对，则称G为无向图（为无向图（und

3、irected graph）；若）；若ek=(vi,vj)是有序对，则称是有序对，则称G为有向图（为有向图（directed graph），），vi为的起点，为的起点，vj为的终点，称去掉有向图的方向得到的图为为的终点，称去掉有向图的方向得到的图为基础图（基础图（underlying graph）。5.1.1 5.1.1 图的定义图的定义 一个图称为有限图，如果它的顶点集和边集都有限。图一个图称为有限图，如果它的顶点集和边集都有限。图G的顶点数用符号的顶点数用符号|V|表示，边数用表示，边数用|E|表示。表示。端点重合为一点的边称为环端点重合为一点的边称为环(loop)。连接两个相同顶点的边。

4、连接两个相同顶点的边的条数称为边的重数，重数大于的条数称为边的重数，重数大于1的边称为重边的边称为重边(multi-edges)。在有向图中，两个顶点相同但方向相反的边称为。在有向图中，两个顶点相同但方向相反的边称为对称边对称边(symmetric edge)。一个图称为简单图。一个图称为简单图(simple graph)，如果它既没有环也没有重边。，如果它既没有环也没有重边。5.1.2 5.1.2 完全图、二分图、子图完全图、二分图、子图 每一对不同的顶点都有一条边相连的简单图称为完全图每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n个顶点的完全图记为个顶

5、点的完全图记为Kn；完全图的定；完全图的定向图称为竞赛图。向图称为竞赛图。若若V(G)=XY，XY=空集，空集，|X|Y|0,X中无相邻顶点对，中无相邻顶点对，Y中亦然，则称中亦然，则称G为二分图为二分图(bipartite graph)；特别地，若对；特别地，若对任意的任意的xX,yY，都有，都有xy E(G)，则称，则称G为完全二分图，为完全二分图，记成记成K|X|,|Y|。G的支撑子图是指满足的支撑子图是指满足V(H)=V(G)的子图。的子图。若若H是是G的子图，则的子图，则G称为称为H的母图。的母图。GH 图图H叫做图叫做图G的子图，记作的子图，记作，如果，如果)()(GVHV5.1.

6、3 5.1.3 顶点的度顶点的度 设设vV(G)，G中与中与v关联的边数（每个环算作两条边）称为关联的边数（每个环算作两条边）称为v的度的度(degree)，记作，记作d(v)。若。若d(v)是奇数，称是奇数，称v是奇度顶点是奇度顶点(odd point)；若；若d(v)是偶数，称是偶数，称v是偶度顶点是偶度顶点(even point)。对有向图，以对有向图，以v为起点的有向边数称为为起点的有向边数称为v的出度的出度(out-degree)，记作，记作d+(v)；以为终点的有向边数称为的入度；以为终点的有向边数称为的入度(in-degree)，记作，记作d(v)；顶点的度；顶点的度d(v)=d

7、+(v)+d(v)。5.1.4 5.1.4 迹、路、圈与连通迹、路、圈与连通 无向图无向图G的一条途径的一条途径(walk)是指一个有限的非空序列是指一个有限的非空序列W=v0e1v1e2e kvk，其中，其中eiE(G)，1ik，v j V(G)，0 j k，e i 与与v i-1 v i 关联，称关联，称k为为W的长的长(length)。若途经的边。若途经的边互不相同，则称互不相同，则称W为迹为迹(trail)；若途径的顶点互不相同，则称；若途径的顶点互不相同，则称W为路为路(path)；如果；如果v0=v k，并且没有其他相同的，并且没有其他相同的 顶点，则称顶点，则称W为圈为圈(cyc

8、le)。若图若图G的两个顶点的两个顶点u,v间存在道路，则称间存在道路，则称u和和v连通连通(connected)。u,v间的最短轨的长叫做间的最短轨的长叫做u,v间的距离。记作间的距离。记作d(u,v)。若图。若图G的任二顶点均连通，则称的任二顶点均连通，则称G是连通图。是连通图。5.1.5 5.1.5 图与网络的数据结构图与网络的数据结构 为了在计算机上实现网络优化的算法，首先我们必须有一为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的

9、操说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网作方案是有关系的。这里我们介绍计算机上用来描述图与网络的络的5种常用表示方法：邻接矩阵表示法、关联矩阵表示法、种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。弧表表示法、邻接表表示法和星形表示法。首先假设首先假设G=(V,A)是一个简单有向图，是一个简单有向图，|V|=n,|A|=m，并，并假设假设V中的顶点用自然数中的顶点用自然数1,2,n表示或编号，表示或编号，A中的弧用自中的弧用自然数然数1,2,m表示或编号。表示或编号。5.1.5 5.1.5

10、图与网络的数据结构图与网络的数据结构-邻接矩阵表示法邻接矩阵表示法 邻接矩阵表示法是将图以邻接矩阵（邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图的形式存储在计算机中。图G=(V,A)的邻接矩阵是如下定义的邻接矩阵是如下定义的：的：C是一个是一个nn的矩阵，即的矩阵，即nnnnijcC1,0)(.),(,0,),(,1AjiAjicij5.1.5 5.1.5 图与网络的数据结构图与网络的数据结构-邻接矩阵表示法邻接矩阵表示法 对于下图所示的有向图，可以用邻接矩阵表示为对于下图所示的有向图，可以用邻接矩阵表示为011001010000010010000

11、0110 对于网络中的权，也可以用类似邻接矩阵的矩阵表示。只是对于网络中的权，也可以用类似邻接矩阵的矩阵表示。只是此时一条弧所对应的元素不再是此时一条弧所对应的元素不再是1，而是相应的权而已。无向，而是相应的权而已。无向图的邻接矩阵为对称阵。图的邻接矩阵为对称阵。邻接矩阵举例邻接矩阵举例 n支球队循环赛，每场比赛支球队循环赛，每场比赛 只计胜负，没有平局只计胜负，没有平局.根据比赛结果排出各队名次根据比赛结果排出各队名次.方法方法1.寻找按箭头方向通过寻找按箭头方向通过全部顶点的路径全部顶点的路径.123456312456146325方法方法2.计算得分：计算得分：无法排名无法排名2,3队队,

12、4,5队无法排名队无法排名!6支球队比赛结果支球队比赛结果32，4 5排名排名 132456 合理吗合理吗?1队胜队胜4场，场，2,3队各胜队各胜3场，场，4,5队各胜队各胜2场，场，6队胜队胜1场场.123(1)123(2)1234(1)1234(2)1234(3)1234(4)循环比赛的结果循环比赛的结果竞赛图竞赛图3个顶点个顶点的竞赛图的竞赛图名次名次1，2，3(1,2,3)并列并列1,2,3,42,(1,3,4)(1,3,4),24个顶点个顶点的竞赛图的竞赛图名次名次(1,2),(3,4)1,2,3,4?竞赛图竞赛图每对顶点间都有边相连的有向图每对顶点间都有边相连的有向图1234123

13、41234(1)(2)(3)1234(4)竞赛图的竞赛图的3种形式种形式 具有唯一的具有唯一的完全路径完全路径，如，如(1)；双向连通图双向连通图任一对顶点存在两条任一对顶点存在两条 有向路径相互连通，如有向路径相互连通，如(4)；其他，如其他，如(2)，(3).竞赛图竞赛图的性质的性质 必存在完全路径；必存在完全路径；若存在唯一的完全路径，则由它确定的顶若存在唯一的完全路径，则由它确定的顶 点顺序与按得分排列的顺序一致，如点顺序与按得分排列的顺序一致，如(1).4个顶点个顶点的竞赛图的竞赛图TeAes)1,1,1(,级得分向量1)1,1,2,2()1(TAes级得分向量2)2,1,2,3()

14、1()2(TAss0001100011000110AEvvEvvajijiij,0,11234(4)双向连通竞赛图双向连通竞赛图G=(V,E)的名次排序的名次排序邻接矩阵邻接矩阵Tnssss),(21得分向量得分向量TTss)3,3,5,5(,)3,2,3,3()4()3(eAAsskkk)1()(?,)(kskTTss)8,5,8,9(,)5,3,6,8()6()5(TTss)13,9,17,21(,)9,8,13,13()8()7(双向连通竞赛图的名次排序双向连通竞赛图的名次排序 对于对于n(3)个顶点的双向连通竞赛图，存在个顶点的双向连通竞赛图，存在 正整数正整数r，使邻接矩阵，使邻接矩

15、阵A 满足满足Ar 0，A称称素阵素阵.eAAsskkk)1()(0001100011000110A排名为排名为1，2，4，3sskk)(,)(归一化后Ts)230.0,167.0,280.0,323.0(,4.1用用s排名排名1234(4)1,2,3,4?素阵素阵A的最大特征根为正单的最大特征根为正单 根根，对应正特征向量，对应正特征向量s，且，且seAkkk lim000100100100110000001010111000111010A,)1,2,2,3,3,4()1(Ts1234566支球队比赛结果支球队比赛结果Ts)104.0,150.0,113.0,231.0,164.0,238.

16、0(,232.2排名次序为排名次序为1，3，2，5，4，632,4 5排名排名 132456?,)9,12,7,16,10,15()3(Ts,)3,4,3,9,5,8()2(TsTs)16,25,21,32,28,38()4(1:4分分;2,3:3分分;4,5:2分分;6:1分分.5.2.1 5.2.1 最短路问题最短路问题 5.2 5.2 最短路问题与最大流问题最短路问题与最大流问题 背景：给定连接若干城市的铁路网，寻求从指定城市到各背景：给定连接若干城市的铁路网，寻求从指定城市到各城去的最短道路。城去的最短道路。数学模型：图为一赋权图，对任给的，寻求路，使得数学模型：图为一赋权图，对任给的

17、，寻求路，使得),(min),(00的路到取自所有vvPPWvvPW其中是路上各边权之和。这一问题可用其中是路上各边权之和。这一问题可用Dijkstra算法解决算法解决。STA1 A2 A3 B1 B2 C1 C2 633665874678956 例例1 在纵横交错的公路网中，货车司机希望找到一条从在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路。下图表示的是公路网一个城市到另一个城市的最短路。下图表示的是公路网,节点表示货车可以停靠的城市，弧上的权表示两个城市节点表示货车可以停靠的城市，弧上的权表示两个城市之间的距离之间的距离(百公里百公里)。那么。那么,货车从城市货

18、车从城市S出发到达城市出发到达城市T，如何选择行驶路线，使所经过的路程最短，如何选择行驶路线，使所经过的路程最短?STA1 A2 A3 B1 B2 C1 C2 633665874678956分析分析 假设从假设从S到到T的最优行驶路线的最优行驶路线 P 经过城市经过城市C1,则则P中从中从S到到C1的的子路也一定是从子路也一定是从S到到C1的最优行驶路线的最优行驶路线;假设假设 P 经过城市经过城市C2,则则P中从中从S到到C2的子路也一定是从的子路也一定是从S到到C2的的最优行驶路线最优行驶路线.因此因此,为得到从为得到从S到到T的最优行驶路线的最优行驶路线,只需先求出从只需先求出从S到到

19、Ck(k=1,2)的最优行驶路线的最优行驶路线,就可方便地得到从就可方便地得到从S到到T的最优行驶路线。的最优行驶路线。同样同样,为了求出从为了求出从S到到Ck(k=1,2)的最优行驶路线的最优行驶路线,只需要先求出只需要先求出从从S到到Bj(j=1,2)的最优行驶路线的最优行驶路线;为了求出从为了求出从S到到Bj(j=1,2)的最优行驶路线的最优行驶路线,只需要先求出从只需要先求出从S到到Ai(i=1,2,3)的最优行驶路线的最优行驶路线.而而S到到Ai(i=1,2,3)的最优行驶路线是很容的最优行驶路线是很容易得到的易得到的(实际上实际上,此例中此例中S到到Ai(i=1,2,3)只有唯一的

20、道路只有唯一的道路)。分析分析 STA1 A2 A3 B1 B2 C1 C2 633665874678956此例中可把从此例中可把从S到到T的行驶过程分成的行驶过程分成4个阶段个阶段,即即 SAi(i=1,2或或3),Ai Bj(j=1或或2),Bj Ck(k=1或或2),Ck T.记记d(Y,X)为城市为城市Y与城与城市市X之间的直接距离之间的直接距离(若这两个城市之间没有道路直接相连，则可若这两个城市之间没有道路直接相连，则可以认为直接距离为以认为直接距离为)，用，用L(X)表示城市表示城市S到城市到城市X的最优行驶路线的最优行驶路线的路长的路长:0;1min,.2YXL SL XL Yd

21、 Y XXS本例的计算本例的计算 1231123321233112221221216,3,3;min6,8,7107;min5,6,474;min6,8158;min7,9169;min5,6205.L AL AL AL BL AL AL AL AL BL AL AL AL AL CL BL BL BL CL BL BL BL TL CL CL CSTA1 A2 A3 B1 B2 C1 C2 633665874678956所以所以,从从S S到到T T的最优行驶路线的路长为的最优行驶路线的路长为20.20.进一步分析以上求解进一步分析以上求解过程过程,可以得到从可以得到从S S到到T T的最优

22、行驶路线为的最优行驶路线为S A3 B2 C1 T.这种计算方法在数学上称为动态规划(Dynamic Programming)本例的本例的LINGO求解求解“CITIES”(城市城市):一个基本集合一个基本集合(元素通过枚举给出元素通过枚举给出)L:CITIES对应的属性变量对应的属性变量(我们要求的最短路长我们要求的最短路长)“ROADS”(道路):由CITIES导出的一个派生集合(请特别注意其用法),由于只有一部分城市之间有道路相连，所以不应该把它定义成稠密集合，将其元素通过枚举给出，这就是一个稀疏集合。D:稀疏集合ROADS对应的属性变量(给定的距离)本例的本例的LINGO求解求解从模型

23、中还可以看出：这个从模型中还可以看出：这个LINGO程序可以没有目标程序可以没有目标函数，这在函数，这在LINGO中，可以用来找可行解中，可以用来找可行解(解方程组和解方程组和不等式组不等式组)。在数据段对在数据段对L进行赋值，只有进行赋值，只有L(S)=0已已知，后面的值为空知，后面的值为空(但位置必须留出来，但位置必须留出来，即逗号即逗号“，”一个也不能少，否则会出一个也不能少，否则会出错错)。如果这个语句直接写成。如果这个语句直接写成“L=0；”，语法上看也是对的，但其含义是语法上看也是对的，但其含义是L所有所有元素的取值全部为元素的取值全部为0，所以也会与题意，所以也会与题意不符。不符

24、。本例的本例的LINGO求解求解虽然集合虽然集合CITIES中的元素不是数字，但当中的元素不是数字，但当它以它以CITIES(I)的形式出现在循环中时，引的形式出现在循环中时，引用下标用下标I却实际上仍是正整数，也就是说却实际上仍是正整数，也就是说I指指的正是元素在集合中的位置的正是元素在集合中的位置(顺序顺序)，一般称，一般称为元素的索引为元素的索引(INDEX)。在在for循环中的过滤条件里用了一个函数循环中的过滤条件里用了一个函数“index”,其作用是返回一个元素在集合其作用是返回一个元素在集合中的索引值，这里中的索引值，这里index(S)=1(即元素即元素S在在集合中的索引值为集合

25、中的索引值为1)，所以逻辑关系式，所以逻辑关系式“I#GT#index(S)”可以可以直接等价地可以可以直接等价地写成写成“I#GT#1”。这里。这里index(S)实际上还实际上还是是index(CITIES,S)的简写，即返回的简写，即返回S在集在集合合CITIES中的索引值。中的索引值。本例的本例的LINGO求解结果求解结果从S到T的最优行驶路线的路长为20(进一步分析，可以得到最优行驶路线为S A3 B2 C1 T)。本例中定义稀疏集合本例中定义稀疏集合ROADS的方法是将其元素通过枚举的方法是将其元素通过枚举给出，有时如果元素比较多，用起来不方便。另一种定给出，有时如果元素比较多，用

26、起来不方便。另一种定义稀疏集合的方法是义稀疏集合的方法是“元素过滤元素过滤”法，能够从笛卡儿积法，能够从笛卡儿积中系统地过滤下来一些真正的元素。中系统地过滤下来一些真正的元素。n(),ijnnW个顶点的赋权图的赋权矩阵是一个个顶点的赋权图的赋权矩阵是一个阶阶 矩阵矩阵 其分量为其分量为nn(,),(,),ijijijvvvvEa其他.最短路问题的直接解法最短路问题的直接解法STA1 A2 A3 B1 B2 C1 C2 633665874678956 假设图有假设图有n个顶点，现需要求从顶点个顶点，现需要求从顶点1到顶点到顶点 的最短路的最短路.设决策变量为设决策变量为 ,当当 ,说明弧说明弧

27、位于顶点位于顶点1至顶点至顶点 的路上；否则不在的路上；否则不在.其数学其数学规划表达式为规划表达式为nijx1ijx(,)i jn(,)1,(,)1,(,)m in (3)1,1,.1,(4)0,1,.0,(,).(5)ijiji jEnnijjiji jEjj iEijxis txxininxi jE最短路问题的直接解法最短路问题的直接解法 之前我们接触到了最短路问题的求解，当时之前我们接触到了最短路问题的求解，当时的求解方法是按照的求解方法是按照Dijkstra算法设计的，下面介算法设计的，下面介绍的方法是按照规划问题绍的方法是按照规划问题(3)-(5)设计的设计的.求例求例1中，从城市

28、中，从城市S到城市到城市T的最短路的最短路.解：解：写出相应的写出相应的LINGO程序程序MODEL:1!We have a network of 9 cities.We want to find 2 the length of the shortest route from city 1 to city 9;3最短路问题的直接解法最短路问题的直接解法 4sets:5 !Here is our primitive set of nine cities;6 cities/S,A1,A2,A3,B1,B2,C1,C2,T/;7 8 !The Derived set roads lists the

29、roads that 9 exist between the cities;10 roads(cities,cities)/11 S,A1 S,A2 S,A3 A1,B1 A1,B2 A2,B1 A2,B2 A3,B1 12 A3,B2 B1,C1 B1,C2 B2,C1 B2,C2 C1,T C2,T/:w,x;13endsets 14 15data:16 !Here are the distances that correspond 17 to above links;18 w=6 3 3 6 5 8 6 7 4 6 7 8 9 5 6;19enddata 20 21n=size(citi

30、es);!The number of cities;22min=sum(roads:w*x);23for(cities(i)|i#ne#1#and#i#ne#n:24 sum(roads(i,j):x(i,j)=sum(roads(j,i):x(j,i);25sum(roads(i,j)|i#eq#1:x(i,j)=1;END 在上述程序中，在上述程序中，21句中的句中的n=size(cities)是是计算集计算集cities的个数，这里的计算结果是的个数，这里的计算结果是n=9,这样编这样编写方法目的在于提高程序的通用性写方法目的在于提高程序的通用性.22句表示目标句表示目标函数函数(3),

31、即求道路的最小权值即求道路的最小权值.23,24句表示约束句表示约束(4)中中 的情况，即最短路中中间点的约束的情况，即最短路中中间点的约束条件条件.25句表示约束中句表示约束中 的情况，即最短路中的情况，即最短路中起点的约束起点的约束.1,iin1i 约束约束(4)中中 的情况，也就是最短路中终点的的情况，也就是最短路中终点的情况，没有列在程序中，因为终点的约束方程与前情况，没有列在程序中，因为终点的约束方程与前个方程相关个方程相关.当然，如果你将此方程列入到当然，如果你将此方程列入到LINGO程序中，计算时也不会出现任何问题，因为程序中，计算时也不会出现任何问题，因为LINGO in 软件

32、可以自动删除描述线性规划可行解中的多软件可以自动删除描述线性规划可行解中的多余方程余方程.LINGO软件计算结果（仅保留非零变量）如下软件计算结果（仅保留非零变量）如下 Global optimal solution found.Objective value:20.00000 Variable Value Reduced Cost X(S,A3)1.000000 0.000000 X(A3,B2)1.000000 0.000000 X(B2,C1)1.000000 0.000000 X(C1,T)1.000000 0.000000 即最短路是即最短路是 ,最短路长为最短路长为20个单位个单位

33、.321SABCT 例例2 现需要将城市现需要将城市s的石油通过管道运送到城市的石油通过管道运送到城市t，中间有，中间有4个中转站个中转站 和和 ,城市与中转站的连接以及管道城市与中转站的连接以及管道的容量如图所示，求从城市的容量如图所示，求从城市s到城市到城市t的最大流的最大流.123,v v v4v5.2.5.2.2 2 最大流问题最大流问题 图中给出的有一个源和一个汇的网络图中给出的有一个源和一个汇的网络.网络网络 中每一条边中每一条边 有一个容量有一个容量 ,除此之外除此之外,每每 对边对边 还有一个通过边的流还有一个通过边的流(Flow),记为记为 .显然显然,边边 上的流量上的流量

34、 不会超过该边上的容量不会超过该边上的容量 ,即即G(,)u v(,)c u v(,)u v(,)fu v(,)u v(,)fu v(,)c u v0(,)(,)(6)fu vc u v称满足不等式（称满足不等式（6）的网络）的网络 是相容的是相容的.对于所有中间顶点对于所有中间顶点,流入的总量应等于流出的流入的总量应等于流出的总量总量 ,即即:G(,)c u v(,)(,)(7)v Vv Vf u vf v u 一个网络一个网络 的流量的流量(Value of flow)值定义为从值定义为从源源 流出的总流量流出的总流量,即即Gs()(,)(8)v VV ff s v 由式由式(18)和和(

35、19)式可以看出式可以看出,的流量值也为流的流量值也为流入汇入汇 的总流量,即:ft()(,)(9)vVVffvt(),(,)(,)0,(10)(),.V fvsf v Vf V vvV vs vtV fvt当当当 称满足式(10)的网络 为守恒的.G7（）8（）9（）定义定义 如果流如果流 满足不等式满足不等式(6)和式和式 (10),则称流则称流 是可行的是可行的.如果存在可行流如果存在可行流 ,使得对所有的可行流使得对所有的可行流 均有均有fff*f*()()VfVf则称则称 为最大流为最大流(Maximum Flow).*f 通过上述推导得到最大流的数学规划表达式通过上述推导得到最大流

36、的数学规划表达式(,)(,)max ;(11),s.t.,(12)0,0,(,).ffijjifj Vj Vi jAj iAijijvvisffvitis tfcijA (13)MODEL:1sets:2 nodes/s,1,2,3,4,t/;3 arcs(nodes,nodes)/4 s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/:c,f;5endsets 6data:7 c=8 7 5 9 9 2 5 6 10;8enddata 9max=flow;10for(nodes(i)|i#ne#1#and#i#ne#size(nodes):11sum(arcs(i,j)

37、:f(i,j)-sum(arcs(j,i):f(j,i)=0);12sum(arcs(i,j)|i#eq#1:f(i,j)=flow;13for(arcs:bnd(0,f,c);程序的第程序的第10到到 12行表示约束行表示约束(12),第第13行表示行表示有界约束有界约束(13).相应的相应的LINGO程序程序LINGO软件的计算结果（只保留流值软件的计算结果（只保留流值 ）如下）如下:fGlobal optimal solution found at iteration:6 Objective value:14.00000 Variable Value Reduced Cost FLOW

38、14.00000 0.000000 F(S,1)7.000000 0.000000 F(S,2)7.000000 0.000000 F(1,2)2.000000 0.000000 F(1,3)5.000000 0.000000 F(2,4)9.000000 -1.000000 F(3,2)0.000000 0.000000 F(3,T)5.000000 -1.000000 F(4,3)0.000000 1.000000 F(4,T)9.000000 0.000000 因此，该网络的最大流为因此，该网络的最大流为14，F的值对应弧的值对应弧上的流，如图所示上的流，如图所示,其中网络中的第一个数为

39、容其中网络中的第一个数为容量，第二个数为流量量，第二个数为流量.在上面的程序中，采用稀疏集的编写方法，下在上面的程序中，采用稀疏集的编写方法，下面介绍的程序编写方法是利用邻接矩阵，这样可以不面介绍的程序编写方法是利用邻接矩阵，这样可以不使用稀疏集的编写方法，更便于推广到复杂网络使用稀疏集的编写方法，更便于推广到复杂网络.MODEL:1sets:2 nodes/s,1,2,3,4,t/;3 arcs(nodes,nodes):p,c,f;4endsets 5data:6 p=0 1 1 0 0 0 7 0 0 1 1 0 0 8 0 0 0 0 1 0 9 0 0 1 0 0 1 10 0 0

40、0 1 0 1 11 0 0 0 0 0 0;12 c=0 8 7 0 0 0 13 0 0 5 9 0 0 14 0 0 0 0 9 0 15 0 0 2 0 0 5 16 0 0 0 6 0 10 17 0 0 0 0 0 0;18enddata 19max=flow;20for(nodes(i)|i#ne#1#and#i#ne#size(nodes):21 sum(nodes(j):p(i,j)*f(i,j)22 =sum(nodes(j):p(j,i)*f(j,i);23sum(nodes(i):p(1,i)*f(1,i)=flow;24for(arcs:bnd(0,f,c);END在

41、上述程序中，由于使用了邻接矩阵，当两点之间在上述程序中，由于使用了邻接矩阵，当两点之间无弧时，定义弧容量为零无弧时，定义弧容量为零.计算结果与前面程序的结计算结果与前面程序的结果完全相同，这里就不再列出了果完全相同，这里就不再列出了.（续例（续例2）由于输油管道的长短不一，或地质）由于输油管道的长短不一，或地质等原因，使每条管道上运输费用也不相同，因此，等原因，使每条管道上运输费用也不相同，因此，除考虑输油管道的最大流外，还需要考虑输油管道除考虑输油管道的最大流外，还需要考虑输油管道输送最大流的最小费用，图中所示是带有运费的网输送最大流的最小费用，图中所示是带有运费的网络，其中第络，其中第1个

42、数字是网络的容量，第个数字是网络的容量，第2个数字是网个数字是网络的单位运费络的单位运费.5.2.5.2.3 3 最小费用最大流问题最小费用最大流问题 本例所提出的问题就是最小费用最大流问题本例所提出的问题就是最小费用最大流问题(Minimum-cost maximum flow)，即考虑网络在最，即考虑网络在最大流情况下的最小费用大流情况下的最小费用.例例2虽然给出了最大流一组方虽然给出了最大流一组方案，但它是不是关于费用的最优方案呢？这还需要案，但它是不是关于费用的最优方案呢？这还需要进一步讨论进一步讨论.1.最小费用流的数学表达式最小费用流的数学表达式(,)ijiji jAc f(1 4

43、)(,)(,),ijjiij Vj Vi jAj iAffd(1 5)0,(,).ijijfuijA(16),0,.fifvisdvitis t(17)min s.t.其中其中 当当 为网络的最大流进，数学规划为网络的最大流进，数学规划 表表示的就是最小费用最大流问题示的就是最小费用最大流问题.fv(14)(17)MODEL:1sets:2 nodes/s,1,2,3,4,t/:d;3 arcs(nodes,nodes)/4 s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/:c,u,f;5endsets 6data:7 d=14 0 0 0 0 -14;8 c=2 8

44、5 2 3 1 6 4 7;9 u=8 7 5 9 9 2 5 6 10;10enddata 11min=sum(arcs:c*f);12for(nodes(i)|i#ne#1#and#i#ne#size(nodes):13 sum(arcs(i,j):f(i,j)-sum(arcs(j,i):f(j,i)=d(i);14sum(arcs(i,j)|i#eq#1:f(i,j)=d(1);15for(arcs:bnd(0,f,u);ENDLINGO软件软件的计算结果的计算结果(仅保留流值仅保留流值 )如下如下:fGlobal optimal solution found at iteration

45、:3 Objective value:205.0000 Variable Value Reduced Cost F(S,1)8.000000 -1.000000 F(S,2)6.000000 0.000000 F(1,2)1.000000 0.000000 F(1,3)7.000000 0.000000 F(2,4)9.000000 0.000000 F(3,2)2.000000 -2.000000 F(3,T)5.000000 -7.000000 F(4,T)9.000000 0.000000因此，最大流的最小费用是因此，最大流的最小费用是205单位单位.而原最大而原最大流费用为流费用为210单位，原方案并不是最优的单位，原方案并不是最优的.下课！下课！