运筹学 朱道立课件09

本章主要讨论图论基本概念、理论和方法以及最短路问题、最大流问题和最小费用流问题等网络优化模型及其基本算法。

第九章网络优化模型

目录图与网络树最短路问题最大流问题最小费用流问题目录图与网络树最短路问题最大流问题最小费用流问题基本概念：

顶点、弧、有向图、无向图、链、道路、环、连通图、连通子图、次1234123412345213次道路顶点无向图链有向图弧环连通图弧是由一对有序的顶点组成，表示了两个顶点之间可能运动的方向连通子图

由顶点集和弧组成的图称为有向图

由顶点集和边组成的图称为无向图

链有一序列弧，如果每一个弧与前一个弧恰有一个公共顶点，则称这一序列弧为一个链。

道路如果链中每一个弧的终点是下面一个弧的起点，则这个链称为一个道路。

环连接a点与b点的一条链，如果a与b是同一个点时，称此链为环。

连通图一个图中任意两点间至少有一个链相连，则称此图为连通图。

任何一个不连通图都可以分为若干个连通子图，每一个子图称为原图的一个分图。

次:以a点为顶点的边的条数称为顶点的次

网络点或边带有某种数量指标的图叫网络图，简称网络。与点或边有关的某些数量指标，我们经常称之为权，权可以代表如距离、费用、容量等。左图可以看作：从发电厂（节点1）向某城市（节点6）输送电力，必须通过中转站（节点2，3，4，5）转送，边上数字代表两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。一个输油管道网。节点1表示管道的起点，节点6表示管道的终点，节点2到5表示中转站，旁边的数字表示该段管道能通过的最大输送量。应怎样安排输油线路，使从节点1到节点6的总输送量最大？一张城市分布图。现在要在各城市之间架设电话线，应如何架设，使各城市之间既能通话，又使总的架设路线最短？目录图与网络树最短路问题最大流问题最小费用流问题树：连通且不含环的无向图

树的性质：任意两顶点之间必有一条且仅有一条链。去掉任一条边，则树成为不连通图。不相邻的两个顶点间添上一条边，恰好得到一个环。部分图、生成子图、部分树部分图生成子图部分树如果V1V，E1E则称G1为G的部分图；设G=(V，E)和G1=(V1，E1)如果G1=(V1，E1)，G=(V，E)，并且V1V，,则称G1为G的生成子图；如果G=(V，E)的部分图G1=(V，E1)是树，则称G1为G的一个部分树。最小生成树：具有最小权的生成树

1325464332322最小生成树不一定唯一目录图与网络树最短路问题最大流问题最小费用流问题最短路问题从一特殊的节点出发，找出从该节点到网络中任何其它节点的最短路径问题某人买了一辆价值1200美元的新车，一辆车每年的维护费用依赖于年初时的车龄，具体费用见下表。为了避免旧车的高维护费用，他决定卖掉旧车买新车。旧车的价格依赖于交易时的车龄，见下表。为计算简单起见，假设任何时间新车的价格不变均为1200美元。他希望在今后5年内的净费用最小（即：净费用=购买价+维护价-售出价）。

车龄每年的维护费用交易费用012345200040005000900012000700060002000100001234562177777121212213131441221算法1325464332322第0步：P(1)=0,T(i)=+∞；

第1步：与1相连的标号为2,3，均是T标号，修改2,3的标号，T(2)=min{T(2),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标号；只剩下节点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)=0

例：从发电厂（记为节点1）向某城市（记为节点6）输送电，必须通过中转站（记为节点2，3，4，5）转送。图给出了两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。即从节点1到节点6的最短路径。这就是一个最短路问题。用Excel求解最短路算法

净流量=流出该节点的流量—流入该节点的流量

中间节点的平衡值为0，起点为1，终点为-1。各个点的净流量等于平衡值最短路平衡流P(6)=8P(5)=6P(3)=3P(1)=0

城市出租车公司在纽约市为出租车司机已经确定了10个搭乘车站。为了减少运行时间，提高服务质量以及最大化利用公司的车队，管理方希望出租车司机尽可能地选择最短路线。使用下面公路与街道的网络图，请说明司机从车站1到车站10应选择什么样的路线。运行时间如图所示。

