Vk,n (sk , uk , , sn1) fk [sk , uk ,Vk 1,n (sk 1, uk 1, , 1)] ③函数 fk (sk , uk ,Vk 1,n ) 对于变量 Vk1,n 要严格单调。
8.2 动态规划模型建立
下面以投资问题为例介绍动态规划的建模条件。
【例8-2】 某公司现有资金20万元,若投资于三个
8.1 动态规划基础知识
(5)状态转移方程:状态转移方程是确定过程由一
个状态转移到另一个状态的演变过程。动态规划中某一状
态以及该状态下的决策,与下一状态之间具有一定的函数
关系,称这种函数关系的表达式为状态转移方程。如果第
k段的状态为 sk ,该阶段的决策为
的状态就可以用下式来表示:
uk
sk
,则第k+1段
阶段的指标函数,是该阶段最优的指标函数。
8.2 动态规划模型建立
建立动态规划模型,就是在分析实际问题的基础上建 立该问题的动态规划基本方程。成功地应用动态规划方法 的关键,在于识别问题的多阶段特征,将问题分解成为可 用递推关系式联系起来的若干子问题,或者说正确地建立 具体问题的基本方程,这需要经验与技巧。而正确建立基 本递推关系方程的关键又在于正确选择状态变量,保证各 阶段的状态变量具有递推的状态转移关系。
第8章 动态规划
动态规划(DYnamic Programming,缩写为DP)方法 ,是本世纪50年代初期由美国数学家贝尔曼(Richard E ,Bellman)等人提出,后来逐渐发展起来的数学分支, 它是一种解决多阶段决策过程最优化问题的数学规划法 。动态规划的数学模型和求解方法比较灵活,对于连续 的或离散的,线性的或非线性的,确定性的或随机性的 模型,只要能构成多阶段决策过程,便可用动态规划方 法求其最优解。因而在自然科学、社会科学、工程技术 等许多领域具有广泛的用途,甚至一定程度上比线性规 划(LP)、非线性规划(NLP)有成效,特别是对于某 些离散型问题,解析数学无法适用,动态规划方法就成 为非常有用的求解工具。