熊伟编《运筹学》习题六详细解答.doc
文本预览下载声明
习题六
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是某
显示全部