运筹学13-动态规划I-11培训资料.ppt

第13讲 动态规划I 本讲提纲 1. 多阶段决策问题 2. 动态规划的基本概念与最优性原理 3. 动态规划模型的建立 1. 多阶段决策问题 动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指一类活动过程，它可以分为若干个互相联系的阶段，在每个阶段都需要做出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的和达到最优。 例1：最短路问题 求：A到E的最短路径 以S(X—Y)表示X—Y的最短距离 即要求S(A—〉E) 动态规划的思想 由最底部的小问题开始计算，然后循序向上，直至求出整个问题的答案。 将较小问题的计算结果进行存储，在计算较大问题过程中，如有需要可直接调用，无需每次重新计算。 动态规划是一种自下而上(bottom-up)解决问题的方式。 拾火柴游戏：桌子上放30根火柴，每人一次可拾起1~3根，谁拾起最后1根火柴谁输，如果让你先拾，你有没有办法保证能赢得游戏？ 2. 动态规划的基本概念和最优性原理 (1) 阶段 阶段是对整个过程的自然划分。通常可根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。描述阶段的变量称为阶段变量，常用k 表示。 (2) 状态 状态表示每个阶段开始时过程所处的自然状况或客观条件。描述状态的变量称为状态变量，通常用sk表示第k个阶段的状态变量。 第k个阶段所有状态的集合，称为第k个阶段的允许状态集或状态可能集，记为Sk，即 状态变量的选择既要能确切描述过程演变的特征又要满足无后效性，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。 在最短路问题中，状态可以定义为在每个阶段初所处的节点位置。 (3) 决策 当到达一个阶段的某个状态后，可以做出各种选择，从而演变到下一阶段的某个状态，这种选择就是决策。 描述决策的变量称为决策变量，通常用 表示第k个阶段处于状态sk时的决策变量，即第k个阶段处于状态sk时所作的一种选择，该选择使系统从第k个阶段的状态sk演变到第k +1个阶段的某个状态sk+1 。 状态sk 状态sk+1 决策xk 决策xk+1 当处于某个阶段的某个状态时，所允许的全部决策的集合，称为允许决策集，即决策变量的允许范围，以 表示处于第k阶段状态sk时所允许的全部决策集合。 在最短路问题中，决策可以定义为在每个阶段的某个节点处时对下一个阶段的节点选择。 例如，x1(A)=B2表示在第1阶段节点A处时，选择路径AB2到达第2阶段的节点B2 (4) 策略 策略，也称全过程策略，是从初始阶段(k=1)到最终阶段(k=n)，每一阶段的决策所形成的决策序列，表示为 k-子策略：从第 k 阶段到最终阶段，每一阶段的决策所形成的决策序列 最优策略 (5) 状态转移方程 在确定性过程中，一旦某个阶段的状态和决策已知，下一个阶段的状态便完全确定。用状态转移方程表示这种演变规律，写作 在最短路问题中，下一个阶段的初始状态(节点位置)就是上一个阶段的决策选择，所以 描述两个相继阶段状态之间的关系 (6) 阶段效应与最优指标函数 当处于第k个阶段的某个状态sk时，实施决策xk(sk)，得到一个反映该阶段(第k个阶段)的效应指标，称为第k阶段的阶段效应函数(或称阶段指标函数)，记为 当处于第k个阶段的某个状态sk时，实施最优子策略 后，从阶段 k 到最终阶段 n 可获得的总效应，称为最优指标函数，记为 第k阶段的阶段效应 第k+1阶段到第n阶段的最优总效应 对于可加性指标函数： 对于可乘性指标函数： 其中 opt 可根据具体情况取 max 或 min 最优性原理 若 是最优策略，则它的任意k-子策略 对于由s1和 确定的 为起点的第 k 到 n 的后部子过程而言，也是最优策略。 通俗地说：不论过去的状态和决策如何，对于前面的决策形成的当前状态而言，后续的各个决策必定构成最优子策略。 一个最优策略的子策略总是最优的。 3. 动态规划模型的建立 动态规划的基本方程(递归方程) 对于可加性指标函数： 对于可乘性指标函数： 边界条件 边界条件 动态规划模型建立的基本步骤 (1) 划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 (2) 正确选择状态变量 选择变量既要能确切描述