5.2 用元素差额法直接给出表5-53及表5-54下列两个运输问题的近似最优解．
表5-53
表5-54
【解】表5-53。
表5-54 Z=495
5.3 求表5-55及表5-56所示运输问题的最优方案． （1）用闭回路法求检验数（表5-55）
表5-55
（2）用位势法求检验数（表5-56）
表5-56
【解】（1）
(2)
5.4 求下列运输问题的最优解 （1）C 1目标函数求最小值；（2）C 2目标函数求最大值
⎡7101520⎤60⎡3592⎤50
⎥25 C =⎢141396⎥30
C 1=⎢6485⎢⎥⎢⎥
⎢⎢⎣1113127⎥⎦30⎣58710⎥⎦90
15 45 20 40 60 30 50 40
(3)目标函数最小值,B 1的需求为30≤b 1≤50, B 2的需求为40，B 3的需求为20≤b 3≤60,A 1不可达A 4 ，B 4的需求为30．
⎡497-⎤70⎢6532⎥20 ⎢⎥⎢⎣84910⎥⎦50
【解】（1）
（2）
5
5.5（1）建立数学模型
设x ij (I=1,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往B 1，B 2两城市的台班数，则
max Z =40(80x 11+65x 12+60x 21+50x 22+50x 31+40x 32) ⎧40x 11+40x 21+40x 31=400⎪40x +40x +40x =600
2232⎪12
⎪⎪x 11+x 12≤5⎨
⎪x 11+x 22≤10⎪x 31+x 32≤15⎪⎪⎩x ij ≥0(i =1, 2,3; j =1, 2)
(2)写平衡运价表
（3）最优调度方案：
即甲第天发5辆车到B 1城市，乙每天发5辆车到B 1城市，5辆车到B 2城市，丙每天发10辆车到B 2城市，多余5辆，最大收入为
Z=40（5×80+5×60+5×50+10×40）=54000（元）
5.6（1）设x ij 为第i 月生产的产品第j 月交货的台数，则此生产计划问题的数学模型为
min Z =x 11+1.15x 12+1.3x 13+1.45x 14+Mx 21+ +0.98x 44⎧x 11+x 21+x 31+x 41=50⎪
⎪x 12+x 22+x 32+x 42=40⎪x 13+x 23+x 33+x 43=60⎪
⎪x 14+x 24+x 34+x 44=80⎪
⎨x 11+x 12+x 13+x 14≤65⎪x +x +x +x ≤65⎪21222324
⎪x 31+x 32+x 33+x 34≤65⎪
⎪x 41+x 42+x 43+x 44≤65⎪x ij ≥0,(i , j =1, , 4) ⎩
（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量
25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用
Z=235万元。
5.7 假设在例5.15中四种产品的需求量分别是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人每人做一项工作．
⎡126915⎤⎢20121826⎥
⎥ （1）C ＝⎢
⎢35181025⎥⎢⎥6101520⎣⎦
【解】最优解
1⎤⎡
⎢1⎥
⎥, Z =43 X =⎢
⎢1⎥⎢⎥1⎣⎦
⎡26
⎢25
（2）C ＝⎢
⎢20⎢⎣22
38333031
41444745
52595653
27⎤21⎥⎥
25⎥⎥20⎦
最优解：甲～戊完成工作的顺序为3、5、1、2、4，最优值Z=165
最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。
5.9 求解下列最大值的指派问题：
⎡109617⎤⎢15141020⎥
⎥ （1）C ＝⎢
⎢18131319⎥⎢⎥⎣1681226⎦
【解】最优解
1⎤⎡
⎢1⎥
⎥, Z =64 X =⎢
⎢1⎥⎢⎥
1⎣⎦
⎡96510⎤
⎢4－85⎥⎢⎥
（2）C ＝⎢710912⎥
⎢⎥615716⎢⎥⎢⎣9868⎥⎦
【解】最优解
⎡1⎤
⎢⎥1⎢⎥X =⎢1⎥, Z =44
⎢⎥
1⎢⎥⎢1⎥⎣⎦
第5人不安排工作。
5.10 学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-58所示．如何从中选拔一个接力队，使预期的比赛成绩最好．
【解】设x ij 为第i 人参加第j 项目的状态，则数学模型为
表5-58 成绩表(分钟)
min Z =20x 11+43x 12+33x 13+29x 14+ 28x 54⎧x 11+x 12+x 13+x 14=1⎪x +x +x +x =1⎪21222324
⎪x 31+x 32+x 33+x 34=1⎪
⎪x 41+x 42+x 43+x 44=1⎪x +x +x +x =1⎪51525354⎨
⎪x 11+x 21+x 31+x 41+x 51=1⎪x 12+x 22+x 32+x 42+x 52=1⎪
⎪x 13+x 23+x 33+x 43+x 53=1⎪x +x +x +x +x =1⎪1424344454⎪⎩x ij =0或1, i =1, 2, ,5; j =1, 2,3, 4
接力队最优组合 乙 长跑 丙 游泳 丁 登山 戊 自行车
甲淘汰。预期时间为107分钟。
习题六
6.1如图6－39所示，建立求最小部分树的0－1整数规划数学模型。 【解】边[i ，j ]的长度记为c ij ，设
⎧1边[i , j ]包含在最小部分树内
x ij =⎨
⎩0否则
数学模型为：
图6－
39
min Z =c ij x ij
⎧⎪∑x ij =5⎪i , j
⎪x 12
+x 13+x 23≤2, x 23+x 24+x 34≤2
⎪⎪
x 34+x 36+x 46≤2, x 35+x 36+x 56≤2
⎨x +x 23+x 26+x 36≤2, x 1213+x 24+x 34≤3
⎪⎪x 34
+x 35+x 46+x 56≤3, x 12+x 13+x 26+x 36
≤3
⎪⎪
x 23+x 35+x 26+x 56≤3, x 12+x 15+x 26+x 56≤3⎪x ⎩
ij =1或0, 所有边[i , j ]6.2如图6－40所示，建立求v 1到v 6的整数规划数学模型。
【解】弧(i ，j ) 的长度记为c ij ，设
x ⎧⎨
1弧(i , j ) 包含在最短路径中
ij = ⎩0否则
数学模型为：
图6－
40
min Z =∑c ij x ij
i , j
⎧⎪x 12+x 13=1, x 12=x 23+x 24+x 25
⎪⎨
x 13
+x 23=x 34+x 35, x 24+x 34=x 45+x 46
⎪x 25+x 35+x 45=x 56, x 46+x 56=1⎪⎩
x ij =1或0, 所有弧(i , j ) 6.3如图6－40所示，建立求v 1到v 6的最大流问题的线性规划数学模型。
【解】 设x ij 为弧（i , j ）的流量，数学模型为
min Z =x 12+x 13
⎧x ⎪12+x 13=x 46+x 56⎪x 12
=x 23+x 24+x
25⎪⎪⎨
x 13+x 23=x 34+x 35
⎪x 24+x 34=x 45+x 46⎪⎪x 25+x 35+x 45=x 56⎪⎩0≤x ij ≤c ij , 所有弧(i , j )
6.4求图6－41的最小部分树。图6-41（a ）用破圈法, 图6-41（b ）用加边法。
最短路问题的0－1
运筹学 习题答案
11
图6－41
【解】图6-41（a ），该题有4个解，最小树长为21，其中一个解如下图所示。
图6-41（b ），最小树长为20。最小树如下图所示。
6.5 某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。
表6-20
12
【解】属于最小树问题。用加边法，得到下图所示的方案。
最低总成本74.3万元。
6.6在图6－42中，求A 到H 、I 的最短路及最短路长，并对图(a ) 和(b ) 的结果进行比较。
图6－42
【解】图6－42(a ):
A 到H 的最短路P AH ={A,B,F,H},{A,C,F,H}最短路长22；A 到I 的最短路P AI ={A,B,F,I},{A,C,F,I}最短路长21。 对于图6－42(b ) ：
A 到H 的最短路P AH ={A,C,G,F,H},最短路长21；A 到I 的最短路P AI ={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年的设备购置和维护总费用最小。 【解】设点v j 为第j 年年初购置新设备的状态，（i ，j ）为第i 年年初购置新设备使用到第j 年年初，弧的权为对应的费用（购置费＋维护费），绘制网络图并计算，结果见下图所示。
总费用最小的设备更新方案为：第一种方案，第1年购置一台设备使用到第5年年末；第二种方案，第1年购置一台设备使用到第2年年末，第3年年初更新后使用到第5年年末。总费用为11.5万元。
6.8图6－43是世界某6大城市之间的航线，边上的数字为票价（百美元），用Floyd 算法设计任意两城市之间票价最便宜的路线表。
【解】教师可利用模板求解：data\chpt6\ch6.xls
图6－43
最优票价表：
v 1、v 2、„、v 6到各点的最优路线图分别为：
6.9 设图6－43是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离(km)。现要在6个工厂中选一个建装配车间。
（1）应选那个工厂使零配件的运输最方便。
（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨，运价为2元/吨公里。应选那个工厂使总运费最小。 【解】(1)利用习题6.8表L3的结果
L =min i
max j
{L ij }=12.8
选第1个工厂最好。
(2)
选第4个工厂最好。
6.10 如图6－44，（1）求v 1到v 10的最量；（2）求最小割集和最小割量。 【解】给出初始流如下
图6－44
大流及最大流
第一轮标号：得到一条增广链，调整量等于5，如下图所示
调整流量。
第二轮标号：得到一条增广链，调整量等于2，如下图所示
调整流量。
第三轮标号：得到一条增广链，调整量等于3，如下图所示
调整流量。
第四轮标号：不存在增广链，最大流量等于45，如下图所示
取 V 1={v 1, v 2, v 3, v 4, v 5, v 6, v 8},1={v 7, v 9, v 10}，最小截集{(3,7),(4,7),(6,9),(8,10)，最小截量等于45。
6.11 将3个天然气田A 1、A 2、A 3的天然气输送到2个地区C 1、C 2，中途有2个加压站B 1、B 2，天然气管线如图6－45所示。输气管道单位时间的最大通过量c ij 及单位流量的费用d ij 标在弧上(c ij , dij ) 。求(1)流量为22的最小费用流；（2）最小费用最大流。
图6－45
【解】虚拟一个发点和一个收点
T6.11－1
得到流量v ＝22的最小费用流，最小费用为271。求解过程参看第4章PPT 文档习题答案。
T6.11－13
最小费用最大流如下图，最大流量等于27，总费用等于351。
6.12如图6－43所示，（1）求解旅行售货员问题；（2）求解中国邮路问题。
图6-43
【解】（1）旅行售货员问题。
在C
由距离表C1，v 1到v 4，114356211去掉第1行第四列，d 41=∞，得到距离表C2。
距离表C2的每行每列都有零，H 2= H1={ v1, v4 , v 3 , v 5 , v 6 , v 2 , v 1}就是总距离最小的Hamilton 回路，C(H1) =35.2。 (2)中国邮路问题。虚拟一条边
取回路H 1＝{v 1，v 3，v 4}，C(H1)=9+5+3=17,C(v 1，v 3)=9> C(H1)/2，调整回路。
所有回路满足最短回路的准则，上图是最短的欧拉回路，其中边(v 1, v 4) 和(v 4, v 3) 各重复一次。
习题七
7.2(1)分别用节点法和箭线法绘制表7-16的项目网络图，并填写表中的紧前工序。 (2) 用箭线法绘制表7-17的项目网络图，并填写表中的紧后工序
表7-16
表7-17
【解】（1）箭线图：
节点图：
（2）箭线图：
7.3根据项目工序明细表7-18： （1）画出网络图。
（2）计算工序的最早开始、最迟开始时间和总时差。 （3）找出关键路线和关键工序。
表7-18
【解】(1)网络图
(2)网络参数
(3)关键路线：①→②→③→④→⑤→⑥→⑦；关键工序：A 、C 、D 、G ；完工期：48周。 7.4 表7-19给出了项目的工序明细表。
表7-19
（1）绘制项目网络图。
（2）在网络图上求工序的最早开始、最迟开始时间。
（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差。 （4）找出所有关键路线及对应的关键工序。 （5）求项目的完工期。 【解】(1)网络图
（2）工序最早开始、最迟开始时间
（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差
(4)关键路线及对应的关键工序
11→○12；关键工序：B,E,G,H,K,M 关键路线有两条，第一条：①→②→⑤→⑥→⑦→○
11→○12；关键工序：C,F,L,M 第二条：①→④→⑧→⑨→○
（5）项目的完工期为62天。
7.5已知项目各工序的三种估计时间如表7-20所示。
求：
表7-20 （1）绘制网络图并计算各工序的期望时间和方差。
（2）关键工序和关键路线。
（3）项目完工时间的期望值。
（4）假设完工期服从正态分布，项目在56小时内完工的概率
是多少。
（5）使完工的概率为0.98，最少需要多长时间。
【解】（1）网络图
(2)关键工序：A,C,E,F ；关键路线：①→②→④→⑤→⑥
(3) 项目完工时间的期望值：10.17+14.83+17.17+11.83
＝54(小时)
完工期的方差为0.25+0.25+0.6944+0.6944＝1.8889
σ1.37437
(4)X0=56，Φ
⎛X 0-μn ⎫⎛56-54⎫
=Φ⎪ ⎪＝Φ(1.4552）＝0.927
⎝1.37437⎭⎝σn ⎭
56天内完工的概率为0.927
(5) p=0.98，p {X ≤X 0) =Φ(Z ) =0.98, Z =2.05
X 0＝Z σ+μ=2.05⨯1.3744+54=56.82
要使完工期的概率达到0.98，则至少需要56.82小时。
7.6 表7-21给出了工序的正常、应急的时间和成本。
表7-21
（1（2）按应急时间计算完成项目的总成本和工期。
（3）按应急时间的项目完工期，调整计划使总成本最低。
（4）已知项目缩短1天额外获得奖金4万元，减少间接费用2.5万元，求总成本最低的项目完工期。 (1) 正常时间项目网络图 项目网络图
总成本为435，工期为64。 (2)应急时间项目网络图
总成本为560，工期为51。 (3)应急时间调整
工序C 、F 按正常时间施工，总成本为560-9-15＝536，完工期为51。 (4) 总成本最低的项目完工期
工序A 、E 分别缩短3天，总成本为435+15+12-6.5×7＝416.5，完工期为57。
7.7继续讨论表7-21。假设各工序在正常时间条件下需要的人员数分别为9、12、12、6、8、17、14人。 （1）画出时间坐标网络图
（2）按正常时间计算项目完工期，按期完工需要多少人。
（3）保证按期完工，怎样采取应急措施，使总成本最小又使得总人数最少，对计划进行系统优化分析。 【解】（1）正常时间的时间坐标网络图
(2) 按正常时间调整非关键工序的开工时间
(3)略，参看教材。
7.8用WinQSB 软件求解7.5。 7.9用WinQSB 软件求解7.6。
习题八
8.1 在设备负荷分配问题中，n =10，a =0.7，b =0.85，g =15，h =10，期初有设备1000台。试利用公式(8.7)确定10期的设备最优负荷方案。 【解】将教材中a 的下标i 去掉。
n -t
g -h
由公式∑a ≤≤∑a i 得
g (b -a ) i =0i =0
i
n -t -1
(g -h )/g (b -a ) ＝0.2222，a 0＋a 1＋a 2＝1+0.7＋0.49＝2.19＜2.222＜a 0+a 1＋a 2＋a 3＝2.533，n －t －1＝2，t =7，则
1~6年低负荷运行，7~10年为高负荷运行。各年年初投入设备数如下表。
1 2 3 4 5 6 7 8 9 10 年份
设备台数 1000 850 723 614 522 444 377 264 184.8 129
8.2如图8－4，求A 到F 的最短路线及最短距离。
【解】A 到F 的最短距离为13；最短路线 A→ B2→ C3 → D2 → E2 → F及A→C2 → D2 → E2 → F
8.3求解下列非线性规划
max Z =x 1x 2x 3⎨⎪⎩x j ≥0, j =1, 2,3max Z =x 1x 2x 3⎨⎪⎩x j ≥0, j =1, 2,3
22
min Z =x 1+x 2+x 3m a x Z =x 21+x 32+x 23
（3） ⎧x 1+x 2+x 3=10
(1) ⎧⎪x 1+x 2+x 3=C (2) ⎧x 1+x 2+x 3=C
⎨
⎩x 1, x 2, x 3≥0max Z =x 1x 2x 3
⎨
⎩x 1, x 2, x 3≥0
2
max Z =x 12+2x 1+2x 2+x 3⎨
⎩x 1, x 2, x 3≥0
(4) ⎪⎧x 1+4x 2+2x 3=10 (5) ⎪⎧2x 1+4x 2+x 3≤10 （6）⎧x 1+x 2+x 3=8
⎨
⎪⎩x j ≥0, j =1, 2,3
【解】（1）设s 3=x3 , s3+x2=s2，s 2+x1=s1=C
则有 x 3= s3 ，0≤x2≤s2，0≤x1≤s1=C 用逆推法，从后向前依次有
k ＝3， f 3(s 3) =max(x 3) =s 3 及最优解 x 3*=s3
x 3=s 3
k ＝2，f 2(s 2) =max [x 2f 3(x 3) =max [x 2(s 2-x 2)]=max h 2(s 2, x 2)
0≤x 2≤s 2
0≤x 2≤s 2
0≤x 2≤s 2
由
∂h 21
=s 2-2x 2=0, 则x 2＝s 2 ∂x 22
1∂2h 2
x =s 2为极大值点。 故 ＝－2
2∂x 2
121212
所以 f 2(s 2) =s 2-s 2=s 2 及最优解x 2*=s2
244
12
k =1时， f 1(s 1) =max[x 1f 2(s 2)]=max x 1(s 1-x 1) =max h 1(s 1, x 1) ，
0≤x 1≤s 10≤x 1≤s 10≤x 1≤s 14
1∂h 12*2
由1=(s 1-4s 1x 1+3x 1) =0，得x 1=s 1
3∂x 14
1113
s 1(s 1-s 1) 2=s 1 故f 1(s 1) =12327
已知知x 1 + x 2+ x 3 = C，因而按计算的顺序推算，可得各阶段的最优决策和最优解如下
113*
x 1=C ，f 1(C ) =c
327
11
C , f 2(s 2) =C 2 3911*
由s 3=s 2－x 2*=C/3，x 3=C , f 3(s 3) =C
33
由s 2=s 1－x 1*=2C/3，x 2=
*
最优解为：
11113
X =(C , C , C ) T ; z =C
33327
【解】（2）设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=C
则有 x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=C 用逆推法，从后向前依次有
k ＝3， f 3(s 3) =min(x ) 3=s 3及最优解 x 3*=s3
x 3=s 3
2
k ＝2，f 2(s 2) =min [x 2+f 3(x 3) =min [x 2+(s 2-x 2) ]=min h 2(s 2, x 2)
0≤x 2≤s 2
0≤x 2≤s 2
0≤x 2≤s 2
222
由
∂h 21
=4s 2-2x 2=0, 则x 2＝s 2 ∂x 22
∂2h 21
s 2为极小值点。 =4>0,故 x =22
2∂x 2
12*1
因而有f 2(s 2) =s 2, x 2=s 2
22
12+(s -k ＝1时， f 1(s 1) =min [x 11x ) 1=min h (s 1, x 1) 0≤x 1≤s 10≤x ≤1s 12
1∂h *
由1=1-s 1+x 1=0知 x 1=s 1-1, f 1(s 1) =s 1-
2∂x 1
得到最优解
1
1
X =(C -1, 1/2, 1/2) T ; z =C -
2
【解】(3) 设s 3=x3 , s3+x2=s2，s 2+x1=s1=10 则有 x 3= s3 ，0≤x2≤s2，0≤x1≤s1=10 用逆推法，从后向前依次有
k ＝3时，f 3(s 3) =max(x 3) =s 3 及最优解 x 3=s3
x 3=s 3
2
k ＝2时，f 2(s 2) =max [3x 2+(s 2-x 2) ]=max h 2(s 2, x 2)
0≤x 2≤s 2
0≤x 2≤s 2
2
∂h 23
=3-2s 2+2x 2=0时x 2=-+s 2 ∂x 22
∂2h 23 而 =2>0, 故x =-+s 2不是一个极大值点。 22
∂x 22
2
讨论端点：当 x 2=0时f 2(s 2) ＝s 2, x 2= s 2时f 2(s 2) =3s 2
如果s 2>3
2
时, f 2(s 2) =s 2
2
0≤x 1≤s 1
0≤x 1≤s 1
k ＝1时，f 1(s 1) =max[2x 1+(s 1-x 1) ]=max h 1(s 1, x 1)
∂h 1
=2-2s 1+2x 1=0时x 1=-1+s 1 ∂x 1
∂2h 1 =2>0, 故x 1=-1+s 2不是一个极大值点 2
∂x 1
同理有, x 1=0, f 1（s 1）= s 12= 100，x 1= s 1, f 1（s 1）= 2s 1= 20 (舍去) 得到最优解
X =(0,0,10); z =100
【解】(4) 设s 3=x 3 ,2s 3+4x 2=s2，s 2+x 1=s1=10 则有 x 3= s3 ，0≤x 2≤s2/4，0≤x 1≤s1=10 用逆推法，从后向前依次有 k ＝1，
f 3(s 3) =max(x 3) =s 3及最优解 x 3*=s3
x 3=s 3
1
m x x [2(s 2-0≤x 2≤s 42
∂h 11
由2=s 2-4x 2=0,则 x 2=s 2
8∂x 22
k ＝2， f 2(s 2) =
x 22=)
0≤x 224
m a h x 2, 2s 2( x
)
1∂2h 2
x =s 2为极大值点。 , 故 =-4
8∂x 2
2
s 2
则f 2(s 2) = 及最优解x 2*=s2/8
32
1
x 1(s 1-x 1) 2]=max h 1(s 1, x 1)
0≤x 1≤s 1320≤x 1≤s 1
13∂h 12*1f (s ) =s 1 1=，故 (s 1-4s 1x 1+3x 2) =0, x =s 11111
216∂x 1323
k ＝1， f 1(s 1) =max[ 得到最优解
X =(10/3, 5/6, 5/3) T ; z =125/27
【解】(5) 按问题中变量的个数分为三个阶段s 1 ，s 2 ，s 3 ，且s 3≤10，x 1，x 2，x 3为各阶段的决策变量，
各阶段指标函数相乘。
设s 1=2x 1 , s1+4x 2=s2，s 2+x 3=s3≤10，则有 x 1= s1/2 ，0≤x 2≤s2/4，0≤x 3≤s3=10 用顺推法，从前向后依次有 k ＝1， f 1(s 1) =max (x 1) =
x 1=s 1/2
s 1
及最优化解 x 1*=s1/2 2
x 42=)
0≤x 2≤s 2/4
1
m a x [x 2s (-20≤x 2≤s 2/42
1∂h 1*
由2=s 2-4x 2=0, 则 x 2=s 2
8∂x 22
k ＝2， f 2(s 2) =
m a h x 2s 2( x 2,
)
113∂2h 2
x =s f (s ) =s 2 , 故 为极大值点。则=-4
832∂x 2
1
x 3(s 3-x 3) 2]=max h 3(s 3, x 3) k ＝3， f 3(s 3) =max [
0≤x 3≤s 3320≤x 3≤s 3
∂h 1212*由3=(s 3-4s 3x 3+3x 3) =0, x 3=s 3 ∂x 3323
13
s 3，由于s 3≤10，则s 3=10时取最大值，x 3＝10/3，s 2=s3－x 3＝20/3，x 2＝5/6，s 1=s2－4x 2故f 3(s 3) =216
＝10/3，x 1＝5/3
得到最优解
X =(5/3, 5/6, 10/3) T ; z =125/27
【解】（6）设s 1=x1, s1+x2=s2，s 2+x3=s3=8
k ＝1，f 1(s 1) =max(x 1+2x 1) =s 1+2s 1 及最优化解 x 1*=s 1
x 1=s 1
2
2
2
2
k ＝2，f 2(s 2) =max [2x 2+(s 2-x 2) +2(s 2-x 2)]=max h 2(s 2, x 2)
0≤x 2≤s 2
0≤x 2≤s 2
∂h 2∂2h 2
=6x 2-2s 2-2, =6>0 2∂x 2∂x 2
x 2*=0时，f 2（s 2）=s22+2s2, x 2*= s2时，f 2（s 2）=2s22
22
故 f 2(s 2) =max{s 2+2s 2,2s 2}
k ＝3，
①当x 2*=0时， f 3(s 3) =max [x 3+(s 3-x 3) +2(s 3-x 3)]=max h 3(s 3, x 3) 同样得x 3*=0时
x 3*=s3时，f 3（s 3）=s3 所以， f 3（s 3）= s32+2s3=80 ②当x 2*= s2时，f 3（s 3）=max [x3+2（s 3-x 3）2] 同样得x 3*=0时
x 3*=s3时，f 3（s 3）=s3 =8 所以， f 3（s 3）= 2s32=128 最优解为
0≤x 3≤s 3
，f 3（s 3）=2s32 =128
2
0≤x 3≤s 3
，f 3（s 3）=s32+2s3
0≤x 3≤s 3
X =(0,8, 0); z =128
8.4用动态规划求解下列线性规划问题。
max Z =2x 1+4x 2⎧2x 1+x 2≤6⎪x ≤2⎪1⎨
⎪x 2≤4⎪⎩x 1, x 2≥0
【解】设s 2=x 2 ,s 2+2x 1=s1≤6
则有 0≤x2=s2≤4，0≤x1≤s1/2 用逆推法，从后向前依次有 f 2(s 2) =4s 2及最优解 x 2*=s2
f 1(s 1) =
0≤x 1≤s 1/2
m a x [x 21+f 2s (2=) ]
0≤x 1≤s 1/2
m a x s 1-[4 x 16]
0≤x 1≤s 1/2
由 s 2=s1－2x 1≤4， s 1≤6，取s 1＝6，
又1≤x 1≤2，取x 1＝1， 最优解
f 1(s 1) =max [24-6x 1]
f 1(s 1) =18
X =(1,4) T ; z =18
8.5 10吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表8.24所示。应该如何装载货物使总价值最大。
【解】设装载第I i m a x z =3x x x 1+42+53
⎧2x 1+3x 2+4x 3≤9
⎨
且为整数⎩x 1, x 2, x 3≥0
利用背包问题的前向动态规划计算，建立动态规划模型。由于决策变量离散型值，所以可用列表法求
解。当R=1时，
f 1(s 2) =max (3x 1) 。计算结果如下：
0≤x ≤s /2
当R=2时，f 2（s 3）=[4x2+f1（s 3-3x 2）]
0≤x 1≤s 2/4
当R=3时，f 3（9）=max [5x3+f2（9-4x 3）] （x 3为整数）=max [f2（9），5+f2（5），10+f2（1）]=max[13，
0≤x 3≤2
0≤x 2≤2
12，10]=13
8.6 有一辆货车载重量为10吨 ，用来装载货物A 、B 时成本分别为5元/吨和4元/吨。现在已知每吨
货物的运价与该货物的重量有如下线性关系：
A ：P 1=10-2x 1 ，B ：P 2=12-3x 2
其中x 1 、x 2 分别为货物A 、B 的重量。如果要求货物满载，A 和B 各装载多少，才能使总利润最大 【解】将原题改为A ：P 1=15-x 1 ，B ：P 2=18-2x 2 由题意可得各种货物利润函数为
2
g 1(x 1) =(1-5x 1-5x ) =1x 0-x 111
g 2(x 2) =(1-8x 22-4x 2) =1x 24-x 22
2
max z =(10x 1-x 12) +(14x 2-2x 2)
2
原问题的数学模型归结为
⎧x 1+x 2=10⎨
⎩x 1, x 2≥0
最优解：x 1 =6，x 2 =4；z ＝48
8.7 现有一面粉加工厂，每星期上五天班。生产成本和需求量见表8-25。
表8-25
面粉加工没有生产准备成本，每袋面粉的存储费为h k ＝0.5元/袋，按天交货，分别比较下列两种方案的最优性，求成本最小的方案。
（1）星期一早上和星期五晚的存储量为零，不允许缺货，仓库容量为S=40袋； （2）其它条件不变，星期一初存量为8。 【解】动态规划求解过程如下： 阶段k ：日期，k =1,2,…,6
状态变量s k ：第k 天早上（发货以前）的冷库存量 决策变量x k ：第k 天的生产量 状态转移方程：s k +1=s k +xk －d k ；
决策允许集合：D k (s k ) =x k x k ≥0, 0≤s k +x k -d k ≤40 阶段指标： v k (s k ，x k )=c k x k +0.5s k 终端条件：f 6(s 6)=0, s 6=0； 递推方程：
{}
f k (x k ) =min {v k (s k , x k ) +f k +1(s k +1) }
x k ∈D k (s k )
=min
x k ∈D k (s k
{v k (s k , x k ) +f k +1(s k +x k -d k ) })
当k =5时，因为s 6=0，有s 6=s 5+x 5-d 5=0, 由于s 5≤15，
x 5=15-s 5,
f 5(s 5) =min {10x 5+0.5s 5}
x 5∈15-s 5
*
5
=150-9.5s 5, x =15-s 5
k =4时，0≤s 5≤15，0≤s 4+x 4-30≤15, 有30-s 4≤x 4≤45-s 4，
f 4(s 4) =min {12x 4+0.5s 4+f 5(s 5)}
=min
x 4∈D 4(s 4)
*
⎧-11.5s 4+510s 4≤30, x 4=30-s 4=⎨*
⎩-9s 4+43540≤s 4≤30, x 4=0
k =3时，当0≤s 4≤30时，0≤s 3+x 3-25≤30，得
x 4∈D 4(s 4)
{2.5x 4-9s 4+435}
运筹学 习题答案 31
25-s 3≤x 3≤55-s 3
有D 3(s 3) =x 3max[0.25-s 3]≤x 3≤55-s 3
{}
f 3(s 3) =min
3
3
{9x 3+0.5s 3+f 4(s 4)}
=min {9x 3+0.5s 3-11.5s 4+510}x ∈D (s )
=min {-2.5x 3-11s 3+797.5}x ∈D (s )
x 3∈D 3(s 3)
3
3
3
3
=-8.5s 3+660
当30≤s 4≤40时，x 4=0,30≤s 3+x 3-25≤40，有
*
取上界：x 3=55-s 3
D 3(s 3) ={x 355-s 3≤x 3≤65-s 3}
f 3(1)(s 3) =min
=min
3
3
{9x 3+0.5s 3-9s 4+435}*
=min {-8.5x 3+210}, x 3取任意值x ∈D (s )
x 3∈D 3(s 3)
3
x 3∈D 3(s 3)
{9x 3+0.5s 3+f 4(s 4)}
显然此决策不可行。
当k =2时，由0≤s 4≤30,0≤s 3≤25，0≤s 2+x 2-20≤25, x 2的决策允许集合为
D 2(s 2) ={x 2max[0,20-s 2]≤x 2≤45-s 2}
f 2(s 2) =min
2
2
{6x 2+0.5s 2+660-8.5s 2}
=min {-2.5x 2-8s 2+830}x ∈D (s )
x 2∈D 2(s 2)
2
*
取上界：x 2=45-s 2
=-5.5s 2+717.5
当k =1时，由0≤s 2≤20，0≤s 1+x 1-10≤20，则x 1的决策允许集合为
D 1(s 1) ={x 1max[0,10-s 1]≤x 1≤30-s 1} f 1(s 1) =min {8x 1+0.5s 1+717.5-5.5s 2}
=min {2.5x 1-5s 1+772.5}x 1∈D 1(s 1)
=797.5
因为s 1=0, x 1=10,
x 1∈D 1(s 1)
s 2=10-10=0, x 2=45-s 2=45, s 3=s 2+x 2-20=25, x 3=55-s 3=30, s 4=s 3+x 3-25=30, x 4=30-s 4=0, s 5=s 4+x 4-30=0, x 5=15-s 5=-15.
(2)期初存储量s 1=8, 与前面计算相似，x 1=2. Min Z=772.5+2.5x1-5s 1=737.5 则总成本最小的方案是第二种。
8.8 某企业计划委派10个推销员到4个地区推销产品，每个地区分配1~4个推销员。各地区月收益（单位：10万元）与推销员人数的关系如表8－26所示。
表8-26
32
企业如何分配4个地区的推销人员使月总收益最大。
【解】设x k 为第k 种货物的运载重量，该问题的静态规划模型为
max Z =v 1(x 1) +v 2(x 2) +v 3(x 3) +v 4(x 4) ⎧⎪x 1+x 2+x 3+x 4=8⎨⎪⎩x j =0, 2, 4,6,8
利用图表法：
故最优解为x 1=0, x 2=0, x 3=x 4=4
则 max Z=44
8.9 有一个车队总共有车辆100辆，分别送两批货物去A 、B 两地，运到A 地去的利润与车辆数目满足关系100x ，x 为车辆数，车辆抛锚率为30%，运到B 地的利润与车辆数y 关系为80y ，车辆抛锚率为20%，总共往返3轮。请设计使总利润最高的车辆分配方案。 【解】动态规划求解过程如下。
阶段k ：共往数k=1,2,3,4，k=1表示第一趟初，k =4表示第三趟末（即第六年初）；
状态变量s k ：第k 趟初完好的车辆数（k =1,2,3,4），也是第k －1趟末完好的车辆数，其中s 4表示第三趟末的完好车辆数。
决策变量x k ：第k 年初投入高负荷运行的机器数；
状态转移方程：s k +1=0.7x k +0.8(s k －x k ) 决策允许集合：D k (s k )={x k |0≤x k ≤s k } 阶段指标：v k (s k ，x k )=100x k +80(s k －x k ) 终端条件：f 4(s 4)=0 递推方程：
f k (s k ) =max
0≤x k ≤s k
x k ∈D k (s k )
{v k (s k , x k ) +f k +1(s k +1) }
=max {100x k +80(s k -x k ) +f k +1[0.7x k +0.8(s k -x k ) ]}
f k (x k ) 表示第k 趟初分配x k 辆车到A 地，到第3趟末的最大总运价为
f 3(s 3) =max {100x 3+80(s 3-x 3) +f 4(s 4) }
0≤x 3≤s 3
=max{20x 3+80s 3}=100s 3
0≤x 3≤s 3
x =s 3最优
*3
f 2(s 2) =max {100x 2+80(s 2-x 2) +f 3(s 3) }
0≤x 2≤s 2
=max {10x 2+160s 2}=170s 2
0≤x 2≤s 2
*x 2=s 2最优
f 1(s 1) =max {100x 1+80(s 1-x 1) +f 2(s 2) }
0≤x 1≤s 1
=max{3x 1+216s 1}=219s 1
0≤x 1≤s 1
x =s 1最优
*1
因为s 1=100，最大总运价f 1(s 1)=21900元
8.10 系统可靠性问题。一个工作系统由n 个部件串联组成，见图8-5。只要有一个部件失灵，整个系统就不能工作。为提高系统的可靠性，可以增加部件的备用件。例如，用5个部件1并联起来作为一个部件与部件2串联，如果其中一个部件失灵其它4个部件仍能正常工作。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。
图8-5
假设部件i (i =1,2, , n ) 上装有x i 个备用件，该部件正常工作的概率为p i (x i ) 。设装一个部件i 的备用件的成本为c i ，要求备件的总费用为C 。那么该问题模型为：
n
max P =∏p i (x i )
i =1
⎧n （8.8）
c x ≤C ∑i i ⎪⎨i =1
⎪x ≥0并且为整数，i =1, 2, , n ⎩j
同理，如果一个复杂的工作系统由n 个部件并联组成的，只有当n 个部件都失灵，整个系统就不能工作，见图8-6。
图8-6
假设p i (x i ) 为第i 个部件失灵的概率，为提高系统的可靠性，可以增加部件的备用件。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。系统的可靠性为1-则该问题的数学模型归结为
∏p (x ) ，
i
i
i =1
n
min P =∏p i (x i )
i =1
n
（8.9） ⎧n
c x ≤C ⎪∑i i ⎨i =1
⎪x ≥0并且为整数，i =1, 2, , n ⎩j
利用式(8.8)或（8.9）求解下列问题。
（1）工厂设计的一种电子设备，其中有一系统由三个电子元件串联组成。已知这三个元件的价格和可靠性如表8-27所示，要求在设计中所使用元件的费用不超过200元，试问应如何设计使设备的可靠性达到最大。
表8-27
（
2场调查和预测得出，如表8-28所示，试求在哪一周以什么价格购入，使其采购价格的期望最小，并求出期望值。
表8-28
max Z =(1-0.05x 1)(1-0.2x 2)(1-0.4x 3) ⎧40x 1+35x 2+20x 3≤200⎨
⎩x 1, x 2, x 3≥0并且为整数
最优解X=(1，2，4) ；可靠性Z=0.888653，总费用190。 （2）
5.2 用元素差额法直接给出表5-53及表5-54下列两个运输问题的近似最优解．
表5-53
表5-54
【解】表5-53。
表5-54 Z=495
5.3 求表5-55及表5-56所示运输问题的最优方案． （1）用闭回路法求检验数（表5-55）
表5-55
（2）用位势法求检验数（表5-56）
表5-56
【解】（1）
(2)
5.4 求下列运输问题的最优解 （1）C 1目标函数求最小值；（2）C 2目标函数求最大值
⎡7101520⎤60⎡3592⎤50
⎥25 C =⎢141396⎥30
C 1=⎢6485⎢⎥⎢⎥
⎢⎢⎣1113127⎥⎦30⎣58710⎥⎦90
15 45 20 40 60 30 50 40
(3)目标函数最小值,B 1的需求为30≤b 1≤50, B 2的需求为40，B 3的需求为20≤b 3≤60,A 1不可达A 4 ，B 4的需求为30．
⎡497-⎤70⎢6532⎥20 ⎢⎥⎢⎣84910⎥⎦50
【解】（1）
（2）
5
5.5（1）建立数学模型
设x ij (I=1,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往B 1，B 2两城市的台班数，则
max Z =40(80x 11+65x 12+60x 21+50x 22+50x 31+40x 32) ⎧40x 11+40x 21+40x 31=400⎪40x +40x +40x =600
2232⎪12
⎪⎪x 11+x 12≤5⎨
⎪x 11+x 22≤10⎪x 31+x 32≤15⎪⎪⎩x ij ≥0(i =1, 2,3; j =1, 2)
(2)写平衡运价表
（3）最优调度方案：
即甲第天发5辆车到B 1城市，乙每天发5辆车到B 1城市，5辆车到B 2城市，丙每天发10辆车到B 2城市，多余5辆，最大收入为
Z=40（5×80+5×60+5×50+10×40）=54000（元）
5.6（1）设x ij 为第i 月生产的产品第j 月交货的台数，则此生产计划问题的数学模型为
min Z =x 11+1.15x 12+1.3x 13+1.45x 14+Mx 21+ +0.98x 44⎧x 11+x 21+x 31+x 41=50⎪
⎪x 12+x 22+x 32+x 42=40⎪x 13+x 23+x 33+x 43=60⎪
⎪x 14+x 24+x 34+x 44=80⎪
⎨x 11+x 12+x 13+x 14≤65⎪x +x +x +x ≤65⎪21222324
⎪x 31+x 32+x 33+x 34≤65⎪
⎪x 41+x 42+x 43+x 44≤65⎪x ij ≥0,(i , j =1, , 4) ⎩
（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量
25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用
Z=235万元。
5.7 假设在例5.15中四种产品的需求量分别是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人每人做一项工作．
⎡126915⎤⎢20121826⎥
⎥ （1）C ＝⎢
⎢35181025⎥⎢⎥6101520⎣⎦
【解】最优解
1⎤⎡
⎢1⎥
⎥, Z =43 X =⎢
⎢1⎥⎢⎥1⎣⎦
⎡26
⎢25
（2）C ＝⎢
⎢20⎢⎣22
38333031
41444745
52595653
27⎤21⎥⎥
25⎥⎥20⎦
最优解：甲～戊完成工作的顺序为3、5、1、2、4，最优值Z=165
最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。
5.9 求解下列最大值的指派问题：
⎡109617⎤⎢15141020⎥
⎥ （1）C ＝⎢
⎢18131319⎥⎢⎥⎣1681226⎦
【解】最优解
1⎤⎡
⎢1⎥
⎥, Z =64 X =⎢
⎢1⎥⎢⎥
1⎣⎦
⎡96510⎤
⎢4－85⎥⎢⎥
（2）C ＝⎢710912⎥
⎢⎥615716⎢⎥⎢⎣9868⎥⎦
【解】最优解
⎡1⎤
⎢⎥1⎢⎥X =⎢1⎥, Z =44
⎢⎥
1⎢⎥⎢1⎥⎣⎦
第5人不安排工作。
5.10 学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-58所示．如何从中选拔一个接力队，使预期的比赛成绩最好．
【解】设x ij 为第i 人参加第j 项目的状态，则数学模型为
表5-58 成绩表(分钟)
min Z =20x 11+43x 12+33x 13+29x 14+ 28x 54⎧x 11+x 12+x 13+x 14=1⎪x +x +x +x =1⎪21222324
⎪x 31+x 32+x 33+x 34=1⎪
⎪x 41+x 42+x 43+x 44=1⎪x +x +x +x =1⎪51525354⎨
⎪x 11+x 21+x 31+x 41+x 51=1⎪x 12+x 22+x 32+x 42+x 52=1⎪
⎪x 13+x 23+x 33+x 43+x 53=1⎪x +x +x +x +x =1⎪1424344454⎪⎩x ij =0或1, i =1, 2, ,5; j =1, 2,3, 4
接力队最优组合 乙 长跑 丙 游泳 丁 登山 戊 自行车
甲淘汰。预期时间为107分钟。
习题六
6.1如图6－39所示，建立求最小部分树的0－1整数规划数学模型。 【解】边[i ，j ]的长度记为c ij ，设
⎧1边[i , j ]包含在最小部分树内
x ij =⎨
⎩0否则
数学模型为：
图6－
39
min Z =c ij x ij
⎧⎪∑x ij =5⎪i , j
⎪x 12
+x 13+x 23≤2, x 23+x 24+x 34≤2
⎪⎪
x 34+x 36+x 46≤2, x 35+x 36+x 56≤2
⎨x +x 23+x 26+x 36≤2, x 1213+x 24+x 34≤3
⎪⎪x 34
+x 35+x 46+x 56≤3, x 12+x 13+x 26+x 36
≤3
⎪⎪
x 23+x 35+x 26+x 56≤3, x 12+x 15+x 26+x 56≤3⎪x ⎩
ij =1或0, 所有边[i , j ]6.2如图6－40所示，建立求v 1到v 6的整数规划数学模型。
【解】弧(i ，j ) 的长度记为c ij ，设
x ⎧⎨
1弧(i , j ) 包含在最短路径中
ij = ⎩0否则
数学模型为：
图6－
40
min Z =∑c ij x ij
i , j
⎧⎪x 12+x 13=1, x 12=x 23+x 24+x 25
⎪⎨
x 13
+x 23=x 34+x 35, x 24+x 34=x 45+x 46
⎪x 25+x 35+x 45=x 56, x 46+x 56=1⎪⎩
x ij =1或0, 所有弧(i , j ) 6.3如图6－40所示，建立求v 1到v 6的最大流问题的线性规划数学模型。
【解】 设x ij 为弧（i , j ）的流量，数学模型为
min Z =x 12+x 13
⎧x ⎪12+x 13=x 46+x 56⎪x 12
=x 23+x 24+x
25⎪⎪⎨
x 13+x 23=x 34+x 35
⎪x 24+x 34=x 45+x 46⎪⎪x 25+x 35+x 45=x 56⎪⎩0≤x ij ≤c ij , 所有弧(i , j )
6.4求图6－41的最小部分树。图6-41（a ）用破圈法, 图6-41（b ）用加边法。
最短路问题的0－1
运筹学 习题答案
11
图6－41
【解】图6-41（a ），该题有4个解，最小树长为21，其中一个解如下图所示。
图6-41（b ），最小树长为20。最小树如下图所示。
6.5 某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。
表6-20
12
【解】属于最小树问题。用加边法，得到下图所示的方案。
最低总成本74.3万元。
6.6在图6－42中，求A 到H 、I 的最短路及最短路长，并对图(a ) 和(b ) 的结果进行比较。
图6－42
【解】图6－42(a ):
A 到H 的最短路P AH ={A,B,F,H},{A,C,F,H}最短路长22；A 到I 的最短路P AI ={A,B,F,I},{A,C,F,I}最短路长21。 对于图6－42(b ) ：
A 到H 的最短路P AH ={A,C,G,F,H},最短路长21；A 到I 的最短路P AI ={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年的设备购置和维护总费用最小。 【解】设点v j 为第j 年年初购置新设备的状态，（i ，j ）为第i 年年初购置新设备使用到第j 年年初，弧的权为对应的费用（购置费＋维护费），绘制网络图并计算，结果见下图所示。
总费用最小的设备更新方案为：第一种方案，第1年购置一台设备使用到第5年年末；第二种方案，第1年购置一台设备使用到第2年年末，第3年年初更新后使用到第5年年末。总费用为11.5万元。
6.8图6－43是世界某6大城市之间的航线，边上的数字为票价（百美元），用Floyd 算法设计任意两城市之间票价最便宜的路线表。
【解】教师可利用模板求解：data\chpt6\ch6.xls
图6－43
最优票价表：
v 1、v 2、„、v 6到各点的最优路线图分别为：
6.9 设图6－43是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离(km)。现要在6个工厂中选一个建装配车间。
（1）应选那个工厂使零配件的运输最方便。
（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨，运价为2元/吨公里。应选那个工厂使总运费最小。 【解】(1)利用习题6.8表L3的结果
L =min i
max j
{L ij }=12.8
选第1个工厂最好。
(2)
选第4个工厂最好。
6.10 如图6－44，（1）求v 1到v 10的最量；（2）求最小割集和最小割量。 【解】给出初始流如下
图6－44
大流及最大流
第一轮标号：得到一条增广链，调整量等于5，如下图所示
调整流量。
第二轮标号：得到一条增广链，调整量等于2，如下图所示
调整流量。
第三轮标号：得到一条增广链，调整量等于3，如下图所示
调整流量。
第四轮标号：不存在增广链，最大流量等于45，如下图所示
取 V 1={v 1, v 2, v 3, v 4, v 5, v 6, v 8},1={v 7, v 9, v 10}，最小截集{(3,7),(4,7),(6,9),(8,10)，最小截量等于45。
6.11 将3个天然气田A 1、A 2、A 3的天然气输送到2个地区C 1、C 2，中途有2个加压站B 1、B 2，天然气管线如图6－45所示。输气管道单位时间的最大通过量c ij 及单位流量的费用d ij 标在弧上(c ij , dij ) 。求(1)流量为22的最小费用流；（2）最小费用最大流。
图6－45
【解】虚拟一个发点和一个收点
T6.11－1
得到流量v ＝22的最小费用流，最小费用为271。求解过程参看第4章PPT 文档习题答案。
T6.11－13
最小费用最大流如下图，最大流量等于27，总费用等于351。
6.12如图6－43所示，（1）求解旅行售货员问题；（2）求解中国邮路问题。
图6-43
【解】（1）旅行售货员问题。
在C
由距离表C1，v 1到v 4，114356211去掉第1行第四列，d 41=∞，得到距离表C2。
距离表C2的每行每列都有零，H 2= H1={ v1, v4 , v 3 , v 5 , v 6 , v 2 , v 1}就是总距离最小的Hamilton 回路，C(H1) =35.2。 (2)中国邮路问题。虚拟一条边
取回路H 1＝{v 1，v 3，v 4}，C(H1)=9+5+3=17,C(v 1，v 3)=9> C(H1)/2，调整回路。
所有回路满足最短回路的准则，上图是最短的欧拉回路，其中边(v 1, v 4) 和(v 4, v 3) 各重复一次。
习题七
7.2(1)分别用节点法和箭线法绘制表7-16的项目网络图，并填写表中的紧前工序。 (2) 用箭线法绘制表7-17的项目网络图，并填写表中的紧后工序
表7-16
表7-17
【解】（1）箭线图：
节点图：
（2）箭线图：
7.3根据项目工序明细表7-18： （1）画出网络图。
（2）计算工序的最早开始、最迟开始时间和总时差。 （3）找出关键路线和关键工序。
表7-18
【解】(1)网络图
(2)网络参数
(3)关键路线：①→②→③→④→⑤→⑥→⑦；关键工序：A 、C 、D 、G ；完工期：48周。 7.4 表7-19给出了项目的工序明细表。
表7-19
（1）绘制项目网络图。
（2）在网络图上求工序的最早开始、最迟开始时间。
（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差。 （4）找出所有关键路线及对应的关键工序。 （5）求项目的完工期。 【解】(1)网络图
（2）工序最早开始、最迟开始时间
（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差
(4)关键路线及对应的关键工序
11→○12；关键工序：B,E,G,H,K,M 关键路线有两条，第一条：①→②→⑤→⑥→⑦→○
11→○12；关键工序：C,F,L,M 第二条：①→④→⑧→⑨→○
（5）项目的完工期为62天。
7.5已知项目各工序的三种估计时间如表7-20所示。
求：
表7-20 （1）绘制网络图并计算各工序的期望时间和方差。
（2）关键工序和关键路线。
（3）项目完工时间的期望值。
（4）假设完工期服从正态分布，项目在56小时内完工的概率
是多少。
（5）使完工的概率为0.98，最少需要多长时间。
【解】（1）网络图
(2)关键工序：A,C,E,F ；关键路线：①→②→④→⑤→⑥
(3) 项目完工时间的期望值：10.17+14.83+17.17+11.83
＝54(小时)
完工期的方差为0.25+0.25+0.6944+0.6944＝1.8889
σ1.37437
(4)X0=56，Φ
⎛X 0-μn ⎫⎛56-54⎫
=Φ⎪ ⎪＝Φ(1.4552）＝0.927
⎝1.37437⎭⎝σn ⎭
56天内完工的概率为0.927
(5) p=0.98，p {X ≤X 0) =Φ(Z ) =0.98, Z =2.05
X 0＝Z σ+μ=2.05⨯1.3744+54=56.82
要使完工期的概率达到0.98，则至少需要56.82小时。
7.6 表7-21给出了工序的正常、应急的时间和成本。
表7-21
（1（2）按应急时间计算完成项目的总成本和工期。
（3）按应急时间的项目完工期，调整计划使总成本最低。
（4）已知项目缩短1天额外获得奖金4万元，减少间接费用2.5万元，求总成本最低的项目完工期。 (1) 正常时间项目网络图 项目网络图
总成本为435，工期为64。 (2)应急时间项目网络图
总成本为560，工期为51。 (3)应急时间调整
工序C 、F 按正常时间施工，总成本为560-9-15＝536，完工期为51。 (4) 总成本最低的项目完工期
工序A 、E 分别缩短3天，总成本为435+15+12-6.5×7＝416.5，完工期为57。
7.7继续讨论表7-21。假设各工序在正常时间条件下需要的人员数分别为9、12、12、6、8、17、14人。 （1）画出时间坐标网络图
（2）按正常时间计算项目完工期，按期完工需要多少人。
（3）保证按期完工，怎样采取应急措施，使总成本最小又使得总人数最少，对计划进行系统优化分析。 【解】（1）正常时间的时间坐标网络图
(2) 按正常时间调整非关键工序的开工时间
(3)略，参看教材。
7.8用WinQSB 软件求解7.5。 7.9用WinQSB 软件求解7.6。
习题八
8.1 在设备负荷分配问题中，n =10，a =0.7，b =0.85，g =15，h =10，期初有设备1000台。试利用公式(8.7)确定10期的设备最优负荷方案。 【解】将教材中a 的下标i 去掉。
n -t
g -h
由公式∑a ≤≤∑a i 得
g (b -a ) i =0i =0
i
n -t -1
(g -h )/g (b -a ) ＝0.2222，a 0＋a 1＋a 2＝1+0.7＋0.49＝2.19＜2.222＜a 0+a 1＋a 2＋a 3＝2.533，n －t －1＝2，t =7，则
1~6年低负荷运行，7~10年为高负荷运行。各年年初投入设备数如下表。
1 2 3 4 5 6 7 8 9 10 年份
设备台数 1000 850 723 614 522 444 377 264 184.8 129
8.2如图8－4，求A 到F 的最短路线及最短距离。
【解】A 到F 的最短距离为13；最短路线 A→ B2→ C3 → D2 → E2 → F及A→C2 → D2 → E2 → F
8.3求解下列非线性规划
max Z =x 1x 2x 3⎨⎪⎩x j ≥0, j =1, 2,3max Z =x 1x 2x 3⎨⎪⎩x j ≥0, j =1, 2,3
22
min Z =x 1+x 2+x 3m a x Z =x 21+x 32+x 23
（3） ⎧x 1+x 2+x 3=10
(1) ⎧⎪x 1+x 2+x 3=C (2) ⎧x 1+x 2+x 3=C
⎨
⎩x 1, x 2, x 3≥0max Z =x 1x 2x 3
⎨
⎩x 1, x 2, x 3≥0
2
max Z =x 12+2x 1+2x 2+x 3⎨
⎩x 1, x 2, x 3≥0
(4) ⎪⎧x 1+4x 2+2x 3=10 (5) ⎪⎧2x 1+4x 2+x 3≤10 （6）⎧x 1+x 2+x 3=8
⎨
⎪⎩x j ≥0, j =1, 2,3
【解】（1）设s 3=x3 , s3+x2=s2，s 2+x1=s1=C
则有 x 3= s3 ，0≤x2≤s2，0≤x1≤s1=C 用逆推法，从后向前依次有
k ＝3， f 3(s 3) =max(x 3) =s 3 及最优解 x 3*=s3
x 3=s 3
k ＝2，f 2(s 2) =max [x 2f 3(x 3) =max [x 2(s 2-x 2)]=max h 2(s 2, x 2)
0≤x 2≤s 2
0≤x 2≤s 2
0≤x 2≤s 2
由
∂h 21
=s 2-2x 2=0, 则x 2＝s 2 ∂x 22
1∂2h 2
x =s 2为极大值点。 故 ＝－2
2∂x 2
121212
所以 f 2(s 2) =s 2-s 2=s 2 及最优解x 2*=s2
244
12
k =1时， f 1(s 1) =max[x 1f 2(s 2)]=max x 1(s 1-x 1) =max h 1(s 1, x 1) ，
0≤x 1≤s 10≤x 1≤s 10≤x 1≤s 14
1∂h 12*2
由1=(s 1-4s 1x 1+3x 1) =0，得x 1=s 1
3∂x 14
1113
s 1(s 1-s 1) 2=s 1 故f 1(s 1) =12327
已知知x 1 + x 2+ x 3 = C，因而按计算的顺序推算，可得各阶段的最优决策和最优解如下
113*
x 1=C ，f 1(C ) =c
327
11
C , f 2(s 2) =C 2 3911*
由s 3=s 2－x 2*=C/3，x 3=C , f 3(s 3) =C
33
由s 2=s 1－x 1*=2C/3，x 2=
*
最优解为：
11113
X =(C , C , C ) T ; z =C
33327
【解】（2）设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=C
则有 x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=C 用逆推法，从后向前依次有
k ＝3， f 3(s 3) =min(x ) 3=s 3及最优解 x 3*=s3
x 3=s 3
2
k ＝2，f 2(s 2) =min [x 2+f 3(x 3) =min [x 2+(s 2-x 2) ]=min h 2(s 2, x 2)
0≤x 2≤s 2
0≤x 2≤s 2
0≤x 2≤s 2
222
由
∂h 21
=4s 2-2x 2=0, 则x 2＝s 2 ∂x 22
∂2h 21
s 2为极小值点。 =4>0,故 x =22
2∂x 2
12*1
因而有f 2(s 2) =s 2, x 2=s 2
22
12+(s -k ＝1时， f 1(s 1) =min [x 11x ) 1=min h (s 1, x 1) 0≤x 1≤s 10≤x ≤1s 12
1∂h *
由1=1-s 1+x 1=0知 x 1=s 1-1, f 1(s 1) =s 1-
2∂x 1
得到最优解
1
1
X =(C -1, 1/2, 1/2) T ; z =C -
2
【解】(3) 设s 3=x3 , s3+x2=s2，s 2+x1=s1=10 则有 x 3= s3 ，0≤x2≤s2，0≤x1≤s1=10 用逆推法，从后向前依次有
k ＝3时，f 3(s 3) =max(x 3) =s 3 及最优解 x 3=s3
x 3=s 3
2
k ＝2时，f 2(s 2) =max [3x 2+(s 2-x 2) ]=max h 2(s 2, x 2)
0≤x 2≤s 2
0≤x 2≤s 2
2
∂h 23
=3-2s 2+2x 2=0时x 2=-+s 2 ∂x 22
∂2h 23 而 =2>0, 故x =-+s 2不是一个极大值点。 22
∂x 22
2
讨论端点：当 x 2=0时f 2(s 2) ＝s 2, x 2= s 2时f 2(s 2) =3s 2
如果s 2>3
2
时, f 2(s 2) =s 2
2
0≤x 1≤s 1
0≤x 1≤s 1
k ＝1时，f 1(s 1) =max[2x 1+(s 1-x 1) ]=max h 1(s 1, x 1)
∂h 1
=2-2s 1+2x 1=0时x 1=-1+s 1 ∂x 1
∂2h 1 =2>0, 故x 1=-1+s 2不是一个极大值点 2
∂x 1
同理有, x 1=0, f 1（s 1）= s 12= 100，x 1= s 1, f 1（s 1）= 2s 1= 20 (舍去) 得到最优解
X =(0,0,10); z =100
【解】(4) 设s 3=x 3 ,2s 3+4x 2=s2，s 2+x 1=s1=10 则有 x 3= s3 ，0≤x 2≤s2/4，0≤x 1≤s1=10 用逆推法，从后向前依次有 k ＝1，
f 3(s 3) =max(x 3) =s 3及最优解 x 3*=s3
x 3=s 3
1
m x x [2(s 2-0≤x 2≤s 42
∂h 11
由2=s 2-4x 2=0,则 x 2=s 2
8∂x 22
k ＝2， f 2(s 2) =
x 22=)
0≤x 224
m a h x 2, 2s 2( x
)
1∂2h 2
x =s 2为极大值点。 , 故 =-4
8∂x 2
2
s 2
则f 2(s 2) = 及最优解x 2*=s2/8
32
1
x 1(s 1-x 1) 2]=max h 1(s 1, x 1)
0≤x 1≤s 1320≤x 1≤s 1
13∂h 12*1f (s ) =s 1 1=，故 (s 1-4s 1x 1+3x 2) =0, x =s 11111
216∂x 1323
k ＝1， f 1(s 1) =max[ 得到最优解
X =(10/3, 5/6, 5/3) T ; z =125/27
【解】(5) 按问题中变量的个数分为三个阶段s 1 ，s 2 ，s 3 ，且s 3≤10，x 1，x 2，x 3为各阶段的决策变量，
各阶段指标函数相乘。
设s 1=2x 1 , s1+4x 2=s2，s 2+x 3=s3≤10，则有 x 1= s1/2 ，0≤x 2≤s2/4，0≤x 3≤s3=10 用顺推法，从前向后依次有 k ＝1， f 1(s 1) =max (x 1) =
x 1=s 1/2
s 1
及最优化解 x 1*=s1/2 2
x 42=)
0≤x 2≤s 2/4
1
m a x [x 2s (-20≤x 2≤s 2/42
1∂h 1*
由2=s 2-4x 2=0, 则 x 2=s 2
8∂x 22
k ＝2， f 2(s 2) =
m a h x 2s 2( x 2,
)
113∂2h 2
x =s f (s ) =s 2 , 故 为极大值点。则=-4
832∂x 2
1
x 3(s 3-x 3) 2]=max h 3(s 3, x 3) k ＝3， f 3(s 3) =max [
0≤x 3≤s 3320≤x 3≤s 3
∂h 1212*由3=(s 3-4s 3x 3+3x 3) =0, x 3=s 3 ∂x 3323
13
s 3，由于s 3≤10，则s 3=10时取最大值，x 3＝10/3，s 2=s3－x 3＝20/3，x 2＝5/6，s 1=s2－4x 2故f 3(s 3) =216
＝10/3，x 1＝5/3
得到最优解
X =(5/3, 5/6, 10/3) T ; z =125/27
【解】（6）设s 1=x1, s1+x2=s2，s 2+x3=s3=8
k ＝1，f 1(s 1) =max(x 1+2x 1) =s 1+2s 1 及最优化解 x 1*=s 1
x 1=s 1
2
2
2
2
k ＝2，f 2(s 2) =max [2x 2+(s 2-x 2) +2(s 2-x 2)]=max h 2(s 2, x 2)
0≤x 2≤s 2
0≤x 2≤s 2
∂h 2∂2h 2
=6x 2-2s 2-2, =6>0 2∂x 2∂x 2
x 2*=0时，f 2（s 2）=s22+2s2, x 2*= s2时，f 2（s 2）=2s22
22
故 f 2(s 2) =max{s 2+2s 2,2s 2}
k ＝3，
①当x 2*=0时， f 3(s 3) =max [x 3+(s 3-x 3) +2(s 3-x 3)]=max h 3(s 3, x 3) 同样得x 3*=0时
x 3*=s3时，f 3（s 3）=s3 所以， f 3（s 3）= s32+2s3=80 ②当x 2*= s2时，f 3（s 3）=max [x3+2（s 3-x 3）2] 同样得x 3*=0时
x 3*=s3时，f 3（s 3）=s3 =8 所以， f 3（s 3）= 2s32=128 最优解为
0≤x 3≤s 3
，f 3（s 3）=2s32 =128
2
0≤x 3≤s 3
，f 3（s 3）=s32+2s3
0≤x 3≤s 3
X =(0,8, 0); z =128
8.4用动态规划求解下列线性规划问题。
max Z =2x 1+4x 2⎧2x 1+x 2≤6⎪x ≤2⎪1⎨
⎪x 2≤4⎪⎩x 1, x 2≥0
【解】设s 2=x 2 ,s 2+2x 1=s1≤6
则有 0≤x2=s2≤4，0≤x1≤s1/2 用逆推法，从后向前依次有 f 2(s 2) =4s 2及最优解 x 2*=s2
f 1(s 1) =
0≤x 1≤s 1/2
m a x [x 21+f 2s (2=) ]
0≤x 1≤s 1/2
m a x s 1-[4 x 16]
0≤x 1≤s 1/2
由 s 2=s1－2x 1≤4， s 1≤6，取s 1＝6，
又1≤x 1≤2，取x 1＝1， 最优解
f 1(s 1) =max [24-6x 1]
f 1(s 1) =18
X =(1,4) T ; z =18
8.5 10吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表8.24所示。应该如何装载货物使总价值最大。
【解】设装载第I i m a x z =3x x x 1+42+53
⎧2x 1+3x 2+4x 3≤9
⎨
且为整数⎩x 1, x 2, x 3≥0
利用背包问题的前向动态规划计算，建立动态规划模型。由于决策变量离散型值，所以可用列表法求
解。当R=1时，
f 1(s 2) =max (3x 1) 。计算结果如下：
0≤x ≤s /2
当R=2时，f 2（s 3）=[4x2+f1（s 3-3x 2）]
0≤x 1≤s 2/4
当R=3时，f 3（9）=max [5x3+f2（9-4x 3）] （x 3为整数）=max [f2（9），5+f2（5），10+f2（1）]=max[13，
0≤x 3≤2
0≤x 2≤2
12，10]=13
8.6 有一辆货车载重量为10吨 ，用来装载货物A 、B 时成本分别为5元/吨和4元/吨。现在已知每吨
货物的运价与该货物的重量有如下线性关系：
A ：P 1=10-2x 1 ，B ：P 2=12-3x 2
其中x 1 、x 2 分别为货物A 、B 的重量。如果要求货物满载，A 和B 各装载多少，才能使总利润最大 【解】将原题改为A ：P 1=15-x 1 ，B ：P 2=18-2x 2 由题意可得各种货物利润函数为
2
g 1(x 1) =(1-5x 1-5x ) =1x 0-x 111
g 2(x 2) =(1-8x 22-4x 2) =1x 24-x 22
2
max z =(10x 1-x 12) +(14x 2-2x 2)
2
原问题的数学模型归结为
⎧x 1+x 2=10⎨
⎩x 1, x 2≥0
最优解：x 1 =6，x 2 =4；z ＝48
8.7 现有一面粉加工厂，每星期上五天班。生产成本和需求量见表8-25。
表8-25
面粉加工没有生产准备成本，每袋面粉的存储费为h k ＝0.5元/袋，按天交货，分别比较下列两种方案的最优性，求成本最小的方案。
（1）星期一早上和星期五晚的存储量为零，不允许缺货，仓库容量为S=40袋； （2）其它条件不变，星期一初存量为8。 【解】动态规划求解过程如下： 阶段k ：日期，k =1,2,…,6
状态变量s k ：第k 天早上（发货以前）的冷库存量 决策变量x k ：第k 天的生产量 状态转移方程：s k +1=s k +xk －d k ；
决策允许集合：D k (s k ) =x k x k ≥0, 0≤s k +x k -d k ≤40 阶段指标： v k (s k ，x k )=c k x k +0.5s k 终端条件：f 6(s 6)=0, s 6=0； 递推方程：
{}
f k (x k ) =min {v k (s k , x k ) +f k +1(s k +1) }
x k ∈D k (s k )
=min
x k ∈D k (s k
{v k (s k , x k ) +f k +1(s k +x k -d k ) })
当k =5时，因为s 6=0，有s 6=s 5+x 5-d 5=0, 由于s 5≤15，
x 5=15-s 5,
f 5(s 5) =min {10x 5+0.5s 5}
x 5∈15-s 5
*
5
=150-9.5s 5, x =15-s 5
k =4时，0≤s 5≤15，0≤s 4+x 4-30≤15, 有30-s 4≤x 4≤45-s 4，
f 4(s 4) =min {12x 4+0.5s 4+f 5(s 5)}
=min
x 4∈D 4(s 4)
*
⎧-11.5s 4+510s 4≤30, x 4=30-s 4=⎨*
⎩-9s 4+43540≤s 4≤30, x 4=0
k =3时，当0≤s 4≤30时，0≤s 3+x 3-25≤30，得
x 4∈D 4(s 4)
{2.5x 4-9s 4+435}
运筹学 习题答案 31
25-s 3≤x 3≤55-s 3
有D 3(s 3) =x 3max[0.25-s 3]≤x 3≤55-s 3
{}
f 3(s 3) =min
3
3
{9x 3+0.5s 3+f 4(s 4)}
=min {9x 3+0.5s 3-11.5s 4+510}x ∈D (s )
=min {-2.5x 3-11s 3+797.5}x ∈D (s )
x 3∈D 3(s 3)
3
3
3
3
=-8.5s 3+660
当30≤s 4≤40时，x 4=0,30≤s 3+x 3-25≤40，有
*
取上界：x 3=55-s 3
D 3(s 3) ={x 355-s 3≤x 3≤65-s 3}
f 3(1)(s 3) =min
=min
3
3
{9x 3+0.5s 3-9s 4+435}*
=min {-8.5x 3+210}, x 3取任意值x ∈D (s )
x 3∈D 3(s 3)
3
x 3∈D 3(s 3)
{9x 3+0.5s 3+f 4(s 4)}
显然此决策不可行。
当k =2时，由0≤s 4≤30,0≤s 3≤25，0≤s 2+x 2-20≤25, x 2的决策允许集合为
D 2(s 2) ={x 2max[0,20-s 2]≤x 2≤45-s 2}
f 2(s 2) =min
2
2
{6x 2+0.5s 2+660-8.5s 2}
=min {-2.5x 2-8s 2+830}x ∈D (s )
x 2∈D 2(s 2)
2
*
取上界：x 2=45-s 2
=-5.5s 2+717.5
当k =1时，由0≤s 2≤20，0≤s 1+x 1-10≤20，则x 1的决策允许集合为
D 1(s 1) ={x 1max[0,10-s 1]≤x 1≤30-s 1} f 1(s 1) =min {8x 1+0.5s 1+717.5-5.5s 2}
=min {2.5x 1-5s 1+772.5}x 1∈D 1(s 1)
=797.5
因为s 1=0, x 1=10,
x 1∈D 1(s 1)
s 2=10-10=0, x 2=45-s 2=45, s 3=s 2+x 2-20=25, x 3=55-s 3=30, s 4=s 3+x 3-25=30, x 4=30-s 4=0, s 5=s 4+x 4-30=0, x 5=15-s 5=-15.
(2)期初存储量s 1=8, 与前面计算相似，x 1=2. Min Z=772.5+2.5x1-5s 1=737.5 则总成本最小的方案是第二种。
8.8 某企业计划委派10个推销员到4个地区推销产品，每个地区分配1~4个推销员。各地区月收益（单位：10万元）与推销员人数的关系如表8－26所示。
表8-26
32
企业如何分配4个地区的推销人员使月总收益最大。
【解】设x k 为第k 种货物的运载重量，该问题的静态规划模型为
max Z =v 1(x 1) +v 2(x 2) +v 3(x 3) +v 4(x 4) ⎧⎪x 1+x 2+x 3+x 4=8⎨⎪⎩x j =0, 2, 4,6,8
利用图表法：
故最优解为x 1=0, x 2=0, x 3=x 4=4
则 max Z=44
8.9 有一个车队总共有车辆100辆，分别送两批货物去A 、B 两地，运到A 地去的利润与车辆数目满足关系100x ，x 为车辆数，车辆抛锚率为30%，运到B 地的利润与车辆数y 关系为80y ，车辆抛锚率为20%，总共往返3轮。请设计使总利润最高的车辆分配方案。 【解】动态规划求解过程如下。
阶段k ：共往数k=1,2,3,4，k=1表示第一趟初，k =4表示第三趟末（即第六年初）；
状态变量s k ：第k 趟初完好的车辆数（k =1,2,3,4），也是第k －1趟末完好的车辆数，其中s 4表示第三趟末的完好车辆数。
决策变量x k ：第k 年初投入高负荷运行的机器数；
状态转移方程：s k +1=0.7x k +0.8(s k －x k ) 决策允许集合：D k (s k )={x k |0≤x k ≤s k } 阶段指标：v k (s k ，x k )=100x k +80(s k －x k ) 终端条件：f 4(s 4)=0 递推方程：
f k (s k ) =max
0≤x k ≤s k
x k ∈D k (s k )
{v k (s k , x k ) +f k +1(s k +1) }
=max {100x k +80(s k -x k ) +f k +1[0.7x k +0.8(s k -x k ) ]}
f k (x k ) 表示第k 趟初分配x k 辆车到A 地，到第3趟末的最大总运价为
f 3(s 3) =max {100x 3+80(s 3-x 3) +f 4(s 4) }
0≤x 3≤s 3
=max{20x 3+80s 3}=100s 3
0≤x 3≤s 3
x =s 3最优
*3
f 2(s 2) =max {100x 2+80(s 2-x 2) +f 3(s 3) }
0≤x 2≤s 2
=max {10x 2+160s 2}=170s 2
0≤x 2≤s 2
*x 2=s 2最优
f 1(s 1) =max {100x 1+80(s 1-x 1) +f 2(s 2) }
0≤x 1≤s 1
=max{3x 1+216s 1}=219s 1
0≤x 1≤s 1
x =s 1最优
*1
因为s 1=100，最大总运价f 1(s 1)=21900元
8.10 系统可靠性问题。一个工作系统由n 个部件串联组成，见图8-5。只要有一个部件失灵，整个系统就不能工作。为提高系统的可靠性，可以增加部件的备用件。例如，用5个部件1并联起来作为一个部件与部件2串联，如果其中一个部件失灵其它4个部件仍能正常工作。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。
图8-5
假设部件i (i =1,2, , n ) 上装有x i 个备用件，该部件正常工作的概率为p i (x i ) 。设装一个部件i 的备用件的成本为c i ，要求备件的总费用为C 。那么该问题模型为：
n
max P =∏p i (x i )
i =1
⎧n （8.8）
c x ≤C ∑i i ⎪⎨i =1
⎪x ≥0并且为整数，i =1, 2, , n ⎩j
同理，如果一个复杂的工作系统由n 个部件并联组成的，只有当n 个部件都失灵，整个系统就不能工作，见图8-6。
图8-6
假设p i (x i ) 为第i 个部件失灵的概率，为提高系统的可靠性，可以增加部件的备用件。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。系统的可靠性为1-则该问题的数学模型归结为
∏p (x ) ，
i
i
i =1
n
min P =∏p i (x i )
i =1
n
（8.9） ⎧n
c x ≤C ⎪∑i i ⎨i =1
⎪x ≥0并且为整数，i =1, 2, , n ⎩j
利用式(8.8)或（8.9）求解下列问题。
（1）工厂设计的一种电子设备，其中有一系统由三个电子元件串联组成。已知这三个元件的价格和可靠性如表8-27所示，要求在设计中所使用元件的费用不超过200元，试问应如何设计使设备的可靠性达到最大。
表8-27
（
2场调查和预测得出，如表8-28所示，试求在哪一周以什么价格购入，使其采购价格的期望最小，并求出期望值。
表8-28
max Z =(1-0.05x 1)(1-0.2x 2)(1-0.4x 3) ⎧40x 1+35x 2+20x 3≤200⎨
⎩x 1, x 2, x 3≥0并且为整数
最优解X=(1，2，4) ；可靠性Z=0.888653，总费用190。 （2）