这里我们仅通过Excel电子表格求解，在表格中，我们并不是把每一对连接的点都输入进去，比如，我们输入了从V7到V10，很明显不需要再输入从V7到V8，从V8到V10这两对点对，因为他们加起来的距离明显要比前者长。最优路线为：1－５－４－６－７－10，最短距离是25目录图与网络树最短路问题最大流问题最小费用流问题容量网络、可行流24531142010519152730流量容量

容量网络：标有弧容量的网络。156104610150可行流

网络流的两个条件：每个弧的流量不能超过该弧的最大通过能力，即容量；中间支点的流量为零。可行流：中间点的流量为零。而发点和收点的流量必须相等。增广链13425201051419152730156104610150饱和弧非饱和弧零弧增广链增广链:

设f是一个可行流，C是从发点Vs到收点Vt的一条链，若C满足以下条件，则称C为一条增广链：(1)在弧上，，即C+(弧的方向与链的方向一致

)中每一条弧是非饱和弧(2)在弧上，，即C-(弧的方向与链的方向相反

)中每一条弧是非零流弧

C＋中每一条弧是非饱和弧;C－中每一条弧是非零流弧。

割集21st28811

任给一个包含收点但不包含发点的支点集V*，则称i(弧起点)不属于V*，j(弧终点)属于V*的弧(i,j)的全体为割集。割集的容量是割集中所有弧的容量的总和。如果将割集从网络中移去，则就不可能有从起点到终点的路径。一个网络可能有许多割集。任何从发点到收点的可行流小于等于任何割集的容量。

V*割集任何割集的容量是从起点到终点的最大流的上界。如果能找到一个可行流和一个割集使得割集从起点到终点的容量等于可行流的流量，则该可行流就是一个最大流。

最大流---最小割定理

V*={1,t}割集是{(s,1)，(2,t)}

支点集V*={1,2,t},割集？{(s,1)，(s,2)}

求最大流的标号算法从一个可行流出发，（若网络中没有给定f，则可以设f是零流）需要经过标号过程与调整过程。1．标号过程在这个过程中，网络中的点或是标号点或是未标号点。每个标号点的标号包含两部分：第一标号表示它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。标号过程开始时，总是先给发点标上。其余各点标号的规则是：设是已标号的点，检查与点关联的另一顶点未标号的弧：（1）如果在弧上（即前向弧），，则给标号，其中。如果，则不标号。（2）如果在弧上（即后向弧），，则给标号，其中，负号说明经后向弧到。如果，则不标号。重复上述步骤，直到被标上号，表明得到一条从到的增广链C，转入调整过程。求最大流的标号算法

2．调整过程由收点标号算出的作为调整量（即）。对增广链各弧的调整如下：

增广链以外各弧流量不变。去掉所有标号，对新的可行流，重新进入标号过程。直到标号过程中断。当前流就是最大流。标号算法vsv2v1v3vt32223(0,+∞)

找到初始可行流。

给网络中的各个点标号：总是先给发点vs标上(0,+∞)。其余各点标号的规则是：设vi是已标号的点，检查与点vi关联的另一顶点未标号的弧：（1）如果在弧(vi,vj)上（即前向弧），fij<cij，则给vj标号(vi,l(vj))，其中l(vj)=min{l(vi),cij-fij}。如果fij=cij，则vj不标号。（2）如果在弧(vj,vi)上（即后向弧），fij>0，则给vj标号(-vi,l(vj))，其中l(vj)=min{l(vi),fji}，负号说明经后向弧到vi。如果fji=0，则vj不标号。调整：按照第一标号找到增广链，按第二标号的最小值调整可行流，得到新的可行流。

重复标号过程，直到没有增广链，即得到最大流。

2112114(vs,2)(v3,1)(-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如下图所示，弧上数字表示该弧的容量，求该网络的最大流。最大流量为从发点流出的量这时的可行流就是所求的最大流

目录图与网络树最短路问题最大流问题最小费用流问题从一个费用最小的可行流出发（这样的可行流一定存在，因为费用，所以就是一个流量为0的最小费用流），找出这个可行流的