管理运筹学第四版 10第十章 动态规划

《管理运筹学第四版 10第十章 动态规划》由会员分享，可在线阅读，更多相关《管理运筹学第四版 10第十章 动态规划（84页珍藏版）》请在金锄头文库上搜索。

1、 管理运筹学 第十章动态规划 0 前言 动态规划是解决多阶段决策过程最优化问题的一种方法 它将困难的多阶段决策问题变换成一系列互相联系较容易的单阶段问题 解决了这一系列较容易的单阶段问题 也就解决了复杂的多阶段决策问题 可以解决管理中的问题 最短路问题 装载问题 库存问题 资源分配问题 生产过程最优化问题等可以分为 离散确定性决策过程 离散随机性决策过程 连续确定性决策过程 连续随机性决策过程 多阶段决策过程最优化问题举例 基本概念 基本方程与最优化原理 动态规划的应用 1 动态规划的应用 2 多阶段决策过程最优化问题举例 例1最短路径问题下图表示从起点A到终点E之间各点的距离 求A到E的最短

2、路径 B C B D B C D E C 4 1 2 3 1 2 3 1 2 3 2 2 1 6 4 7 2 4 8 3 8 6 7 5 6 1 10 6 3 7 5 1 1 1多阶段决策过程最优化问题举例 讨论 以上求从A到E的最短路径问题 可以转化为四个性质完全相同 但规模较小的子问题 即分别从Di Ci Bi A到E的最短路径问题 1 1多阶段决策过程最优化问题举例 第四阶段 两个始点D1和D2 终点只有一个 分析得知 从D1和D2到E的最短路径唯一 1 第三阶段 有三个始点C1 C2 C3 终点有D1 D2 分别求C1 C2 C3到D1 D2的最短路径问题 分析得知 如果经过C1 则最

3、短路为C1 D2 E 如果经过C2 则最短路为C2 D2 E 如果经过C3 则最短路为C3 D1 E 多阶段决策过程最优化问题举例 1 第二阶段 始点B1 B2 B3 B4 终点C1 C2 C3 分别求B1 B2 B3 B4到C1 C2 C3的最短路径问题 分析得知 如果经过B1 则走B1 C2 D2 E 如果经过B2 则走B2 C3 D1 E 如果经过B3 则走B3 C3 D1 E 如果经过B4 则走B4 C3 D1 E 1 多阶段决策过程最优化问题举例 第一阶段 只有1个始点A 终点有B1 B2 B3 B4 分别求A到B1 B2 B3 B4的最短路径问题 可以得到 从A到E的最短路径为A

4、B4 C3 D1 E 1 多阶段决策过程最优化问题举例 以上计算过程及结果 可用下图表示 不仅得到了从A到D的最短路径 同时也得到了从图中任一点到E的最短路径 以上过程 仅用了22次加法 计算效率远高于穷举法 B C B D B C D E C 4 1 2 3 1 2 3 1 2 3 3 2 1 6 4 7 2 4 8 3 8 6 7 5 1 6 10 6 0 10 6 12 11 11 12 13 14 14 12 7 5 1 2 1 多阶段决策过程最优化问题举例 多阶段决策过程最优化问题举例 基本概念 基本方程与最优化原理 动态规划的应用 1 动态规划的应用 2 一 基本概念 1 阶段k

5、表示决策顺序的离散的量 可以按时间或空间划分 2 状态sk 能确定地表示决策过程当前特征的量 可以是数量 字符 数量状态可以连续 离散 3 决策xk 从某一状态向下一状态过渡时所做的选择 是所在状态的函数 记为xk sk 4 决策允许集合Dk sk 在状态sk下 允许采取决策的全体 5 策略Pk n sk 从第k阶段开始到最后第n阶段的决策序列 称k子策略 P1 n s1 即为全过程策略 2 基本概念 基本方程与最优化原理 6 状态转移方程sk 1 Tk sk xk 某一状态及该状态下的决策 与下一状态之间的函数关系 7 阶段指标函数vk sk xk 从状态sk出发 选择决策xk所产生的第k阶

