运筹学应用实例.ppt

4.7 应应 用用 举举 例例 例例1 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 年年初这段年年初这段 期间的全部费用。期间的全部费用。v4151521402921302216294055182317v1v6v5v3v2求解得求解得v1到到v6得最短路径为：得最短路径为：v1-v3-v6，最短路长为最短路长为51。设备更新的计划是设备更新的计划是：第一年初购置一台新设备，使用到第二年末，：第一年初购置一台新设备，使用到第二年末，第三年初购置一台新设备，使用到第五年末，总费用为第三年初购置一台新设备，使用到第五年末，总费用为51。例例4.4.房屋设计问题房屋设计问题下图是某建筑物的平面图，要求在建筑物的内部从每一房间下图是某建筑物的平面图，要求在建筑物的内部从每一房间都能走到别的所有房间，问至少要在墙上开多少门？试给出都能走到别的所有房间，问至少要在墙上开多少门？试给出一个开门的方案。一个开门的方案。ABCDEFIHGJKIABCJKHDGEF把每一房间看作一个顶点，如果两房间相邻（有共同的隔把每一房间看作一个顶点，如果两房间相邻（有共同的隔墙），则用边把对应的两个顶点连起来，这样就得到一个墙），则用边把对应的两个顶点连起来，这样就得到一个无向图，如图。无向图，如图。从一个房间到另一房间相当于从这个顶点有一条链能到另一从一个房间到另一房间相当于从这个顶点有一条链能到另一个顶点。个顶点。解：解：图的任意一个连通图的任意一个连通的生成子图，在它的生成子图，在它的所有边对应的隔的所有边对应的隔墙上开门，即可达墙上开门，即可达到要求。到要求。令所有边的权为令所有边的权为1，为了使开的门尽可能少，就要使这个连，为了使开的门尽可能少，就要使这个连通子图的生成子图的边尽可能少，即求图的最小生成树。通子图的生成子图的边尽可能少，即求图的最小生成树。开门方案开门方案最小生成树最小生成树IBACDEFKJHG对应的开门方案如图所对应的开门方案如图所示，共开示，共开10个门。个门。ABCDEFIHGJK例例5 5：选址问题：选址问题有六个居民点有六个居民点v1，v2，v3，v4，v5，v6，拟定建一夜校，已知拟定建一夜校，已知各点参加学习的人数为各点参加学习的人数为25、20、30、10、35、45人，其道路人，其道路如图所示，试确定学校位于哪一个居民点，才能使学习者所如图所示，试确定学校位于哪一个居民点，才能使学习者所走的总路程最少？（图中边旁的数字为路段长度）走的总路程最少？（图中边旁的数字为路段长度）v1v3v5v6v4v22746811363解：首先计算各点对间的最短路，每个学习者为使所走的路解：首先计算各点对间的最短路，每个学习者为使所走的路程最短，应走最短路。程最短，应走最短路。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 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点，由点，由C6得到相应路径。得到相应路径。V1.V4：V1-V2-V3-V4V2.V4：V2-V3-V4V3.V4：V3-V4V5.V4：V5 -V4V6.V4：V6-V5-V4=1065 835 535 520 525 750 例例 6 6：网络运输容量问题：网络运输容量问题有三个仓库运送某种产品到四个市场上去，仓库的供应量有三个仓库运送某种产品到四个市场上去，仓库的供应量是是2020、2020和和100100件，市场需求量是件，市场需求量是2020、2020、6060和和2020件。仓库件。仓库与市场之间的线路上的容量如下表所示（容量零表示两点与市场之间的线路上的容量如下表所示（容量零表示两点之间无直接的线路可通）。确定现有线路容量是否能满足之间无直接的线路可通）。确定现有线路容量是否能满足市场的需求。若不能，应修改哪条线路的容量。市场的需求。若不能，应修改哪条线路的容量。仓库仓库市场市场 B1 B2 B3 B4 供供 应应 量量A1A2A3需需 求求 量量 20 20 60 20 30 10 0 40 200 0 10 50 2020 10 40 5 100用点用点A A1 1，A A2 2，A A3 3表示三个仓库；点表示三个仓库；点B B1 1，B B2 2，B B3 3，B B4 4表示四个市表示四个市场；若仓库与市场间有线路可通，则在对应点间连一条弧，场；若仓库与市场间有线路可通，则在对应点间连一条弧，弧的容量就是线路的容量。弧的容量就是线路的容量。增设一发点增设一发点S，连接连接S与与Ai，容量为容量为Ai的供应量；增设一收点的供应量；增设一收点T，连接连接Bi与与T，容量为容量为Bi的需求量，得到如下的网络。的需求量，得到如下的网络。问题转化成求问题转化成求S到到T的最大流问题。的最大流问题。STA1A2A3B1B2B3B420201001040102050201040520602030STA1A2A3B1B2B3B420,2020,20100,7010,1040,510,1020,2050,1010,1040,405,520,2060,5020,20f=11030,520,15由于最大流量为由于最大流量为110,而市场总需求量为而市场总需求量为120,所以现有线路容量所以现有线路容量不能满足市场的需求。不能满足市场的需求。由上图得到，市场由上图得到，市场B3的需求量不能满足，而仓库的需求量不能满足，而仓库A3的供应量的供应量尚有余量，所以考虑将弧（尚有余量，所以考虑将弧（A3，B3）容量增至容量增至50，可满足市，可满足市场的需要。场的需要。例例8 8：分派问题：分派问题某飞行队有某飞行队有5名正驾驶员和名正驾驶员和5名副驾驶员。由于种种原因，某些名副驾驶员。由于种种原因，某些正、副驾驶员不能同时飞行，某些则可以，如下表所示，（正、副驾驶员不能同时飞行，某些则可以，如下表所示，（*表示可同机飞行）每架飞机出航时需要正、副驾驶员各一人，表示可同机飞行）每架飞机出航时需要正、副驾驶员各一人，问最多能有几架飞机同时出航？应如何安排正、副驾驶员？问最多能有几架飞机同时出航？应如何安排正、副驾驶员？A1 *A2 *A3 *A4 *A5 *副副正正B1 B2 B3 B4 B5用顶点用顶点A1，A2，A3，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 9：桥梁切断问题：桥梁切断问题如下图如下图A、B、C、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，而而D，E，F不能获得标号，不能获得标号，从而知道该最大流对应的最小割为从而知道该最大流对应的最小割为（A，E），（），（C，D），），（C，F）因此，切断因此，切断AE，CD，CF三座桥梁，即可阻止对方三座桥梁，即可阻止对方部队过河。部队过河。由最大流最小割定理，分离由最大流最小割定理，分离A和和F的最小割容量等于由的最小割容量等于由A到到F的的最大流量最大流量例例11:11:生产计划问题生产计划问题某工厂与客户签定合同某工厂与客户签定合同,当月起连续三个月每月末向客户提供当月起连续三个月每月末向客户提供某种产品。该厂三个月的生产能力、单位产品生产成本及客某种产品。该厂三个月的生产能力、单位产品生产成本及客户需求见下表。户需求见下表。已知单位产品每积压一个月需支付存储费已知单位产品每积压一个月需支付存储费2 2元。在签定合同时，元。在签定合同时，工厂有该产品的库存量工厂有该产品的库存量5 5个，工厂希望在第三个月末完成合同个，工厂希望在第三个月末完成合同后还能存储该产品后还能存储该产品1010个。问工厂应如何安排生产计划，使在个。问工厂应如何安排生产计划，使在满足上述条件的情况下，总的费用最小？满足上述条件的情况下，总的费用最小？月份月份正常生正常生产能力产能力加班生加班生产能力产能力需求量需求量单位产品正单位产品正常生产成本常生产成本单位产品加单位产品加班生产成本班生产成本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结结 束！束！