熊伟第二版运筹学1-6章参考答案2

习题五

5.2 用元素差额法直接给出表5-52及表5-53下列两个运输问题的近似最优解．

表5-52

表5-53

【解】

双击演示过程→

表5-52。Z=824

表5-53结果如下，Z=495（最优值Z=480）

5.3 求表5-54及表5-55所示运输问题的最优方案． （1）用闭回路法求检验数（表5-54）

表5-54

（2）用位势法求检验数（表5-55）

表5-55

解（1）最优表如下，最优值Z＝610

(2)解 最优表如下，最优值Z＝445

5.4 求下列运输问题的最优解

（1）C1目标函数求最小值； （2）C2目标函数求最大值

53C164

1113

15

45

981220

2507

525C214

730540

60

1013830

159750

2060

630 109040

(3)目标函数最小值,B1的需求为30≤b1≤50, B2的需求为40，B3的需求为20≤b3≤60,A1不

可达B4 ，B4的需求为30．

468

954

739

70

220 1050

【解】（1）

（2）

5.5（1）建立数学模型

设xij(I=1,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则

maxZ40(80x1165x1260x2150x2250x3140x32)

40x1140x2140x31400

40x1240x2240x32600x11x125

xx221011

x31x3215xij0(i1,2,3;j1,2)

(2)写平衡运价表

（3）最优调度方案：

即甲第天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10辆车到B2城市，多余5辆，最大收入为

Z=40（5×80+5×60+5×50+10×40）=54000（元）

5.6（1）设xij为第i月生产的产品第j月交货的台数，则此生产计划问题的数学模型为

minZx111.15x121.3x131.45x14Mx210.98x44

x11x21x31x4150

x12x22x32x4240xxxx6013233343

x14x24x34x4480

x11x12x13x1465xxxx65

222324

21

x31x32x33x3465

x41x42x43x4465x0,(i,j1,,4)ij

（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费

上表表明：一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用Z=235万元。

5.7 假设在例5－16中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案．

【解】将表5-35所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000．

第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2； 总成本

Z＝1000×(58＋920＋510＋110)＝1598000

注：结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。

5.8 求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作．

1220

（1）C＝

356

6121810

9181015

1526

 2520

【解】最优解

X

1

2625

（2）C＝

2022

38333031

41444745

52595653

2721 2520

1

,Z43 

1

1

【解】虚拟一个人，其效率取4人中最好的，构造效率表为



最优解：X1



1



1

，最优值Z=165 

1

1

甲～戊完成工作的顺序为3、5、1、2、4，

最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。

5.9 求解下列最大值的指派问题： 1015

（1）C＝

18161015

【解】 C＝

1816

[1**********]8

[1**********]312

1720

 1926

1720

 最优解X

119

26

11





,Z64 1

（2）【解】 9

4C＝7

697129107

6－[1**********]8

[1**********]0

109

54127166

89611408

6010158

[1**********]

[1**********]23

16

16161616611408

0

0000

00

050203

00

05230

915507

41023

611408

00

050304

00

814506

30022

5

10407

0

01 100

5380

410102

30022

1

0

6001

0550

1



最优解X



1

1

1



或X

11

1

1

1

1



；Z44 

表5-57 成绩表(分钟) 第5人不安排工作或第1人不安排工作。

5.10 学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-57所示．如何从中选拔一个接力队，使预期的比赛成绩最好． 【解】设xij为第i人参加第j项目的状态，则数学模型为

minZ20x1143x1233x1329x1428x54x11x12x13x141

xx22x23x24121

x31x32x33x341

x41x42x43x441xxxx1

52535451



xx21x31x41x51111

x12x22x32x42x521

x13x23x33x43x531xxxxx1

24344454

14xij0或1,i1,2,,5;j1,2,3,4

接力队最优组合 乙 丙 丁 戊

长跑 游泳 登山 自行车

甲淘汰。预期时间为107分钟。

习题六

6.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。

【解】边[i，j]的长度记为cij，设

图6－42

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

0否则

数学模型为：

minZcijxij

xij5i,j

xx13x232,x23x24x34212

x34x36x462,x35x36x562

x12x13x24x343

xxxx3

34354656

x23x24x46x363

x12x13x24x46x364xxxxx4,2335244656

x12x13x24x35x46x565

xij1或0,所有边[i,j]

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

1弧(i,j)包含在最短路径中xij

0否则

数学模型为：

minZ

c

i,j

ij

xij

图6－

43

x12x131

x12x23x24x250xxxx013233435



,x24x34x45x460xxxx0

354556

25

x46x561xij1或0,所有弧(i,j)

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

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

minZx12x13x12x13

xx2312x13x23

xx3424

x25x350xij

x46x56x24x25x34x35x45x46x45x56

cij,所有弧(i,j)

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

图6－44

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

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

6.5 某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的

目标。根据勘测，10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。

表6-20

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

最低总成本74.3万元。

6.6在图6－45中，求A到H、I的最短路及最短路长，并对图(a)和(b)的结果进行比较。

图6－45

【解】图6－45(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－45(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－46是世界某6大城市之间的航线，边上的数字为票价（百美元），用Floyd算法设计任意两城市之间票价最便宜的路线表。

【解】教师可利用模板求解：data\chpt6\ch6.xls

图6－46

v1、v2、„、v6

6.9 设图6－46是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离(km)。现要在6个工厂中选一个建装配车间。

（1）应选那个工厂使零配件的运输最方便。

（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨，运价为2元/吨公里。应选那个工厂使总运费最小。 【解】(1)利用习题6.8表L3的结果

LminmaxLij8.8

i

j

选第1

(2)

选第4

6.10 如图6－47，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量。

【解】给出初始流如下

图6－47

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

调整流量。

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

调整流量。

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

调整流量。

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

取 V1{v1,v2,v3,v4,v5,v6,v8},V1{v7,v9,v10}，最小截集{(3,7),(4,7),(6,9),(8,10)，最小截量等于45。

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

图6－48

【解】虚拟一个发点和一个收点

T6.11－1

得到流量v＝22的最小费用流，最小费用为271。求解过程参看习题部分答案PPT文档。

T6.11－13

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

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

图6-46

【解】（1）旅行售货员问题。

在C

由距离表C1，v[1**********]去掉第1行第四列，d41=∞，得到距离表C2。

距离表C2211435621Hamilton回路，C(H1) =35.2。

(2)中国邮路问题。虚拟一条边

取回路H1＝{v1，v3，v4}，C(H1)=9+5+3=17,C(v1，v3)=9> C(H1)/2，调整回路。

所有回路满足最短回路的准则，上图是最短的欧拉回路，其中边(v1, v4)和(v4, v3)各重复一次。