6、段指标 8 过程指标函数Vk n sk xk xk 1 xn 从状态sk出发 选择决策xk xk 1 xn所产生的过程指标 过程指标具有可分离性 若Vk n sk xk xk 1 xn vk sk xk Vk 1 sk 1 xk 1 xn 称指标具有可加性 若Vk n sk xk xk 1 xn vk sk xk Vk 1 sk 1 xk 1 xn 称指标具有可乘性 2 基本概念 基本方程与最优化原理 二 基本方程 最优指标函数fk sk 从状态sk出发 对所有的策略Pk n 过程指标Vk n的最优值 即对于可加性指标函数 上式可以写为上式中 opt 表示 max 或 min 对于可乘性指标函

7、数 上式可以写为称为动态规划最优指标的递推方程 终端条件 为了使以上的递推方程有递推的起点 必须要设定最优指标的终端条件 一般 对加指标 最后一个状态n 1下最优指标fn 1 sn 1 0 2 基本概念 基本方程与最优化原理 三 最优化原理作为整个过程的最优策略具有如下性质 不管在此最优策略上的某个状态以前的状态和决策如何 对该状态来说 以后的所有决策必定构成最优子策略 就是说 最优策略的任意子策略都是最优的 2 基本概念 基本方程与最优化原理 多阶段决策过程最优化问题举例 基本概念 基本方程与最优化原理 动态规划的应用 1 动态规划的应用 2 一 资源分配问题例2 某公司拟将某种设备5台 分

8、配给所属的甲 乙 丙三个工厂 各工厂获得此设备后 预测可创造的利润如表所示 问这5台设备应如何分配给这3个工厂 使得所创造的总利润为最大 解 按甲 乙 丙工厂分为三个阶段 编号1 2 3 设 分配给第k个厂至第3个厂的设备台数 分配给第k个厂的设备台数 已知 并有从与的定义和本题目已知数据的特点 可知 第三阶段 将台设备都分配给第3工厂时 第3阶段的指标值 盈利 为最大 即由于第3阶段是最后的阶段 故有其中可取值为0 1 2 3 4 5 其数值计算见表 表示取3子过程上最优指标值时的的决策 例 在表中可知当时 有此时 即当时 此时取 把4台设备分配给第3厂 是最优决策 此时阶段指标值 盈利 为

9、12 最优3子过程最优指标值也为12 第二阶段 当把台设备分配给第2工厂和第3工厂时 则对每个值 有一种最优分配方案 使最大盈利 即最优2子过程最优指标函数值为 因为上式也可写成 数值计算如表 例如在的这一行里 当时 查前两表可知 当时 同样可知当时 当时 当时 由于 不可能分2厂5台设备 故当时 栏不填 从这些数值中取最大 即得 在取最大值的上加一横 可知的最优决策为1或2 第一阶段 把台设备分配给第1 第2 第3厂时 最大盈利为其中然后按计算表格的顺序推算 可知最优分配方案有两个 1 由于 根据 查表10 7可知 再由 求得 即分配给甲厂0台 乙厂2台 丙厂3台 2 由于 根据 查表10

10、7可知 再由 求得 即分配给甲厂2台 乙厂2台 丙厂1台 这两种分配方案都能得到最高的总盈利21万元 二 背包问题设有种物品 每种物品数量无限 第种物品每件重量为公斤 每件价值元 现有一只可装载重量为公斤的背包 求各种物品应各取多少件放入背包 使背包中物品的价值最高 用整数规划模型来描述 设为第种物品装入背包的件数 背包中物品的总价值为 则且为整数 用动态规划方法解 设阶段变量 第k次装载第k种物品状态变量 第k次装载时背包还可以装载的重量 决策变量 第k次装载第k种物品的件数 决策允许集合 状态转移方程 阶段指标 最优过程指标函数 第k到n阶段容许装入物品的最大价值 递推方程 终端条件 例3

11、 某咨询公司有10个工作日可以去处理四种类型的咨询项目 每种类型的咨询项目中待处理的客户数量 处理每个客户所需工作日数以及所获得的利润如表所示 显然该公司在10天内不能处理完所有的客户 它可以自己挑选一些客户 其余的请其他咨询公司去做 应如何选择客户使得在这10个工作日中获利最大 解 我们把此问题分成四个阶段 第一阶段我们决策将处理多少个第一种咨询项目类型中的客户 第二阶段决策将处理多少个第二种咨询项目类型中的客户 第三阶段 第四阶段我们也将作出类似的决策 设 分配给第k种咨询项目到第四种咨询项目的客户的总工作日 第k阶段的状态变量 在第k种咨询项目中处理客户的数量 第k阶段的决策变量 已知

