第6章训练题

一．基本技能训练

1．已知网络图各段路线所需费用如下图所示，试选择从A到B线的最小费用路线，并计算其总的费用。图中A线和B线上的数字分别代表相应点的有关费用。 2 3 1 4 2 5 7 1 ● ● ●

2 5 6 1 3 2

● 3 ● 3 3 2 1 4 3 5 ● ● ● 2 4 3 1 2 6 2 1 A线 B线 1．最小费用路线有两条：一条是从A线最上方费用为2的点到B线最上方费用为3的点止。其总费用为17。

用动态规划方法求解2题至13题。

23222．maxz?x1x2x3 3．maxz?5x1?x1?9x2?2x2

x1?x2?x3?6xi?0,i?1,2,3 x1?x2?5xi?0,i?1,2

224．minz?3x12?4x2 5．maxz?5x1?10x2?3x3?6x4 ?x3x1x2x3?9xi?0,i?1,2,3x1?x2?3 x1?4x2?5x3?10x4?11xi?0且为整数,i?1,2,3,4x1?x2?x3?x4?10

22226．maxz?3x1(2-x1)?2x2(2?x2) 7．maxz?x1?x2?x3?x4

xi?0且为整数,i?1,2xi?0且为整数,i?1,2,3,428．maxz?4x1?5x2?8x3 9．maxz?7x12?6x1?5x2

x1?x2?x3?10x1?2x2?10x1?3x2?6x3?13 x1?3x2?9 x1?4x3?11xi?0且为整数,i?1,2,32x1?x2?10x3?bxi?0,i?1,2,3xi?0,i?1,2223210．maxz?8x1?4x2?x3 11．maxz?ax1?x2x3?x2x4

x1?x2?x3?x4＝10 xi?0,i?1,2,3,4

b为整数a为实数2．最优解为：x1?2,x2?1,x3?3;zmax?108。

59131。 ,x2?;zmax?2484．最优解为：x1?1.82,x2?1.574,x3?3.147;zmax?29.751。

3．最优解为：x1?5．最优解为：x1?9.6,x2?0.2,;zmax?702.92。

bb3;zmax?6．最优解为：当b?4000时，x1?0,x2?0,x3?。 1010002 当0?b?4000时，x1?0,x2?b,x3?0;zmax?4b。

1

7．最优解为：当a?时，x1?10,x2?0,x3?0,x4?0;zmax?100a。

411 当??a?时，有两个最优决策：

44x1?0,x2?5,x3?5,x4?0;zmax?25

或x1?0,x2?5,x3?0,x4?5;zmax?25

1时，也有两个最优决策： 41020a20a100x1?,x2?,x3?,x4?0;zmax?a

4a?14a?14a?14a?11020a20a100或x1?,x2?,x3?0,x4?;zmax?a

4a?14a?14a?14a?18．最优解为：x1?11,x2?0,x3?0,x4?0;zmax?55

当a??9．最优解为：x1?1,x2?1;zmax?3

10．有六个最优决策：x1?2,x2?3,x3?3,x4?2;zmin?26

x1?3,x2?2,x3?3,x4?2;zmin?26 x1?3,x2?3,x3?2,x4?2;zmin?26 x1?2,x2?2,x3?3,x4?3;zmin?26 x1?2,x2?3,x3?2,x4?3;zmin?26 x1?3,x2?2,x3?2,x4?3;zmin?26

11．最优解为：x1?9,x2?1,x3?0;zmax?41 12．maxz?8x1?7x2

2x1?x2?85x1?2x2?15

x1,x2为非负整数?12．最优解为x1?0，x2?7，z?49。

??13． maxz?3x1?5x2

x1

?42x2?12

3x1?2x2?18x1,x2?0

*13．x1?2，x2?6；z?36。

**14．如图所示，在A处有一油库，E为一港口。今需从A铺设输油管道到E处，拟在B1,B2,B3之一，C1,C2,C3之一以及D1,D2之一各建一个中间站，各站之间的管道走向如图所示，连线旁的数字表示两站间的管道长。现要求选择3个合适的中间站，使A到E的总输油管道长度最短。

