第6章 动态规划
判断
06100011判断：在动态规划模型中，问题的阶段数等于问题中的子问题的数目；
06100021判断：动态规划中，定义状态时应保证在各个阶段中所作决策的相互独立性； 06100031判断：）动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做
出的决策；
06100041判断：对一个动态规划问题，应用顺推或逆推解法可能会得出不同的最优解； 06100051判断：动态规划计算中的“维数障碍”主要是由于问题中阶段数的急剧增加而引
起的；
06100061判断：）假如一个线性规划问题含有5个变量和3个约束，则用动态规划方法求解
时将划分为3个阶段，每个阶段的状态将由一个5维的向量组成；
06100071判断：任何一个多阶段决策过程的最优化问题，都可以用非线性规划模型来描述。 06100081判断： 动态规划问题如果按状态转移率区分,可分成确定性的与随机性的.
简答
06200011简答：
一个N阶段的决策过程具有哪特征？ 06200021简答：试述动态规划的优点。 06200031简答：试述最优化原理的内容
06200041简答：试述动态规划数学模型的四种类型.
计算题
最短路问题
06301012设某厂自国外进口一步精密机器，由机器制造厂至出口港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，期间的运输成本如下图所示，试求运费最低的路线。
70 30 30 B2 30 B3 40 10 40 60 C2 30 D2 30 D1 30 B1 20 40 A C1 20 40 40 10 E 30 C3 40 50 机器制造厂 ——> 出口港 ——> 进口港 ——> 城市 ——> 某工厂
06301022、某工厂从国外引进一台设备，由A到G港口有多条通路可供选择，其路线及费
用如下图所示。现要确定一条从A到G的使总费用最小的路线。请将该问题描述成一个动态规划问题，然后求其最优解。
B 20 A 60 40 70 40 D 50 30 E 30 G 30 C F 40
资源分配
06302012有一部货车每天沿着公路给四个零售店卸下6箱货物，如果各零售店出售该货物
所得利润如下表所示，试求在各零售店卸下几箱货物，能使总利润最大？其值是多少？ 零售店 利润 箱数 0 1 2 3 4 5 6 0 4 6 7 7 7 7 0 2 4 6 8 9 10 0 3 5 7 8 8 8 0 4 5 6 6 6 6 1 2 3 4
06302022设有某种肥料共6个单位重量，准备供给四块粮田用，其每块粮田施肥数量与增
产粮食数字如下表，试求对每块田施多少单位重量的肥料，才使总的增产粮食最多。 施肥 0 1 2 3 4 5 6 粮田 1 0 20 42 60 75 85 90 2 0 25 45 57 65 70 73 3 0 18 39 61 78 90 95 4 0 28 47 65 74 80 85 06302033某公司打算向承包的三个营业区增设六个销售店，每个营业地区至少增设一个，
从各区赚取的利润与增设的销售店个数有关，其数据如下表所示。 销售店增加数 0 1 2 3 4 A区利润 100 200 280 330 340 B区利润 200 210 220 225 230 C区利润 150 160 170 180 200 试求各区应分配几个增设的零售店，才能使总利润最大？其值是多少？
存储控制问题
06303012设某工厂调查了解市场情况，估计在今后四个时期市场对产品的需求量如下表所
示。
时期 需求量 1 2 2 3 3 2 4 4 假定不论在任何时期，生产每批产品的固定成本为3（千元）就，若不生产，则为0。每单 位生产成本费为1（千元）。同时任何一个时期生产能力所允许的最大生产批量为不超过6 个单位。又设每个时期的每个单位产品库存费为0.5（千元），同时规定在第一期初及第四期 末均无产品库存。试问，该厂如何安排各个时期的生产与库存，使所花的总成本最低？
随机性动态规划
06304013某罐头制造公司需要在近五周内必须采购原料一批，估计未来五周内价格有波动， 其浮动价格和概率如下表所示，试求各周以什么价格购入，使采购价格的数学期望值最小。
单价 9 8 7 概率 0.4 0.3 0.3
06304021某人外出旅游，需将5个物品装入背包，但背包装物重量有限制，总重量W不得
超过13千克。物品重量及价值的关系如下表所示。试问：如何装入这些物品，使背包的价值最大？
物品 A B C D E 重量（千克） 7 5 4 3 1 价值（元） 9 4 3 2 0.5
06304033某种工业产品需经过A，B，C三道工序，其合格率分别为0.70，0.60，0.80；假
设各工序的合格率相互独立，从而产(成)品的合格率为0.70 * 0.60*0.80＝0.336。为了提高产品的合格率，现准备以限额为5万元的投资，在三道工序中采取如下表所示的各种提高产品质量的措施。这些措施的投资金额和采取措施后各工序预期的合格率均列在下表中。问：应采取哪些措施，才能使产(成)品的合格率达到最大? 措施项目 ①维持原状 ②调整轴承 ③加装自停装置 投资金额 工序的预期合格率 0 每工序1万元 0.80 0.70 0.90 ④调换轴承并加装自停装置 每工序2万元 每工序3万元 0.90 0.80 0.90 0.95 0.90 0.94 A 0.70 B 0.60 C 0.80
06304042某住宅建筑公司拟建甲、乙、丙三类住宅出售。已知：甲类住宅楼每栋耗资100
万元，售价100万元；乙类住宅楼每栋耗资60万元，售价110万元；丙类住宅楼每栋耗资30万元，售价70万元。由于市政当局的限制，建造每类住宅楼不得多于三栋，该公司共有可利用的资金350万元。问：应如何拟定建筑计划，方能使该公司的售房收入最大?
06304051某有限公司有5台新设备，将有选择地分配给下属三个工厂，所得效益如表所示。
问：该公司应如何分配这些设备可使总收益最大?
单元：干元
新工厂台数 0 1 2 3 4 5 工厂 Ⅰ 0 3 7 9 12 13 Ⅱ 0 5 10 11 11 11 Ⅲ 0 4 6 11 12 12
06304063设有两种资源：第一种资源有a单位，第二种资源有b单位。拟将这两种资源分
配给N个部门。第一种资源xi单位、第二种资源yi单位分配给部门i所得利润为
ri(xi,yi)。现设a＝3，b=3，N=3，其利润ri(xi,yi)列于下表中。问：应如何分配这两
种资源，使总利润最大? yi xic2??4?2(yi?yi?1)yi?1?yi 0 1 2 3 r1(x1,y1) 1 1 5 6 7 2 3 6 7 8 3 6 7 8 9 r2(x2,y2) 0 0 1 4 6 1 2 4 6 8 2 4 6 8 3 6 7 9 r3(x3,y3) 0 0 2 4 1 3 5 7 9 2 5 7 9 3 8 9 11 0 0 4 5 6 10 11 6 11 13 06304072 某制造厂根据合同，要在1至4月份的每月底供应零件各为40，50，60，80件。
该厂1月初并无存货，至4月末亦不准备留存。已知每批的生产准备费用为100元；若当月生产的零件交运不出去，需要仓库存贮，存贮费用为2元／(件月)。该厂每月的最大生产能力为100件。问：应如何安排生产，才能使费用总和为最小?
06304082某公司计划在今后4个月内经营一种高级成衣。根据预测该种商品在5至8月份
的每套进价和售价如下表所示。已知库存能力为600套，5月初有存货2肋套，并假定销售是在月初进行，至月末全部售完。试对这4个月的购销做出安排，使总的利润最大？
月份 进价 售价 5 40 45 6 38 42 7 40 39 8 42 44
06304093设某种机器可以在高、低两种不同负荷下生产。若机器在高负荷下生产，则产品
的年产量。和投入生产的机器数量x的关系为a=8x, ，机器的年折损率β＝0．3；若机器在低负荷下生产，则产品年产量b投入生产的机器数量x关系为b＝5x，机器的年折损率α＝0．1。设开始时有完好机器1000台，要求制定一个四年计划，每年年初分配完好机器在不同负荷下工作，使四年产品总产量达到最大。
06304102 某工厂在一年内进行A,B，C三种新产品试制。估计年内这三种新产品研制不成功
的概率分别为0．40，0．60，0．80。厂领导为了促进三种新产品的研制，决定拨2万元追加研制费。假设：这些追加研制费(以万元为单元)分配给不同新产品研制时不成功的概率分别如下表中所示。试问：应如何分配这笔追加研制费，使这三种新产品都没有研制成功的概率最小。
新产品 研制费 0 1 2 不成功概率 A 0.40 0.20 0.15 B 0.60 0.40 0.20 C 0.80 0.50 0.30
06304112一名学生要从四个系中挑选10门选修课程。他必须从每个系中至少选一门课，他
的目的是把10门课分到四个系中，使得他在四个领域中的“知识”最多。由于他对课程内容的理解力和课程内容的重复，他认为:如果在某一个系所选的课程超过一定数目时，他的知识就不能显著增加。为此，他采用100分作为衡量他的学习能力，并以此作为在每个系选修课程的依据。经过详细调查分析得到表中各数据。试确定这名学生选修课程的最优方案。
课程 分数 系别 Ⅰ Ⅱ Ⅲ Ⅳ 1 2 3 4 5 6 7 8 9 10 25 20 40 10 50 70 60 20 60 90 80 90 80 100 100 40 100 100 100 50 100 100 100 60 100 100 100 70 100 100 100 80 100 100 100 90 100 100 100 100
06304123考虑一家公司在今后5个时期内确定劳动力多少的问题。如果5个时期中所需劳
动力的最低数是bi，是5，7，8，4，6（单位：百人）（ i=1,?5）。设yi（?bi）是第
i个时期所拥有的实际劳动力，若yi>bi，将导致额外费用c1?3(yi?bi)；；若yi?1?yi，则劳动力的费用为：
R4jC4j
?4?2(yi?yi?1), c2??其他?0yi?1?yi
假定 y0=5（百人），试确定劳动力支出费用最小的方案。
06304133设有一个4个部件串联组成的系统。为提高系统的可靠性，考虑在每个部件上并
联1个、2个或3个同类元件，每个部件（i=1,2,3,4）配备j 个并联元件（j=1,2,3）
后的可靠性Rij和 Cij（单位百元）由下表给出。假设该系统的总成本允许为15千元，试问：如何确定个部件配备元件的数目，使该系统的可靠性最大？
i=1 j 1 2 3 i=2 i=3 i=4 R1j 0.70 0.75 0.85 C1j 4 5 7 R2j 0.60 0.80 - C2j 2 4 - R3j 0.90 - - C3j 3 - - R4j 0.80 0.82 - C4j 3 5 -
06304142某工厂使用一种关键设备，每年年初设备科需对该设备的更新与否作出决策。现
已知在5年内购置该种新设备的费用和各年内维修费如下表所示。试制订5年内的设备更新计划，使总的支付费用最少。
单位：千元/台 第 i年 购置费用 第i年初 维修费用 1 11 1 5 2 11 2 6 3 12 3 8 4 12 4 11 5 13 5 18 06304152设有6万元资金用于四个工厂的扩建。已知每年工厂的利润增长同投资数额的大
小有关，详细数据见下表。问应该如何确定对着 4个厂的投资额，使总利润增长最大。
1 2 3 4 0 100 200 300 400 500 600 0 0 0 0 20 25 18 28 42 45 39 47 60 57 61 65 75 65 78 74 85 70 90 80 90 73 95 85 接 06304163某项工程有３个设计方案。据现在有条件，这些方案不能完成的概率分别为
0.40,0.60,0.80,即３个方案均完不成的概率为0.40?0.60?0.80?0.192。为使这３个方案中至少完成一个的概率尽可能大，决定追加２万元资金。当使用追加投资后，上述方案完不成的概率见下表．问应如何分配追加投资，才能使其中止至少一个方案完成的概率为最大 追加投资（万元） ０ 1 2
06304172设有某种机器设备，用于完成两种工作甲和乙。几ｋ年初完好的机器数量为xk，
若以数量uk用于工作甲，余下的(xk?uk)用于工作乙，则该年的预期收入为
１ 0.40 0.20 0.15 ２ 0.60 0.40 0.20 ３ 0.80 0.50 0.30 g?uk??h(xk?uk)。已知g?uk??8uk。又设备再使用中会有损耗，设机器用于工作
甲，一年后能继续使用的完好机器数量占年初投入量的７０％；若用于乙项工作时，一年后能继续使用的完好机器数量占年初投入量的９０％，即下一年初能使用于完成这两项工作的机器数为xk?1?uk?7%?(xk?uk)?90%设第一年初完好的机器总数为１０
００。问在５年内应该如何分配甲，乙两项工作的机器数，才能使５年的总收益为最大？ 06304183 某商店在未来的4个月里，准备利用商店的一个仓库专门经销某种商品，该仓库
最多能装这种商品1000单位。假定商店每月只能卖出仓库现有的货。当商店决定在某个月购货时，只有在该月的下个月才能得到该货物，据估计在未来4个月这种商品买卖价格如表所示。假定商店在1月份开始经销时，仓库储存该商品500单位。问如何制定这4个月的定购与销售计划，使获得利润最大（不考虑仓库的储存费用） 月份（k） 1 2 3 4 买价（Ck） 10 9 11 15 卖价（Pk） 12 9 13 17
06304191某仓库有一辆载重量为10吨的卡车，现要装运以下三种货物，这三种货物的每件
重量和单价如下表所示： 货 物 A B C 每 件 重 量 2 3 4 单 价 40 58 72 现在要确定这三种货物应各装几件，才能使每辆卡车所装货物的价值最大。如果用动态规划解这个问题，试确定阶段、各阶段的方案及其相应的数量指标和各阶段的状态。
06304201某公司准备在甲、乙、丙三个地区设置四个销售点。根据预测资料，在各地区设
置个数不同的销售点后，每月所得到的利润（单位：百元）见下表：
地 区 甲 乙 丙 销 售 点 个 数 0 0 0 0 1 16 13 12 2 28 24 22 3 40 34 36 4 50 42 47 现在要确定在各地区应设置几个销售点，才能使每个月所获得的总利润最大。如果用动态规划解这个问题，试确定阶段、各阶段的方案及其相应的数量指标和各阶段的状态。
06304211某仓库有一辆载重量为10吨的卡车，现要装运以下三种货物，这三种货物的每件
重量和单价如下表所示： 货 物 A B C 每 件 重 量 2 3 4 单 价 40 58 72 定义最优指标函数并写出基本方程。
06304221某公司准备在甲、乙、丙三个地区设置四个销售点。根据预测资料，在各地区设
置个数不同的销售点后，每月所得到的利润（单位：百元）见下表： 地 区 甲 乙 丙 销 售 点 个 数 0 0 0 0 1 16 13 12 2 28 24 22 3 40 34 36 4 50 42 47 定义最优指标函数并写出基本方程。
06304232某公司有五套新设备，拟分配给所属的一厂、二厂、三厂。各厂将不同套数的新
设备投入生产后，每年创造的产值（单位：万元）如下表所示： 厂 名 一 厂 二 厂 三 厂 新 设 备 的 套 数 0 0 0 0 1 3 5 4 2 7 8 6 3 9 10 11 4 12 13 12 5 14 16 15 现在要确定应怎样分配这五套新设备，才能使整个公司所增加的总产值最多。如果用动态规划的逆序计算解这个问题，试确定阶段、各阶段的方案及其相应的数量指标和各阶段的状态，并写出基本方程。用逆序方法求解
06304242假定某厂在明年头四个月对燃料的需求量以及各月的固定订货费和单位存储费用
如下表所示： 月 份i 1 2 需求量?i（吨） 2 2 固定订货费ki（元） 200 150 单位存储费用hi（元） 50 40 3 4 1 4 100 100 40 40 如果每吨燃料的价格是800元，该厂在每月开始时采购。用动态规划方法确定每月的采购量，试总成本最小。
06304253某工厂的一种产品在明年头四个月的计划产量分别是3千件、4千件、5千件和3
千件。工厂在生产该种产品时，每月需负担固定成本10万元，如当月未生产该种产品，则不负担固定成本。单位变动成本（原材料、工资和直接动力费等）在1月份和2月份是50元，在3月份和4月份是45元。由于设备的限制，每月最多只能生产该种产品5千件。又当月生产的该种产品如未能售出，则转入库存后，每月要负担每件8元的存储费用。
假定在明年年初该种产品无存货，到4月底时所有产品都能售出。问明年头四个月应各生产该种产品多少件，才能使生产和存储的总成本最少。
06304263 如果要考虑某种设备在今后4年内的更新问题，并且新的设备成本是6.7万元，使用t年后的残值在t≤4时，s?t??4?t；t>4时，s?t??0；使用t年后每年所创造的利润在t≤4时，p?t??4/?1?t?。开始时设备已使用了两年，其余数据不变，问每年年初应如何作出决策，才能使四年内的净利润达到最大。
06304273某企业要考虑一种设备在5年内的更新问题。在每年年初要作出决策，是继续使
用还是更新。如果继续使用，则需支付维修费用。已知使用了不同年限后的设备每年所需的维修费用（单位：百元）如下表所示： 使用年数 每年维修费用 年 份 价格（单位：百元） 0～1 5 1 11 1～2 6 2 11 2～3 8 3 12 3～4 11 4 12 4～5 18 5 13 如果要更新设备，则已知在各年年初该种设备的价格如下表所示（残值忽略不计）：
如果开始时设备已使用1年，问每年年初应怎样作出决策，才能使5年内该项设备的购置和维修费用最少？
用动态规划求解非线性规划问题
06305012用动态规划方法求解下列非线性规划问题：
maxZ?x1?2x2?3x3
x1?3x2?2x3?12x1,x2,x3?0
06305022用动态规划方法求解下列非线性规划问题：
maxZ?4x1?7x2?8x3
2x1?3x2?4x3?8x1,x2,x3?0且为整数
06305033 将６４分成４个正数之和，使这４个数的积最大
06305043 用动态规划的方法求解如下问题：
maxz?8x1?7x2
2x1?x2?85x1?2x2?15
x1,x2?0且为整数
06305053用动态规划的方法求解如下问题：
maxz?4x1?14x2
2x1?7x2?21约束条件：7x1?2x2?21
x1,x2?0
06305063用动态规划的方法求解如下问题：
maxz??x1?2??x2x3??x4?5?
22x1?x2?x3?x4?5
x1,x2,x3,x4?0且为整数
06305073 用动态规划解下列问题：
minz??yi2
i?110约束条件：
?yi10i?8,yi?0