动态规划教学课件PPT.ppt

1 第六章动态规划 1问题的提出 2基本概念 基本方程与最优化原理 3动态规划的应用 2 1问题的提出 一 引例 最短路径问题下图表示从起点a到终点e之间各点的距离 求a到e的最短路径 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 3 1问题的提出 用穷举法的计算量 非常大 讨论 1 以上求从a到e的最短路径问题 可以转化为四个性质完全相同 但规模较小的子问题 即分别从di ci bi a到e的最短路径问题 第四阶段 两个始点d1和d2 终点只有一个 表6 1分析得知 从d1和d2到e的最短路径唯一 4 第三阶段 有三个始点c1 c2 c3 终点有d1 d2 对始点和终点进行分析和讨论分别求c1 c2 c3到d1 d2的最短路径问题 表6 2分析得知 如果经过c1 则最短路为c1 d2 e 如果经过c2 则最短路为c2 d2 e 如果经过c3 则最短路为c3 d1 e 1问题的提出 5 第二阶段 有4个始点b1 b2 b3 b4 终点有c1 c2 c3 对始点和终点进行分析和讨论分别求b1 b2 b3 b4到c1 c2 c3的最短路径问题 表6 3分析得知 如果经过b1 则走b1 c2 d2 e 如果经过b2 则走b2 c3 d1 e 如果经过b3 则走b3 c3 d1 e 如果经过b4 则走b4 c3 d1 e 1问题的提出 6 第一阶段 只有1个始点a 终点有b1 b2 b3 b4 对始点和终点进行分析和讨论分别求a到b1 b2 b3 b4的最短路径问题 表6 4最后 可以得到 从a到e的最短路径为a b4 c3 d1 e 1问题的提出 7 以上计算过程及结果 可用图2表示 可以看到 以上方法不仅得到了从a到e的最短路径 同时 也得到了从图中任一点到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问题的提出 8 1问题的提出 从引例的求解过程中可以得到以下启示 1 对一个问题是否用上述方法求解 其关键在与能否将问题转化为相互联系的多个阶段的决策问题 2 对问题的求解是从全局考虑解决局部 阶段 的问题 3 各阶段选取的决策依赖于当前的状态 又随即引起状态的转移 整个决策序列就是在变化的状态中产生出来 故有 动态 含义 4 决策过程是与阶段发展过程逆向而行 9 1问题的提出 二 动态规划的含义及适用范围1 动态规划动态规划是解决一类多阶段决策问题的优化方法 它是考察问题的一种途径 而不是一种算法 多阶段决策问题 把一个问题看作是一个前后关联具有链状结构的多阶段过程 也称为序贯决策过程 2 适用范围如果一个问题可将其过程划分为若干个相互联系的阶段问题 且它的每一阶段都需要进行决策 则这类问题均可用动态规划方法进行求解 10 一 基本概念1 阶段和阶段变量用动态规划方法求解问题时 首先将问题的全过程适当地分成若干个互相联系的阶段 以便能按一定的次序去求解 阶段的划分 一般根据时序和空间的自然特征来划分 如引例可按照空间划分为4个阶段 阶段变量 描述阶段的变量称为阶段变量 用k表示 引例中 k 1 2 3 4 2 状态和状态变量sk状态就是阶段的起始位置 它既是该阶段某支路的起点 又是前一阶段某支路的终点 状态可以是数量 也可以是字符 数量状态可以是连续的 也可以是离散的 2基本概念 基本方程与最优化原理 11 2基本概念 基本方程与最优化原理 状态变量 描述过程状态的变量称为状态变量 它可用一个数 一组数或一向量 多维情形 来描述 常用sk第k阶段的状态变量 通常一个阶段有若干个状态 第k阶段的状态就是该阶段所有始点的集合 3 决策与决策变量决策 在某阶段对可供选择状态的决定 或选择 决策变量 描述决策的变量 常用xk sk 表示第k阶段处于状态sk时的决策变量 它是状态变量的函数 4 策略与子策略策略是一个决策序列的集合 由所有各阶段的决策组成的决策函数序列称为全过程策略 简称策略 记为 p1 n s1 子策略 从第k个阶段开始到最后阶段的决策组成的决策函数序列称为k子过程策略 简称子策略 记为 pk n sk 最优策略 能够达到总体最优的策略 12 2基本概念 基本方程与最优化原理 5 状态转移方程它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程 用sk 1 tk sk xk 表示 该方程描述了第k阶段到第k 1阶段的状态转移规律 因此又称为状态转移函数 6 阶段指标函数rk sk xk 从状态sk出发 选择决策xk所产生的第k阶段指标 7 最优指标函数fk sk 表示从第k阶段的状态sk开始采用最优子策略 到第n阶段的终止时所得到的最优指标函数值 13 二 基本方程最优指标的递推方程 动态规划的基本方程 对于可加性指标函数 上式可以写为上式中 opt 表示 max 或 min 对于可乘性指标函数 上式可以写为终端条件 为了使以上的递推方程有递推的起点 必须要设定最优指标的终端条件 一般最后一个状态n 1下最优指标fn 1 sn 1 0 2基本概念 基本方程与最优化原理 14 三 最优化原理作为整个过程的最优策略具有如下性质 不管在此最优策略上的某个状态以前的状态和决策如何 对该状态来说 以后的所有决策必定构成最优子策略 就是说 最优策略的任意子策略都是最优的 2基本概念 基本方程与最优化原理 15 2基本概念 基本方程与最优化原理 四 动态规划求解过程 1 将问题的过程划分成恰当的阶段 2 正确选择状态变量sk 使它能够恰当地描述过程的演变 3 确定决策变量xk 4 正确写出状态转移方程sk 1 tk sk xk 5 写出最优指标的递推方程 fn 1 sn 1 0终点条件 16 一 资源分配问题例2 某公司拟将某种设备5台 分配给所属的甲 乙 丙三个工厂 各工厂获得此设备后 预测可创造的利润如表10 5所示 问这5台设备应如何分配给这3个工厂 使得所创造的总利润为最大 表8 5 3动态规划的应用 17 解 1 划分阶段 将问题按工厂分为三个阶段 甲 乙 丙三个厂分别编号为1 2 3厂 2 确定状态变量 设sk 分配给第k个厂至第3个厂的设备台数 k 1 2 3 3 确定决策变量 设xk 分配给第k个设备台数 4 写出状态转移方程 已知s1 5 并有 3动态规划的应用 18 第三阶段 表6 6 3动态规划的应用 19 第二阶段 表6 7 3动态规划的应用 20 第一阶段 把台设备分配给第1 第2 第3厂时 最大盈利为其中可取值0 1 2 3 4 5 数值计算见表8 8表6 8然后按计算表格的顺序推算 可知最优分配方案有两个 1 由于 根据 查表6 7可知 再由 求得 即分配给甲厂0台 乙厂2台 丙厂3台 2 由于 根据 查表6 7可 3动态规划的应用 21 知 再由 求得 即分配给甲厂2台 乙厂2台 丙厂1台 这两种分配方案都能得到最高的总盈利21万元 3动态规划的应用 22 二 背包问题设有n种物品 每一种物品数量无限 第i种物品每件重量为wi公斤 每件价值ci元 现有一只可装载重量为w公斤的背包 求各种物品应各取多少件放入背包 使背包中物品的价值最高 这个问题可以用整数规划模型来描述 设xi为第i种物品装入背包的件数 i 1 2 n 背包中物品的总价值为z 则maxz c1x1 c2x2 cnxns t w1x1 w2x2 wnxn wx1 x2 xn 0且为整数 3动态规划的应用 23 下面用动态规划逆序解法求解它 设 1 阶段变量k 第k次装载第k种物品 k 1 2 n 2 状态变量sk 第k次装载时背包还可以装载的重量 3 决策变量uk xk 第k次装载第k种物品的件数 4 状态转移方程 sk 1 sk wkxk 5 最优过程指标函数fk sk 第k到n阶段容许装入物品的最大使用价值 阶段指标 rk ckxk 递推方程 fk sk max ckxk fk 1 sk 1 max ckxk fk 1 sk wkxk x dk sk 终端条件 fn 1 sn 1 0 3动态规划的应用 24 例3 某咨询公司有10个工作日可以去处理四种类型的咨询项目 每种类型的咨询项目中待处理的客户数量 处理每个客户所需工作日数以及所获得的利润如表6 9所示 显然该公司在10天内不能处理完所有的客户 它可以自己挑选一些客户 其余的请其他咨询公司去做 应如何选择客户使得在这10个工作日中获利最大 表6 9 3动态规划的应用 25 解 用动态规划来求解此题 1 把此问题分成四个阶段 第一阶段我们决策将处理多少个第一种咨询项目类型中的客户 第二阶段决策将处理多少个第二种咨询项目类型中的客户 第三阶段 第四阶段我们也将作出类似的决策 2 设状态变量 分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日 第k阶段的状态变量 3 设决策变量 在第k种咨询项目中处理客户的数量 第k阶3段的决策变量 4 写出状态转移方程已知 10 并有 3动态规划的应用 26 并从与的定义可知从第四阶段开始计算 显然将个工作日尽可能分配给第四类咨询项目 即时 第四阶段的指标值为最大 其中 表示取不大于的最大整数 符号为取整符号 故有由于第四阶段是最后的阶段 故有 3动态规划的应用 27 因为至多为10 其数值计算见表6 10 表6 10 3动态规划的应用 28 第三阶段 当把个工作日分配给第四类和第三类咨询项目时 则对每个值 都有一种最优分配方案 使其最大盈利即最优3子过程最优指标函数值为因为因为至多为10 所以的取值可为0 1 2 其数值计算见表6 11 3动态规划的应用 29 表6 11 3动态规划的应用 30 第二阶段 同样以每个值都有一种最优分配方案 使其最大盈利即最优2子过程最优指标函数值为 因为 故有因为至多为10 所以的取值为0 1 2 3 其数值计算见表6 12 3动态规划的应用 31 3动态规划的应用 表6 12 32 第一阶段 我们已知 又因为 同样有因为 故可取值为0 1 2 10 其数值计算见表6 13 表6 13 3动态规划的应用 33 从表6 13可知 从而得 10 0 10 在表6 12的的这一行可知 由 查表6 11的的这一行可知 最后由 查表6 10的的这一行得 综上所述得最优解为 此时最大盈利为28 现在我们不妨假设该咨询公司的工作计划有所改变 只有8个工作日来处理这四类咨询项目 那么该咨询公司如何选择客户使得获利最大呢 我们不必从头开始重做这个问题 而只要在第一阶段上把改成8 重新计算就可得到结果 如表6 14所示 这是动态规划的一个好处 3动态规划的应用 34 表6 14如上一样可从表6 14 6 12 6 11 6 10得到两组最优解如下 它们的最优解 即最大盈利 都为22 一旦咨询的工作日不是减少而是增加 那么我们不仅要重新计算第一阶段 而且要在第二 第三 第四阶段的计算表上补上增加的工作日的新的信息 也可得到新的结果 3动态规划的应用 35 实际上 背包问题我们也可以用整数规划来求解 如果背包携带物品重量的限制为w公斤 这n种物品中第i种物品的重量为 价值为 第i种物品的总数量的 我们可以设表示携带第i种物品的数量 则其数学模型为 s t 且为整数 我们不妨用此模型去求解例3 也一定得出同样的结果 3动态规划的应用 36 三 生产与存贮问题例4 某公司为主要电力公司生产大型变压器 由于电力采取预订方式购买 所以该公司可以预测未来几个月的需求量 为确保需求 该公司为新的一年前四个月制定一项生产计划 这四个月的需求如表6 15所示 生产成本随着生产数量而变化 调试费为4 除了调度费用外 每月生产的头两台各花费为2 后两台花费为1 最大生产能力每月为4台 生产成本如表6 16所示 表6 15 3动态规划的应用 37 表6 16每台变压器在仓库中由这个月存到下个月的储存费为1 仓库的最大储存能力为3台 另外 知道在1月1日时仓库里存有一台变压器 要求在4月30日仓库的库存量为零 试问该公司应如何制定生产计划 使得四个月的生产成本和储存总费用最少 解 1 我们按月份来划分阶段 第i个月为第i阶段 i 1 2 3 4 2 设为第k阶段期初库存量 k 1 2 3 4 3动态规划的应用 38 3 为第k阶段生产量 k 1 2 3 4为第k阶段需求量 k 1 2 3 4 这已在表10 15中告诉我们 4 写出状态转移方程因为下个月的库存量等于上个月的库存量加上上个月的产量减去上个月的需求量 我们就得到了如下状态转移方程 因为 故有因为 故有 3动态规划的应用 39 由于必须要满足需求 则有通过移项得到另一方面 第k阶段的生产量必不大于同期的生产能力 4台 也不大于第k阶段至第四阶段的需求之和与第k阶段期初库存量之差 否则第k阶段的生产量就要超过从第k阶段至第四阶段的总需求 故有以下我们从第四阶段开始计算 从以上的状态转移方程可知这样就有 3动态规划的应用 40 这里的阶段指标可以分成两部分 即生产成本与储存费 即为由于第四阶段末要求库存为零 即有 这样可得对于每个的可行值 的值列于表6 17 表6 17 3动态规划的