10 B1 C1 9 8 7 15 13 D1 9 7 14 A 5 B2 6 C2 E 9 12 11 12 16 15 D2 11 B 7 C 6 33 始点站 第一站 第二站 第三站 终点站

A 1 2 3 4 E

14．管道最短长度为32，路线为A?B2?C2?D1?E。

15．石油输送管道铺设最优方案的选择问题：考虑如下网络图，设A地为出发地，E为目的地，B、C、D分别为三个必须建立油泵加压站的地区，其中的B1，B2，B3；C1，C2，C3；D1，D2，分别为可供选择的各站站位。下图中的线段表示管道可铺设的位置，线段旁的数字表示了铺设这些管线所需的费用。问如何铺设管道才能使总费用最小？ 7 B1 1 C1 4 4 6 2 D1 3

3 6 E 4 2 B A C 22 4 4 3

3 D2 4 3 1 BC3 3 3 5 15．最优方案为（A，B2，C1，D1，E）或（A，B3，C1，D1，E）或（A，B3，C2，D2，E）；总费用是11。

16．最短路线问题：从起点A到终点G分六个阶段，每个阶段各有若干条可选择的道路，每条道路的长度如图所示。试确定从A点到G点的最短路线。 6 C1 8 2 3 1 D1 E1 F1 B1 3 3 5 2 4 C 5 25 6 5 1 G D2 A E2 3 8 2 2 3 C3 7 3 6 B2 5 3 16．A-B1-C2-D1-E2-F2-G总长度为18。 二．实践能力训练

1．某商店在未来四个月里,利用仓库经销某种商品。该仓库的最大容量为1000件，每月中旬订购商品，并于下月初取到订货。据估计:今后四个月这种商品的购价和售价如下表所示。假定商店在1月初开始经销时仓库已存有该种商品500件，每月市场需求不限，问应如何计划每个月订购与销售数量，使这四个月的总利润最大（不考虑仓库的存储费用）？ 1．各月份生产货物数量的最优决策为： 期前存货(sk) 售出量(xk) 月 月份 1 2 3 4 购价 10 9 11 15 售价 12 9 13 17 购进量(yk) 1 500 500 0 2 0 0 1000 3 1000 1000 1000 4 1000 1000 0 利润最大值为12?500?10?1000?16000 2．某工厂在未来3个月连续生产某种产品。每月初开始生产，月产量为x，生产成本

2b1?100,b2?110,b3?120。为x，库存费为每月每单位1元。假如3个月的需求量预测为：

且初始存货s0?0，第三个月的期末存货s3?0。问应如何安排生产使总成本最小？ 2．最佳生产量为：x1?110,x2?110,x3?109121；最低费用为36321元。 23．（生产存储问题）某工厂与购货单位签订的供货合同如右表所示。表中的数字为月份交货量。该厂每月最大产量为4百件，仓库

月份 1 2 3 4 5 6 的存货能力为3百件。已知每一百件货物的生

产费用为一万元。在生产月份，每批产品的生交货量 1 2 5 3 2 1 产准备费为4千元，仓库保管费每一百件货物（百件） 每月一千元。假定1月初开始时及6月底交货

后仓库中都无存货。问该厂应该如何安排每月的生产与库存，才能既满足交货合同的要求，又使总费用最小？

3．各月份生产货物数量的最优决策为： 月份 生产货物量（百件）

4．(背包问题)某工厂生产三种产品,各种产品重量与利润重量（吨利润（元种类 \\件） \\件） 关系如右表所示。现将此三种产品运往市场销售，运输能力总

1 2 80 重量不超过6吨。问如何安排运输使总利润最大？

2 4 180 4．运输1，2两种产品各一吨或运输第3类产品两吨，总利润3 3 130 最大值为260元。 5．（设备更新问题）设某企业在今后4年内需使用一辆卡车。现有一辆已使用2年的旧车，根据统计资料分析，预计卡车的年收入、年维修费（包括油料等费）、一次更新重置费及4年后残值如右表所示，k =1,2,3,4。试确定4年中的最优更新计划，以使总利润最大。

