运筹学课后练习答案(熊伟第二版,后七章).doc

教材习题答案第1章 线性规划 第2章 线性规划的对偶理论 第3章 整数规划 第4章 目标规划 第5章 运输与指派问题 第6章 网络模型 第7章 网络计划 第8章 动态规划 第9章 排队论 第10章 存储论 第11章 决策论 第12章 对策论 目录 教材习题答案 1 习题六 1 习题七 11 习题八 17 习题九 27 习题十 34 习题十一 40 习题十二 45 由于篇幅的限制，本文档只有运筹学第六章---第十二章的内容，前五章的内容请继续有哪些信誉好的足球投注网站“运筹学课后练习答案（熊伟第二版，前五章）” 习题六 6.1如图6－39所示，建立求最小部分树的0－1整数规划数学模型。边[i，j]的长度记为cij，设 数学模型为： 6.2如图6－40所示，建立求v1到v6的最短路问题的0－1整数规划数学模型。 弧(i，j)的长度记为cij，设 数学模型为： 6.3如图6－40所示，建立求v1到v6的最大流问题的线性规划数学模型。 设xij为弧（i,j）的流量，数学模型为 6.4求图6－41的最小部分树。图（a）用破圈法,图（b）用加边法。 图6－41 图（a） 图（） 6.5 某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。 表6-20 两村庄之间修建公路的费用(万元) 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 12.8 10.5 9.6 8.5 7.7 13.8 12.7 13.1 12.6 11.4 13.9 11.2 8.6 7.5 8.3 14.8 15.7 8.5 9.6 8.9 8.0 13.2 12.4 10.5 9.3 8.8 12.7 14.8 12.7 13.6 15.8 9.8 8.2 11.7 13.6 9.7 8.9 10.5 13.4 14.6 9.1 10.5 12.6 8.9 8.8 【解】属于最小树问题。用加边法，得到下图所示的方案。 最低总成本74.3万元。 6.6在图6－42中，求A到H、I的最短路及最短路长，并对图(a)和(b)的结果进行比较。 图6－42 图6－42(a) A到H的最短路PAH={A,B,F,H},{A,C,F,H}最短路长22；A到I的最短路PAI={A,B,F,I},{A,C,F,I}最短路长21。 对于图6－42(b)： A到H的最短路PAH={A,C,G,F,H},最短路长21；A到I的最短路PAI={A,C,G,F,I},最短路长20； 结果显示有向图与无向图的结果可能不一样。 6.7已知某设备可继续使用5年，也可以在每年年末卖掉重新购置新设备。已知年年初购置新设备的价格分别为3.5、3.8、4.0、4.2和4.5万元。使用时间在1～5年内的维护费用分别为0.4、0.9、1.4、2.3和3万元。试确定一个设备更新策略，使5年的设备购置和维护总费用最小。 总费用最小的设备更新方案为：第一种方案，第1年购置一台设备使用到第5年年末；第二种方案，第1年购置一台设备使用到第2年年末，第3年年初更新后使用到第5年年末。总费用为11.5万元。 6.8图6－43是世界某6大城市之间的航线，边上的数字为票价（百美元），用Floyd算法设计任意两城市之间票价最便宜的路线表。 v1 v2 v3 v4 v5 v6 v1 0 8.8 9 5.6 8 6 v2 8.8 0 10 5 100 4 v3 9 10 0 3 4.8 14 v4 5.6 5 3 0 12 100 v5 8 100 4.8 12 0 9 v6 6 4 14 100 9 0 L2 　 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 14 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 14 9 9 0 L3 　 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 12 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 12 9 9 0 最优票价表： 　 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 0 8 5 13 4 v3 0 3 4.8 12 v4 0 7.8 9 v5 0 9 v6