动态规划模型的建立 - 幻灯片1.pptVIP

§5.2 动态规划模型的建立 下面以资源分配问题为例介绍动态规划的建模 过程。 资源分配就是将一定数量的一种或几种资源 恰当地分配给使用者， 以获取最大效益。 资源可以是 资金、原材料、设备或劳动力等。 例5.2.1（资源分配问题） 某公司有资金10万元， 若投 资于项目 的投资额为 时， 其收益分别为 问应如何 分配投资数额才能使总收益最大？ 分析： 这是一个与时间无明显关系的静态最优化问 题， 可列出其静态模型。 目的是求 使 并且满足约束条件 为了应用动态规划方法求解， 我们可以人为地 赋予它“时段”的概念。 将投资项目排序， 依次考虑 项目1、项目2和项目3的投资， 即把问题划分为三个 阶段， 每个阶段只决定对一个项目应投资的金额。 这样问题转化为一个三阶段决策问题。 题是如何正确选择状态变量， 接下来的问 具有递推关系。 使各后部子过程之间 通常可以把决策变量 态问题中的变量 定为原静 即令 状态变量和决策变量有密切关系， 为累计量或随递推过程变化的量。 即状态变量一般 段可供使用的资金定为状态变量 这里可以把每阶 初始状态 为可分配用于第一种项目的最大资金， 则当第一 阶段（k=1）时， 有 第二阶段（k=2）时， 状态变量 其余两个项目的资金，即 为余下可投资于 一般地， 第k时段 于是本例中有： 阶段k： k =1，2，3，4； 状态变量 第k段可以投资于第 k项到第3个项目 的资金。 决策变量 决定给第k个项目投资的资金。 状态转移方程： 指标函数： 最优指标函数 当可投资金为 时， 投资第 k-3项所得的最大收益。 基本方程为： 用动态规划方法逐段求解， 便可得到各项目最佳投 资金额， 就是所求的最大收益。 建立动态规划模型的步骤： ①划分阶段： 按时间或空间的顺序适当地将过程划 划成若干个相互联系的阶段； ②确定状态变量及其取值范围： 决策过程演变的状态，又要满足无后效性的要求， 状态变量要能描述 而且维数要尽可能地少。 ③确定决策变量及其取值范围： ④建立状态转移方程： ⑤建立动态规划的基本方程。 §5.3 动态规划的求解 两 种 基 本 方 法 逆序解法： 顺序解法： 寻优的方向与多阶段决策过程的 实际行进方向相反，从最后一阶 段开始计算，逐段前推，求得全 过程的最优策略 寻优方向与多阶段决策过程的实 际行进方向相同，从第一阶段开 始计算，逐段向后递推，计算后 一阶段要用到前一阶段的寻优结 果，最后一段计算的结果即为全 过程的最优结果 因为逆序解法前已提及， 所以这里我们只讨论顺 序解法， 仍以例5.1.1为例， 因为该问题的始点A与终点 E都是固定的， 计算由A点到E点的最短路径与由E点 到A点的最短路径应当一样， 所以若用 表示从 起点A到第k阶段状态 的最短距离， 则可以从前向 后逐步求出起点A到各阶段起点的最短距离， 最后求出 从A点到 E点的最短距离及最短路线， 计算过程如下： k=0时， 即为边界条件。 k=1时，按 的定义有： k=2时， A B1 B2 B3 C1 C2 C3 D1 D2 E 图5.1.2 k=3时， 或 或 k=4时， 按定义可知 为所求的最短路长， 而最短路 径则为 A B1 B2 B3 C1 C2 C3 D1 D2 E 图5.3.1 与前节逆序解法结论相同，全部计算情况如图5.3.1 图中每节点上方括号内的数表示该点到A点的最短 距离。 上述解法可写成如下递推方程： 这里 顺序解法和逆序解法的区别 ： 1．状态转移方式不同 逆 序 解 法 状态 转移 方程 顺 序 解 法 顺序转移方程 逆序转移方程 n n 1 k 图5.3.3 顺序解法 1 k 图5.3.2 逆序解法 2．指标函数的定义不同 逆序解法： 最优指标函数 逆序解法： 最优指标函数 第k阶段从状态 出发，到终点后部子过程最优效益值。 第k阶段时从起 点到状态 的前部子过程最优效益 值。 整体最优函数值： 整体最优函数值： 3．基本方程形式不同 逆序解法： 顺序解法： ①指标函数为阶段指标和形式 ②指标函数为阶段指标积形式 逆序解法： 顺序解法： 当动态规划模型中状态变量与决策变量为连 续变量时， 则可灵活选取求解方法， 法、非线性规划方法、经典解析方法或者其它数 如线性规划方 值方法等。 如例5.2.1，状态变量和决策变量均取 连续值。 这里我们分别采用逆序解法和顺序解法 来求解。 1．用逆序解法求解 由前面分析知， 该问题为三阶段决策问题 第k段