动态规划问题研究

　2007 年 8 月 系统理论与实践 第 8 期 　 文章编号 :100026788 (2007) 0820056209 动态规划问题研究 李 　端1 ,钱富才2 ,李 　力3 ,高建军1 (11 香港中文大学 系统工程与工程管理系 ,香港 ;21 西安理工大学 自动化与信息工程学院 ,西安 ; 31 哈尔滨工业大学 深圳研究生院经济管理学部 ,深圳) 摘要 : 　回顾动态规划在过去一些年的发展 ,特别是它在多目标优化与不可分优化问题中的可喜进展. 介绍了动态规划在解决多阶段均值2方差组合投资问题中的创造性应用. 旨在进一步推动动态规划的理 论研究 ,拓广它在各行各业中的应用. 关键词 : 　动态规划 ;多目标优化 ;不可分优化问题 ;多阶段均值2方差组合投资 中图分类号 : 　TP13 　　　　　　　　文献标志码 : 　A 　　　 Research on Dynamic Programming LI Duan1 , QIAN Fu2cai2 , LI Li3 , GAO Jian2jun1 (11Department of Systems Engineering and Engineering Management , The Chinese University of Hong Kong , Hong Kong ; 21School of Automation and Information Engineering , Xi’an University of Technology , Xi’an ;31Department of Economics and Management , Harbin Institute of Technology Shenzhen Graduate School ,Shenzhen) Abstract: 　Dynamic programming , when applicable , is one of the most powerful solution schemes in solving sequential decision2making problems. We summarize in this paper some recent development of dynamic programming in the past two decades , especially its significant advancement in multi2objective optimization and in nonseparable optimization problems , as well as its prominent application in multi2period portfolio selection within a mean2variance framework. The ultimate goal of this paper is to stimulate more research interests in dynamic programming , thus extending the reach of dynamic programming in optimization. Key words : 　dynamic programming ; multi2objective optimization ; nonseparable optimization ; dynamic portfolio selection under mean2variance criterion 收稿日期 :2007205231 资助项目 :香港研究基金会基金 (N2CUHK445Π05) ;高等学校博士学科点专项基金 (20060700007) ;陕西省自然科学基金 (2005F15) 　　作者简介 :李端 ,香港中文大学系统工程与工程管理系教授、系主任 ,现任中国数学规划学会副理事长 ;钱富才 ,西安理 工大学自动化与信息工程学院教授 ;李力 ,哈尔滨工业大学深圳研究生院管理学部副教授 ;高建军 ,香港中文大学系统工程 与工程管理系博士研究生. 1 　引言 无可置疑 ,Bellman 在上世纪五十年代提出的动态规划引入了决策科学中最具革命性意义的最优性原 理 ,为动态最优化奠定了坚实的基础. 过去五十年 ,动态规划在运筹学 ,控制论 ,管理科学的发展中 ,发挥了 无可比拟的领军作用 ,对这些学科的成功 ,影响卓越. 在适用的情况下 ,动态规划是求解动态决策问题的最 有效工具之一. 考虑以下的动态优化问题 : (DOP) 　　min f = ∑ T- 1 t = 0 f t ( x ( t) , u ( t) ) + f T ( x ( T) ) s. t . x ( t + 1) = Ht ( x ( t) , u ( t) ) , 　t = 0 ,1 , ⋯, T - 1 , 其中 , t 是整数 ,示时间阶段 , T 表示有限终端时间 , x ( t) ∈Rn 代表状态 , u ( t) ∈Rp 代表决策变量 , x (0) 为一给定的系统初始状态 , Ht (·,·) : Rn ×Rp →Rn , t = 0 ,1 , ⋯, T - 1 ,为代表状态转移的 n 维向量函数 , f 为整体目标函数 ,而 f t ( t = 0 ,1 , ⋯, T)代表各阶段目标函数. Bellman 最优性原理深刻刻画了 (DOP) 问题最优策略的一个至关重要的特性 :就最优策略而言 ,不论 当前状态是由以前何种决策所造成 ,余下的策略对当前的状态 ,亦必定构成最优策略. 最优性原理使得求 解在整个时间段上一个全局解的问题能化解为一系列在各个时间段上的局部优化问题 , min ∑ T- 1 t = 0 f t ( x ( t) , u ( t) ) + f T ( x ( T) ) = min u (0) { f 0 ( x (0) , u (0) ) + min u (1) { f 1 ( x (1) , u (1) ) + ⋯+ min u ( T- 2) { f T- 2 ( x ( T - 2) , u ( T - 2) ) + min u ( T- 1) { f T- 1 ( x ( T - 1) , u ( T - 1) ) + f T ( x ( T) ) }} ⋯}}. 　　定义在 t 阶段状态 x ( t)上的最优 cost2to2go 为 : J 3t ( x ( t) ) = min u ( t) ⋯u ( T- 1) ∑ T- 1 j = t f j ( x ( j) , u ( j) ) + f T ( x ( T) ) , 　t = T - 1 , ⋯,0 , 则我们根据 Bellman 最优性原理有以下递推 : J 3t ( x ( t) ) = min u ( t) [ f t ( x ( t) , u ( t) ) + J 3t +1 ( Ht ( x ( t) , u ( t) ) ) ] , 　t = T - 1 , ⋯,0 , (1) 其中边界条件为 J 3T ( x ( T) ) = f T ( x ( T) ) . 从 (1) 可以看出 ,运用动态规划可将多阶段最优决策问题 (DOP) 分解为一系列单阶段最优决策问题 ,从而使问题的求解计算量得到极大的降低. 相比其它解法 ,动态规划 总是提供一个反馈控制策略. 而这在有扰动或在随机情况下是至关紧要的. 在应用动态规划求解以上单目标多阶段最优决策问题时 ,问题 ( DOP)的目标函数必须是可分的 ,且具 有单调性. 而在实际复杂决策问题中 ,目标函数往往不具备可分性结构. 另外在现实生活中 ,彼此冲突的多 目标属性常常无法用一个目标函数统一度量. 本文介绍近年来文献中动态规划在多目标多阶段与不可分 多阶段决策问题中的一些拓广 ,并介绍这些发展在金融工程中的一项应用. 2 　多目标动态规划的包络法 不同于单目标动态规划 ,我们在多目标动态规划中需要用 k 个整体目标函数来评估决策 : (MDP) 　　min u f = f 1 ( x (0) , u (0) , x (1) , u (1) , ⋯, x ( T - 1) , u ( T - 1) , x ( T) ) f 2 ( x (0) , u (0) , x (1) , u (1) , ⋯, x ( T - 1) , u ( T - 1) , x ( T) ) … f k ( x (0) , u (0) , x (1) , u (1) , ⋯, x ( T - 1) , u ( T - 1) , x ( T) ) s. t . x ( t + 1) = Ht ( x ( t) , u ( t) ) , 　t = 0 ,1 , ⋯, T - 1. 注意我们现在并不限定任意整体目标函数为可加型. 求解问题 (MDP)是要找出它的非劣解集. 一个满足系 统状态方程的可行解 ( x^ (0) , u^ (0) , x^ (1) , u^ (1) , ⋯, x^ ( T - 1) , u^ ( T - 1) , x^ ( T) ) 被称作非劣解 ,如果不存在 另一个可行解 ( „x (0) ,‰u (0) ,„x (1) , ‰u (1) , ⋯,„x ( T - 1) , ‰u ( T - 1) ,„x ( T) )使得对所有 i = 1 , ⋯, k , f i ( „x (0) , ‰u (0) ,„x (1) , ‰u (1) , ⋯,„x ( T - 1) , ‰u ( T - 1) ,„x ( T) ) ≤f i ( x^ (0) , u^ (0) , x^ (1) , u^ (1) , ⋯, x^ ( T - 1) , u^ ( T - 1) , x^ ( T) ) , 并至少有一个不等式是严格的. 为了用动态规划求解上述问题 (MDP) ,每个整体目标函数必须满足两个条件 :1) 可分性与 2) 单 调性. 在问题 (MDP)中 ,目标函数向量 f = [ f 1 , f 2 , ⋯, f k ]′被称为是后向可分 ,如果存在函数 0. (5) 以上假定 (5)保证单调性条件得到满足. 方程 (4)能够写成如下更紧凑的形式 : yT = 记录

混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载