i 0 1 2 3 4 5 6 1 4 2 0 3 4 4 3 5 3 6 0 rk(i)vk(i)ck(i)t5(i)

6．某科学实验可以用3套不同的仪器（A，B，C）中任一套去完成。每做完一次试验后，如果下次实验仍使用原仪器就必须对仪器进行整修，中间要耽搁一段时间；如果下次使用另一套仪器，则卸旧装新也要耽搁一段时间。耽搁时间tij如右表所示。假定一次试验的时间大于tij，

161?? 1421815 1122112 83258 54293 24340 ???0 下次使用仪器 本次使用仪器 1 10 9 6 2 9 12 5 3 14 10 8 1（A） 2（B） 3（C） 因而某套仪器换下后隔一次再用时，不再另有耽搁。现在要做4次实验，首次实验指定用仪器A，其余各实验可用任一套仪器。问应如何安排使用仪器的顺序，才能使总的耽搁时间最短？

6．第一次试验使用A，第二次使用B，第三次使用C，第四次使用B。最

购货销售短时间24。 月份 成本 价格 7．某公司准备经销某种货物，货物入库后才能销售，仓库容量为9001 40 45 2 38 42 件。公司每月月初订购货物，月底才到货。每月的销售量由公司自己确定（销

3 40 40 售月初库存货物）。现在一至四月各单位货物的购货成本及销售价格如右表

4 42 44 所示。又知一月初存货200件，问如何安排每月的货物购进量与销售量，使

四个月的利润最大。

8.计算如右图所示的从A到E的最短路线及其长度。 B1 D4 4 （1）用逆推解法； 2 3 3 3 C5 （2）用标号法。 1 2 3 1 A BE D8．最短路线 2 3 1 1 4 5 A?B2?C1?D1?E，3 C2 5 B3 D其路长为8。 3 9．某人在每年年底要决策明年的投资与积累的资金分配。设开始时，他可利用的资金数为C，年利率为?(??1)，在i年里若投资yi所得到的效益用gi(yi)?byi(b为常数)来表示。试用逆推解法和顺推解法来建立该问题在n年里获得的最大效益的动态规划模型。

9．逆推法：设状态变量si表示第i年初拥有的资金数，则有逆推关系式

fn(sn)?max{gi(yn)}??yn?sn?f(s)?max{g(y)?f[a(s?y)]} iiiii?1ii?0?yi?si?i?n?1,?,2,1顺推法：：设状态变量si表示第i?1年初拥有的资金数，则有顺推关系式

f1(s1)?max{g1(y1)}?0?y1?ac?s1??yi?sif(s)?max{g(y)?f[]} ?iiiii?10?y?ac?siia?i?2,?,n10．已知某指派问题的有关数据（每人完成各项工作的人 时间）如右表所示，试对此问题用动态归划方法求解。要求：1 （1）列出动态规划的基本方程； 2 3 （2）用逆推法求解。

4 10．（1）任务的指派分4个阶段完成，用状态变量sk表示第k阶段初未指派的工作的集合，决策变量为ukj

工作 1 15 19 26 19 2 18 23 18 21 3 21 22 16 23 4 24 18 19 17 j项工作,?1,k阶段被指派完成第 ukj??0,否则.?状态转移方程为sk?1?{Dk(sk)/j,当ukj?1}。逆推关系式为

