运筹学chap6网络优化模型

1、本章主要讨论图论基本概念、理论和方法以及最短路问题、最大流问题和最小费用流问题等网络优化模型及其基本算法。 第六章 图与网络优化模型 第一节 图与网络运筹学的重要分支主要应用领域：物理学、化学、控制论、信息论、科学管理、电子计算机等图论理论和方法应用实例：在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。图论的起源与发展七桥问题：哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上

2、有七座桥。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。图8-1(a)图6-1欧拉在1736年发表了图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问题。欧拉将此问题归结为如图6-1(b)所示图形的一笔画问题。即能否从某一点开始，不重复地一笔画出这个图形，最后回到出发点。欧拉证明了这是不可能的，因为图6-1(b)中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。一、 图的基本概念人们为反映一些对象之间关系时，常会用示意图。例1 右图是我国北京、上海等十个城市间的铁路交通图，反映了这十个城市间的铁路分布情况。这里用点代表城市，用点和点之

3、间的连线代表这两个城市之间的铁路线。其他示意图的例子电话线分布图、煤气管道图、航空线图等。铁路交通示意图图6-2图是由点和边构成，可以反映一些对象之间的关系。例2 有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况用图表示出来。已知甲队和其他各队都比赛过一次，乙队和甲、丙队比赛过，丙队和甲、乙、丁队比赛过，丁队和甲、丙、戊队比赛过，戊队和甲、丁队比赛过。为了反映这个情况，可以用点分别代表这五个队，某两个队之间比赛过，就在这两个队所相应的点之间联一条线，这条线不过其他的点，如图6-3所示。比赛情况图图6-3关系的对称性和非对称性：几个例子中涉及到的对象之间的“关系”具有“对称性”，就是说，如果甲与

4、乙有这种关系，那么同时乙与甲也有这种关系。实际生活中，有许多关系不具有这种对称性。 如例2，如果人们关心的是五个球队比赛的胜负情况，那么从图5-3中就看不出来了。为了反映这一类关系，可以用一条带箭头的连线表示。例如，如果球队v1胜了球队v2，可以从v1引一条带箭头的连线到v2类似胜负这种非对称性的关系，在生产和生活中是常见的，如交通运输中的“单行线”，部门之间的领导与被领导的关系，一项工程中各工序之间的先后关系等。比赛胜负图6-4术语顶点（结点）、弧、边（取消弧的方向）、有向图、无向图、链、道路、环、连通图、连通子图、次1234123412345213次道路顶点无向图链有向图弧环连通图 弧是由

5、一对有序的顶点组成，表示了两个顶点之间可能运动的方向 连通子图 由顶点集和弧 组成的图称为有向图 由顶点集和边组成的图称为无向图 链有一序列弧，如果每一个弧与前一个弧恰有一个公共顶点，则称这一序列弧为一个链。 道路 如果链中每一个弧的终点是下面一个弧的起点，则这个链称为一个道路。 环 连接a点与b点的一条链，如果a与b是同一个点时，称此链为环。 连通图 一个图中任意两点间至少有一个链相连，则称此图为连通图。 任何一个不连通图都可以分为若干个连通子图，每一个子图称为原图的一个分图。 次: 以a点为顶点的边的条数称为顶点的次 图6-5例： 设V = v1 , v2 , v3 , v4, E = v

6、1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 画出G = (V, E ) 的图。或二、网络 点或边带有某种数量指标的图叫网络图，简称网络。 与点或边有关的某些数量指标，我们经常称之为权，权可以代表如距离、费用、容量等。 左图可以看作： 从发电厂（节点1）向某城市（节点6）输送电力，必须通过中转站（节点2，3，4，5）转送，边上数字代表两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。 一个输油管道网。节点1表示管道的起点，节点6表示管道的终点，节点2到5表示中转站，旁边的数字表示该段管道能通过的最大输送量。应怎样安排输油线路，使从节点

