第6章 动态规划

第第 6 章章 动态规划动态规划 判断 06100011 判断：在动态规划模型中，问题的阶段数等于问题中的子问题的数目； 06100021 判断：动态规划中，定义状态时应保证在各个阶段中所作决策的相互独立性； 06100031 判断：）动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已 做出的决策； 06100041 判断：对一个动态规划问题，应用顺推或逆推解法可能会得出不同的最优解； 06100051 判断：动态规划计算中的“维数障碍”主要是由于问题中阶段数的急剧增加而引 起的； 06100061 判断：）假如一个线性规划问题含有 5 个变量和 3 个约束，则用动态规划方法求 解时将划分为 3 个阶段，每个阶段的状态将由一个 5 维的向量组成； 06100071 判断：任何一个多阶段决策过程的最优化问题，都可以用非线性规划模型来描述。 06100081 判断： 动态规划问题如果按状态转移率区分,可分成确定性的与随机性的. 简答 06200011 简答： 一个 N 阶段的决策过程具有哪特征？ 06200021 简答：试述动态规划的优点。 06200031 简答：试述最优化原理的内容 06200041 简答：试述动态规划数学模型的四种类型. 计算题 最短路问题 06301012 设某厂自国外进口一步精密机器，由机器制造厂至出口港口可供选择，而进口港 又有三个可供选择，进口后可经由两个城市到达目的地，期间的运输成本如下图所示，试 求运费最低的路线。 50 40 A E B1 B2 C1 C2 C3 D1 D2 B3 20 30 70 40 20 30 10 60 30 30 40 4030 4030 30 40 10 机器制造厂 出口港 进口港 城市 某工厂 06301022、某工厂从国外引进一台设备，由 A 到 G 港口有多条通路可供选择，其路线及费 用如下图所示。现要确定一条从 A 到 G 的使总费用最小的路线。请将该问题描述成一个动 态规划问题，然后求其最优解。 50 40A G B C D E F 20 60 40 30 40 30 30 资源分配 06302012 有一部货车每天沿着公路给四个零售店卸下 6 箱货物，如果各零售店出售该货物 所得利润如下表所示，试求在各零售店卸下几箱货物，能使总利润最大？其值是多少？ 零售店 利润 箱数 1234 00000 14234 26455 37676 47886 57986 671086 06302022 设有某种肥料共 6 个单位重量，准备供给四块粮田用，其每块粮田施肥数量与增 产粮食数字如下表，试求对每块田施多少单位重量的肥料，才使总的增产粮食最多。 粮田 施肥1234 00000 120251828 242453947 360576165 475657874 585709080 690739585 06302033 某公司打算向承包的三个营业区增设六个销售店，每个营业地区至少增设一个， 从各区赚取的利润与增设的销售店个数有关，其数据如下表所示。 销售店增加数A 区利润B 区利润C 区利润 0 1 2 3 4 100 200 280 330 340 200 210 220 225 230 150 160 170 180 200 70 试求各区应分配几个增设的零售店，才能使总利润最大？其值是多少？ 存储控制问题 06303012 设某工厂调查了解市场情况，估计在今后四个时期市场对产品的需求量如下表所 示。 时期1234 需求量2324 假定不论在任何时期，生产每批产品的固定成本为 3（千元）就，若不生产，则为 0。每单 位生产成本费为 1（千元） 。同时任何一个时期生产能力所允许的最大生产批量为不超过 6 个单位。又设每个时期的每个单位产品库存费为 0.5（千元） ，同时规定在第一期初及第四 期 末均无产品库存。试问，该厂如何安排各个时期的生产与库存，使所花的总成本最低？ 随机性动态规划 06304013 某罐头制造公司需要在近五周内必须采购原料一批，估计未来五周内价格有波动， 其浮动价格和概率如下表所示，试求各周以什么价格购入，使采购价格的数学期望值最 小。 单价概率 9 8 7 0.4 0.3 0.3 06304021 某人外出旅游，需将 5 个物品装入背包，但背包装物重量有限制，总重量 W 不得 超过 13 千克。物品重量及价值的关系如下表所示。试问：如何装入这些物品，使背包 的价值最大？ 物品重量（千克）价值（元） A79 B54 C43 D32 E10.5 06304033 某种工业产品需经过 A，B，C 三道工序，其合格率分别为 0.70，0.60，0.80；假 设各工序的合格率相互独立，从而产(成)品的合格率为 0.70 * 0.60*0.800.336。 为了提高产品的合格率，现准备以限额为 5 万元的投资，在三道工序中采取如下表所 示的各种提高产品质量的措施。这些措施的投资金额和采取措施后各工序预期的合格 率均列在下表中。问：应采取哪些措施，才能使产(成)品的合格率达到最大? 措施项目 维持原状调整轴承 加装自停装 置 调换轴承并加装自停装 置 投资金额 0 每工序 1 万每工序 2 万元 每工序 3 万元 元 A0.700.800.900.95 B0.600.700.800.90 工序的 预期合 格率 C0.800.900.900.94 06304042 某住宅建筑公司拟建甲、乙、丙三类住宅出售。已知：甲类住宅楼每栋耗资 100 万元，售价 100 万元；乙类住宅楼每栋耗资 60 万元，售价 110 万元；丙类住宅楼每栋 耗资 30 万元，售价 70 万元。由于市政当局的限制，建造每类住宅楼不得多于三栋， 该公司共有可利用的资金 350 万元。问：应如何拟定建筑计划，方能使该公司的售房 收入最大? 06304051 某有限公司有 5 台新设备，将有选择地分配给下属三个工厂，所得效益如表所示。 问：该公司应如何分配这些设备可使总收益最大? 单元：干元 工厂新工厂台 数 0000 1354 27106 391111 4121112 5131112 06304063 设有两种资源：第一种资源有 a 单位，第二种资源有 b 单位。拟将这两种资源分 配给 N 个部门。第一种资源单位、第二种资源单位分配给部门 i 所得利润为 i x i y 。现设 a3，b=3，N=3，其利润列于下表中。问：应如何分配这两( ,) iii r x y( ,) iii r x y 种资源，使总利润最大? 111 ( ,)r x y 222 (,)r xy 333 (,)r xy i y i x 211 42() iiii cyyyy 012301230123 0013602460358 1456714672579 25678468947911 36789681011691113 06304072 某制造厂根据合同，要在 1 至 4 月份的每月底供应零件各为 40，50，60，80 件。 该厂 1 月初并无存货，至 4 月末亦不准备留存。已知每批的生产准备费用为 100 元； 若当月生产的零件交运不出去，需要仓库存贮，存贮费用为 2 元(件月)。该厂每月 的最大生产能力为 100 件。问：应如何安排生产，才能使费用总和为最小? 06304082 某公司计划在今后 4 个月内经营一种高级成衣。根据预测该种商品在 5 至 8 月份 的每套进价和售价如下表所示。已知库存能力为 600 套，5 月初有存货 2 肋套，并假 定销售是在月初进行，至月末全部售完。试对这 4 个月的购销做出安排，使总的利润 最大？ 月份 5678 进价 40384042 售价 45423944 06304093 设某种机器可以在高、低两种不同负荷下生产。若机器在高负荷下生产，则产品 的年产量。和投入生产的机器数量 x 的关系为 a=8x, ，机器的年折损率 03；若 机器在低负荷下生产，则产品年产量 b 投入生产的机器数量 x 关系为 b5x，机器的 年折损率 01。设开始时有完好机器 1000 台，要求制定一个四年计划，每年年 初分配完好机器在不同负荷下工作，使四年产品总产量达到最大。 06304102 某工厂在一年内进行 A,B，C 三种新产品试制。估计年内这三种新产品研制不成 功的概率分别为 040，060，080。厂领导为了促进三种新产品的研制，决定拨 2 万元追加研制费。假设：这些追加研制费(以万元为单元)分配给不同新产品研制时 不成功的概率分别如下表中所示。试问：应如何分配这笔追加研制费，使这三种新产 品都没有研制成功的概率最小。 不成功概率新产品 研制费ABC 00.400.600.80 10.200.400.50 20.150.200.30 06304112 一名学生要从四个系中挑选 10 门选修课程。他必须从每个系中至少选一门课， 他的目的是把 10 门课分到四个系中，使得他在四个领域中的“知识”最多。由于他对 课程内容的理解力和课程内容的重复，他认为:如果在某一个系所选的课程超过一定数 目时，他的知识就不能显著增加。为此，他采用 100 分作为衡量他的学习能力，并以 此作为在每个系选修课程的依据。经过详细调查分析得到表中各数据。试确定这名学 生选修课程的最优方案。 课 程 分数 系别 12345678910 25506080100100100100100100 207090100100100100100100100 406080100100100100100100100 102090405060708090100 06304123 考虑一家公司在今后 5 个时期内确定劳动力多少的问题。如果 5 个时期中所需劳 动力的最低数是，是 5，7，8，4，6（单位：百人） （ i=1,5） 。设（）是 i b i y i b 第 i 个时期所拥有的实际劳动力，若，将导致额外费用；若 i y i b 1 3() ii cyb ，则劳动力的费用为： 1ii yy 4 4 j j R C 11 2 42(), 0 iiii yyyy c 其他 假定=5（百人） ，试确定劳动力支出费用最小的方案。 0 y 06304133 设有一个 4 个部件串联组成的系统。为提高系统的可靠性，考虑在每个部件上并 联 1 个、2 个或 3 个同类元件，每个部件（i=1,2,3,4）配备 j 个并联元件 （j=1,2,3） 后的可靠性和 （单位百元）由下表给出。假设该系统的总成本允 ij R ij C 许为 15 千元，试问：如何确定个部件配备元件的数目，使该系统的可靠性最大？ i=1i=2i=3i=4 j 1j R 1j C 2 j R 2 j C 3 j R 3 j C 4 j R 4 j C 10.7040.6020.9030.803 20.7550.804-0.825 30.857- 06304142 某工厂使用一种关键设备，每年年初设备科需对该设备的更新与否作出决策。现 已知在 5 年内购置该种新设备的费用和各年内维修费如下表所示。试制订 5 年内的设 备更新计划，使总的支付费用最少。 单位：千元/台 第 i 年 12345 购置费用 11 11121213 第 i 年初 12345 维修费用 5681118 06304152 设有 6 万元资金用于四个工厂的扩建。已知每年工厂的利润增长同投资数额的大 小有关，详细数据见下表。问应该如何确定对着 4 个厂的投资额，使总利润增长最大。 0100200300400500600 10204260758590 20254557657073 30183961789095 40284765748085 接接 06304163 某项工程有个设计方案。据现在有条件，这些方案不能完成的概率分别为 0.40,0.60,0.80,即个方案均完不成的概率为。为使这个0.40 0.60 0.800.192 方案中至少完成一个的概率尽可能大，决定追加万元资金。当使用追加投资后，上 述方案完不成的概率见下表问应如何分配追加投资，才能使其中止至少一个方案完 成的概率为最大 追加投资（万元） 0.400.600.80 10.200.400.50 20.150.200.30 06304172 设有某种机器设备，用于完成两种工作甲和乙。几年初完好的机器数量为， k x 若以数量用于工作甲，余下的用于工作乙，则该年的预期收入为 k u() kk xu 。已知。又设备再使用中会有损耗，设机器用于工作 () kkk g uh xu 8 kk g uu 甲，一年后能继续使用的完好机器数量占年初投入量的；若用于乙项工作时， 一年后能继续使用的完好机器数量占年初投入量的，即下一年初能使用于完成 这两项工作的机器数为设第一年初完好的机器总数为 1 7%() 90% kkkk xuxu AA 。问在年内应该如何分配甲，乙两项工作的机器数，才能使年的总收益 为最大？ 06304183 某商店在未来的 4 个月里，准备利用商店的一个仓库专门经销某种商品，该仓库 最多能装这种商品 1000 单位。假定商店每月只能卖出仓库现有的货。当商店决定在某 个月购货时，只有在该月的下个月才能得到该货物，据估计在未来 4 个月这种商品买 卖价格如表所示。假定商店在 1 月份开始经销时，仓库储存该商品 500 单位。问如何 制定这 4 个月的定购与销售计划，使获得利润最大（不考虑仓库的储存费用） 月份（k） 买价（） k C卖价（） k P 11012 299 31113 41517 06304191 某仓库有一辆载重量为 10 吨的卡车，现要装运以下三种货物，这三种货物的每 件重量和单价如下表所示： 货 物每 件 重 量单 价 A240 B358 C472 现在要确定这三种货物应各装几件，才能使每辆卡车所装货物的价值最大。如果用动态 规划解这个问题，试确定阶段、各阶段的方案及其相应的数量指标和各阶段的状态。 06304201 某公司准备在甲、乙、丙三个地区设置四个销售点。根据预测资料，在各地区设 置个数不同的销售点后，每月所得到的利润（单位：百元）见下表： 销 售 点 个 数 地 区 01234 甲016284050 乙013243442 丙012223647 现在要确定在各地区应设置几个销售点，才能使每个月所获得的总利润最大。如果用动 态规划解这个问题，试确定阶段、各阶段的方案及其相应的数量指标和各阶段的状态。 06304211 某仓库有一辆载重量为 10 吨的卡车，现要装运以下三种货物，这三种货物的每 件重量和单价如下表所示： 货 物每 件 重 量单 价 A240 B358 C472 定义最优指标函数并写出基本方程。 06304221 某公司准备在甲、乙、丙三个地区设置四个销售点。根据预测资料，在各地区设 置个数不同的销售点后，每月所得到的利润（单位：百元）见下表： 销 售 点 个 数 地 区 01234 甲016284050 乙013243442 丙012223647 定义最优指标函数并写出基本方程。 06304232 某公司有五套新设备，拟分配给所属的一厂、二厂、三厂。各厂将不同套数的新 设备投入生产后，每年创造的产值（单位：万元）如下表所示： 新 设 备 的 套 数 厂 名 012345 一 厂03791214 二 厂058101316 三 厂046111215 现在要确定应怎样分配这五套新设备，才能使整个公司所增加的总产值最多。如果用动 态规划的逆序计算解这个问题，试确定阶段、各阶段的方案及其相应的数量指标和各阶段 的状态，并写出基本方程。用逆序方法求解 06304242 假定某厂在明年头四个月对燃料的需求量以及各月的固定订货费和单位存储费用 如下表所示： 月 份 i需求量（吨） i 固定订货费 ki（元）单位存储费用 hi（元） 1220050 2215040 3110040 4410040 如果每吨燃料的价格是 800 元，该厂在每月开始时采购。用动态规划方法确定每月的 采购量，试总成本最小。 06304253 某工厂的一种产品在明年头四个月的计划产量分别是 3 千件、4 千件、5 千件和 3 千件。工厂在生产该种产品时，每月需负担固定成本 10 万元，如当月未生产该种产 品，则不负担固定成本。单位变动成本（原材料、工资和直接动力费等）在 1 月份和 2 月份是 50 元，在 3 月份和 4 月份是 45 元。由于设备的限制，每月最多只能生产该 种产品 5 千件。又当月生产的该种产品如未能售出，则转入库存后，每月要负担每件 8 元的存储费用。 假定在明年年初该种产品无存货，到 4 月底时所有产品都能售出。问明年头四个月应 各生产该种产品多少件，才能使生产和存储的总成本最少。 06304263 如果要考虑某种设备在今后 4 年内的更新问题，并且新的设备成本是 6.7 万元， 使用 t 年后的残值在 t4 时，；t4 时，；使用 t 年后每年所创造的 4s tt 0s t 利润在 t4 时