f4(s4)?min{a4j}??u4j?D4(s4)?f(s)?max{a?f(s)} kkkjk?1k?1?ukj?D(sk)?k?3,2,1（2）k?4时 s4 1 19 2 21 3 23 4 17 a4j u4j j?1 19 j?2 21 j?3 23 j?4 17 *u3j f4(s4) k?3时 u3j s3 （1，2） （1，3） （1，4） （2，3） （2，4） （3，4） a3j?f4(s4) u32?1 26＋21 26＋23 26＋17 u32?1 18＋19 18＋23 18＋17 u33?1 16＋19 16＋21 16＋17 u34?1 19＋19 19＋21 19＋23 f3(s3) 37 35 38 37 35 33 u32?1 u33?1 u34?1 u33?1 u32?1 u33?1 *u2j k?2时 u2j s2 （1，2，3） （1，2，4） a2j?f3(s3) u21?1 19＋37 19＋35 u22?1 23＋35 23＋38 u23?1 22＋37 u24?1 18＋37 f2(s2) 56 54 u21?1 u21?1 （1，3，4） （2，3，4） 19＋33 23＋33 22＋38 22＋35 18＋35 18＋37 52 55 u21?1 u24?1 *u1j k?1时 u1j s1 u11?1 a1j?f2(s2) u12?1 18＋52 u13?1 21＋54 u14?1 24＋56 f1(s1) 70 （1，2，3，4） 15＋55 u11?1或u12?1 最优解为：u11?u24?u33?u42?1或u12?u21?u33?u44?1。 11．某公司打算在三个不同的地区设置4个销售店 0 1 地区 销售点，根据市场预测部门估计，在不同的地区

1 0 16 设置不同数量的销售店，每月可得到的利润如右

2 0 12 表所示。试问在各个地区应如何设置销售点，才3 0 10 能使每月获得的总利润最大？其值为多少？ 11．最优决策为：在第一个地区设置2个销售点，在第二个地区设置 1个销售点，在第三个地区设置1个销售点。每月可获总利润为47。

2 25 17 14 3 30 21 16 4 32 22 17 12．某工厂购进100台机器，准备生产p1,p2两种产品。若生产产品p1，每台机器每年可收入45万元，损坏率为65%；若生产产品p2，每台机器每年收入为35万元，但损坏率只有35%；估计三年后将有新的机器出现，旧的机器将全部淘汰。试问每年应如何安排生产使在三年内收入最多？

12．最优决策为：第一年将100台机器全部生产产品p2，第二年把余下的机器继续生产产品p2，第三年把余下的所有机器全部生产产品p1。三年总收入为7676.25万元。 13．设有两种资源，第 一种资源有x单位，第二种 资源有y单位，计划分配给

x y r1(x,y) 0 1 2 3 0 1 3 6 4 5 6 7 4 6 7 8 6 7 8 9 r2(x,y) 0 1 2 3 0 2 4 6 1 4 6 7 4 6 8 9 6 8 10 11 r3(x,y) 0 1 2 3 0 3 5 8 2 5 7 9 4 7 9 11 6 9 11 13 n个部门。把第一种资源xi

0 1 2 3

单位，第二种资源yi单位分配给部门i所得的利润记为ri(xi,yi)。如设x?3,y?3,n?3，

其利润ri(x,y)列于下表中。试用动态规划方法如何分配这两种资源到i个部门中去，使

总的利润最大？

13．最优决策为：x1?0,y1?0;x2?2,y2?0;x3?0,y3?3。最大利润为：

r1(1,0)?r2(2,0)?r3(0,3)?4?4?8?16?f1(3,3)

14.某公司有三个工厂，它们都可以考虑改造扩建。每个工厂可有若干种方案可供选择，各种方案的

方案 工厂1 投资 收益 工厂2 投资 收益 工厂3 投资 收益 1 2 3 4 0 1 2 - 0 5 6 - 0 2 3 4 0 8 9 12 0 1 - - 0 3 - - 投资及所能取得的收益如右表所示（单位：千万元）。现公司有资金5千万元，问应如何分配投资使公司的总收益最大？ 14．有三个最优方案：（3，2，2） 或（2，3，2）或（2，4，1）总收益是17千万元。

15．某公司在今后三年的每一年的年初将资金投入A和B两投资 回收 概率 项工程，年末的回收及其概率如右表所示。每年至多做一项投资，0 0.4 A每次只能投入1000万元。求三年后所拥有的期望金额最大的投资2000 0.6 方案。 1000 0.9 B15．最优方案是每年均投资于A，三年后的最大利润为440万元。 2000 0.1 16.某商店在未来的4个月里，准备利用商店里一个仓库来专 月份 买价 卖价 门经销某种商品，该仓库最多能装这种商品1000单位。假定商店