7、1到节点6的总输送量最大？ 一张城市分布图。现在要在各城市之间架设电话线，应如何架设，使各城市之间既能通话，又使总的架设路线最短？ 第二节 树定义1（树的定义）连通且不含环的无向图称为树。例1 某工厂的组织机构如下所示工厂组织机构图 树的性质： 任意两顶点之间必有一条且仅有一条链。 去掉任一条边，则树成为不连通图。 不相邻的两个顶点间添上一条边，恰好得到一个环。部分图、生成子图、部分树 部分图如果V1 V， E1 E则称G1为(全部顶点和部分边)G的部分图；设G=(V，E)和G1=(V1，E1)部分图、生成子图、部分树 部分图生成子图设G=(V，E)和G1=(V1，E1) 如果G1=(V1，E

8、1)，G=(V，E)，并且V1 V ， ,则称G1为G的生成子图；部分图、生成子图、部分树 部分图生成子图部分树如果V1 V， E1 E则称G1为G的部分图；设G=(V，E)和G1=(V1，E1) 如果G1=(V1，E1)，G=(V，E)，并且V1 V ， ,则称G1为G的生成子图； 如果G=(V，E)的部分图G1=(V，E1)是树，则称G1为G的一个部分树。 1325464332322最小生成树不一定唯一最小生成树：设有一连通图G=(V,L),对于每一边e=(vi,vj)，有一个权wij0。一棵生成树所有树枝上权的总和，称为这个生成树的权。具有最小权的生成树称为最小生成树（最小树）。 例：某

9、大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。v1331728541034v7v6v5v4v2v3图6-11方法一：破圈法步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v

10、5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)解：按照图16-11的(f)设计，可使此网络的总的线路长度为最短，为1900米。方法二：(加边)避圈法（Kruskal）开始选一条最小权的边，以后每一步中，总从未被选中的边中选一条最小权的边，使之与已选的边不构成圈，直到所有的边都检验完，即可得最小树。（每步中，若有两条或两条以上的边都是权最小的边，则从中任选一条）。 例：右图,用避圈法求其最小生成树。 类似地,可定义连通图G 的最大生成树.练习：房屋开发商正规

11、划设计某居住新区的下水管道，图中各数字表示各栋楼房之间铺设管道的工程费用。房屋开发商应怎样设计最佳的管道铺设方案，使总工程费用最少。 2873965657单位：十万元6V1V2V3V5V4V6从一特殊的节点出发，找出从该节点到网络中任何其它节点的最短路径问题某人买了一辆价值12000美元的新车，一辆车每年的维护费用依赖于年初时的车龄，具体费用见下表。为了避免旧车的高维护费用，他决定卖掉旧车买新车。旧车的价格依赖于交易时的车龄，见右表。为计算简单起见，假设任何时间新车的价格不变均为12000美元。他希望在今后5年内的净费用最小（即：净费用=购买价+维护价-售出价）。 车龄每年的维护费用售出价格1

12、23456200040005000900012000700060002000100001234562177777121212213131441221第三节 最短路问题 节点i表示第i年年初，当ij时，弧（i,j）表示第i年年初买一辆新车并一直用到第j年年初。弧（i,j）的长度为cij，cij表示如果第i年年初买车并在第j年年初卖掉更换新车，从第i年年初到第j年年初期间总费用。Cij=(i,i+1,j-1年的维护费)+第i年年初买新车的费用-第j年年初该车的售出价格C12=2+12-7=7C13+c35+c56是1到6的最小费用，第3年年初与第五年初交易，今后5年的净费用最小。算法（Dijkst

13、ra(迪杰斯特拉) 1959年提出的）1325464332322 第0步：P(1)=0,T(i)=+； 第1步：与1相连的标号为2,3，均是T标号，修改2,3的标号，T(2)=minT(2),P(1)+w12=min+,P(1)+w12=4,T(3)=3；在所有的T标号中，3的标号最小，改3的标号为P(3)=3； 第2步：修改与3相连的T标号；在所有剩下的T标号中，2的标号最小，改为P(2)=4； 第3步：修改与2相连的T标号；在所有剩下的T标号中，5的标号最小，改为P(5)=6； 第4步：修改与5相连的T标号；在所有剩下的T标号中，4的标号最小，改为P(4)=7； 第5步：修改与4相连的T标

14、号；只剩下节点6是T标号，修改6的标号，P(6)=8。 从节点6开始回退，得到最短路。P(1)=0T(3)=+T(2)=+T(3)=3T(5)=+P(3)=3T(5)=6T(2)=4T(4)=+T(6)=+P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)=8P(6)=8P(5)=6P(3)=3P(1)=0Dijkstra方法的基本思想：从vs出发，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)，或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号

