熊伟编《运筹学》习题六详细解答

1边[i,j]包含在最小部分树内

xx2,x1边[i,j]包含在最小部分树内

xx2,xxxx31弧(i,j)包含在最短路径中

c

xxxx,xxxx1213

3545560

iji,j

23263612132434x34

图6－40

121312232425

1323343524344546x12134656x

xxx

ij0否则

x

xxx3,xxxx3xxxx3,xxxx30否则

xxx,xx1xxxxxx

24344546xx2,xxx2xx2,xxx2

35465612132636253545564656xij12232425x图6－39

121323232434

2335265612152656x10,所有弧(i,j)132334351或0,所有边[i,j]ijxxx

6.1如图6－39所示，建立求最小部分树的0－1整数规划数学模型。【解】边[i，j]的长度记为cij，设

xij数学模型为：minZcxijijx5

343646353656x

6.2如图6－40所示，建立求v1到v6的最短路问题的0－1整数规划数学模型。【解】弧(i，j)的长度记为cij，设

xij数学模型为：minZxijiji,jxx1,xxxx

6.3如图6－40所示，建立求v1到v6的最大流问题的线性规划数学模型。

【解】设xij为弧（i,j）的流量，数学模型为minZxxxxxx

x

xc,(i,j)

6.4求图6－41的最小部分树。图6-41（a）用破圈法,图6-41（b）用加边法。

212.89.613.812.68.68.510.5212.89.613.812.68.68.510.511.47.59.69.38.38.98.88.012.7310.57.713.111.215.712.415.89.88.211.7456788.512.713.914.813.213.613.414.69.110.5912.710.5108.9【解】图6-41（a），该题有4个解，最小树长为21，其中一个解如下图所示。

图6-41（b），最小树长为20。最小树如下图所示。

6.5某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。

表6-20两村庄之间修建公路的费用(万元)1123456

14.89.78.813.68.912.6

714.89.78.813.68.912.68910【解】属于最小树问题。用加边法，得到下图所示的方案。

最低总成本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)：

图6－43

A到H的最短路PAH={A,C,G,F,H},最短路长21；A到I的最短路PAI={A,C,G,F,I},最短路长图6－4320；结果显示有向图与无向图的结果可能不一样。

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算法设计任意两城市之间票价最便宜的路线表。【解】教师可利用模板求解：：L1v1v2v3v4v5v6v108.895.686v28.801051004

910034.8910034.8145.65301210081004.81209641410090v58134.87.809v58134.87.809v58134.87.800v66414990v66412990v6641299v4v5v6L2v1v2v3v4v108.88.65.6v28.8085v38.6803v45.6530v58134.87.8v664149L3v1v2v3v4v108.88.65.6v28.8085v38.6803v45.6530v58134.87.8v664129最优票价表：v1v2v3v4v108.88.65.6v2085v303v40v5v6v1、v2、…、v6到各点的最优路线图分别为：

12.8ij

6.9设图6－43是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离(km)。现要12.8ij在6个工厂中选一个建装配车间。（1）应选那个工厂使零配件的运输最方便。（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨，运价为2元/吨公里。应选那个工厂使总运费最小。【解】(1)利用习题6.8表L3的结果LminmaxLijv1v2v3v4v5v6Maxv108.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如图6－44，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量。【解】给出初始流如下

图6－44

第一轮标号：得到一条增广链，调整量等于5，如下图所示

调整流量。第二轮标号：得到一条增广链，调整量等于2，如下图所示

调整流量。第三轮标号：得到一条增广链，调整量等于3，如下图所示

调整流量。第四轮标号：不存在增广链，最大流量等于45，如下图所示

V{v,V{v,v,v,v,v,v,v},V112345681ij)。求(1)流量为{v,v,v}79

量等于45。

6.11将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2，中途有2个加压站B1、B2，天然气管线如图6－45所示。输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上(cij,d22的最小费用流；（2）最小费用最大流。

图6－45【解】虚拟一个发点和一个收点

T6.11－1得到流量v＝22的最小费用流，最小费用为271。求解过程参看第4章PPT文档习题答案。

66414∞66414∞9∞60.40最小费用最大流如下图，最大流量等于27，总费用等于351。

6.12如图6－43所示，（1）求解旅行售货员问题；（2）求解中国邮路问题。

图6-43【解】（1）旅行售货员问题。距离表C123451∞8.895.6828.8∞105∞3910∞34.845.653∞1258∞4.812∞66414∞9在C中行列分别减除对应行列中的最小数，得到距离表C1。距离表C1123451∞3.23.400.622.8∞61∞

1,4

1,4

3471,4

1,440.620∞7.2∞51.2∞07.2∞