- 1、本文档共10页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
熊伟编《运筹学》习题六详细解答
习题六
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的最小部分树。图6-41(a)用破圈法,图6-41(b)用加边法。
图6-41
【解】图6-41(a),该题有4个解,最小树长为21,其中一个解如下图所示。
图6-41(b),最小树长为20。最小树如下图所示。
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年,也可以在每年年末卖掉重新购置新设备。已知5年年初购置新设备的价格分别为3.5、3.8、4.0、4.2和4.5万元。使用时间在1~5年内的维护费用分别为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图6-43是世界某6大城市之间的航线,边上的数字为票价(百美元),用Floyd算法设计任意两城市之间票价最便宜的路线表。
【解】教师可利用模板求解:data\chpt6\ch6.xls
L1
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 0 v1、v2、…、v6到各点的最优路线图分别为:
6.9 设图6-43是某
您可能关注的文档
最近下载
- 2024年大数据技术试题库(含答案).pdf
- 艾兰德ALD6000P系列变频器使用手册(中文).pdf
- NB∕SH∕T 0944.2-2020 润滑剂抗磨损性能的测定 FE8滚动轴承磨损试验机法 第2部分:润滑脂.pdf
- 四川大学2020年11月课程考试考试《103014电子商务》参考答案.doc
- 廉洁案例教育(廉洁党课)-1.ppt VIP
- 游泳馆突发紧急事件处理预案.doc
- 国开(中央电大)专科《财务管理》网上形考(任务一至四)试题及答案.docx
- 我的教育教学故事(荟萃20篇).docx VIP
- 部编版小学语文六年级上册期中考试试卷(含答案).doc
- 数学北师大版五年级上《比较图形的面积》说课课件.pptx
文档评论(0)