1、4.7 应 用 举 例 例1：比赛安排问题有五名运动员参加游泳比赛，下表给出了每位运动员参加的比赛项目，问如何安排比赛，才能使每位运动员都不连续地参加比赛？运动员运动员 50m仰泳仰泳 50m蛙泳蛙泳 100m蝶泳蝶泳 100m自由泳自由泳 200m自由泳自由泳 A *B *C *D *E *解：如果两项比赛没有同一名运动员参加，把这两项紧排在一起v1v2v3v4v5为了解决这个问题，只需找到一条包含所有顶点的初等链。如：v4，v1，v2，v3，v5是一条初等链，对应的比赛是：100m自由泳，50m仰泳，50m蛙泳，100m碟泳，200m自由泳。用顶点v1，v2，v3，v4，v5表示五项比赛项
2、目用一条边把代表这两个项目的顶点连接起来。这样得到下图此问题的方案不唯一。例 2.线路铺设问题下图是一个城镇的地图，现在要在该城镇的各地点铺设管道，已知各点相互之间的铺设费用（单位：千元），如何设计铺设线路，使各地互通的总铺设费用最少？3578479812547610251解：求各边相通且总费用最少的方案，实际上求最小树，保证了各点之间连通且费用最少。35472514其总费用为：31千元例3.设备更新问题某单位使用一台生产设备，在每年年底，单位领导都要决策下年度是购买新设备还是继续使用旧设备。若购置新设备，需要支付一笔购置费；如果继续使用旧的，则要支付一定的维修费用。一般说来，维修费随设备使用
3、年限的延长而增加。根据以往的统计资料，已经估算出设备在各年年初的价格和不同使用年限的年维修费用，分别示于表1和表2。年份年份 1 2 3 4 5 购置费购置费 10 10 11 12 13 使用年限使用年限 0-1 1-2 2-3 3-4 4-5 维修费维修费 5 6 8 11 15 表1表2解：为解决好这一问题，建立下述网络模型，并用最短路法求解。令：vi 第 i 年年初购进一台新设备，i=1,2,3,4,5,6 v6 指第五年年末。（vi，vj）第 i年年初引进新设备一直使用到第 j 年年初。Wij 第 i 年年初购进的新设备一直使用到第 j 年年初这段 期间的全部费用。v41515214
4、02921302216294055182317v1v6v5v3v2求解得v1到v6得最短路径为：v1-v3-v6，最短路长为51。设备更新的计划是：第一年初购置一台新设备，使用到第二年末，第三年初购置一台新设备，使用到第五年末，总费用为51。例4.房屋设计问题下图是某建筑物的平面图，要求在建筑物的内部从每一房间都能走到别的所有房间，问至少要在墙上开多少门？试给出一个开门的方案。ABCDEFIHGJKIABCJKHDGEF把每一房间看作一个顶点，如果两房间相邻（有共同的隔墙），则用边把对应的两个顶点连起来，这样就得到一个无向图，如图。从一个房间到另一房间相当于从这个顶点有一条链能到另一个顶点。解
5、：图的任意一个连通的生成子图，在它的所有边对应的隔墙上开门，即可达到要求。令所有边的权为1，为了使开的门尽可能少，就要使这个连通子图的生成子图的边尽可能少，即求图的最小生成树。开门方案最小生成树IBACDEFKJHG对应的开门方案如图所示，共开10个门。ABCDEFIHGJK例5：选址问题有六个居民点v1，v2，v3，v4，v5，v6，拟定建一夜校，已知各点参加学习的人数为25、20、30、10、35、45人，其道路如图所示，试确定学校位于哪一个居民点，才能使学习者所走的总路程最少？（图中边旁的数字为路段长度）v1v3v5v6v4v22746811363解：首先计算各点对间的最短路，每个学习者
6、为使所走的路程最短，应走最短路。V1 V2 V3 V4 V5 V6 D0=V1V2V3V4V5V6 0 2 7 2 0 4 6 8 7 4 0 1 3 6 1 0 1 6 8 3 1 0 3 6 3 0V1 V2 V3 V4 V5 V6V1V2V3V4V5V6C0=1 1 1 1 1 1 2 2 2 2 2 23 3 3 3 3 34 4 4 4 4 45 5 5 5 5 56 6 6 6 6 6 迭代得到最短距离矩阵D0和相应的中间点矩阵C0如下：V1 V2 V3 V4 V5 V6 D6=V1V2V3V4V5V60 2 6 7 8 92 0 4 5 6 96 4 0 1 2 57 5 1 0
7、 1 4 8 6 2 1 0 311 9 5 4 3 0V1V2V3V4V5V6C6=1 1 2 3 4 5 2 2 2 3 4 5 2 3 3 3 4 53 3 4 4 4 54 4 4 5 5 55 5 5 5 6 6 V1 V2 V3 V4 V5 V6考虑各点的学习人数，对矩阵D6的每一行乘以相应各点的人数，得到：D=0 50 150 175 200 275 40 0 80 100 120 180 180 120 0 30 60 150 70 50 10 0 10 40 280 210 70 35 0 105 495 405 225 180 135 0最短路程为520，即夜校应设在v4点
8、，由C6得到相应路径。V1.V4：V1-V2-V3-V4V2.V4：V2-V3-V4V3.V4：V3-V4V5.V4：V5 -V4V6.V4：V6-V5-V4D=1065 835 535 520 525 750 例 6：网络运输容量问题有三个仓库运送某种产品到四个市场上去，仓库的供应量是20、20和100件，市场需求量是20、20、60和20件。仓库与市场之间的线路上的容量如下表所示（容量零表示两点之间无直接的线路可通）。确定现有线路容量是否能满足市场的需求。若不能，应修改哪条线路的容量。仓库仓库市场市场 B1 B2 B3 B4 供供 应应 量量A1A2A3需需 求求 量量 20 20 60
9、20 30 10 0 40 200 0 10 50 2020 10 40 5 100用点A1，A2，A3表示三个仓库；点B1，B2，B3，B4表示四个市场；若仓库与市场间有线路可通，则在对应点间连一条弧，弧的容量就是线路的容量。增设一发点S，连接S与Ai，容量为Ai的供应量；增设一收点T，连接Bi与T，容量为Bi的需求量，得到如下的网络。问题转化成求S到T的最大流问题。STA1A2A3B1B2B3B420201001040102050201040520602030STA1A2A3B1B2B3B420,2020,20100,7010,1040,510,1020,2050,1010,1040,40
10、5,520,2060,5020,20f=11030,520,15由于最大流量为110,而市场总需求量为120,所以现有线路容量不能满足市场的需求。由上图得到，市场B3的需求量不能满足，而仓库A3的供应量尚有余量，所以考虑将弧（A3，B3）容量增至50，可满足市场的需要。例8：分派问题某飞行队有5名正驾驶员和5名副驾驶员。由于种种原因，某些正、副驾驶员不能同时飞行，某些则可以，如下表所示，（*表示可同机飞行）每架飞机出航时需要正、副驾驶员各一人，问最多能有几架飞机同时出航？应如何安排正、副驾驶员？A1 *A2 *A3 *A4 *A5 *副副正正B1 B2 B3 B4 B5用顶点A1，A2，A3，
11、A4，A5表示5位副驾驶员；B1，B2，B3，B4，B5表示5位正驾驶员；若正、副驾驶员可同机飞行，则在对应的点之间连一条弧，方向由A指向B；增设一个起点S和终点T，得到下图，各弧的容量均为1。则问题转化成求S到T的最大流问题。STA1A2A3A4A5B1B2B3B4B5111111111111111111fmax=4，知道最多能有4架飞机同时出航。分配方案为：A2-B1；A3-B4 ;A4-B2；A5-B5STA1A2A3A4A5B1B2B3B4B51,01,01,11,11,11,11,11,01,11,11,11,11,01,01,01,11,11,1例9：桥梁切断问题如下图A、B、C、
12、D、E、F分别表示陆地和岛屿，若河的两岸分别被敌对两方部队占领，问至少切断哪几座桥梁才能阻止对方部队过河？BCDEAF陆地、河流及桥梁示意图解：将A，B，C，D，E，F分别用一个点表示，相互之间有桥相连的连一条弧；弧的容量就是两点间的桥梁数；设一个方向，得到网络图如下：BACDFE22111121222割是分离A和F的弧的集合,若切断一个割的所有弧对应的桥梁,就可切断A和F之间的线路。切断最小割包含的弧对应的桥梁，是切断A和F之间线路的桥梁数最少的方法。B(A,1)A(0,+)CDF E2,12,11,11,01,11,12,01,12,12,12,0(B,1)由上图得知：已标号点为A，B，C
13、，而D，E，F不能获得标号，从而知道该最大流对应的最小割为（A，E），（C，D），（C，F）因此，切断AE，CD，CF三座桥梁，即可阻止对方部队过河。由最大流最小割定理，分离A和F的最小割容量等于由A到F的最大流量例11:生产计划问题某工厂与客户签定合同,当月起连续三个月每月末向客户提供某种产品。该厂三个月的生产能力、单位产品生产成本及客户需求见下表。已知单位产品每积压一个月需支付存储费2元。在签定合同时，工厂有该产品的库存量5个，工厂希望在第三个月末完成合同后还能存储该产品10个。问工厂应如何安排生产计划，使在满足上述条件的情况下，总的费用最小？月份正常生产能力加班生产能力需求量单位产品正常生产成本单位产品加班生产成本1 30 15 30 50 552 40 15 30 60 653 20 10 30 55 62解：构造网络图如下X1 工厂处于正常生产状态X2 工厂处于加班生产状态Vj 第j个月生产产品的存储与供货点。增设起点S和终点T。这样问题就转化为求从S到T的最小费用最大流问题。X1X2STV1V2V35,2+,0+,0+,230,5040,6020,5515,5515,6510,6240,030,030,0+,2结 束！