15、的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p1步，就可以求出从vs到各点的最短路。例：用Dijkstra方法求图8-4所示的赋权图中，从v1到所有点的最短路。图8-4解： 计算的最后结果为P(v1)=0，P(v4)=1，P(v3)=3，P(v2)=5，P(v5)=6，P(v9)=8，P(v7)=9，P(v6)=10，P(v8)=11。这样从v1到v8的最短链为(v1，v3，v2，v5，v9，v8)，总权为11。练习： 设备更新问题。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设

16、备，则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少。我们用一个五年之内要更新某种设备的计划为例，若已知该种设备在各年年初的价格为：第1年第2年第3年第4年第5年1111121213还已知使用不同时间(年)的设备所需要的维修费用为：使用年数0112233445维修费用5681118可供选择的设备更新方案显然是很多的。例如，每年都购置一台新设备，则其购置费用为11+11+12+12+13=59，而每年支付的维修费用为5，五年合计为25。于是五年总的支付费用为59+25=84。又如决定在第一、三、五年各购进一台，这个方案的设备购置费为11+12+13=3

17、6，维修费为5+6+5+6+5=27。五年总的支付费用为63。解：如何制定使得总的支付费用最少的设备更新计划呢?可以把这个问题化为最短路问题，见图8-5。图8-5这样一来，制定一个最优的设备更新计划问题就等价于寻求从v1到v6的最短路的问题。按求解最短路的计算方法，v1，v3，v6及v1，v4，v6均为最短路，即有两个最优方案。一个方案是在第1年、第3年各购置一台新设备；另一个方案是在第1年、第4年各购置一台新设备。五年总的支付费用均为53。 城市出租车公司在纽约市为出租车司机已经确定了10个搭乘车站。为了减少运行时间，提高服务质量以及最大化利用公司的车队，管理方希望出租车司机尽可能地选择最短

18、路线。使用下面公路与街道的网络图，请说明司机从车站1到车站10应选择什么样的路线。运行时间如图所示。最优路线为：110，最短距离是25 例：六个村庄每村上学人数见下表，村与村的距离见下图，现只能在某一个村建一所小学，问在哪个村建校最为合理？村庄ABCDEF上学人数6040503070100ABCEFD633647281第四节 网络最大流问题一、基本概念与基本定理二、寻求最大流的标号法容量网络、可行流24531142010519152730流 量容量 容量网络：标有弧容量的网络。156104610150可行流 网络流的两个条件：每个弧的流量不能超过该弧的最大通过能力，即容量；中间支点的流量为零。

19、可行流：中间点的流量为零。而发点和收点的流量必须相等。可行流与最大流 在运输网络的实际问题中可以看出，对于流有两个明显的要求：1.是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；2.是中间点的流量为零。 因为对于每个点，运出这点的产品总量与运进这点的产品总量之差，是这点的净输出量，简称为是这一点的流量；由于中间点只起转运作用，所以中间点的流量必为零。 易见发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。因此有：定义： 满足下述条件的流 f 称为可行流： (1) 容量限制条件：对每一弧(vi，vj)A0fijcij (2) 平衡条件： 对于中间点：流出量等于流入量，即对每

20、个i(is,t发点与收点)有对于发点vs，记对于收点vt，记 式中v(f )称为这个可行流的流量，即发点的净输出量(或收点的净输入量)。可行流总是存在的。比如令所有弧的流量fij=0，就得到一个可行流(称为零流)。其流量v(f)=0。最大流问题就是求一个流fij使其流量v(f)达到最大，并且满足：0fijcij (vi，vj)A 最大流问题是一个特殊的线性规划问题。即求一组fij，在满足条件和下使v(f)达到极大。将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。 增广链13425201051419152730156104610150饱和弧非饱和弧零弧增广链增广链

