运筹学复习第九章-网路优化

1、第九章 网络优化第一节 图与网络第二节 树和最小树问题第三节 最短路问题第四节 最大流问题第五节 最小费用流问题第六节 用Excel求解网络优化问题第一节 图与网络一、 图的概念二、 网络 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例如城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。图论的起源：哥尼斯堡七桥问题：世纪欧洲的哥尼斯堡城有一条流经全城的普雷格尔河，河的两岸与河中的两个小岛之间有七座桥彼此相通。从陆地A、B、C、D中的任一地方开始能否通过每座桥一次且仅通过

2、一次，就返回原出发地？CD河AB1736年瑞士数学家欧拉（E.Euler）将此问题抽象为一个具有个点，条边的图，如下。上述问题变成从图中任一点出发，能否一笔画出图形？（边不能重复）DBAC欧拉证明不能！图的若干示例大阪新加坡纽约上海悉尼伦敦巴黎例1航线分布问题补例、有八种化学药品A、B、C、D、P、R、S、T要放进贮藏室保管。出于安全原因，下列各种药品不能贮藏在同一室内：AR，AC，AT，RP，PS，ST，TB，TD，BD，DC，RS，RB，PD，SC，SD，问贮存这八种药品至少需要多少间贮藏室？如图，将八种药品表示为个点，不能放在同一室的两种药品用一条边相连。两种药品没有边相连说明可以放在一

3、起。ACDPRST从上图中边最多的点出发开始分析！A、B、S，R、D，P、T、C三间D-R或AS-A与BT-C与P或RB补例、有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如下表，打的是各运动员报名参加的比赛项目。要求合理安排六个项目的比赛顺序，使得每个运动员都不连续地参加两项比赛。ABCDEF甲乙丙丁戊己把六个比赛项目表示为六个点，如果两个项目有同一名运动员参加，就在这两个项目的点之间连一条边，如下图：从相邻边最多的点开始，找出一个点的序列，使依次排列的两个点不相邻（没有边相连），即达到要求。ABCDEFA、C、B、F、E、D就是一种比赛安排，还有其它的安排

4、方式！（从边最多的点开始安排）补例3、农夫m、狼w、羊s、草g过河问题。有位农夫，要带一匹狼、一只羊、一担草过河，农夫在，相安无事。河边只有一条小船，一次摆渡农夫只能带一样东西（狼、羊或草）。农夫不在场，狼要吃羊，羊要吃草。农夫怎样才能把这三样东西摆渡到对岸？至少要摆渡几次？解：首先要考虑这四个对象的组合问题。 全部组合如下：(1)m,w,s,g,(2)m,w,s,g(3)m,s,w,g(4)m,g,w,s(5)m,w,s,g(6)m,w,g,s(7)w,s,g,m(8)m,s,g,w显然，上面的2，4，7组合是不允许的！去掉这三个组合，还剩下10个状态。现在用一个顶点代表一种状态，按照状态中

5、是否有人m存在，分成上下两组，如下图：12345678910m,w,s,g m,s m,w,s m,w,g m,s,g w,g g s w找出从顶点1到顶点6的一条路！(1-7-4-10-3-9-2-6,1-7-4-8-5-9-2-6)补例4、分油问题。 现在有一个8升的瓶子装满了油，想利用一个3升和一个5升的瓶子将油分成两个4升，如何分?至少要分几次?8,0,03,5,06,0,24,4,07,0,15,0,35,3,02,3,32,5,17,1,04,1,33,2,36,2,01,5,21,4,3将8、5、3升瓶子中的油数列成一个三数组，表示一个状态，作为图的一个顶点，状态之间的转化用箭头

6、线相连，如下图。 从上面的例子可以得知： 在自然界和人类社会中，大量的事物以及事物间的关系都可以用图来加以描述。一般来讲，图论中的图是由点以及点与点之间的连线所构成的，通常用点代表所研究的对象，用线代表两个对象之间的关系，至于图中点的相对位置如何，点与点之间的连线是长还是短、是曲线还是直线，对于反映对象之间的关系，并不十分重要。因此，图论中的图与几何中的图形不是等价的！已知甲、乙、丙、丁、戊共5名乒乓球参赛选手，其中： 甲和其他各选手都赛过一次 乙和甲、丙赛过 丙和甲、乙、丁赛过 丁和甲、丙、戊赛过 戊和甲、丁赛过为反映这个情况，可用一个抽象图表示： 甲戊丁丙乙v1v2v3v4v5e1e2e5