1 10 12 每月只能卖出仓库现有的存货。当商店决定在某个月购货时，只

2 9 9 有在该月的下个月初才能得到该货。据估计未来4个月这种商品

3 11 13 买卖价格如右表所示。假定商店在1月开始经销时，仓库存储商

4 15 17 品有500单位。试问：如何制订这4个月的订购与销售计划，使 获得利润最大？（不考虑仓库的存储费用）

16．各月份生产货物数量的最优决策为：

月份 生产货物量（百件） 1 4 2 0 3 4 4 3 5 3 6 0

17.某鞋店出售橡胶雪靴，热销季节是从101 2 3 月份 10 11 12 月1日至次年3月31日，销售部门对这段时间的需求 40 20 30 40 30 20 需求量预测如右表所示。 （双） 每月订货数目只有10，20，30，40，50几种

可能性，所需费用相应的为48，86，118，138，160（元）。每月末的存货不应超过40双，存储费用按月末存靴数计算，每月每双为0.2元。因为雪靴季节性强，且样式要变化，希望热销前后存货均为零。假定每月的需求率为常数，贮存费用按每月存货量计算，订购一次的费用为10元。求使热销季节的总费用为最小的定货方案。 17．热销季节每月最佳订货方案为： 月份 10 11 12 1 2 3 订购数（双） 40 50 0 40 50 0 18．设某种机器可以在高、低两种不同负荷下生产。若机器在高负荷下生产，则产品年产量a和投入生产的机器数量x的关系为a?8x，机器的年折损率??0.3；若机器在低负荷下生产，则产品年产量b和投入生产的机器数量x的关系为b?5x，机器的年折损率??0.1。设开始有完好的机器1000台，要求制定一个四年计划，每年年初分配完好机器在不同负荷下工作，使四年产品总产量达到最高。 18．分配方案为 第一年 第二年 第三年 第四年 0 900 630 441 高负荷 1000 0 0 0 低负荷 总产量为20768。 19．某工厂在一年进行了A,B,C三种新产品试制，由于资金不足，估计在年内这三种新产品研制不成功的概率分别为0.40,0.60,0.80，因而都研制不成功的概率为

0.40?0.60?0.80?0.192。

为了促进新产品的研制，决定增拨2万元的研制费，并要资金集中使用，以万元为单位进

行分配，其增拨研制费与新产品不成功的概率如下表所示 新产品 不成功概率 A B 研制费S 0 0.40 0.60 1 0.20 0.40 2 0.15 0.20 试问如何分配费用，使这三种新产品都研制不成功的概率为最小。

C 0.80 0.50 0.30 19.分为三个阶段，状态变量sk表示第k种产品至第n种产品的研制费用，xk表示第k种产品研制费用。pk(xk)表示第k种产品补加研制费xk后的不成功概率。模型为

minz??pi(xi)

i?13x1?x2?x3?2,xi?0且为整数

f4(s4)?1???f(s)?min{p(x)?f(s?x)} k?1kk??kk0?xk?skkkk?3,2,1第三阶段，设s3万元(s3?0,1,2)，全部分配给新产品C，则不成功概率为

f3(s3)?min[p3(x3)?0.4?0.6]

x3?s3其计算如下： x3 p3(x3) f3(s3) s3 0 1 2 0 0.8 1 0.5 2 0.3 0.8 0.5 0.3 *x3 0 1 2 第二阶段，设s2万元(s2?0,1,2)，全部分配给新产品B,C，则不成功概率为

f2(s2)?min[p2(x2)?f2(s2?x2)]

0?x2?s2其计算如下： x2 p2(x2)?f2(s2?x2) f2(s2) *x2 s2 0 1 2 0 1 2 0.48 0.30 0.16 0 0 2 0.6?0.8 0.6?0.5 0.6?0.3 0.4?0.8 0.4?0.5 0.2?0.8 第一阶段，设s1?2万元，全部分配给新产品A,B,C，则不成功概率为

