运筹学课程设计

《运筹学课程设计》由会员分享，可在线阅读，更多相关《运筹学课程设计（26页珍藏版）》请在装配图网上搜索。

1、韦鳥理三大伊QINGDAO TECHNOLOGICAL UNIVERSITY运筹学案例6.1 网络中的服务及设施布局（a）在 11 个小区内准备共建一套医务所，邮局，储蓄所，综合 超市等服务设施，应建于哪一个居民小区，使对居民总体来 说感到方便；问题分析为满足题目的要求。只需要找到每一个小区到其他任何一个小 区的最短距离。然后再用每一小区的人数进行合理的计算后累加，结 果最小的便是最合理的建设地。以下表中数据dij表示图中从i至Uj点的最短距离7i234567891011i0411611158121613172407510121211151716311701165191412241846511

2、0591061015115111065041286171261512594016117211378121910121604859812111468114049591615121067840126101317241517215912061117161811121395660设施建于各个小区时居民所走路程设施建于各个小区时居民所走路程1234567891011012000 33000 18000 33000 4500024000 3600048000390005100014400 02450017500 55000 4200042000 3850052500 595005600040700 259

3、00 040700 22200 1850070300 5180044400 629006660030000 25000 55000 0 25000 4500050000 3000050000 750005500033000 30000 18000 15000 01200036000 2400018000 510003600037500 30000 12500 22500 10000 040000 2750017500 525003250022400 33600 53200 28000 33600 448000 1120022400140002520054000 49500 63000 2700

4、0 36000 4950018000 018000 405002250052800 49500 39600 33000 19800 23100 26400 132000396001980052000 68000 96000 60000 68000 84000 20000 36000 4800002400059500 56000 63000 38500 42000 45500 31500 17500 21000210000395900 379500 457800 457700 324400 409400 358200 285700 339800 455000 366100由以上数据可知。各项服务

5、设施应建于第八个居民小区。（b）电信部门拟将宽带网铺设到各个小区，应如何铺设最为经济 问题分析要解决这个问题时期最为经济。只需要找到图找的最小部 分树便可以。 以下是最小部分树。起点 终点 距离1444 254 555 646 354868748947 10510110所以按照以上路径进行线路铺设，就可达到最经济。总的距离为42（c）一个考察小组从小区1 出发，经 5.8.10。小区（考察顺序不限)，最后到小区9 再离去，请帮助选一条最短的考察路线。 问题分析找出这几个小区通过的不同组合，计算出路程总和，最短的就是 最优路线。以下是不同组合以及各个路程-15(11) 58(8) 810(9)

6、109(12)404115(11) 510(17)108(9) 89(4)三18(12) 810(9)105(17) 59(6)44四18(12) 85(8)510(17) 109(12)49五 1 10 (13) 105 (17) 58 (8) 89 (4)42六 1 10 (13) 108 (9) 85 (8) 59 (6)36由以上数据可知最短的考察路线是110859案例 8.2 用不同的方法解决最短路问题说明：为了解题的方便，现将图中的代号修改如下。A、B1、B2、B3、C1、C2、D1、D2、D3、E.修改为 1、2、3、4、5、7、 8、 9、 10。问题分析(a)乙提出用动态规划