7、e7e3e4e6边点v1，v2 ,v3 ,v4 ,v5分别代表这5名选手边 ei 表示对应的两名选手赛过一次。如果进一步反映参赛选手间的胜负关系，可用一条带箭头的连线表示：甲戊丁丙乙v1v2v3v4v5a1a2a5a7a3a4a6弧ai 表示对应的两名选手赛过一次，其箭头方向进一步表示这次比赛的胜负关系。如甲胜乙、乙胜丙等。 通常用点表示研究对象,用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显得并不重要。因此，图论中的图与几何图及工程图等本质上是不同的。为以后研究的方便，我们首先给出有关图的一些基本概念。

8、 一、图的概念图是由作为研究对象的有限个顶点的集合和表达这些顶点之间关系的m条线的集合组成的。记顶点集合为 ，线集合为 。线又分为弧（Arc）和边（Edge）。则图记为G=（V，L）。顶点有时也称为节点（node）。弧是由一对有序的顶点组成，表示了两个顶点之间可能运动的方向。如 表示从顶点 指向顶点 的弧， 是起点， 是终点。取消弧的方向就变成了边。边是只要任两点之间有连线，两个方向均可使用。弧可看作是城市道路中的单行道，而边则是双行道。由顶点集和弧组成的图称为有向图，如图（a）。由顶点集和边组成的图称为无向图，如图（b） (a)(b)链：有一序列弧 ，如果每一个弧 与前一个弧 恰有一个公共顶

9、点，则称这一序列弧为一个链。道路：如果链中每一个弧的终点是下面一个弧的起点，则这个链称为一个道路。环（圈）：连接 与 的一条链，如果 与 是同一个点时，称此链为环。次（或度）：以 为顶点的边的条数称为顶点 的次（或度），记作 。次为零的点称为弧立点，次为1的点称为悬挂点。悬挂点的边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。子图：设有两个图G1=V1，E1, G2=V2，E2，如果V2V1，E2E1，称G2是G1的子图；如果V2 V1，E2E1，称G2是G1的真子图；如果V2 =V1，E2E1，称G2是G1的生成子图（或称支撑子图）。连通图：一个图中任意两点间至少有一个链相连，则称

10、此图为连通图。否则称为不连通图。任何一个不连通图都可以分为若干个连通子图。v1v5v4v2v3e1e8e7e6e5e4e3e2v1v5v4v2e1e5e3子图v1v5v4v2v3e8e6e5e2生成子图二、网络 点或边带有某种数量指标的图叫网络图，简称网络。 与点或边有关的某些数量指标，我们经常称之为权，权可以代表如距离、费用、容量等。 左图可以看作： 从发电厂（节点1）向某城市（节点6）输送电力，必须通过中转站（节点2，3，4，5）转送，边上数字代表两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。 一个输油管道网。节点1表示管道的起点，节点6表示管道的终点，节点2

11、到5表示中转站，旁边的数字表示该段管道能通过的最大输送量。应怎样安排输油线路，使从节点1到节点6的总输送量最大？ 一张城市分布图。现在要在各城市之间架设电话线，应如何架设，使各城市之间既能通话，又使总的架设路线最短？ 第二节 树和最小树问题一、 树的概念及性质二、 图的子树三、 最小生成树四、 最小生成树算法一、树的概念及性质连通且不含环的无向图称为树。 树具有下面的性质：性质9.1：在树中，任意两顶点之间必有一条且仅有一条链。性质9.2：在树中去掉任一条边，则树成为不连通图。性质9.3：在树中不相邻的两个顶点间添上一条边，恰好得到一个环。树：连通且不含圈的无向图 树的性质： 任意两顶点之间必

12、有一条且仅有一条链。 去掉任一条边，则树成为不连通图。 不相邻的两个顶点间添上一条边，恰好得到一个环（圈）。树与古代美女一样，是恰到好处的，“减一分则瘦，加一分则肥”二、 图的子树子树：如果图G=（V，L）的子图是树，则称T为G的一个子树。如下图中的两个图，(b)是(a)的一个部分树。显然，如果图G有子树，则G必定是连通图。反之，如果图G是连通图，则G必有子树。三、 最小生成树最小生成树：设有一连通图G=（V，L），对于每一条边 ，有一个权 。一棵生成树所有树枝上权的总和，称为这个生成树的权，具有最小权的生成树称为最小生成树简称最小树。最小树定理：如果T是图G的一颗树，则它是最小树，当且仅当对

