运筹学应用实例

运筹学应用实例解:如果两项比赛没有同一名运动员参加,把这两项紧排在一起v1v2v3v4v5为了解决这个问题,只需找到一条包含所有顶点得初等链。如:{v4,v1,v2,v3,v5}就是一条初等链,对应得比赛就是:100m自由泳,50m仰泳,50m蛙泳,100m碟泳,200m自由泳。用顶点v1,v2,v3,v4,v5表示五项比赛项目用一条边把代表这两个项目得顶点连接起来。这样得到下图此问题得方案不唯一。例2、线路铺设问题下图就是一个城镇得地图,现在要在该城镇得各地点铺设管道,已知各点相互之间得铺设费用(单位:千元),如何设计铺设线路,使各地互通得总铺设费用最少？3578479812547610251解:求各边相通且总费用最少得方案,实际上求最小树,保证了各点之间连通且费用最少。35472514其总费用为:31千元例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得最短路径为:v1-v3-v6,最短路长为51。设备更新得计划就是:第一年初购置一台新设备,使用到第二年末,第三年初购置一台新设备,使用到第五年末,总费用为51。例4、房屋设计问题下图就是某建筑物得平面图,要求在建筑物得内部从每一房间都能走到别得所有房间,问至少要在墙上开多少门？试给出一个开门得方案。ABCDEFIHGJKIABCJKHDGEF把每一房间看作一个顶点,如果两房间相邻(有共同得隔墙),则用边把对应得两个顶点连起来,这样就得到一个无向图,如图。从一个房间到另一房间相当于从这个顶点有一条链能到另一个顶点。解:图得任意一个连通得生成子图,在她得所有边对应得隔墙上开门,即可达到要求。令所有边得权为1,为了使开得门尽可能少,就要使这个连通子图得生成子图得边尽可能少,即求图得最小生成树。开门方案最小生成树IBACDEFKJHG对应得开门方案如图所示,共开10个门。ABCDEFIHGJK大家有疑问的，可以询问和交流可以互相讨论下，但要小声点例5:选址问题有六个居民点v1,v2,v3,v4,v5,v6,拟定建一夜校,已知各点参加学习得人数为25、20、30、10、35、45人,其道路如图所示,试确定学校位于哪一个居民点,才能使学习者所走得总路程最少？(图中边旁得数字为路段长度)v1v3v5v6v4v22746811363解:首先计算各点对间得最短路,每个学习者为使所走得路程最短,应走最短路。V1V2V3V4V5V6D0=V1V2V3V4V5V6027

20468

74013

6101683103

630V1V2V3V4V5V6V1V2V3V4V5V6C0=111111222222333333444444555555666666迭代得到最短距离矩阵D0和相应得中间点矩阵C0如下:V1V2V3V4V5V6D6=V1V2V3V4V5V60267892045696401257510148621031195430V1V2V3V4V5V6C6=112345222345233345334445444555555566V1V2V3V4V5V6考虑各点得学习人数,对矩阵D6得每一行乘以相应各点得人数,得到: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:网络运输容量问题有三个仓库运送某种产品到四个市场上去,仓库得供应量就是20、20和100件,市场需求量就是20、20、60和20件。仓库与市场之间得线路上得容量如下表所示(容量零表示两点之间无直接得线路可通)。确定现有线路容量就是否能满足市场得需求。若不能,应修改哪条线路得容量。仓库市场

B1B2B3B4供应量A1A2A3需求量20206020

301004020001050202010405100用点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,405,520,2060,5020,20f=11030,520,15由于最大流量为110,而市场总需求量为120,所以现有线路容量不能满足市场得需求。由上图得到,市场B3得需求量不能满足,而仓库A3得供应量尚有余量,所以考虑将弧(A3,B3)容量增至50,可满足市场得需要。例8:分派问题某飞行队有5名正驾驶员和5名副驾驶员。由于种种原因,某些正、副驾驶员不能同时飞行,某些则可以,如下表所示,(*表示可同机飞行)每架飞机出航时需要正、副驾驶员各一人,问最多能有几架飞机同时出航？应如何安排正、副驾驶员？A1

*A2

*

*A3

*

*A4

*

*

A5

*副正B1B2B3B4B5用顶点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-B5STA1A2A3A4