《熊伟编《运筹学》习题六详细解答》由会员分享，可在线阅读，更多相关《熊伟编《运筹学》习题六详细解答（10页珍藏版）》请在金锄头文库上搜索。
1、习题六习题六6.1 如图 639 所示，建立求最小部分树的 01 整数规划数学模型。 【解解】边i，j的长度记为 cij，设否则包含在最小部分树内边0,1jixij数学模型为： , 013, 33, 33, 22, 22, 25min5626151256263523362613125646353434241312362623563635463634342423231312,jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxcZijjiijijij所有边或6.2 如图 640 所示，建立求 v1到 v6的 最短路问题的 01 整数规划数学模型。【解解】弧(i，j)的
2、长度记为 cij，设否则包含在最短路径中弧0),(1jixij数学模型为：),(, 011, 1min5646564535254645342435342313252423121312,jixxxxxxxxxxxxxxxxxxxxxxcZijjiijij所有弧或6.3 如图 640 所示，建立求 v1到 v6的最大流问题的线性规划数学模型。【解】 设 xij为弧（i,j）的流量，数学模型为),(,0min56453525464534243534231325242312564613121312jicxxxxxxxxxxxxxxxxxxxxxxxZijij所有弧图图 639图图 6406.4 求图
3、641 的最小部分树。图 6-41（a）用破圈法,图 6-41（b）用加边法。图图 641【解】图 6-41（a） ，该题有 4 个解，最小树长为 21，其中一个解如下图所示。图 6-41（b） ，最小树长为 20。最小树如下图所示。6.5 某乡政府计划未来 3 年内，对所管辖的 10 个村要达到村与村之间都有水泥公路相通的 目标。根据勘测，10 个村之间修建公路的费用如表 6-20 所示。乡镇府如何选择修建公路 的路线使总成本最低。表表 6-20两村庄之间修建公路的费用(万元)123456789101 2 3 4 512.810.5 9.68.5 7.7 13.812.7 13.1 12.6
4、 11.413.9 11.2 8.6 7.5 8.314.8 15.7 8.5 9.6 8.913.2 12.4 10.5 9.3 8.812.7 13.6 15.8 9.8 8.28.9 10.5 13.4 14.6 9.16 7 8 9 108.012.7 14.811.7 13.6 9.710.5 12.6 8.9 8.8【解】属于最小树问题。用加边法，得到下图所示的方案。最低总成本 74.3 万元。6.6 在图 642 中，求 A 到 H、I 的最短路及最短路长，并对图(a)和(b)的结果进行比较。图图 642【解解】图图 642(a):A 到 H 的最短路 PAH=A,B,F,H,A
5、,C,F,H最短路长 22；A 到 I 的最短路 PAI=A,B,F,I, A,C,F,I最短路长 21。 对于图对于图 642(b)：A 到 H 的最短路 PAH=A,C,G,F,H,最短路长 21；A 到 I 的最短路 PAI=A,C,G,F,I,最短路长 20； 结果显示有向图与无向图的结果可能不一样。6.7 已知某设备可继续使用 5 年，也可以在每年年末卖掉重新购置新设备。已知 5 年年初购 置新设备的价格分别为 3.5、3.8、4.0、4.2 和 4.5 万元。使用时间在 15 年内的维护费用 分别为 0.4、0.9、1.4、2.3 和 3 万元。试确定一个设备更新策略，使 5 年的
6、设备购置和维护 总费用最小。 【解解】设点 vj为第 j 年年初购置新设备的状态， （i，j）为第 i 年年初购置新设备使用到第 j 年年初，弧的权为对应的费用（购置费维护费） ，绘制网络图并计算，结果见下图所示。总费用最小的设备更新方案为：第一种方案，第 1 年购置一台设备使用到第 5 年年末； 第二种方案，第 1 年购置一台设备使用到第 2 年年末，第 3 年年初更新后使用到第 5 年年 末。总费用为 11.5 万元。6.8 图 643 是世界某 6 大城市之间的航线，边 上的数字为票价（百美元） ，用 Floyd 算法设计任 意两城市之间票价最便宜的路线表。 【解解】教师可利用模板求解：
7、datachpt6ch6.xls L1v1v2v3v4v5v6v108.895.686v28.801051004图图 643v3910034.814v45.653012100v581004.81209v6641410090L2v1v2v3v4v5v6v108.88.65.686v28.8085134v38.68034.814v45.65307.89v58134.87.809v66414990L3v1v2v3v4v5v6v108.88.65.686v28.8085134v38.68034.812v45.65307.89v58134.87.809v66412990最优票价表：v1v2v3v4v5v
8、6v108.88.65.686v2085134v3034.812v407.89v509v60v1、v2、v6到各点的最优路线图分别为：6.9 设图 643 是某汽车公司的 6 个零配件加工厂，边上的数字为两点间的距离(km)。现 要在 6 个工厂中选一个建装配车间。 （1）应选那个工厂使零配件的运输最方便。 （2）装配一辆汽车 6 个零配件加工厂所提供零件重量分别是 0.5、0.6、0.8、1.3、1.6 和 1.7 吨，运价为 2 元/吨公里。应选那个工厂使总运费最小。 【解解】(1)利用习题 6.8 表 L3 的结果 minmax12.8ijijLLv1v2v3v4v5v6Maxv108.
9、88.65.6868.8v28.808513412.8v38.68034.81212v45.65307.899v58134.87.80912.8v6641299012选第 1 个工厂最好。 (2)计算单件产品的运价，见下表最后一行。计算单件产品的运费，见下表最后一列。v1v2v3v4v5v6单件产品运费v108.88.65.68684.88v28.808513489.16v38.68034.81282.16v45.65307.8971.96v58134.87.80981.92v6641299082.2运价11.21.62.63.23.4选第 4 个工厂最好。6.10 如图 644， （1）求
10、v1到 v10的最 大流及最大流量；（2）求最小割集和 最小割量。 【解】给出初始流如下图图 644第一轮标号：得到一条增广链，调整量等于 5，如下图所示调整流量。 第二轮标号：得到一条增广链，调整量等于 2，如下图所示调整流量。 第三轮标号：得到一条增广链，调整量等于 3，如下图所示调整流量。 第四轮标号：不存在增广链，最大流量等于 45，如下图所示取 ，最小截集(3,7),(4,7),(6,9),(8,10)，最小截1123456817910 , ,Vv v v v v v vVv v v量等于 45。6.11 将 3 个天然气田 A1、A2、A3的天然气输送到 2 个地区 C1、C2，中
11、途有 2 个加压站 B1、B2，天然气管线如图 645 所示。输气管道单位时间的最大通过量 cij及单位流量的费 用 dij标在弧上(cij, dij)。求(1)流量为 22 的最小费用流；（2）最小费用最大流。图图 645【解解】虚拟一个发点和一个收点T6.111 得到流量 v22 的最小费用流，最小费用为 271。求解过程参看第 4 章 PPT 文档习题答案。T6.1113 最小费用最大流如下图，最大流量等于 27，总费用等于 351。6.12 如图 643 所示， （1）求解旅行售货员问题；（2）求解中国邮路问题。图图 6-43 【解】 （1）旅行售货员问题。 距离表 C12345618
12、.895.68628.81054391034.81445.65312 584.8129664149 在 C 中行列分别减除对应行列中的最小数，得到距离表 C1。 距离表 C112345613.23.400.60.422.8610347001140.6207.2 51.207.29600103.2 由距离表 C1，v1到 v4， H1= v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1, C(H1)=5.6+3+4.8+9+4+8.8=35.2 去掉第 1 行第四列，d41=，得到距离表 C2。 得到距离表 C212356 22.860 347011 4207.2 51.209 600103.2 距离表 C2 的每行每列都有零，H2= H1= v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1就是总距离最小的 Hamilton 回路，C(H1) =35.2。 (2)中国邮路问题。虚拟一条边取回路 H1v1，v3，v4，C(H1)=9+5+3=17,C(v1，v3)=9 C(H1)/2，调整回路。所有回路满足最短回路的准则，上图是最短的欧拉回路，其中边(v1, v4)和(v4, v3)各重复一次。
