运筹学案例6.1网络中的服务及设施布局（a）在11个小区内准备共建一套医务所，邮局，储蓄所，综合超市等服务设施，应建于哪一个居民小区，使对居民总体来说感到方便；●问题分析为满足题目的要求。
只需要找到每一个小区到其他任何一个小区的最短距离。
然后再用每一小区的人数进行合理的计算后累加，结果最小的便是最合理的建设地。
●以下表中数据d ij表示图中从i到j点的最短距离设施建于各个小区时居民所走路程由以上数据可知。
各项服务设施应建于第八个居民小区。
（b）电信部门拟将宽带网铺设到各个小区，应如何铺设最为经济●问题分析要解决这个问题时期最为经济。
只需要找到图找的最小部分树便可以。
●以下是最小部分树。
起点终点距离1 4 44 2 54 5 55 6 46 3 54 8 68 7 48 9 47 10 510 11 0所以按照以上路径进行线路铺设，就可达到最经济。
总的距离为42 （c）一个考察小组从小区1出发，经5.8.10。
小区（考察顺序不限），最后到小区9再离去，请帮助选一条最短的考察路线。
问题分析找出这几个小区通过的不同组合，计算出路程总和，最短的就是最优路线。
以下是不同组合以及各个路程一·1→5（11）5→8（8）8→10（9）10→9（12）40二·1→5（11）5→10（17）10→8（9）8→9（4）41三·1→8（12）8→10（9）10→5（17）5→9（6）44四·1→8（12）8→5（8）5→10（17）10→9（12）49五·1→10（13）10→5（17）5→8（8）8→9（4）42六·1→10（13）10→8（9）8→5（8）5→9（6）36由以上数据可知最短的考察路线是1→10→8→5→9案例8.2用不同的方法解决最短路问题说明：为了解题的方便，现将图中的代号修改如下。
A、B1、B2、B3、C1、C2、D1、D2、D3、E.修改为1、2、3、4、5、7、8、9、10。
问题分析（a）乙提出用动态规划的方法求解。
现将解题过程描述如下。
用所在的点p i表示状态，决策集合就是除p i以外的点，选定一个p j 以后，得到效益后转入新状态p j，当状态是p n时，过程停止。
以下是用lingo解题的代码和数据：model:data:n=10;end datasets:way/1..n/:F; roads(way,way)/1,2 1,3 1,42,7 2,5 2,63,5 3,64,5 4,6 4,95,7 5,8 5,96,7 6,8 6,97,108,109,10/:D,P;end setsdata:D=3 2 14 4 31 33 5 32 5 31 4 2315;end dataF(n)=0;@for(way(i) | i#lt#n:F(i)=@min(roads(i,j):D(i,j)+F(j)););@for(roads(i,j):P(i,j)=@if(F(i) #eq# D(i,j)+F(j),1,0)); End数据：Feasible solution found.Total solver iterations: 0Variable Value N 10.00000F( 1) 8.000000F( 2) 7.000000F( 3) 6.000000F( 4) 8.000000F( 5) 5.000000F( 6) 4.000000F( 7) 3.000000F( 8) 1.000000F( 9) 5.000000F( 10) 0.000000D( 1, 2) 3.000000D( 1, 3) 2.000000D( 1, 4) 1.000000D( 2, 7) 4.000000D( 2, 5) 4.000000D( 2, 6) 3.000000D( 3, 5) 1.000000D( 3, 6) 3.000000D( 4, 5) 3.000000D( 4, 6) 5.000000D( 4, 9) 3.000000D( 5, 7) 2.000000D( 5, 8) 5.000000D( 8, 10) 1.000000D( 9, 10) 5.000000P( 1, 2) 0.000000P( 1, 3) 1.000000P( 1, 4) 0.000000 P( 2, 7) 1.000000 P( 2, 5) 0.000000 P( 2, 6) 1.000000 P( 3, 5) 1.000000 P( 3, 6) 0.000000 P( 4, 5) 1.000000 P( 4, 6) 0.000000 P( 4, 9) 1.000000 P( 5, 7) 1.000000 P( 5, 8) 0.000000 P( 5, 9) 0.000000 P( 6, 7) 1.000000 P( 6, 8) 0.000000 P( 6, 9) 0.000000 P( 7, 10) 1.000000 P( 8, 10) 1.000000 P( 9, 10) 1.00000 D( 5, 9) 3.000000 D( 6, 7) 1.000000 D( 6, 8) 4.000000 D( 6, 9) 2.000000 D( 7, 10) 3.000000 D( 9, 10) 5.000000 P( 1, 2) 0.000000 P( 1, 3) 1.000000如果p（i，j）=1则点i到点n的最短路的第一步是i→j，否则就不是。
所以有结果可知，最优的路线是1→3→5→7→10，也就是A→B2→C1→D1→E 最短路程是8（b）丙提出用整数规划模型求解●问题分析设用a ij表示权数，x ij表示：=1时为最短路径上的一段i到j的弧。
=0时表示不是。
数学模型是：minz=∑a ij x ijs.t ∑x ij=1(i=1.2……m)∑a ij=1(j=1.2……n)x ij=0\1(i=1.2……m j=1.2……n )由以上模型可以得出，在A→B1\B2\B2,这一段时。
可以取A→B2，在B1\B2\B2→C1\C2这一段时可以取B2→C1，在C1\C2→D1\D2\D3这一段时可以取C1→D1，在D1\D2\D3→E这一段可取D1→E。
所以求得的最短路线是A→B2→C1→D1→E 最短路程是8。
（C）丁用求最小部分树的方法解决●问题分析求出最小部分树后。
如果在最先部分数上有一条吧A到E联通的路径，那这个就是最短路径。
以下是求的最小部分数：由此可知在最小部分数中存在那样的一条链：1→3→5→7→10，也就是原题中的路径：A→B2→C1→D1→E，最短路程是8案例二1、某造船厂根据合同要在当年算起的连续三年年末各提供三条规格相同的大型货轮。
已知该厂今后三年的生产能力及生产成本如下表所示：已知加班生产情况下每条货轮成本比正常生产时高出70万元，又知造出的货轮如当年不交货，每条货轮每积压一年增加维护保养等损失为40万元，在签订合同时该厂已有两条积压未交货的货轮，该厂希望在第三年末在交完合同任务后能储存一条备用，问该厂应如何安排计划，使在满足上述要求的条件下，使总费用支出为最少？要求：（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;约束条件：x1<=2;y1<=3;x2<=4;y2<=2;x3<=1;y3<=3;x1+y1+2>=3;x2+y2+x1+y1-1>=3;x3+y3+x2+y2+x1+y1-4=4;以下是用lingo计算的结果：Global optimal solution found.Objective value: 4730.000Total solver iterations: 2Variable Value Reduced CostX1 2.000000 0.000000X2 2.000000 0.000000X3 1.000000 0.000000Y1 0.000000 10.00000Y2 0.000000 70.00000Y3 3.000000 0.000000Row Slack or Surplus Dual Price1 4730.000 -1.0000002 0.000000 60.000003 3.0000000.0000004 2.000000 0.0000005 2.000000 0.0000006 0.000000 70.000007 0.000000 0.0000008 1.000000 0.0000009 0.000000 -20.0000010 0.000000 -620.0000由以上数据可知，将生产安排如下可使费用最少。
X1 2.000000X2 2.000000X3 1.000000Y1 0.000000Y2 0.000000Y3 3.000000总费用支出为4730万。
（2）问题分析将此问题转化为最小费用最大流问题。
网络图如下所示：网络图中的数字含义说明：表示C ij(B ij),代表最大容量和费用。
问题答案用运筹学软件的解题过程如下所示：从节点1到节点2的最大流起点终点流量费用1 2 2 500此问题的最大流为:2 此问题的最小费用为:1000 从节点1到节点3的最大流起点终点流量费用1 2 2 5001 3 4 6002 3 2 40此问题的最大流为:6 此问题的最小费用为:3480 从节点1到节点4的最大流起点终点流量费用1 2 1 5001 4 1 5502 3 1 403 4 1 40此问题的最大流为:2此问题的最小费用为:1130 从节点2到节点3的最大流起点终点流量费用2 3 2 40此问题的最大流为:2此问题的最小费用为:80从节点3到节点4的最大流起点终点流量费用3 4 1 40此问题的最大流为:1此问题的最小费用为:40从节点5到节点2的最大流起点终点流量费用5 2 3 570此问题的最大流为:3此问题的最小费用为:1710从节点5到节点3的最大流起点终点流量费用5 2 2 5705 3 2 6702 3 2 40此问题的最大流为:4 此问题的最小费用为:2560 从节点5到节点4的最大流起点终点流量费用5 2 1 5705 46 6202 3 1 403 4 1 40此问题的最大流为:7此问题的最小费用为:4370由最大流最小费用的知识可知，对于此问题来说。