运筹学第五、六、七、八章答案

5.2 用元素差额法直接给出表5-53及表5-54下列两个运输问题的近似最优解．表5-53 B1 B2 B3 B4 B5 Ai A1 19 16 10 21 9 18 A2 14 13 5 24 7 30 A3 25 30 20 11 23 10 A4 7 8 6 10 4 42 Bj 15 25 35 20 5 表5-54 B1 B2 B3 B4 Ai A1 5 3 8 6 16 A2 10 7 12 15 24 A3 17 4 8 9 30 Bj 20 25 10 15 【解】表5-53。Z=824 表5-54 Z=495 5.3 求表5-55及表5-56所示运输问题的最优方案．（1）用闭回路法求检验数（表5-55）
表5-55 B1 B2 B3 B4 Ai A1 10 5 2 3 70 A2 4 3 1 2 80 A3 5 6 4 4 30 bj 60 60 40 20 （2）用位势法求检验数（表5-56）
表5-56 B1 B2 B3 B4 Ai A1 9 15 4 8 10 A2 3 1 7 6 30 A3 2 10 13 4 20 A4 4 5 8 3 43 bj 20 15 50 15 【解】（1）
(2) 5.4 求下列运输问题的最优解（1）C1目标函数求最小值；
（2）C2目标函数求最大值 15 45 20 40 60 30 50 40 (3)目标函数最小值,B1的需求为30≤b1≤50, B2的需求为40，B3的需求为20≤b3≤60,A1不可达A4 ，B4的需求为30．【解】（1）
（2）
（3）先化为平衡表　 B11 B12 B2 B31 B32 B4 ai A1 4 4 9 7 7 M 70 A2 6 6 5 3 3 2 20 A3 8 8 5 9 9 10 50 A4 M 0 M M 0 M 40 bj 30 20 40 20 40 30 180 最优解：
5.5（1）建立数学模型设xij(I=1,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则 (2)写平衡运价表将第一、二等式两边同除以40，加入松驰变量x13,x23和x33将不等式化为等式，则平衡表为：
B1 B2 B3 ai 甲乙丙 80 60 50 65 50 40 0 0 0 5 10 15 bj 10 15 5 为了平衡表简单，故表中运价没有乘以40，最优解不变（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月交货的台数，则此生产计划问题的数学模型为（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量为30。

1 2 3 4 5 ai 1 2 3 4 1 M M M 1.15 1.25 M M 1.3 1.4 0.87 M 1.45 1.55 1.02 0.98 0 0 0 0 65 65 65 65 bj 50 40 60 80 30 (3)用表上作业法，最优生产方案如下表：
1 2 3 4 5 ai 1 2 3 4 50 15 25 60 10 5 65 30 65 65 65 65 Bi 50 40 60 80 30 上表表明：一月份生产65台，当月交货50台；
二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；
三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用Z=235万元。

5.7 假设在例5.15中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案．【解】将表5-35所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000．　产品1 产品2 产品3 产品4 工厂1 58 138 540 1040 工厂2 75 100 450 920 工厂3 65 140 510 1000 工厂4 82 110 600 1120 用匈牙利法得到最优表第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2；

总成本 Z＝1000×(58＋920＋510＋110)＝1598000 注：结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。

5.8 求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作．（1）
【解】最优解（2）
【解】虚拟一个人，其效率取4人中最好的，构造效率表为　 1 2 3 4 5 甲 26 38 41 52 27 乙 25 33 44 59 21 丙 20 30 47 56 25 丁 22 31 45 53 20 戊 20 30 41 52 20 最优解：甲～戊完成工作的顺序为3、5、1、2、4，最优值Z=165 最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。

5.9 求解下列最大值的指派问题：
（1）
【解】最优解（2）
【解】最优解第5人不安排工作。

表5-58 成绩表(分钟) 游泳自行车长跑登山甲 20 43 33 29 乙 15 33 28 26 丙 18 42 38 29 丁 19 44 32 27 戊 17 34 30 28 5.10 学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-58所示．如何从中选拔一个接力队，使预期的比赛成绩最好．【解】设xij为第i人参加第j项目的状态，则数学模型为接力队最优组合乙长跑丙游泳丁登山戊自行车甲淘汰。预期时间为107分钟。

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

【解】边[i，j]的长度记为cij，设数学模型为：
图6－40 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－43 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是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离(km)。现要在6个工厂中选一个建装配车间。

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

（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨，运价为2元/吨公里。应选那个工厂使总运费最小。

【解】(1)利用习题6.8表L3的结果　 v1 v2 v3 v4 v5 v6 Max v1 0 8.8 8.6 5.6 8 6 8.8 v2 8.8 0 8 5 13 4 12.8 v3 8.6 8 0 3 4.8 12 12 v4 5.6 5 3 0 7.8 9 9 v5 8 13 4.8 7.8 0 9 12.8 v6 6 4 12 9 9 0 12 选第1个工厂最好。

(2)计算单件产品的运价，见下表最后一行。计算单件产品的运费，见下表最后一列。

　 v1 v2 v3 v4 v5 v6 单件产品运费 v1 0 8.8 8.6 5.6 8 6 84.88 v2 8.8 0 8 5 13 4 89.16 v3 8.6 8 0 3 4.8 12 82.16 v4 5.6 5 3 0 7.8 9 71.96 v5 8 13 4.8 7.8 0 9 81.92 v6 6 4 12 9 9 0 82.2 运价 1 1.2 1.6 2.6 3.2 3.4 选第4个工厂最好。

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

【解】给出初始流如下第一轮标号：得到一条增广链，调整量等于5，如下图所示调整流量。

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

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

第四轮标号：不存在增广链，最大流量等于45，如下图所示取，最小截集{(3,7),(4,7),(6,9),(8,10)，最小截量等于45。

6.11 将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2，中途有2个加压站B1、B2，天然气管线如图6－45所示。输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上(cij, 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 　 1 2 3 4 5 6 1 ∞ 8.8 9 5.6 8 6 2 8.8 ∞ 10 5 ∞ 4 3 9 10 ∞ 3 4.8 14 4 5.6 5 3 ∞ 12 ∞ 5 8 ∞ 4.8 12 ∞ 9 6 6 4 14 ∞ 9 ∞ 在C中行列分别减除对应行列中的最小数，得到距离表C1。

距离表C1 　 1 2 3 4 5 6 1 ∞ 3.2 3.4 0 0.6 0.4 2 2.8 ∞ 6 1 ∞ 0 3 4 7 ∞ 0 0 11 4 0.6 2 0 ∞ 7.2 ∞ 5 1.2 ∞ 0 7.2 ∞ 9 6 0 0 10 ∞ 3.2 ∞ 由距离表C1，v1到v4， H1={ v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1}, C(H1)=5.6+3+4.8+9+4+8.8=35.2 去掉第1行第四列，d41=∞，得到距离表C2。

得到距离表C2 　 1 2 3 5 6 2 2.8 ∞ 6 ∞ 0 3 4 7 ∞ 0 11 4 ∞ 2 0 7.2 ∞ 5 1.2 ∞ 0 ∞ 9 6 0 0 10 3.2 ∞ 距离表C2的每行每列都有零，H2= H1={ v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1}就是总距离最小的Hamilton回路，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)各重复一次。

习题七 7.2(1)分别用节点法和箭线法绘制表7-16的项目网络图，并填写表中的紧前工序。

(2) 用箭线法绘制表7-17的项目网络图，并填写表中的紧后工序表7-16 工序 A B C D E F G 紧前工序－－－ A C A F、D、B、E 紧后工序 D,E　 G　 E　 G　 G　 G　－表7-17 工序 A B C D E F G H I J K L M 紧前工序 - - - B B A,B B D,G C,E,F,H D,G C,E I J,K,L 紧后工序 F E,D,F,G　 I,K　 H,J　 I,K　 I　 H,J　 I　 L　 M　 M　 M　－　【解】（1）箭线图：
节点图：
（2）箭线图：
7.3根据项目工序明细表7-18：
（1）画出网络图。

（2）计算工序的最早开始、最迟开始时间和总时差。

（3）找出关键路线和关键工序。

表7-18 工序 A B C D E F G 紧前工序 - A A B,C C D,E D,E 工序时间（周）
9 6 12 19 6 7 8 【解】(1)网络图 (2)网络参数工序 A B C D E F G 最早开始 0 9 9 21 21 40 40 最迟开始 0 15 9 21 34 41 40 总时差 0 6 0 0 13 1 0 (3)关键路线：①→②→③→④→⑤→⑥→⑦；
关键工序：A、C、D、G；
完工期：48周。

7.4 表7-19给出了项目的工序明细表。

表7-19 工序 A B C D E F G H I J K L M N 紧前工序 - - - A,B B B,C E D,G E E H F,J I,K,L F,J,L 工序时间(天) 8 5 7 12 8 17 16 8 14 5 10 23 15 12 （1）绘制项目网络图。

（2）在网络图上求工序的最早开始、最迟开始时间。

（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差。

（4）找出所有关键路线及对应的关键工序。

（5）求项目的完工期。

【解】(1)网络图（2）工序最早开始、最迟开始时间（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差工序 t TES TEF TLS TLF 总时差S 自由时差F A 8 0 8 9 17 9 0 B 5 0 5 0 5 0 0 C 7 0 7 7 7 0 0 D 12 8 20 17 29 9 9 E 8 5 13 5 13 0 0 F 17 7 24 7 24 0 0 G 16 13 29 13 29 0 0 H 8 29 37 29 37 0 0 I 14 13 27 33 47 20 20 J 5 13 18 19 24 6 6 K 10 37 47 37 47 0 0 L 23 24 47 24 47 0 0 M 15 47 62 47 62 0 0 N 12 47 59 50 62 3 3 (4)关键路线及对应的关键工序关键路线有两条，第一条：①→②→⑤→⑥→⑦→→；
关键工序：B,E,G,H,K,M 第二条：①→④→⑧→⑨→→；
关键工序：C,F,L,M （5）项目的完工期为62天。

7.5已知项目各工序的三种估计时间如表7-20所示。

求：
表7-20 工序紧前工序工序的三种时间（小时）
a m b A － 9 10 12 B A 6 8 10 C A 13 15 16 D B 8 9 11 E B,C 15 17 20 F D,E 9 12 14 （1）绘制网络图并计算各工序的期望时间和方差。

（2）关键工序和关键路线。

（3）项目完工时间的期望值。

（4）假设完工期服从正态分布，项目在56小时内完工的概率是多少。

（5）使完工的概率为0.98，最少需要多长时间。

【解】（1）网络图工序紧前工序工序的三种时间（小时）
期望值方差 a m b A － 9 10 12 10.17 0.25 B A 6 8 10 8 0.4444 C A 13 15 16 14.83 0.25 D B 8 9 11 9.167 0.25 E B,C 15 17 20 17.17 0.6944 F D,E 9 12 14 11.83 0.6944 (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 (4)X0=56， 56天内完工的概率为0.927 (5) p=0.98，要使完工期的概率达到0.98，则至少需要56.82小时。

7.6 表7-21给出了工序的正常、应急的时间和成本。

表7-21 工序紧前工序时间(天) 成本时间的最大缩量(天) 应急增加成本（万元/天）
正常应急正常应急 A 15 12 50 65 3 5 B A 12 10 100 120 2 10 C A 7 4 80 89 3 3 D B,C 13 11 60 90 2 15 E D 14 10 40 52 4 3 F C 16 13 45 60 3 5 G E,F 10 8 60 84 2 12 （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去掉。

由公式得 (g-h)/g(b-a)＝0.2222，a0＋a1＋a2＝1+0.7＋0.49＝2.19＜2.222＜a0+a1＋a2＋a3＝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求解下列非线性规划 (1) (2) （3）
(4) (5) （6）
【解】（1）设s3=x3 , s3+x2=s2，s2+x1=s1=C 则有 x3= s3 ，0≤x2≤s2，0≤x1≤s1=C 用逆推法，从后向前依次有 k＝3，及最优解 x3*=s3 k＝2，由故为极大值点。

所以及最优解x2*=s2 k=1时，，由，得故已知知x1 + x2+ x3 = C，因而按计算的顺序推算，可得各阶段的最优决策和最优解如下，由s2=s1－x1*=2C/3，由s3=s2－x2*=C/3，最优解为：
【解】（2）设s3=x3 , s3+x2=s2，s2+x1=s1=C 则有 x3= s3 ，0≤x2≤s2，0≤x1≤s1=C 用逆推法，从后向前依次有 k＝3，及最优解 x3*=s3 k＝2，由 =4>0,故 x2=为极小值点。

因而有 k＝1时，由知得到最优解【解】(3) 设s3=x3 , s3+x2=s2，s2+x1=s1=10 则有 x3= s3 ，0≤x2≤s2，0≤x1≤s1=10 用逆推法，从后向前依次有 k＝3时，及最优解 x3=s3 k＝2时，而。

讨论端点：当 x2=0时, x2= s2时如果s2>3时, k＝1时，同理有, x1=0, f1（s1）= s12= 100，x1= s1, f1（s1）= 2s1= 20 (舍去) 得到最优解【解】(4) 设s3=x3 ,2s3+4x2=s2，s2+x1=s1=10 则有 x3= s3 ，0≤x2≤s2/4，0≤x1≤s1=10 用逆推法，从后向前依次有 k＝1，及最优解 x3*=s3 k＝2，由=s2-4x2=0,则 x2=s2 ,故为极大值点。

则及最优解x2*=s2/8 k＝1，，故得到最优解【解】(5) 按问题中变量的个数分为三个阶段s1 ，s2 ，s3 ，且s3≤10，x1，x2，x3为各阶段的决策变量，各阶段指标函数相乘。

设s1=2x1 , s1+4x2=s2，s2+x3=s3≤10，则有 x1= s1/2 ，0≤x2≤s2/4，0≤x3≤s3=10 用顺推法，从前向后依次有 k＝1，及最优化解 x1*=s1/2 k＝2，由,则 ,故为极大值点。则 k＝3，由故，由于s3≤10，则s3=10时取最大值，x3＝10/3，s2=s3－x3＝20/3，x2＝5/6，s1=s2－4x2＝10/3，x1＝5/3 得到最优解【解】（6）设s1=x1, s1+x2=s2，s2+x3=s3=8 k＝1，及最优化解 x1*=s1 k＝2， x2*=0时，f2（s2）=s22+2s2, x2*= s2时，f2（s2）=2s22 故 k＝3， ①当x2*=0时，同样得x3*=0时，f3（s3）=s32+2s3 x3*=s3时，f3（s3）=s3 所以， f3（s3）= s32+2s3=80 ②当x2*= s2时，f3（s3）=[x3+2（s3-x3）2] 同样得x3*=0时，f3（s3）=2s32 =128 x3*=s3时，f3（s3）=s3 =8 所以， f3（s3）= 2s32=128 最优解为 8.4用动态规划求解下列线性规划问题。

【解】设s2=x2 ,s2+2x1=s1≤6 则有 0≤x2=s2≤4，0≤x1≤s1/2 用逆推法，从后向前依次有及最优解 x2*=s2 由 s2=s1－2x1≤4， s1≤6，取s1＝6，又1≤x1≤2，取x1＝1，最优解 8.5 10吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表8.24所示。应该如何装载货物使总价值最大。

表8.24 货物编号 1 2 3 单位加工时间 2 3 4 单位价值 3 4 5 【解】设装载第I种货物的件数为xi（ i =1,2,3）则问题可表为：
利用背包问题的前向动态规划计算，建立动态规划模型。由于决策变量离散型值，所以可用列表法求解。当R=1时，。计算结果如下：
s2 0 1 2 3 4 5 6 7 8 9 f1（s2）
0 0 3 3 6 6 9 9 12 12 x1* 0 0 1 1 2 2 3 3 4 4 当R=2时，f2（s3）=[4x2+f1（s3-3x2）] 计算结果如下：
s3 0 1 2 3 4 5 6 7 8 9 x2 0 0 0 0 1 0 1 0 1 0 1 2 0 1 2 0 1 2 0 1 2 3 C2+f2 0 0 3 3 4 6 4 6 7 9 7 8 9 10 8 12 10 11 12 13 11 12 f2（s3）
0 0 3 4 6 7 9 10 12 13 x2* 0 0 0 1 0 1 0 1 0 1 当R=3时，f3（9）=[5x3+f2（9-4x3）] （x3为整数）=[f2（9），5+f2（5），10+f2（1）]=max[13，12，10]=13 8.6 有一辆货车载重量为10吨，用来装载货物A、B时成本分别为5元/吨和4元/吨。现在已知每吨货物的运价与该货物的重量有如下线性关系：
A：P1=10-2x1 ，B：P2=12-3x2 其中x1 、x2 分别为货物A、B的重量。如果要求货物满载，A和B各装载多少，才能使总利润最大【解】将原题改为A：P1=15-x1 ，B：P2=18-2x2 由题意可得各种货物利润函数为原问题的数学模型归结为最优解：x1 =6，x2 =4；
z＝48 8.7 现有一面粉加工厂，每星期上五天班。生产成本和需求量见表8-25。

表8-25 星期(k) 1 2 3 4 5 需求量(dk) 单位：袋 10 20 25 30 30 每袋生产成本(ck) 8 6 9 12 10 面粉加工没有生产准备成本，每袋面粉的存储费为hk＝0.5元/袋，按天交货，分别比较下列两种方案的最优性，求成本最小的方案。

（1）星期一早上和星期五晚的存储量为零，不允许缺货，仓库容量为S=40袋；

（2）其它条件不变，星期一初存量为8。

【解】动态规划求解过程如下：
阶段k：日期，k=1,2,…,6 状态变量sk：第k天早上（发货以前）的冷库存量决策变量xk：第k天的生产量状态转移方程：sk+1=sk+xk－dk；

决策允许集合：
阶段指标：
vk(sk，xk)=ckxk+0.5sk 终端条件：f6(s6)=0, s6=0；

递推方程：
当k=5时，因为s6=0，有由于s5≤15， k=4时，， k=3时，当0≤s4≤30时，，得有当30≤s4≤40时，，有显然此决策不可行。

当k=2时，由x2的决策允许集合为当k=1时，由，则x1的决策允许集合为因为 (2)期初存储量s1=8, 与前面计算相似，x1=2. Min Z=772.5+2.5x1-5s1=737.5 则总成本最小的方案是第二种。

8.8 某企业计划委派10个推销员到4个地区推销产品，每个地区分配1~4个推销员。各地区月收益（单位：10万元）与推销员人数的关系如表8－26所示。

表8-26 地区人数 A B C D 1 4 5 6 7 2 7 12 20 24 3 18 23 23 26 4 24 24 27 30 企业如何分配4个地区的推销人员使月总收益最大。

【解】设xk为第k种货物的运载重量，该问题的静态规划模型为利用图表法：
X1 X2 X3 X4 X5 0 0 0 8 30 0 0 2 6 32 0 2 0 6 31 0 0 8 0 27 0 8 0 0 24 0 0 6 2 30 0 2 6 0 28 0 2 2 4 35 0 4 0 4 36 0 0 4 4 44 0 2 4 2 32 0 4 4 0 32 0 4 2 2 25 2 0 0 6 30 2 0 6 0 27 2 6 0 0 27 2 2 0 4 33 2 0 2 4 34 2 2 4 0 29 2 0 4 2 31 2 4 2 0 22 2 4 0 2 23 4 0 0 4 31 4 0 4 0 27 4 4 0 0 19 4 2 0 2 19 4 0 2 2 20 4 2 2 0 18 6 0 0 2 25 6 0 2 0 24 6 2 0 0 23 8 0 0 0 24 故最优解为则 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表示第三趟末（即第六年初）；

状态变量sk：第k趟初完好的车辆数（k=1,2,3,4），也是第k－1趟末完好的车辆数，其中s4表示第三趟末的完好车辆数。

决策变量xk：第k年初投入高负荷运行的机器数；

状态转移方程：sk+1=0.7xk+0.8(sk－xk) 决策允许集合：Dk(sk)={xk|0£xk£sk} 阶段指标：vk(sk，xk)=100xk+80(sk－xk) 终端条件：f4(s4)=0 递推方程：
fk(xk)表示第k趟初分配xk辆车到A地，到第3趟末的最大总运价为因为s1=100，最大总运价f1(s1)=21900元 8.10 系统可靠性问题。一个工作系统由个部件串联组成，见图8-5。只要有一个部件失灵，整个系统就不能工作。为提高系统的可靠性，可以增加部件的备用件。例如，用5个部件1并联起来作为一个部件与部件2串联，如果其中一个部件失灵其它4个部件仍能正常工作。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。

部件1 部件2 …… 部件n 图8-5 假设部件上装有个备用件，该部件正常工作的概率为。设装一个部件的备用件的成本为，要求备件的总费用为C。那么该问题模型为：
（8.8）
同理，如果一个复杂的工作系统由个部件并联组成的，只有当个部件都失灵，整个系统就不能工作，见图8-6。

图8-6 假设为第个部件失灵的概率，为提高系统的可靠性，可以增加部件的备用件。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。系统的可靠性为，则该问题的数学模型归结为（8.9）
利用式(8.8)或（8.9）求解下列问题。

（1）工厂设计的一种电子设备，其中有一系统由三个电子元件串联组成。已知这三个元件的价格和可靠性如表8-27所示，要求在设计中所使用元件的费用不超过200元，试问应如何设计使设备的可靠性达到最大。

表8-27 元件单价可靠性 1 40 0.95 2 35 0.8 3 20 0.6 （2）公司计划在4周内必须采购一批原料，而估计在未来的4周内价格有波动，其浮动价格和概率根据市场调查和预测得出，如表8-28所示，试求在哪一周以什么价格购入，使其采购价格的期望最小，并求出期望值。

表8-28 周单价概率 1 550 0．1 2 650 0．25 3 800 0．3 4 900 0．35 【解】（1）数学模型为最优解X=(1，2，4)；
可靠性Z=0.888653，总费用190。

（2）