13、T外的每条边 有： 其中， 是树T内连接点 和 的唯一的链。由于图中不同弧的权可能相等，所以最小生成树并不一定唯一。四、 最小生成树算法1求最小生成树的破圈法第1步：先任取一个圈，从圈中去掉一条权最大的边，若在同一圈中有几条都是权最大边，则任选其中的一条边去掉。第2步：在余下的子圈中，重复上述步骤，直至没有圈为止。2求最小生成树的避圈法第1步：选一点v1 ，在所有与v1相关联的边中选取最小权边 (vi, vj) ，标记为“已选”。第2步：把所有点分为两部分V1和V2 ，其中：V1表示与标记为“已选”边相关联的点集；V2 是剩下的点构成的集合。第3步：选取最小权边：如果V2 ，则从边集 (vi,

14、 vj)|viV1, vjV2选取最小权边，标记为“已选”后，返回第2步；否则，算法结束。例9.1用破圈法和避圈法分别求最小生成树。23164515008575805090851004065破圈法避圈法生成树：6个点，只有5条边，最小边长310补例、用破圈法求图的最小支撑树BASDTCE27254143515下图中顶点AT代表村镇，边代表道路，边上的数字为道路长度，现在想沿着道路架设电线，使得所有村镇通电，如何架设总线路最短？（即求图的最小支撑树）7第三节 最短路问题一、 最短路问题二、 最短路问题算法一、 最短路问题设一个连通的赋权有向图G =(V, A)，对于每一个弧e = (vi,vj)

15、，相应地有一个权lij。vs和vt是G中的两个顶点，是G中从vs到vt的任意一条路，定义路的权是中所有弧的权之和，记作L()。最短路问题就是要在所有从vs到vt的路中，寻找一个权最小的路*，亦即L(*) = min L()。*称为从vs到vt的最短路。*的权L(*)称为从vs到vt的距离。二、最短路问题算法Dijkstra基本步骤是：假设每个弧的权是非负的，给每个顶点vi记一个数（称为标号），标号分临时性标号T和永久性标号P，永久性标号表示从到该点的最短路权，得到永久性标号的不再改变标号；临时性标号表示从开始点v1到该点vi的最短路权的上界。算法的每一步都把某一点的T标号改为P标号。开始时给初

16、始点v1的标号记为0，即P(v1)=0，其它点（记为临时性标号）的标号记为，即T(vi)= (i= 2 , ,n)。然后，若vi点是刚得到P标号的点，考虑L中与vi点相连的弧（vi,vj）且vj是T标号。对的标号进行如下更改： T(vj)=minT(vj),P(vi)+wij 比较所有具有T标号的点，把最小者改为P标号。当存在两个以上最小者时，可同时改为P标号。直到全部点均为P标号为止。 1325464332322 第0步：P(1)=0,T(i)=+； 第1步：与1相连的标号为2,3，均是T标号，修改2,3的标号，T(2)=minT(2),P(1)+w12=4,T(3)=3；在所有的T标号中，

17、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)

18、=8P(6)=8P(5)=6P(3)=3P(1)=0最短路问题 车龄每年的维护费用交易费用01234520004000500090001200070006000200010000从一特殊的节点出发，找出从该节点到网络中任何其它节点的最短路径问题某人买了一辆价值12000美元的新车，一辆车每年的维护费用依赖于年初时的车龄，具体费用见下表。为了避免旧车的高维护费用，他决定卖掉旧车买新车。旧车的价格依赖于交易时的车龄，见下表。为计算简单起见，假设任何时间新车的价格不变均为12000美元。他希望在今后5年内的净费用最小（即：净费用=购买价+维护价-售出价）。 123456217777712121221

19、31314412211-02-73-124-195-246-31第四节 最大流问题一、基本概念二、求最大流的标号算法在许多实际的网络系统中都存在着与流量有关的问题。如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。研究物质从一点流到另一点的最大流量问题，称为最大流问题。最大流问题是图与网络理论中十分重要的优化问题，他的应用非常广泛，如交通运输网络中人流、车流、货流，通讯网络中的信息流以及金融领域的资金流等等。本节主要介绍最大流问题的基本概念和算法。一、 基本概念网络与流研究网络流问题时，必须给出各弧的通过能力，它们表示弧的容量，如下图中各弧的权，通常记为 。在有向图中指定一点称为发点，另

