《运筹学》课程教学资源（试卷习题）第5章 动态规划习题

《运筹学》第五章习题1.思考题（1）试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。（2）动态规划的阶段如何划分？（3）试述用动态规划求解最短路问题的方法和步骤。（4）试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值函数、边界函数等概念。（5）试述建立动态规划模型的基本方法。（6）试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动态规划基本方程的关键步骤。2．判断下列说法是否正确（1）动态规划分为线性动态规划和非线性动态规划。（2）动态规划只是用来解决和时间有关的问题。（3）对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。（4）在用动态规划的解题时，定义状态时应保证各个阶段中所做的决策的相互独立性。（5）在动态规划模型中，问题的阶段等于问题的子问题的数目。（6）动态规划计算中的“维数障碍”，主要是由于问题中阶段数的急剧增加而引起的。3.计算下图所示的从A到E的最短路问题BE54.计算下图所示的从A到E的最短路问题XB35.计算从A到B、C、D的最短路线。已知各线段的长度如下图所示

《运筹学》第五章习题 1．思考题 （1）试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。 （2）动态规划的阶段如何划分？ （3）试述用动态规划求解最短路问题的方法和步骤。 （4）试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值 函 数、边界函数等概念。 （5）试述建立动态规划模型的基本方法。 （6）试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动 态 规划基本方程的关键步骤。 2．判断下列说法是否正确 （1）动态规划分为线性动态规划和非线性动态规划。 （2）动态规划只是用来解决和时间有关的问题。 （3）对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。 （4）在用动态规划的解题时，定义状态时应保证各个阶段中所做的决策的相 互独立性。 （5）在动态规划模型中，问题的阶段等于问题的子问题的数目。 （6）动态规划计算中的“维数障碍”，主要是由于问题中阶段数的急剧增加 而引起的。 3．计算下图所示的从 A 到 E 的最短路问题 4．计算下图所示的从 A 到 E 的最短路问题 5．计算从 A 到 B、C、D 的最短路线。已知各线段的长度如下图所示。 1 4 3 4 1 1 3 2 2 2 4 3 3 5 5 3 A 3 B1 B2 B3 C1 C2 D1 D2 D3 E 3 1 5 4 5 A B1 B2 B3 C1 C2 C3 D1 D2 E 3 5 4 1 6 3 3 4 4 2 9 4 2 6 7 5 1 2

