文档介绍：动态规划 (Dynamic Programming,DP)
教学要求:
熟悉动态规划的基本思想
掌握一维离散动态规划的建模和求解方法
了解运用动态规划方法解决一些经济和管理中的基本问题。
目录
动态规划原理和模型
一维动态规划求解方法
动态规划在经济和管理中的应用
概述
动态规划所研究的对象是多阶段决策问题
所谓多阶段决策问题,是指一类活动过程,它可以分为若干个相互联系的阶段,在每个阶段都需要做出决策。这个决策不仅影响该阶段的效益,还会决定下一阶段的初始状态。
在多阶段决策过程中,各个阶段的决策就构成了一个决策序列,称之为一个策略。多阶段决策问题就是求一个最优策略,使各阶段效益的总和达到最优。
1957年,美国数学家贝尔曼(Bellman)等人提出了解决多阶段决策过程优化问题的“最优化原理”,建立了数学规划的新分支——动态规划
动态规划是现代企业管理中的一种重要决策方法,可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。
(Stage)
将所给问题的过程,按时间或空间特征分解成若干互相联系的阶段,以便按次序求每阶段的解。
描述阶段的变量称为阶段变量,用字母k表示,,从A到E可分成四个阶段,k=1,2,3,4
(State)
状态就是阶段的起始时的客观条件,通常一个阶段有若干个状态,描述各阶段状态的变量称为状态变量,可用一个数、一组数或一向量来描述,常用sk表示第k阶段的状态变量。
状态变量sk的取值有一定的允许集合或范围,此集合称为状态集合(或状态允许集合),用Sk表示。,S1={A},S2={B1,B2,B3},S3={C1,C2,C3},S4={D1,D2}
状态具有无后效性,即若某阶段状态给定后,该阶段以后过程的演变,不再受以前各阶段状态的影响。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
第2阶段
第3阶段
第4阶段
第1阶段的状态
第2阶段的状态
第1阶段
(Decision)
决策是指某阶段状态给定后,从该阶段演变到下一阶段某一状态的选择。用uk(sk)表示第k阶段,状态为sk时的决策变量。
决策变量的选取限制于某一范围,此范围称为允许决策集合,用Dk(sk)表示第k阶段从状态sk出发的允许决策集合, uk(sk) ∈ Dk(sk)
,u2(B1)表示第2阶段状态为B1时的决策变量, u2(B1)=C1或C3
第2阶段从状态B1 出发的允许决策集合D2(B1)={C1,C3}, 则有u2(B1) ∈ D2(B1)