第五章动态规划公开课.ppt

* 对偶单纯形法求解 -1/-1 -1/-4 -2 1 0 -1 -4 1 0 x5 -1 0 1 -1 -1 -3 0 x4 0 0 0 -1 -1 -1 1 z RHS x5 x4 x3 x2 x1 z 1/2 -1/4 0 1/4 1 -1/4 0 X2 -1/2 -1/4 1 -3/4 0 -13/4 0 x4 1/2 -1/4 0 -3/4 0 -5/4 1 z RHS x5 x4 x3 x2 x1 z 7/13 -3/13 -1/13 4/13 1 0 0 x2 2/13 1/13 -4/13 3/13 0 1 0 x1 9/13 -2/13 -5/13 -6/13 0 0 1 z RHS x5 x4 x3 x2 x1 z 故最优解为X=(2/13,7/13,0,0,0),最优值为9/13 第五章 动态规划 最短路径问题 生产计划问题 资源分配问题 背包问题 机器负荷分配问题 货郎担问题 多阶段决策过程 ■特点 ▼整个过程分多个阶段，并且各阶段是相互联系的； ▼每个阶段需作出决策；从而使整个过程达到最好的活动效果 ▼每个阶段的决策选取不是任意确定的 ▼前一个阶段的决策影响下一个阶段的决策及整个过程。 ●整个决策都确定后，就形成一个决策序列。 动态规划的基本概念 ■阶段（stage）:把所给问题的整个过程恰当的划分为相互联系的部分，以便求解，其中每一部分称为一个阶段，用K表示。阶段的划分可以按照时间或者空间。 A B1 B2 B3 C1 C2 D 1 3 2 动态规划的基本概念 ■状态: 表示每一阶段开始所处的自然状态或客观条件。一个阶段通常有若干个状态。用SK表示状态变量。 D A B1 B2 B3 C1 C2 S1=﹛ A ﹜ S2=﹛ B1,B2, B3 ﹜ S3=﹛ C1,C2﹜ S4=﹛ D﹜ 动态规划的基本概念 ■决策: 在某一阶段，当状态确定后，往往可以作出不同的决定，从而确定下一阶段的状态。这种决定成为决策。用UK （SK）表示决策变量。 D A B1 B2 B3 C1 C2 U2（B1）= C1 UK （SK） ∈DK （SK） D2（B1）=﹛ C1,C2﹜ ▼允许决策集合: 决策变量的取值往往限制在某一范围内。此范围称为允许决策集合，用DK （SK）表示。 动态规划的基本概念 ■指标函数: 由过程的第k开始到终点为止的数量函数（利润，效益。成本，距离，时间等）， 用VK, n（SK, Uk , SK+1, Uk+1 , …… Sn, Un ）表示。 ■ 最优值指标函数: 指标函数VK, n的最优值。用 fk (SK)表示。 ■阶段指标函数: 某阶段的指标函数，表示在第k阶段由SK到SK＋1的数量函数（利润，效益。成本，距离，时间等）。用dK（SK, Uk ）表示。 动态规划的基本思路 ■ 基本思路: 从终点逐段向始点方向寻找最优路线的一种方法。 D A B1 B2 B3 C1 C2 行进方向 终点 始点 寻优方向 1 2 n-1 n 顺序递推法与逆序法无本质的区别。一般来说，当初始状态给定时，用逆序解法，当终止状态给定时，用顺序解法。若既给定了初始状态又给定了终止状态，则两种方法均可使用。如下题，终点有两个，用顺序解法就较好。 D1 A B1 B2 B3 C1 C2 D2 动态规划的基本方程 fk (SK) =opt﹛dK（SK, Uk (SK) ) fk+1 (SK+1) ﹜ + Uk∈ Dk (SK) ＋ × ÷ ∑ fk+1 (SK+1)＝0 边界条件（视具体情况定） K=n,n-1,………..2,1 最优化(min,max) 动态规划的基本步骤 ①将问题的过程划分为阶段。 ④正确写出状态转移方程。第K+1阶段的状态变量SK＋1随第K阶段的状态变量SK和决策变量UK 的值而变化。描述了由K到K+1阶段的状态演变规律。 ▼一般是根据时间和空间的自然特征划分，将问题转化为多阶段决策过程。 ②正确的选择状态变量SK，使它既能描述过程的演变特征，又要满足无后效性。 ③确定决策变量UK，及每阶段允许的决策集合Dk (SK)＝﹛ UK ﹜。 动态规划的基本步骤 ⑤正确写出指标函数Vk,n。并满足一下性质： ▼它是定义在全过程上的数量函数。（利润、距离等） ⑥写出递推方程的最优值函数和边界条件。 ⑦由终点向始点进行迭代运算。 ▼要有可分离性，并满足递推关系。 Vk,n＝ Vk , k （ Sk ，Uk)+ Vk+1,n（ Sk+1 ，Uk+1) ▼严格单调函数。 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5