6.设某油田要向一炼油厂用管道供应油料，管道铺设途中要经过八个城镇，各城镇间的路程如下图所示，选择怎样的路线铺设，才使总路程最短？7020.60304060油田802013620B20507.用动态规划求解下列各题(1). maxz=5xj-x2+9x,-2x3[x+x≤5[x,≥0(2). maxz=xx2x3[X +X2 +X ≤6[X,X2,≥08.某人外出旅游，需将3种物品装入背包，但背包重量有限制，总重量不超过10千克。物品重量及其价值等数据见下表。试问每种物品装多少件，使整个背包的价值最大？23物品编号1单位重量千克）544单位价值56物品件数XX9.某人外出旅游，需将五件物品装入背包，但包裹重量有限制，总质量不超过13千克。物品重量及其价值的关系如表所示。试问如何装这些物品，使整个背包价值最大？

6．设某油田要向一炼油厂用管道供应油料，管道铺设途中要经过八个城镇，各 城镇间的路程如下图所示，选择怎样的路线铺设，才使总路程最短？ 7．用动态规划求解下列各题 （1）． 2 2 2 2 max z  5x1  x1  9x  2x ；       , 0 5 1 2 1 2 x x x x ； （2）． 3 2 3 2 1 max z  x x x        , , 0 6 1 2 3 1 2 3 x x x x x x ； 8．某人外出旅游，需将 3 种物品装入背包，但背包重量有限制，总重量不超过 10 千克。物品重量及其价值等数据见下表。试问每种物品装多少件，使整个 背包的价值最大？ 物品编号 1 2 3 单位重量（千克） 3 4 5 单位价值 4 5 6 物品件数 1x 2 x 3 x 9．某人外出旅游，需将五件物品装入背包，但包裹重量有限制，总质量不超过 13 千克。物品重量及其价值的关系如表所示。试问如何装这些物品，使整个背包 价值最大？ 13 A B C D 10 7 8 4 8 7 12 6 5 8 3 7 3 2 4 6 5 8 9 10 10 15 7 E1 E2 E3 F1 F2 F3 G1 G2 G3 30 30 30 50 10 40 60 60 30 B1 油田 厂 B2 B3 C1 C2 C3 D1 D2 20 30 70 20 40 20 50 30 20 40 50

物品重量（千克）价值（元）79A4B543CD32E10.510.有一辆最大装载量为17吨的货车，现有4种货物要装运，每种货物的单位重量和相应单位价值如下表所示，应如何装载可使总价值最大？234货物编号143单位重量（吨）56单位价值（千元）7583.5某工厂根据市场需求预测今后4个月的交货任务如下表所示，表中数字为月11.底交货量，该厂的生产能力为每月600件，该厂仓库的存货能力为300件，又每生产100件产品的费用为1000元。在进行生产的月份，工厂要固定支出3000元开工费。仓库保管费用为每100件500元。假定开始时和计划期末库存量都是零。试问应在各个月各生产多少件货物，才能既满足交货任务又使总费用最少？23月份1434需求（百件）22某集团公司有4个单位的资金，要向下属三个子公司投资。由于条件不同，12.使用资金的效益也不同。具体数据见下表。为使此集团获得最大收益，试问每个子公司各投资多少单位资金？（表内数字为投资所获收益）资金02341子公司101A5620235730346613.某公司有500台完好的机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，每台机器每年可收入50万元，机器损坏率为70%，在低负荷下进行生产时，每台机器每年可收入30万元，机器损坏率为30%，估计五年后有新的机器出现，旧的机器将全部淘汰。要求制定一个五年计划，在每年开始时，决定如何分配完好的机器在两种不同的负荷下生产的数量，使在五年内总产值最高。并计算每年初完好机器台数。14.某工厂购近100台设备，准备生产A、B两种产品。如果生产产品A，每台设备每年可收入10万元，但机器损坏率为65%，如果生产产品B，每台设备每年可收入7万元，机器损坏率为40%，三年后的设备完好情况不计，试问应如何安排每年的生产，使三年的总收入最大？又如果要求三年后有20台机器是完好的，则应如何安排每年的生产，使三年的总收入最大？

物 品 重量（千克） 价值（元） A 7 9 B 5 4 C 4 3 D 3 2 E 1 0.5 10．有一辆最大装载量为 17 吨的货车，现有 4 种货物要装运，每种货物的单位重 量和相应单位价值如下表所示，应如何装载可使总价值最大？ 货 物 编 号 1 2 3 4 单位重量（吨） 5 4 3 6 单位价值（千元） 7 5 3．5 8 11．某工厂根据市场需求预测今后 4 个月的交货任务如下表所示，表中数字为月 底交货量，该厂的生产能力为每月 600 件，该厂仓库的存货能力为 300 件，又 每生产 100 件产品的费用为 1000 元。在进行生产的月份，工厂要固定支出 3000 元开工费。仓库保管费用为每 100 件 500 元。假定开始时和计划期末库存量都 是零。试问应在各个月各生产多少件货物，才能既满足交货任务又使总费用最 少？ 月 份 1 2 3 4 需求（百件） 2 3 2 4 12．某集团公司有 4 个单位的资金，要向下属三个子公司投资。由于条件不同， 使用资金的效益也不同。具体数据见下表。为使此集团获得最大收益，试问 每个子公司各投资多少单位资金？（表内数字为投资所获收益） 资金 子公司 0 1 2 3 4 1 0 1 4 5 6 2 0 2 3 5 7 3 0 3 4 6 6 13．某公司有 500 台完好的机器可以在高低两种不同的负荷下进行生产。在高负 荷下进行生产时，每台机器每年可收入 50 万元，机器损坏率为 70% ，在低 负荷下进行生产时，每台机器每年可收入 30 万元，机器损坏率为 30% ，估 计五年后有新的机器出现，旧的机器将全部淘汰。要求制定一个五年计划， 在每年开始时，决定如何分配完好的机器在两种不同的负荷下生产的数量， 使在五年内总产值最高。并计算每年初完好机器台数。 14．某工厂购近 100 台设备，准备生产 A、B 两种产品。如果生产产品 A，每台 设备每年可收入 10 万元，但机器损坏率为 65 %，如果生产产品 B ，每台设 备每年可收入 7 万元，机器损坏率为 40% ，三年后的设备完好情况不计，试 问应如何安排每年的生产，使三年的总收入最大？又如果要求三年后有 20 台 机器是完好的，则应如何安排每年的生产，使三年的总收入最大？

15.某工厂有5个单位的能源要供给3个车间，供给方案及各车间获得能源后所产生的效益在下表给出，问应如何分配这些能源，使工厂的总收益最大？能源20134车间0561--028912-303--注：表中的“一表示没有此方案

15．某工厂有 5 个单位的能源要供给 3 个车间，供给方案及各车间获得能源后所 产生的效益在下表给出，问应如何分配这些能源，使工厂的总收益最大？ 能 源 车间 0 1 2 3 4 1 0 5 6 — — 2 0 — 8 9 12 3 0 3 — — — 注：表中的“——”表示没有此方案