运筹学-第七章-动态规划.ppt

本章主要内容 多阶段决策过程及其问题举例 最短路问题 动态规划的基本概念和基本方程 动态规划应用举例 资源分配问题 背包问题 生产库存问题 ……… 7.1 多阶段决策过程及其问题举例 动态规划研究的问题—多阶段决策问题 在时间或空间上可以划分为若干阶段，每一阶段都需要根据现阶段的情况做出决策 决策者每段决策时，不仅要考虑本阶段目标最优，还应考虑之后各阶段的目标最优，最终达到整个决策活动的总体目标最优 当各个阶段的决策确定后，就构成了一个决策序列 各阶段的决策一般与时间有关，故称“动态”。但某些“静态”问题可通过引进“时间”因素，用动态规划方法来处理 动态规划分类： 离散确定性动态规划 离散随机性动态规划 连续确定性动态规划 连续随机性动态规划 （三）解法步骤 首先将问题划分为若干个阶段，然后选择状态变量与决策变量，并写出转移方程和指标函数，列出基本方程 反向条件优化 正向求最优解 7.3 应用举例 例2 资源分配问题(Ⅰ) 例3 资源分配问题(Ⅱ) 例4 背包问题 例5 生产库存问题 例6 可靠性问题 例7 机器负荷分配问题 …… 例3 资源分配问题(Ⅱ) 某工厂要进行A,B,C三种新产品的试制，为提高三种产品研制成功的概率，决定调拨经费2百万，并要求资金集中使用，也即以百万为单位进行分配，其增加研发费与新产品不成功概率的关系如表所示。问：如何分配资金，可使三种产品都研制不成功的概率最小？ 例4 背包问题 某卡车载重能力为10吨，现要装三种产品，已知每件产品的重量和利润如表。又规定产品3至多装2件。问：如何安排运输可使总利润最大？ 阶段：k=1,2,3 状态变量 sk：第 k 阶段初的可装载能力 决策变量 uk：第 k 阶段的装载件数 状态转移方程： （tk 为 k 产品的单件重量） 最优指标函数 fk(sk)：第k-3阶段采取最优策略时的最大利润 递推公式： k=3,2,1 f4(s4)=0 k =3 例5 生产库存问题 某厂在年末估计，来年4个季度市场对该厂某产品的需求量均为 dk=3 (k=1, 2, 3, 4)，而该厂每季度生产此产品的能力为 bk=5 (k=1, 2, 3, 4) 每季度生产该产品的固定成本为 F=13 (不生产时则为 0)，该产品的单位生产成本为 C=2 如果当季度产品不能售出，则需发生库存费用 g=1/件，仓库能贮存产品的最大数量 Ek=4 (k=1, 2, 3, 4) 年初年末库存为 0，而每个季度可以销售的产品是本季度初的库存及本季度的产量 试问：在满足市场需求的前提下，如何安排 4 个季度的生产使生产和库存的总费用最小? k = 4 k = 3 k = 2 k = 1 某系统由 A, B, C 三个部分串联而成，已知： ① A、B、C 相互独立 ② 各部分的单件故障率分别为 P1=0.4， P2=0.2， P3=0.5 ③ 每个部分的单件价格为：A 部分单价 c1=1 万元； B 部分单价 c2=2 万元；C 部分单价 c3=3 万元 ④ 可投资购置部件的金额为10万元 问：A, B, C 三部分各应购置多少部件才能使系统的总可靠率最大？（假设每部分至少购置一件） 阶段：购置 A、B、C 分别为阶段1、2、3 状态变量 sk：第 k 阶段初可用来购买部件的费用 决策变量 uk：第 k 阶段购置的件数 状态转移方程：sk+1 = sk - ckuk 指标函数：第 k 阶段本身的可靠率 最优指标函数 fk(sk) ：第 k 阶段尚有资金 sk 时可能获得 的最高可靠率 递推方程 fk(sk)= max dk(sk, uk)×fk+1(sk+1) k=3,2,1 f4(s4)=1 第3阶段 此时 C 应至少配备 1 个部件，故 s2≥c3=3 同时 A, B 部件已经至少配备 1个部件，故 s2≤10-c1-c2=7 第2阶段 此时 B、C 应至少各配制 1 个部件，故 s2≥c2+c3=2+3=5 同时 A 部件已经至少配备 1个部件，故 s2≤10－1=9 第1阶段 例7 机器负荷分配问题（其它情形之一）