20、一点称为收点，其余的点称为中间点。流过网络各边的流量具有一定的方向性，图上各边箭头所指方向，即为流量流动的方向。我们把标有弧容量 的网络称为容量网络，把容量网络中实际通过的流量集 称为网络流。 可行流与最大流在实际问题中，网络流必须满足两个条件，一是每个弧的流量不能超过该弧的最大通过能力，即容量；二是中间支点的流量为零。对每个支点，流入和流出该点的物资总量之差，是该点的净输出量，简称为该点的流量，由于中间支点只起中转的作用，所以中间点的流量为零。而发点和收点的流量必须相等。设图G=（V，L），其中支点集 ，这样就得到如下两个约束。（1）容量限制条件：对每个弧 ，有（2）平衡条件：对于中间点：流

21、入量=流出量，即对每个 有对于发点 ：对于收点 ：式中 称为发点（或收点）的流量。我们对满足以上两个条件的网络流称为可行流。网络系统上可行流具有如下特点：（1）发点的总流出量和收点的总流入量必相等；（2）每一个中间点的流入量与流出量的必相等；（3）每一个弧上的流量不能超过它的最大通过能力（即容量）。增广链在网络中，如果 ，则称此弧为饱和弧；如果 则称此弧为非饱和弧；如果 ，则称此弧为零弧。设C是网络中从发点 到收点 的一条链，链的方向是从 到 。对于链上的弧，如果弧的方向与链的方向一致，称此弧为前向弧。前向弧的全体记为 。如果弧的方向与链的方向相反，则称此弧为后向弧。后向弧全体记为 。增广链：

22、设 是一个可行流，C是从发点 到收点 的一条链，若C满足以下条件，则称C为一条增广链：(1) 在弧上 ， ，即 中每一条弧是非饱和弧。(2) 在弧上 ， ，即 中每一条弧是非零流弧。割集：设容量网络G=(V,E,C)，如果点集V被剖分为两个非空集合S1和S2，发点vsS1，收点vtS2，那么将弧集(S1, S2) = (vi, vj) | viS1, vjS2称为G的一个割集。容量最小的割集称为最小割集。最大流-最小割定理：1）设f为容量网络G=(V, E, C)的任一可行流，流量为W( f )， (S1, S2)为G的任一割集，容量为C(S1, S2)。则有W( f ) C(S1, S2)。

23、2）在任一容量网络G=(V, E, C)中，最大流的流量等于最小割的容量。二、求最大流的标号算法标号算法的基本思想是从网络图的一个可行流出发，用给顶点标号的方法找增广链。如果找到增广链，说明当前流不是最大，则增大可行流；然后继续在增大了流量的新可行流中找增广链，直到在某个新可行流中找不到增广链为止，这个新可行流就是最大流，同时也得到了最小割集。具体的算法过程：从一个可行流 出发（若网络中没有给定 ，则可以设 是零流），需要经过标号过程与调整过程。1标号过程在这个过程中，网络中的点或是标号点或是未标号点。每个标号点的标号包含两部分：第一标号表示它的标号是从哪一点得到的，以便找出增广链；第二个标号

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

25、求图9-14所示网络的最大流。弧旁的数为 。 解：1. 标号过程首先给初始点vs标上 。（1）检查vs，在弧(vs,v1)上， ，不满足标号条件。在弧(vs,v2)上， ，则v2的标号为 ，其中 （2）检查v2，在弧(v2,vt)上， ，不满足标号条件。在弧(v1,v2)上， ，则v1的标号为 ，其中（3）检查v1，在弧(v1,v3)上， ，则v3的标号为 ，其中（4）检查v3，在弧(v3,vt)上， ，则vt的标号为 ，其中因vt有了标号，所以转入调整过程。第五节 最小费用流问题 在研究实际问题时，我们不仅考虑流量，还经常要考虑费用的问题。如运输系统的货物流，即要考虑货运量最大，又要考虑总费

26、用最小。对于这类问题就可用下面的最小费用最大流问题来解决。最小费用流问题就是：对于网络图G中的弧，除标明弧的容量 外，还要标明流过该弧单位流量的费用 ，求G的一个可行流 ，使得流的总运输费用达到最小 特别，如果可行流 是最大流时，此问题就是最小费用最大流问题。 求最小费用最大流的基本思路是：从一个费用最小的可行流 出发（这样的可行流一定存在，因为费用 ，所以 就是一个流量为0的最小费用流），找出这个可行流 的费用最小的一条增广链C，沿C调整 ，直到找不到费用最小的增广链，就得到了最小费用最大流。 因此，求费用最小增广链是该问题的关键。 例9.6求下图（a）所示网络的最小费用最大流，弧旁权数为 。 第六节 用Excel求解