运筹学应用实例.ppt

《运筹学应用实例.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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。年份12345购置费1010111213使用年限0-11-22-33-44-5维修费5681115表1表2解：为解决好这一问题，建立下述网络模型，并用最短路法求解。令：vi—第i年年初购进一台新设备，i=1,2,3,4,5,6v6指第五年年末。（vi，vj）—第i年年初引进新设备一直使用到第j年年初。Wij—第i年年初购进的新设备一直使用到第j年年初这段期间的全部费用。v4151521402921302216294055182317v1v6v5v3v2求解得v1到v6

4、得最短路径为：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解：首先计算各点对间的最短路，每个学习者为使所走的路程最短，应走最短路。V1V2V

6、3V4V5V6D0=V1V2V3V4V5V602720468740136101683103630V1V2V3V4V5V6V1V2V3V4V5V6C0=111111222222333333444444555555666666迭代得到最短距离矩阵D0和相应的中间点矩阵C0如下：V1V2V3V4V5V6D6=V1V2V3V4V5V60267892045696401257510148621031195430V1V2V3V4V5V6C6=112345222345233345334445444555555566V1V2V3V4V5V6考虑各点的学习人数，对矩阵D6的

7、每一行乘以相应各点的人数，得到：D=050150175200275400801001201801801200306015070501001040280210703501054954052251801350最短路程为520，即夜校应设在v4点，由C6得到相应路径。V1…….V4：V1-V2-V3-V4V2…….V4：V2-V3-V4V3…….V4：V3-V4V5…….V4：V5-V4V6…….V4：V6-V5-V4=[1065835535520525750]例6：网络运输容量问题有三个仓库运送某种产品到四个市场上去，