运筹学应用实例.ppt

1、4.7 应 用 举 例,例1：比赛安排问题,有五名运动员参加游泳比赛，下表给出了每位运动员参加的比赛项目，问如何安排比赛，才能使每位运动员都不连续地参加比赛？,解：,如果两项比赛没有同一名运动员参加，把这两项紧排在一起,为了解决这个问题，只需找到一条包含所有顶点的初等链。,如：v4，v1，v2，v3，v5是一条初等链，对应的比赛是： 100m自由泳，50m仰泳，50m蛙泳，100m碟泳，200m自由泳。,用顶点v1，v2，v3，v4，v5表示五项比赛项目,用一条边把代表这两个项目的顶点连接起来。这样得到下图,此问题的方案不唯一。,例 2.线路铺设问题,下图是一个城镇的地图，现在要在该城镇的各地

2、点铺设管道，已知各点相互之间的铺设费用（单位：千元），如何设计铺设线路，使各地互通的总铺设费用最少？,解：求各边相通且总费用最少的方案，实际上求最小树，保证了各点之间连通且费用最少。,其总费用为：31千元,例3.设备更新问题,某单位使用一台生产设备，在每年年底，单位领导都要决策下年度是购买新设备还是继续使用旧设备。 若购置新设备，需要支付一笔购置费；如果继续使用旧的，则要支付一定的维修费用。 一般说来，维修费随设备使用年限的延长而增加。根据以往的统计资料，已经估算出设备在各年年初的价格和不同使用年限的年维修费用，分别示于表1和表2。,表1,表2,解：为解决好这一问题，建立下述网络模型，并用最短

3、路法求解。,令： vi 第 i 年年初购进一台新设备，i=1 , 2 , 3 , 4 , 5 , 6 v6 指第五年年末。 （vi，vj） 第 i年年初引进新设备一直使用到第 j 年年初。 Wij 第 i 年年初购进的新设备一直使用到第 j 年年初这段 期间的全部费用。,求解得v1到v6得最短路径为： v1-v3-v6，最短路长为51。 设备更新的计划是：第一年初购置一台新设备，使用到第二年末， 第三年初购置一台新设备，使用到第五年末，总费用为51。,例4.房屋设计问题,下图是某建筑物的平面图，要求在建筑物的内部从每一房间都能走到别的所有房间，问至少要在墙上开多少门？试给出一个开门的方案。,把

4、每一房间看作一个顶点，如果两房间相邻（有共同的隔墙），则用边把对应的两个顶点连起来，这样就得到一个无向图，如图。,从一个房间到另一房间相当于从这个顶点有一条链能到另一个顶点。,解：,图的任意一个连通的生成子图，在它的所有边对应的隔墙上开门，即可达到要求。,令所有边的权为1，为了使开的门尽可能少，就要使这个连通子图的生成子图的边尽可能少，即求图的最小生成树。,开门方案,最小生成树,对应的开门方案如图所示，共开10个门。,例5：选址问题,有六个居民点v1，v2，v3，v4，v5，v6，拟定建一夜校，已知各点参加学习的人数为25、20、30、10、35、45人，其道路如图所示，试确定学校位于哪一个居

5、民点，才能使学习者所走的总路程最少？（图中边旁的数字为路段长度）,解：首先计算各点对间的最短路，每个学习者为使所走的路程最短，应走最短路。,迭代得到最短距离矩阵D0和相应的中间点矩阵C0如下：,考虑各点的学习人数，对矩阵D6的每一行乘以相应各点的人数，得到：,最短路程为520，即夜校应设在v4点，由 C6得到相应路径。,V1.V4：V1- V2 - V3 - V4 V2.V4： V2 - V3 - V4 V3.V4： V3 - V4 V5.V4： V5 - V4 V6.V4： V6- V5 - V4,例 6：网络运输容量问题,有三个仓库运送某种产品到四个市场上去，仓库的供应量是20、20和10

6、0件，市场需求量是20、20、60和20件。仓库与市场之间的线路上的容量如下表所示（容量零表示两点之间无直接的线路可通）。确定现有线路容量是否能满足市场的需求。若不能，应修改哪条线路的容量。,用点A1，A2，A3表示三个仓库；点B1，B2，B3，B4表示四个市场；若仓库与市场间有线路可通，则在对应点间连一条弧，弧的容量就是线路的容量。,增设一发点S，连接S与Ai，容量为Ai的供应量；增设一收点T，连接Bi与T，容量为Bi的需求量，得到如下的网络。 问题转化成求S到T的最大流问题。,由于最大流量为110,而市场总需求量为120, 所以现有线路容量不能满足市场的需求。 由上图得到，市场B3的需求量

7、不能满足，而仓库A3的供应量尚有余量，所以考虑将弧（A3，B3）容量增至50，可满足市场的需要。,例8：分派问题,某飞行队有5名正驾驶员和5名副驾驶员。由于种种原因，某些正、副驾驶员不能同时飞行，某些则可以，如下表所示，（*表示可同机飞行）每架飞机出航时需要正、副驾驶员各一人，问最多能有几架飞机同时出航？应如何安排正、副驾驶员？,用顶点A1，A2，A3，A4，A5表示5位副驾驶员； B1，B2，B3，B4，B5表示5位正驾驶员； 若正、副驾驶员可同机飞行，则在对应的点之间连一条弧，方向由A指向B； 增设一个起点S和终点T，得到下图，各弧的容量均为1。,则问题转化成求S到T的最大流问题。,fma

8、x=4，知道最多能有4架飞机同时出航。 分配方案为： A2 - B1；A3 - B4 ; A4 - B2；A5 - B5,例9：桥梁切断问题,如下图A、B、C、D、E、F分别表示陆地和岛屿，若河的两岸分别被敌对两方部队占领，问至少切断哪几座桥梁才能阻止对方部队过河？,陆地、河流及桥梁示意图,解：,将A，B，C，D，E，F分别用一个点表示，相互之间有桥相连的连一条弧；弧的容量就是两点间的桥梁数；设一个方向，得到网络图如下：,割是分离A和F的弧的集合,若切断一个割的所有弧对应的桥梁,就可切断A和F之间的线路。切断最小割包含的弧对应的桥梁，是切断A和F之间线路的桥梁数最少的方法。,由上图得知：已标号

9、点为A，B，C，而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