运筹学应用实例课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精品课件,*,精品课件,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,4.7 应 用 举 例,例1：比赛安排问题,有五名运动员参加游泳比赛，下表给出了每位运动员参加的比赛项目，问如何安排比赛，才能使每位运动员都不连续地参加比赛？,运动员 50,m,仰泳 50,m,蛙泳 100,m,蝶泳 100,m,自由泳 200,m,自由泳,A,*,B,*,*,C,*,*,D,*,E,*,*,4.7 应 用 举 例 例1：比赛安排问题有五名运动员参,解：,如果两项比赛没有同一名运动员参加，把这两项紧排在一起,v,1,v,2,v,3,v,4,v,5,为了解决这个问题，只需找到一条包含所有顶点的初等链。,如：,v,4,，v,1,，v,2,，v,3,，v,5,是一条初等链，对应的比赛是：,100,m,自由泳，50,m,仰泳，50,m,蛙泳，100,m,碟泳，200,m,自由泳。,用顶点,v,1,，v,2,，v,3,，v,4,，v,5,表示五项比赛项目,用一条边把代表这两个项目的顶点连接起来。这样得到下图,此问题的方案不唯一。,解：如果两项比赛没有同一名运动员参加，把这两项紧排在一起,例 2.线路铺设问题,下图是一个城镇的地图，现在要在该城镇的各地点铺设管道，已知各点相互之间的铺设费用（单位：千元），如何设计铺设线路，使各地互通的总铺设费用最少？,3,5,7,8,4,7,9,8,12,5,4,7,6,10,2,5,1,例 2.线路铺设问题下图是一个城镇的地图，现在要在该城镇的各,解：,求各边相通且总费用最少的方案，实际上求最小树，保证了各点之间连通且费用最少。,3,5,4,7,2,5,1,4,其总费用为：31千元,解：求各边相通且总费用最少的方案，实际上求最小树，保证了各点,例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,例3.设备更新问题某单位使用一台生产设备，在每年年底，单位领,解：,为解决好这一问题，建立下述网络模型，并用最短路法求解。,令：,v,i,第,i,年年初购进一台新设备，,i,=1,2,3,4,5,6,v,6,指第五年年末。,（,v,i,，v,j,）,第,i,年年初引进新设备一直使用到第,j,年年初。,W,ij,第,i,年年初购进的新设备一直使用到第,j,年年初这段,期间的全部费用。,解：为解决好这一问题，建立下述网络模型，并用最短路法求解。令,v,4,15,15,21,40,29,21,30,22,16,29,40,55,18,23,17,v,1,v,6,v,5,v,3,v,2,求解得,v,1,到,v,6,得最短路径为：,v,1,-,v,3,-v,6,，,最短路长为51。,设备更新的计划是,：,第一年初购置一台新设备，使用到第二年末，,第三年初购置一台新设备，使用到第五年末，总费用为51。,v41515214029213022162940551823,例4.房屋设计问题,下图是某建筑物的平面图，要求在建筑物的内部从每一房间都能走到别的所有房间，问至少要在墙上开多少门？试给出一个开门的方案。,A,B,C,D,E,F,I,H,G,J,K,例4.房屋设计问题下图是某建筑物的平面图，要求在建筑物的内部,I,A,B,C,J,K,H,D,G,E,F,把每一房间看作一个顶点，如果两房间相邻（有共同的隔墙），则用边把对应的两个顶点连起来，这样就得到一个无向图，如图。,从一个房间到另一房间相当于从这个顶点有一条链能到另一个顶点。,解：,图的任意一个连通的生成子图，在它的所有边对应的隔墙上开门，即可达到要求。,IABCJKHDGEF把每一房间看作一个顶点，如果两房间相邻,令所有边的权为1，为了使开的门尽可能少，就要使这个连通子图的生成子图的边尽可能少，即求,图的最小生成树,。,开门方案,最小生成树,I,B,A,C,D,E,F,K,J,H,G,对应的开门方案如图所示，共开10个门。,A,B,C,D,E,F,I,H,G,J,K,令所有边的权为1，为了使开的门尽可能少，就要使这个连通子图的,例5：选址问题,有六个居民点,v,1,，v,2,，v,3,，v,4,，v,5,，v,6,，,拟定建一夜校，已知各点参加学习的人数为25、20、30、10、35、45人，其道路如图所示，试确定学校位于哪一个居民点，才能使学习者所走的总路程最少？（图中边旁的数字为路段长度）,v,1,v,3,v,5,v,6,v,4,v,2,2,7,4,6,8,1,1,3,6,3,例5：选址问题有六个居民点v1，v2，v3，v4，v5，v6,解：,首先计算各点对间的最短路，每个学习者为使所走的路程最短，应走,最短路,。,V,1,V,2,V,3,V,4,V,5,V,6,D,0,=,V,1,V,2,V,3,V,4,V,5,V,6,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 0,V,1,V,2,V,3,V,4,V,5,V,6,V,1,V,2,V,3,V,4,V,5,V,6,C,0,=,1 1 1 1 1 1,2 2 2 2 2 2,3 3 3 3 3 3,4 4 4 4 4 4,5 5 5 5 5 5,6 6 6 6 6 6,迭代得到最短距离矩阵,D,0,和相应的中间点矩阵,C,0,如下：,解：首先计算各点对间的最短路，每个学习者为使所走的路程最短，,V,1,V,2,V,3,V,4,V,5,V,6,D,6,=,V,1,V,2,V,3,V,4,V,5,V,6,0 2 6 7 8 9,2 0 4 5 6 9,6 4 0 1 2 5,7 5 1 0 1 4,8 6 2 1 0 3,11 9,5,4 3 0,V,1,V,2,V,3,V,4,V,5,V,6,C,6,=,1 1 2 3 4 5,2 2 2 3 4 5,2 3 3 3 4 5,3 3 4 4 4 5,4 4 4 5 5 5,5 5 5 5 6 6,V,1,V,2,V,3,V,4,V,5,V,6,考虑各点的学习人数，对矩阵,D,6,的每一行乘以相应各点的人数，得到：,V1 V2 V3 V4,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，即夜校应设在,v,4,点，由,C,6,得到相应路径。,V,1,.V,4,：V,1,-V,2,-V,3,-V,4,V,2,.V,4,：V,2,-V,3,-V,4,V,3,.V,4,：V,3,-V,4,V,5,.V,4,：V,5,-V,4,V,6,.V,4,：V,6,-V,5,-V,4,=1065 835 535,520,525 750,D=0 50 150 175 200,例 6：网络运输容量问题,有三个仓库运送某种产品到四个市场上去，仓库的供应量是20、20和100件，市场需求量是20、20、60和20件。仓库与市场之间的线路上的容量如下表所示（容量零表示两点之间无直接的线路可通）。确定现有线路容量是否能满足市场的需求。若不能，应修改哪条线路的容量。,例 6：网络运输容量问题有三个仓库运送某种产品到四个市场上去,仓库,市场,B,1,B,2,B,3,B,4,供 应 量,A,1,A,2,A,3,需 求 量,20 20 60 20,30 10 0 40 20,0 0 10 50 20,20 10 40 5 100,用点,A,1,，A,2,，A,3,表示三个仓库；点,B,1,，B,2,，B,3,，B,4,表示四个市场；若仓库与市场间有线路可通，则在对应点间连一条弧，弧的容量就是线路的容量。,仓库市场 B1 B2,增设一发点,S，,连接,S,与,A,i,，,容量为,A,i,的供应量；增设一收点,T，,连接,B,i,与,T，,容量为,B,i,的需求量，得到如下的网络。,问题转化成求,S,到,T,的最大流问题。,S,T,A,1,A,2,A,3,B,1,B,2,B,3,B,4,20,20,100,10,40,10,20,50,20,10,40,5,20,60,20,30,增设一发点S，连接S与Ai，容量为Ai的供应量；增设一收点T,S,T,A,1,A,2,A,3,B,1,B,2,B,3,B,4,20,20,20,20,100,70,10,10,40,5,10,10,20,20,50,10,10,10,40,40,5,5,20,20,60,50,20,20,f=110,30,5,20,15,由于最大流量为110,而市场总需求量为120,所以现有线路容量不能满足市场的需求。,由上图得到，市场,B,3,的需求量不能满足，而仓库,A,3,的供应量尚有余量，所以考虑将弧（,A,3,，B,3,）,容量增至50，可满足市场的需要。,STA1A2A3B1B2B3B420,2020,20100,例8：分派问题,某飞行队有5名正驾驶员和5名副驾驶员。由于种种原因，某些正、副驾驶员不能同时飞行，某些则可以，如下表所示，（*表示可同机飞行）每架飞机出航时需要正、副驾驶员各一人，问最多能有几架飞机同时出航？应如何安排正、副驾驶员？,A,1,*,A,2,*,*,A,3,*,*,A,4,*,*,A,5,*,副,正,B,1,B,2,B,3,B,4,B,5,例8：分派问题某飞行队有5名正驾驶员和5名副驾驶员。由于种种,用顶点,A,1,，A,2,，A,3,，A,4,，A,5,表示5位副驾驶员；,B,1,，B,2,，B,3,，B,4,，B,5,表示5位正驾驶员；,若正、副驾驶员可同机飞行，则在对应的点之间连一条弧，方向由,A,指向,B；,增设一个起点,S,和终点,T，,得到下图，各弧的容量均为1。,则问题转化成求,S,到,T,的最大流问题。,用顶点A1，A2，A3，A4，A5表示5位副驾驶员；则问题转,S,T,A,1,A,2,A,3,A,4,A,5,B,1,B,2,B,3,B,4,B,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,STA1A2A3A4A5B1B2B3B4B511111111,f,max,=4，,知道最多能有4架飞机同时出航。,分配方案为：,A,2,-B,1,；A,3,-B,4,;A,4,-B,2,；A,5,-B,5,S,T,A,1,A,2,A,3,A,4,A,5,B,1,B,2,B,3,B,4,B,5,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,fmax=4，知道最多能有4架飞机同时出航。STA1A2A3,例9：桥梁切断问题,如下图,A、B、C、D、E、F,分别表示陆地和岛屿，若河的两岸分别被敌对两方部队占领，问至少切断哪几座桥梁才能阻止对方部队过河？,B,C,D,E,A,F,陆地、河流及桥梁示意图,例9：桥梁切断问题如下图A、B、C、D、E、F分别表示陆地和,解：,将,A，B，C，D，E，F,分别用一个点表示，相互之间有桥相连的连一条弧；弧的容量就是两点间的桥梁数；设一个方向，得到网络图如下：,B,A,C,D,F,E,2,2,1,1,1,1,2,1,2,2,2,割是分离,A,和,F,的弧的集合,若切断一个割的所有弧对应的桥梁,就可切断,A,和,F,之间的线路。切断最小割包含的弧对应