12、10 并有 第四阶段 将个工作日尽可能分配给第四类咨询项目 即时 第四阶段的指标值为最大 表示取不大于的最大整数 符号为取整符号 故有由于第四阶段是最后的阶段 故有 因为至多为10 数值计算见表 第三阶段 当把个工作日分配给第四类和第三类咨询项目时 则对每个值 都有一种最优分配方案 使其最大盈利即最优3子过程最优指标函数值为因为 故因为至多为10 所以的取值可为0 1 2 数值计算见表 第二阶段 同样以每个值都有一种最优分配方案 使其最大盈利即最优2子过程最优指标函数值为 因为 故因为至多为10 所以的取值为0 1 2 3 其数值计算见表 第一阶段 已知 又因为 同样有因为 故可取值为0 1

13、2 10 其数值计算见表 由上表知 从而 由表的的这一行可知由由表的的这一行可知由 查表的这一行得综上所述得最优解为 最大盈利为28 现在我们假设该咨询公司的工作计划有所改变 只有8个工作日来处理这四类咨询项目 那么该咨询公司如何选择客户使得获利最大 我们只要在第一阶段上把改成8 重新计算即可 如下表所示 这是动态规划的一个好处 从而得到两组最优解如下 最优解 即最大盈利 都为22 一旦咨询的工作日不是减少而是增加 那么我们不仅要重新计算第一阶段 而且要在第二 第三 第四阶段的计算表上补上增加的工作日的新的信息 也可得到新的结果 三 生产与存贮问题例4 某公司为主要电力公司生产大型变压器 由于

14、电力采取预订方式购买 所以该公司可以预测未来几个月的需求量 为确保需求 该公司为新的一年前四个月制定一项生产计划 这四个月的需求如表所示 生产成本随着生产数量而变化 调试费为4 除了调试费用外 每月生产的头两台各花费为2 后两台花费为1 最大生产能力每月为4台 生产成本如表所示 每台变压器在仓库中由这个月存到下个月的储存费为1 仓库的最大储存能力为3台 另外 1月1日时仓库里存有一台变压器 要求在4月30日仓库的库存量为零 试问 该公司应如何制定生产计划 使得四个月的生产成本和储存总费用最少 解 第k个月为第i阶段设为第k阶段期初库存量 为第k阶段生产量 为第k阶段需求量 因为下个月的库存量等

15、于上个月的库存量加上上个月的产量减去上个月的需求量 得到状态转移方程 因为 故有因为 故有 由于必须要满足需求 则有通过移项得到另一方面 第k阶段的生产量必不大于同期的生产能力 4台 也不大于第k阶段至第四阶段的需求之和与第k阶段期初库存量之差 否则第k阶段的生产量就要超过从第k阶段至第四阶段的总需求 故有 第四阶段 从状态转移方程可知这样就有阶段指标可以分成生产成本与储存费 即由于第四阶段末要求库存为零 即有 可得 对于每个的可行值 的值列于表 当时 可知第四阶段要生产台 总成本为9 同理算出当为1 2 3时的情况 第三阶段 此时有 因为以及所以有结果所示 计算结果如表所示 第二阶段 因为所

16、以有 第一阶段 因为故有计算结果见表 利用递推关系得到两组最优解 这时有最低总成本29 四 系统可靠性问题例5 某科研项目组由三个小组用不同的手段分别研究 它们失败的概率各为0 40 0 60 0 80 为了减少三个小组都失败的可能性 现决定给三个小组中增派两名高级科学家到各小组 各小组科研项目失败概率如下表 问如何分派科学家才能使三个小组都失败的概率 即科研项目最终失败的概率 最小 解 用逆序算法 设阶段 每个研究小组为一个阶段决策变量 分配给第n小组的高级科学家数目 相应的失败概率为 状态变量 在阶段n时可分配于阶段的高级科学家人数 递推关系 当n 3时 当n 2时 当n 1时 最优解为x1 1 x2 0 x3 1 科研项目最终失败的概率为0 060 多阶段决策过程最优化问题举例 基本概念 基本方程与最优化原理 动态规划的应用 1 动态规划的应用 2 一 连续确定性动态规划对于状态变量和决策变量只取连续值 过程的演变方式为确定性时 这种动态规划问题就称为连续确定性动态规划问题 机器负荷分配问题例1一种机器能在高低两种不同的负荷状态下工作 设机器在高负荷下生产时 产量函数为P1 8u