运筹学_第八章_动态规划.ppt

第八章 动态规划;引 言;□动态规划与其他规划方法的不同之处在于： 动态规划是求解某类问题（多阶段决策问题）的一种方法， 是考察问题的一种途径，而不是一种特定算法。 因此，它不像线性规划那样有一个标准的数学表达式和明确 定义的一组（算法）规则，而必须对具体问题进行具体分析处 理。因此，学习动态规划时，除对基本概念和基本方法正确理解 外，还应在一定经验积累基础上，以丰富的想像力去建立模型， 用创造性的技巧去求解。;提 纲;学习目标： 1 明确什么是多阶段的决策问题，特别要注意没有明显 的时段背景的问题如何化归为多阶段的决策问题。;P156 例2 机器负荷分配问题（时间阶段问题） ◎设有某种机器设备，用于完成两类工作A和B。若第k年初完好 机器的数量为 xk ，若以数量 uk 用于A，余下的（xk－uk）用于 工作B，则该年的预期收入为 g( uk ) + h( xk－uk )。这里g( uk ) 和 h( xk－uk )是已知函数，且 g( 0 ) = h( 0 ) = 0。 ◎又机器设备在使用中会有损坏，设机器用于工作A时，一年后 能继续使用的完好机器数占年初投入量的70%；若用于工作B 时，一年后能继续使用的完好机器数占年初投入量的90%。则在 下一年初能继续用于A、B工作的设备数为 xk+1=0.7uk+0.9(xk－ uk)。 ◎设第1年初完好的机器总数为1000台，问在连续5年内每年应如 何分配用于A、B两项工作的机器数，使5年的总收益为最大。;□相应的问题称为多阶段决策问题。;P156 例1 最短路线问题（空间阶段的例子） 设有一个旅行者从下图中的A点出发，途中要经过B、C、D等 处，最后到达终点E。从A到E有很多条路线可以选择，各点之间的距 离如图所示，问该旅行者应选择哪一条路线，使从A到达E的总的路程 为最短。;□从以上两个例子，可以知道 所谓多阶段决策问题是指这样的决策问题：其过程可分为若 干个相互联系的阶段，每一阶段都对应着一组可供选择的决策， 每一决策的选定既依赖于当前面临的状态，又影响以后总体的效 果。 当每一阶段的决策选定以后，就构成一个决策序列，称为一 个策略，它对应着一个确定的效果。多阶段决策问题就是寻找使 此效果最好的策略。;多阶段决策过程的特点;2.各个阶段的决策一般与“时间”有关 □动态规划方法与“时间”关系很密切，随着时间过程的发展而决 定各阶段的决策，从而产生一个决策序列，这就是“动态”的意 思。 □但是，一些与时间无关的静态问题，只要在问题中人为引 入“时间”因素，也可将其看成是多阶段的决策问题，用动态规划 方法去处理。;学习目标： 1 准确、熟练地掌握动态规划的基本概念、特别是状态 变量、决策变量、状态转移律、指标函数、基本方程 等。;□为了便于求解和表示决策及过程的发展顺序，而把所给问题恰 当地划分为若干个相互联系又有区别的子问题，称之为多段决策 问题的阶段。一个阶段，就是需要作出一个决策的子问题。 □通常，阶段是按决策进行的时间或空间上先后顺序划分的。 □描述阶段的变量称为阶段变量，常记为k，k=1,2, …,n。 □如本例可按空间分为4个 阶段来求解， k=1, 2, 3, 4。;□状态：每阶段初的客观条件。描述各阶段状态的变量称为状态 变量，常用xk表示第k阶段的状态。;□动态规划中的状态应满足无后效性（马尔科夫性）： 所谓无后效性指系统到达某个状态前的过程的决策将不影响 到该状态以后的决策。［指系统从某个阶段往后的发展，仅由本 阶段所处的状态及其往后的决策所决定，与系统以前经历的状态 和决策（历史）无关。过程的过去历史只能通过当前的状态去影 响它未来的发展］ □例1中，当某阶段的状态已选定某个点时，从这个点以后的路 线只与该点有关，不受该点以前的路线的影响，所以满足状态的 无后效性。;□状态集合：状态变量 xk 的取值集合称为状态集合，状态集合 实际上是关于状态的约束条件。 □通常用Sk表示状态集合，xk?Sk。;（3）决策（decision）;□决策集合：第k阶段当状态处于xk时决策变量uk( xk )的取值范 称为决策集合，常用Dk( xk ) 表示。;□小结 阶段 k、 状态 xk、 状态集合 Sk、 决策 uk( xk )、 决策集合 Dk( xk )。;（4）状态转移律（方程）;B1;（5）策略（policy）和子策略（subpolicy）;□策略集合：在实际问题中，由于在各个阶段可供选择的决策有 许多个，因此，它们的不同组合就构成了许多可供选择的决策序 列（策略），由它们组成的集合，称为策略