21、: 设f是一个可行流，C 是从发点Vs到收点Vt的一条链，若C 满足以 下条件，则称C 为一条增广链：(1) 在弧 上， ，即C+(弧的方向与链的方向一致 )中每一条弧是非饱和弧(2) 在弧 上， ，即C-(弧的方向与链的方向相反 )中每一条弧是非零流弧 C中每一条弧是非饱和弧; C中每一条弧是非零流弧。 割集21st28811 任给一个包含收点但不包含发点的支点集V*，则称i(弧起点)不属于V*，j(弧终点)属于V*的弧(i,j)的全体为割集。 割集的容量是割集中所有弧的容量的总和。 如果将割集从网络中移去，则就不可能有从起点到终点的路径。 一个网络可能有许多割集。 任何从发点到收点的可行流

22、小于等于任何割集的容量。直观上说，截集是从vs到vt的必经之道。V*割集任何割集的容量是从起点到终点的最大流的上界。如果能找到一个可行流和一个割集使得割集从起点到终点的容量等于可行流的流量，则该可行流就是 一个最大流。 最大流-最小割集定理 V*=1,t割集是(s,1)，(2,t)，容量2+1=3 支点集V*=1,2,t ,割集？(s,1)，(s,2),容量2+8=10 从一个可行流 出发，（若网络中没有给定f，则可以设f是零流）需要经过标号过程与调整过程。1标号过程 在这个过程中，网络中的点或是标号点或是未标号点。每个标号点的标号包含两部分：第一标号表示它的标号是从哪一点得到的，以便找出增广

23、链；第二个标号是为确定增广链的调整量 用的。 标号过程开始时，总是先给发点 标上 。其余各点标号的规则是： 设 是已标号的点，检查与 点关联的另一顶点未标号的弧：（1）如果在弧 上（即前向弧）， ，则给 标号 ，其中 。如果 ，则 不标号。（2）如果在弧 上（即后向弧）， ，则给 标号 ，其中 ，负号说明经后向弧到 。如果 ，则 不标号。 重复上述步骤，直到被 标上号，表明得到一条从 到 的增广链C，转入调整过程。求最大流的标号算法求最大流的标号算法 2调整过程 由收点 标号算出的 作为调整量（即 ）。对增广链各弧的调整如下： 增广链以外各弧流量不变。去掉所有标号，对新的可行流 ，重新进入标号

24、过程。直到标号过程中断。当前流就是最大流。标号算法vsv2v1v3vt32223(0,+) 找到初始可行流。 给网络中的各个点标号： 总是先给发点vs标上(0,+)。 其余各点标号的规则是：设vi是已标号的点，检查与点vi关联的另一顶点未标号的弧：（1）如果在弧(vi,vj)上（即前向弧），fij0，则给vj标号(-vi,l(vj)，其中l(vj)=minl(vi),fji，负号说明经后向弧到vi。如果fji=0，则vj不标号。 调整： 按照第一标号找到增广链， 按第二标号的最小值调整可行流，得到新的可行流。 重复标号过程，直到没有增广链，即得到最大流。 2112114(vs,2)(v3,1)

25、(-v2,1)(v1,1)222022如下图所示，弧上数字表示该弧的容量，求该网络的最大流。增广链以外各弧流量不变 标号算法vsv2v1v3vt32223(0,+)重复标号过程。 给网络中的各个点标号： 先给发点vs标上(0,+)。 检查vs给v2标上(vs,1)，检查v2,在弧(v2,vt)上,f2t=C2t=2,不满足标号条件，在弧(v1,v2)上，f12=0,也不满足标号条件，标号无法继续。算法结束。4(vs,1)222022如下图所示，弧上数字表示该弧的容量，求该网络的最大流。最大流量为从发点流出的量 这时的可行流就是所求的最大流 练习： 用标号法求图8-7所示网络的最大流。弧旁的数是

26、(cij，fij)。图8-7解： (1) 标号过程 首先给vs标上(0，+) 检查vs，在弧(vs，v2)上，fs2=cs2=3，不满足标号条件。弧(vs，v1)上，fs1=1，cs1=5，fs1cs1，则v1的标号为(vs，l (v1)，其中l (v1)=minl (vs)，(cs1-fs1)=min+，5-1=4 检查v1，在弧(v1，v3)上，f13=2，c13=2，不满足标号条件。在弧(v2，v1)上，f21=10，则给v2记下标号为(-v1，l (v2)，这里l (v2)=minl (v1)，f21=min4，1=1 检查v2，在弧(v2，v4)上，f21=3，c24=4，f24c2