湖北工业大学运筹学 动态规划.ppt

5.4 动态规划应用 5.4.1 资源分配问题 2.建立基本方程 令最优值函数 为将设备 分配给用户 k 到用户 n 所获得的最大受益。 3.逆序递推计算 （1）k=3时， 对 的每个取值，分别求出决策变量 的取值范围。 则 当 时， 当 时， 当 时， 当 时， 当 时， 5.4 动态规划应用 5.4.1 资源分配问题 3.逆序递推计算 状态转移方程： 则 表1 第3阶段分配设备所得收益 （2）k=2时， 对 的每个取值，分别求出决策变量 的取值范围。 当 时， 当 时， 当 时， 当 时， 当 时， 5.4 动态规划应用 5.4.1 资源分配问题 3.逆序递推计算 状态转移方程： （2）k=2时， 基本方程： 同理可计算 结果如表2所示 表2 第2阶段分配设备所得收益 5.4 动态规划应用 5.4.1 资源分配问题 3.逆序递推计算 基本方程： 表3 第1阶段分配设备所得收益 （3）k=1时， 5.4 动态规划应用 5.4.1 资源分配问题 4.求全过程最优指标函数与最优策略 全过程最优指标函数： 第1阶段，最优决策 第2阶段初的最优状态 ，最优决策 第3阶段初的最优状态 ，最优决策 各自阶段的收益分别为：60万元、40万元、64万元。 最优策略：分给甲3套、丙1套、不分给乙。 5.4 动态规划应用 构造动态规划的数学模型方法： 1.划分阶段，确定阶段变量k； 2.选择状态变量 及取值范围； 状态变量要满足两个条件：① 能描述过程演变的状态 ② 满足无后效性 3.选择决策变量 及各阶段允许决策集合 4.建立状态转移方程 5.确定阶段指标 和指标函数 6.写出基本方程，即最优值函数满足的递推关系式及端点条件。 在运用动态规划方法解决多阶段决策问题时，关键是根据题意建立动态规划的 数学模型。对模型进行求解，可采用逆序法或顺序法，通常多采用前者。 无后效性：问题从某个阶段往后 的发展演变完全由该问题在本阶 段所处的状态及决策决定，与该 问题以前的状态和决策无关。 湖北工业大学 第5章 动态规划 实际经济社会活动中，许多问题从时间或空间上带有一定的“阶段逻辑”， 从而形成了多阶段的决策问题。动态规划是求解多阶段决策问题的最优化数学 方法。 一个决策问题可分解成若干个相互联系的阶段，每个阶段有若干种方案可 供选择。决策的任务是在每个阶段选择一个适当的方案，从而使整个问题取得 最优效果。 动态规划将复杂的多阶段决策问题分解为一系列简单的单阶段决策问题, 通过解一系列小问题达到求解整个问题目的。 动态规划的各个决策阶段不但要考虑本阶段的决策目标, 还要兼顾整个决 策过程的整体目标, 从而实现整体最优决策。 5.1 多阶段决策问题 多阶段决策问题：是指将一类活动过程分为若干个相互联系的阶段，在每个阶段 都需要作出决策。这个决策不仅决定这一阶段的效益，而且决 定下一阶段的初始状态。 策略：每个阶段的决策确定后，得到的一个决策序列。 多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。 5.1 多阶段决策问题 例1：基建投资问题。一家公司有三个工厂，每个工厂都需要进行扩建。公司 用于扩建的资金总共为7万元，各工厂的投资方案及扩建后预期可获得 的利润如表所示。 厂名 方案1 方案2 方案3 方案4 投资数 利润 投资数 利润 投资数 利润 投资数 利润 一厂 0 0 1 5 2 8 3 10 二厂 0 0 1 3 3 9 4 11 三厂 0 0 2 7 3 11 4 13 公司要确定对各厂投资多少，使公司的总利润达到最大？ 每个工厂都有几种投资方案，对每个工厂作出一项决策，共要做出三项 决策。将每个工厂看成一个阶段，就是一个多阶段的决策问题。 5.1 多阶段决策问题 例2：最短