7、的方法求解。现将解题过程描述如下。用所在的点 pi 表示状态，决策集合就是除 pi 以外的点，选定一个 pj i i j以后，得到效益后转入新状态片，当状态是pn时，过程停止。以下是用lingo解题的代码和数据：model:data:data:D=n=10;3 2 1end data4 4 3sets:1 3way/1.n/:F;3 5 3roads(way,way)/2 5 31,2 1,3 1,41 4 22,7 2,5 2,633,5 3,614,5 4,6 4,95;5,7 5,8 5,9end data6,7 6,8 6,9F(n)=0;7,10for(way(i) | i#lt#n

8、:8,109,10F(i)=min(roads(i,j):D(i,j)+F(j);/:D,P;);end setsfor(roads(i,j):P(i,j)=if(F(i)D(i,j)+F(j),1,0)#eq# );End数据：Feasible solution found.Total solver iterations:N10.00000P( 2, 5)0.000000F( 1)8.000000P( 2, 6)1.000000F( 2)7.000000P( 3, 5)1.000000F( 3)6.000000P( 3, 6)0.000000F( 4)8.000000P( 4, 5)1.00

9、0000F( 5)5.000000P( 4, 6)0.000000F( 6)4.000000P( 4, 9)1.000000F( 7)3.000000P( 5, 7)1.000000F( 8)1.000000P( 5, 8)0.000000F( 9)5.000000P( 5, 9)0.000000F( 10)0.000000P( 6, 7)1.000000D( 1, 2)3.000000P( 6, 8)0.000000D( 1, 3)2.000000P( 6, 9)0.000000D( 1, 4)1.000000P( 7, 10)1.000000D( 2, 7)4.000000P( 8, 10

10、)1.000000D( 2, 5)4.000000P( 9, 10)1.00000D( 5, 9)3.000000D( 2, 6)3.000000D( 6, 7)1.000000D( 3, 5)1.000000D( 6, 8)4.000000D( 3, 6)3.000000D( 6, 9)2.000000D( 4, 5)3.000000D( 7, 10)3.000000D( 4, 6)5.000000D( 9, 10)5.000000D( 4, 9)3.000000P( 1, 2)0.000000D( 5, 7)2.000000P( 1, 3)1.000000D( 5, 8)5.000000D

11、( 8, 10)1.000000D( 9, 10)5.000000P( 1, 2)0.000000P( 1, 3)1.000000P( 1, 4)0.000000VariableValueP( 2, 7) 1.000000如果p (i, j) =1则点i到点n的最短路的第一步是i-j,否则就不 是。所以有结果可知，最优的路线是135710，也就是 A-B2-C1-D1-E最短路程是8( b )丙提出用整数规划模型求解问题分析设用a.表示权数，x.表示：=1时为最短路径上的一段i到j的弧。 ijij=0 时表示不是。数学模型是：minz二工a.x.ij ijs.t Exij=1(i=1.2m)工

12、 a.=1(j=1.2.n) ijXjj=01(i=1.2m j=1.2n )由以上模型可以得出，在AB1B2B2，这一段时。可以取AB2在2，B1B2B2C1C2 这一段时可以取 B2C1，在 C1C2D1D2D3 这 一段时可以取C1D1，在D1D2D3E这一段可取DE。所以求 得的最短路线是 AB2C1D1E 最短路程是 8。(C) 丁用求最小部分树的方法解决 问题分析求出最小部分树后。如果在最先部分数上有一条吧A到E联通的 路径，那这个就是最短路径。以下是求的最小部分数：此问题的杲小生成树如下：起点终点距离141132351572761；I3由此可知在最小部分数中存在那样的一条链：13

13、5-7-10，也就是原题中的路径：AfB2fCfDfE，最短路程是8案例二1、 某造船厂根据合同要在当年算起的连续三年年末各提供三条 规格相同的大型货轮。已知该厂今后三年的生产能力及生产成本 如下表所示：年度正常生产时可完成的货轮数加班生产时可完成的货轮数正常生产时每 条货轮成本/万 元第一年23500第二年42600第三年13550已知加班生产情况下每条货轮成本比正常生产时高出70 万元，又 知造出的货轮如当年不交货，每条货轮每积压一年增加维护保养等损 失为 40 万元，在签订合同时该厂已有两条积压未交货的货轮，该厂 希望在第三年末在交完合同任务后能储存一条备用，问该厂应如何安 排计划，使在

14、满足上述要求的条件下，使总费用支出为最少？要求：(1)分析该实际问题，列出求解使用的数学模型并使用运 筹学软件求解；(2)将该问题转化为最小费用最大流问题，画出网络图并 使用图论方法求数值解。 (1)问题分析设正常生产时第一年、第二年、第三年、可完成的货轮数为 x1、x2、x3, 加班生产时第一年、第二年、第三年、可完成的货轮数 为 y1、 y2、y3。 数学模型目标函数： min=500*x1+600*x2+550*x3+570*y1+670*y2+620*y3+80 +(x1+y1)-1)*40+(x2+y2+(x1+y1-4)*40;约束条件：xlv=2;y1=3;x2v=4;y2=2;

15、x3=1;y3=3; x2+y2+x1+y1-1=3; x3+y3+x2+y2+x1+y1-4=4; 以下是用 lingo 计算的结果： Global optimal solution found.Objectivevalue:4730.000Totalsolveriterations:2VariableValueReduced CostX12.0000000.000000X22.0000000.000000X31.0000000.000000Y10.00000010.00000Y20.00000070.00000Y33.0000000.000000RowSlack or SurplusDua

16、l Price14730.000-1.00000020.00000060.0000033.0000000.00000042.0000000.00000052.0000000.00000060.00000070.0000070.0000000.00000081.0000000.00000090.000000-20.00000100.000000-620.0000由以上数据可知，将生产安排如下可使费用最少。X12.000000X22.000000X31.000000Y10.000000Y20.000000Y33.000000总费用支出为 4730万。（2）问题分析将此问题转化为最小费用最大流问题。

17、网络图如下所示：网络图中的数字含义说明：表示Cjdj),代表最大容量和费用。问题答案用运筹学软件的解题过程如下所示：从节点 1 到节点2 的最大流起点终点流量费用1 2 2500此问题的最大流为:2此问题的最小费用为:1000从节点 1 到节点3的最大流起点终点、八、流量费用12250013460023240此问题的最大流为:6此问题的最小费用为:3480从节点 1 到节点4的最大流起点终点、八、流量费用1215001415502314034140此问题的最大流为:2 此问题的最小费用为:1130从节点 2 到节点3的最大流起点终点、八、流量费用23240此问题的最大流为:2 此问题的最小费用

18、为:80 从节点 3 到节点4的最大流起点 终点 流量 费用3 4 1 40 此问题的最大流为:1 此问题的最小费用为:40 从节点 5 到节点2的最大流起点 终点 流量 费用5 2 3 570此问题的最大流为:3 此问题的最小费用为:1710从节点 5 到节点3的最大流起点 终点55323流量 费用2 2 5702670240从节点 5 到节点4的最大流起点终点、八、流量费用5215705466202314034140此问题的最大流为:4此问题的最小费用为:2560此问题的最大流为:7 此问题的最小费用为:4370由最大流最小费用的知识可知，对于此问题来说。满足题目要求的答 案是 4730

19、万。案例 3.1 光明市的菜篮子工程光明市是一个人口不到 15 万的小城市。根据该市的蔬菜种植情 况，分别在花市（A）、城乡路（B）和下塘街（C）设三个收购站。清 晨 5 点前菜农将蔬菜送至各收购点，再由各收购点分送到全市的8 个 菜市场。该市道路情况、各路段距离（单位：100m）及各个收购点、 菜市场，的具体位置见图33。按常年情况，A、B、C三个收 购点每天收购量分别为 200、 170 和 160（单位： 100kg） ,个菜市场 的每天需求量及发生供应短缺带来的损失（元/kg）见表3-45。设从 收购点至个菜市场蔬菜调运费用为1元/ （100kg100m）。QQ778.4BA65768

20、547Qii5Q4Q6757536686Q10C10115(a) 为该市设计一个从各收购点至个菜市场的定点供应方案，使用于蔬菜调运及预期的短缺损失为最小；(b) 若规定各个菜市场短缺量一律不超过需求量的20%, 重新设计定点供应方案；(c) 为满足城市居民的蔬菜供应，光明市的领导规划增加 蔬菜种植面积,试问增产的蔬菜每天应分别向 A、B、 C 三个采购点各供应多少最经济合理。解：a. 分析上述题目，可以找出各个收购点到各个菜市场的最短距离。加 上各个菜市场短缺损失，可以得出下面的产销平衡表：ABCD （短缺损失）需求量41421107587198608711580191614107011126

21、10100616158552223559020171088020017016080610QQQ供应量9080从上图中可以得出A、B、C各个收购点供货的的情况和短缺损失情况。b. 在第一个解得基础之上对缺量损失的D项作限制。DW15、DW12、DW16、DW14、DW20、DWil、DW18、DW16。解c. 从光明市各收购点运往各菜市场的费用选择最小的费用加到假想收购点D项中可以求出最低费用。再根据结果得出加到各个收购站的8711780191614147011126610061615655222355902017101080供应量200610ACBDQ75Q4020Q80Q70Q3070Q55

22、Q90Q80购点解得如下：菜市场根据解可以得出把所有增加的蔬菜 8000kg 全部增加给 C 收购站可以 消耗最小费用。案例 1.2 长征医院的护士值班安排问题分析由题意可知，在时间段2:00-6:00 完全由第一班护士值班，在时间段 6： 00-10：00 由第一班护士和第二班护士共同值班，在时间段10:00-14:00 由第一班护士和第二班护士共同值班，在时间段 10:00-14:00 由第二 班护士和第三班护士共同值班，在时间段 14:00-18:00 由第三班护士 和第四班护士共同值班，在时间段 18:00-22:00 由第四班护士和第五 班护士共同值班，在时间段 22:00-2:00

23、 由第五班护士值班。又有题意 可知每天第一班上班的护士人数之和即为值班护士总人数。 方案一 模型假设设xi (i=l,2,3,4,5,6,7)为第i天第一班的护士人数。模型如下：Min z=x1+x2+x3+x4+x5+x6+x7X1=12; X2=12; X3=12; X4=12; X5=12; X6=12; X7=12;X1+X2=20; X2+X3=20; X3+X4=20; X4+X5=20;X5+X6=20; X6+X7=20; X1+X7=20;经过软件的调试。得出x (i) =12 (i=l,2,3,4,5,6,7)是达到最优、Min z=x1+x2+x3+x4+x5+x6+x7

24、=84 方案二 模型假设设x1,x2,x3,x4,x5, 分别表示周六至周一、二、三、四、五休息 的人在其他时候的值班人数。x6,x7, x8, x9,x10分别表示周日至周一、二、三、四、五休息的人在其他时候的值班人数。model:min=x1+x2+x3+x4+x5+x6+x7+x8+X9+x 10;x5+x10=18; x10+x2+x9=20; x2+x3+x9+x8=19; x3+x4+x8+x7=17;x5=12; x4+x7=12;x7+x4+x6=18; x4+x5+x6+x1=20; x1+x5+x2+x10=19;x2+x10+x9=17;x7=12;x9=12; x1+x

25、4+x5+x6=18;x1+x5+x10=20; x9+x10=19;x9+x8+x3=17;x3+x8=12;x4+x6=12;x3+x8+x7=18;x6+x7=20;Global optimal solution found.Objective value:x6+x1+x5=19; x1+x5+x2+x10=17; x3+x8=12;x2+x10=12; x2+x3+x9+x8=18; x3+x8+x4+x7=20;x4+x7+x6=19;x6+x1=17;x2+x9=12;x1=12;x9+x10=18;x8+x9=20;x7+x8=19;x6+x7=17;x10=12;x6=12;x

26、1+x2=18;x2+x3=20;x3+x4=19;x4+x5=17;x1=12;x5=12; end105.000013Total solver iterations:VariableValueReduced CostX112.000000.000000X26.0000000.000000X314.000000.000000X45.0000000.000000X512.000000.000000X612.000000.000000X712.000000.000000X87.0000000.000000X913.000000.000000X1012.000000.000000由以上模型可得到答

27、案min=x1+x2+x3+x4+x5+x6+x7+x8+X9+x10;方案三 模型假设设x1,x2,x3,x4,x5, 分别表示周六至周一、二、三、四、五休息 的人在其他时候的值班人数。x6,x7, x8, x9,x10分别表示周日至 周一、二、三、四、五休息的人在其他时候的值班人数。设 x11、 x12、 x13、 x14、 x15、 x16、 x17、 x18、 x19、 x20 代 表在周一到周五期间除休息两天外其他时间值班的人数。model:min=x1+x2+x3+x4+x5+x6+x7+x8+X9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x

28、20;x19+x20+x15+x5+x10=18;x20+x15+x16+x10+x2+x9=20;x16+x17+x2+x3+x9+x8=19;x17+x18+x3+x4+x8+x7=17;x19+x5=12;x18+x4+x7=12;x13+x14+x7+x4+x6=18;x14+x11+x4+x5+x6+x1=20; x11+x16+x20+x1+x5+x2+x10=19; x16+x20+x17+x2+x10+x9=17;x13+x7=12;x17+x9=12;x14+x18+x19+x1+x4+x5+x6=18;x19+x20+x1+x5+x10=20;x20+x12+x9+x10=

29、19;x12+x13+x9+x8+x3=17;x14+x18+x3+x8=12;x13+x4+x6=12;x17+x3+x8+x7=18;x14+x15+x19+x6+x7=20; x14+x15+x19+x11+x6+x1+x5=19; x11+x12+x1+x5+x2+x10=17; x17+x3+x8=12;x12+x2+x10=12; x12+x13+x18+x2+x3+x9+x8=18; x3+x8+x4+x7=20;x15+x4+x7+x6=19;x11+x15+x16+x6+x1=17;x12+x2+x9=12;x11+x16+x1=12;x11+x15+x16+x20+x9+x

30、10=18;x11+x12+x16+x17+x8+x9=20;x12+x13+x17+x18+x7+x8=19;x13+x14+x18+x19+x6+x7=17; x20+x15+x10=12;x19+x14+x6=12;x11+x12+x16+x17+x1+x2=18;x12+x13+x17+x18+x2+x3=20;x11+x16+x1=12;x15+x20+x5=12;84.0000061x13+x14+x18+x19+x3+x4=19;x14+x15+x19+x20+x4+x5=17;endGlobal optimal solution found.Objective value:To

31、tal solver iterations:VariableReduced Cost0.0000000.0000008.0000004.0000008.0000004.0000008.0000000.0000008.0000008.0000000.0000004.0000004.0000004.0000004.00000012.000004.0000000.0000004.0000000.000000ValueX10.000000X20.000000X30.000000X40.000000X50.000000X60.000000X70.000000X80.2000000X90.000000X1

32、00.000000X110.000000X120.000000X130.000000X140.000000X150.000000X160.000000X170.000000X180.2000000X190.000000X200.000000由求解结果可知：min=x1+x2+x3+x4+x5+x6+x7+x8+X9+x10+x11+x12+x13+x1 4+x15+x16+x17+x18+x19+x20=84要解决a是多大的问题。如下所示。x1+x2+x3+x4+x5+x6+x7+x8+X9+x10+（1+%a）*x11+x12+x13+x14+x15+x16+x17+x18+x19+x20=

33、105有计算可得a=47.也就是作为奖励，放弃周末休息的护士，其工资和奖金总额比其他护士增加 47%运筹学课程设计总结在这次课程设计中，我们主要是以小组的形式来完成课程设计 的任务，由组长起带头作用，带领小组中的五个成员通过不同的分工 来共同完成。通过课程设计的完成我们更加清楚理论和实践相结合的 重要性，同时也使我们更加注重团队的合作，在以后的学习或者工作 中我们可以拥有更强的团队意识。总之课程设计完成的还算成功，有 些地方不算完整，可能是由于学习的不够扎实造成的，在以后的学习 中会吸取教训。以下是我们完成课程设计的分工明细表：.完成人员设计案例*课程设计的书写是由王斌完成案例6.1网络中的服务及设施布局王斌，张津国案例8.2用不冋的方法解决最短路问题朱滋洲，赵昭君案例二造船厂王斌，谭天骄，周长龙案例3.1光明市的菜篮子工程周长龙，张津国，朱滋洲案例1.2长征医院的护士值班安排张津国、赵昭君，谭天骄