资源预览内容
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
第9页 / 共10页
第10页 / 共10页
亲,该文档总共10页全部预览完了,如果喜欢就下载吧!
资源描述
习题六习题六6.1 如图 639 所示,建立求最小部分树的 01 整数规划数学模型。 【解解】边i,j的长度记为 cij,设否则包含在最小部分树内边0,1jixij数学模型为: , 013, 33, 33, 22, 22, 25min5626151256263523362613125646353434241312362623563635463634342423231312,jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxcZijjiijijij所有边或6.2 如图 640 所示,建立求 v1到 v6的 最短路问题的 01 整数规划数学模型。【解解】弧(i,j)的长度记为 cij,设否则包含在最短路径中弧0),(1jixij数学模型为:),(, 011, 1min5646564535254645342435342313252423121312,jixxxxxxxxxxxxxxxxxxxxxxcZijjiijij所有弧或6.3 如图 640 所示,建立求 v1到 v6的最大流问题的线性规划数学模型。【解】 设 xij为弧(i,j)的流量,数学模型为),(,0min56453525464534243534231325242312564613121312jicxxxxxxxxxxxxxxxxxxxxxxxZijij所有弧图图 639图图 6406.4 求图 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 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,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 年的设备购置和维护 总费用最小。 【解解】设点 vj为第 j 年年初购置新设备的状态, (i,j)为第 i 年年初购置新设备使用到第 j 年年初,弧的权为对应的费用(购置费维护费) ,绘制网络图并计算,结果见下图所示。总费用最小的设备更新方案为:第一种方案,第 1 年购置一台设备使用到第 5 年年末; 第二种方案,第 1 年购置一台设备使用到第 2 年年末,第 3 年年初更新后使用到第 5 年年 末。总费用为 11.5 万元。6.8 图 643 是世界某 6 大城市之间的航线,边 上的数字为票价(百美元) ,用 Floyd 算法设计任 意两城市之间票价最便宜的路线表。 【解解】教师可利用模板求解: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最优票价表:v1v2v3v4v5v6v108.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.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)求 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,中途有 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.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)各重复一次。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号