f1(2)?min[p1(x1)?f1(2?x1)]

0?x1?2其计算如下： x1 0 1 2 f1(2) 0.06 x1* 1 s1 2 0.4?0.016 0.2?0.3 0.15?0.48 ***故x1?1,x2?0,x3?1,f1(2)?0.06

即A产品分配1万元，B产品不分配，C产品分配1万元，这三种产品都研究不成功的概率最小为0.2?0.6?0.5?0.06。

20．资本安排问题：某公司有三个工厂，它们都可以考虑扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所取得的收益如下表所列（单位：千万元）：总投资为5千万元，问如何分配投资使公司收益最大？ mi （方案） 1 2 3 4 i=1 C(投资) 0 1 2 — R(收益) 0 5 6 — C 0 2 3 4 i=2 R 0 8 9 12 C 0 1 — — i=3 R 0 3 — — 20．.最优方案为：（2，4，1）或（3，2，2）或（2，3，2），总收益都是17万元。

21．某科研项目由三个小组用不同手段分别研究，他们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：

高级科学家 0 1 2 小 组 1 0.40 0.20 0.15 2 0.60 0.40 0.20 3 0.80 0.50 0.30 问如何分派科学家才能使三个小组都失败概率（即科研项目最终失败的概率）最小？ 21． 1，3小组各派一名科学家，科研项目最终失败的概率为0.060。

22．考虑一种由四个部件组成的系统，各部件都运行时系统才能运行。系统的可靠性可以通过在一个或几个部件中并联若干单元而得到提高。并联mi个单元后部件的可靠性（概率）Ri,mi和费用Ci,mi（单位为千元）如下表： mi 1 2 3 i=1 R 0.7 0.75 0.85 C 4 5 7 R 0.6 0.8 — i=2 C 2 4 — R 0.9 — — i=3 C 3 — — R 0.8 0.82 — i=4 C 3 5 — 现有资金15千元。在四个部件中各并联多少个单元才能使系统运行的概率最大？

22．四个部件的并联数各为2，2，1，1单位；系统可靠性（系统正常运行的概率）为0.432。

23．某企业以初始资金C买进两种设备的方式进行投资。若x是投资于甲种设备的金额，那么在第一年年底得到的利润是g1(x)，投资于乙种设备得到的利润是g2(C-x)。企业确定一年后报废设备。时期t甲、乙两种设备的残值各为ptx和qt(C-x)，其中pt和qt分别为时期t的甲、乙两设备的残值系数。在每一年年底企业把报废所得的收入再进行投资。在今后N年，每年收益函数皆为g1，g2。

设C=10,000元，N=5，g1(z)=0.5z，g2(z)=0.7z，pt和qt如下表： t pt qt 年 份 设 备 甲 乙 1 0.5 0.6 1 0.5 0.6 2 0.9 0.1 2 0.9 0.1 3 0.4 0.5 3 0.4 0.5 4 0.5 0.7 4 0.5 0.7 5 0.9 0.5 5 0.9 0.5 问如何投资才使五年的总利润最大？ 23．最优投资方案为 年 份 设 备 甲 乙 1 0 10,000 2 6,000 0 3 0 5,400 4 0 2,700 5 1890 0 总利润为16,615元。 24．某鞋店出售橡胶雪靴，热销季节是从10月1日至明年3月31日，销售部门对明年的需求量预测如下： 月份 需求 10 40 11 20 12 30 1 40 2 30 3 20 每月订货数目只有10，20，30，40，50几种可能性，花去费用相应地为48，86，118，138，160元。每月末的存货不应超过40双，存储费用按月末存靴数计算，每月每双为0.20元。因为雪靴季节性强，且式样要变化，希望热销前后存货均为零。假定每月中的需求率为常数。存储费用按月存货量计算，订购一次的费用为10元。求使总季节费用最小的订货方案。 24．最优进货方案为：10月、11月、12月、1月、2月和3月各进货40、50、0、40、50和0双；总费用为606元。