运筹学chap.6 动态规划 Dynamic Programming.ppt

第六章 动态规划(Dynamic Programming) 用穷举法的计算量:从A到G的6个阶段，一共有48条路线，比较47次。 动态规划的基本概念 最短路问题：某运输公司拟将一批货物从A地运往E地，其间的交通系统网络如下图所示。图上节点表示地点，边表示两地之间的道路，边上的数字表示两地间的运输费用，求运输费用最低的运输路线。 例3：某公司打算在三个不同的地区设置四个销售点，据市场预测部门估计，在不同的地区设置不同数量的销售点，每月可获得的利润如下表所示。试问在各个地区应该如何设置销售点，才能使每月获得的总利润最大？其值是多少？请用动态规划方法分析求解。 解：根据多阶段决策问题的特征，将此问题转化为三个阶段的决策问题。 7. 动态递推方程：f（Sk）= Max ? V（Sk ，Uk）+ f（Sk+1）? k = 2，1 f（S3）= Max ? V（S3 ，U3）? 动态规划适用于求解哪一类问题？ 每个阶段的最优决策过程只与本阶段的初始状态有关，而与以前各阶段的决策（即为了到达本阶段的初始状态而采用哪组决策路线无关）。换言之，本阶段之前的状态与决策，只是通过系统在本阶段所处的初始状态来影响本阶段及以后各个阶段的决策。或者说，系统过程的历史只能通过系统现阶段的状态去影响系统的未来。 具有这种性质的状态称为无后效性（即马尔科夫性）状态。 动态规划方法只适用于求解具有无后效性状态的多阶段决策问题。 解：1. 划分阶段 根据问题的性质，按照时间、空间、变量划分为若干阶段，这是用多阶段决策过程描述一个实际问题的第一步。一个阶段表示需要做出一次决策的子问题，建立动态规划模型要求每个阶段问题具有同一模式。描述阶段的变量称为阶段变量，常用自然数k表示。 可划分为3个阶段求解，对甲产品增加研制费记为第1阶段，对乙产品增加研制费记为第2阶段，对丙产品增加研制费记为第3阶段，k=1，2，3。 2. 确定状态变量及相应的取值范围 多阶段决策过程的进展，可用各阶段的状态演变来描述。状态必须包含表示系统情况和确定决策所需要的全部信息，使其能反映过程的演变特征。同时还要状态满足无后效性，即若已知过程现在处于某一阶段的某一状态，则该阶段以后过程的演变，不再受以前各阶段状态的影响。确定状态变量之后，根据具体问题的性质，找出状态变量在各阶段的取值范围。 把有可能提供的研制费用作状态变量，记为sk，取值为0，1，2（万元） 3. 确定决策变量 决策变量一般由系统最优化的目的所决定。 把给第K种新产品的研制费用的数量作为决策变量uk, 显然，uk不能超过当时拥有的金额sk 即： uk≤sk 4. 建立状态转移方程 根据状态变量和决策变量的含义，写出状态 转移方程。 2、顺推法 一、背包问题 二. 投资分配问题 三、排序问题 背包问题 一位旅行者携带背包旅游，已知他的背包所能承受的重量为w千克，现有n种物品可供他选择装入包中，第i种物品的单件重量为wi 千克，其价值是携带数量 的函数 。问旅行者应如何选择携带物品的件数，使总价值最大？ 生产计划问题 已知企业产品的生产费用、存储费用和市场的需求量，在其生产能力和存储能力许可的前提下，怎样制定各个时期的生产计划，既能完成交货任务，又使总支出最小。 某中转仓库要按月在月初供应一定数量的某种部件给总装车间，由于生产条件的变化，生产车间在各月份中生产每单位这种部件所需耗费的工时不同，各月份的生产量于当月的月底前，全部要存入仓库以备后用。已知总装车间的各个月份的需求量以及在加工车间生产该部件每单位数量所需工时，仓库容量和开始库存量，要求最终库存量为0，要制定一个半年的逐月生产计划，既满足需要和仓库容量的限制，又使生产这种部件的总耗费工时数最少。 生产计划问题 货物存储问题 考虑下面三个月的库存问题，在每月初，公司必须决定在本月内，应生产多少产品。在一个月内生产x单位的产品，所需成本为c(x)，其中c(0)=0，当x0时，c(x)=3+2x。每月最多生产4个单位，每月的需求是随机的，或为1或为2单位。如果生产的数量大于需求，就出现库存。每个月末检查库存，1个单位的库存费用是1元。因为库存能力有限，每月末的库存量不能超过3单位。但同时要求必须及时满足需求。在第3个月末要把现有的库存以每单位2元的价格售出。在第1月的月初，公司有1单位的库存。如何制定生产策略使三个月内的期望费用最小。 设备更新问题 在企业中，经常遇到设备陈旧或部分损坏需要更新的问题。从经济上分析，一种设备应该使用多少年后进行更新最合算。这就是