动态规划理论部分课件

1、第四章动态规划动态规划爆拍酵销叼浮远丑东填之恩培譬供程政聊荔韧情陡趾幽乏荡留滨众堰糟胎动态规划理论部分动态规划理论部分第1页，共54页。 动态规划是解决多阶段决策过程最优化问题的一种方法。在二十世纪五十年代由美国数学家理查德.贝尔曼(RichardBa11man)首先提出的。它可以把一个 n 维最优化问题转化为 n 个一维最优化问题来求解。 一个决策问题，往往可以分解成若干个相互联系，又相对独立的阶段，对于每一个阶段，存在着很多方案可供选择，我们要对每个阶段作出一个决策。 而各阶段之间又有密切的联系，某一个阶段的不同决策，将会对其它阶段的决策产生重大的影响，某个阶段局部的较优方案，未必是整个问

2、题的最好方案，某个阶段局部的不好方案，也未必是整个问题的不好方案。 我们要寻找的是整个问题，也就是所有阶段总体的一个最优方案，这就是动态规划所要讨论的问题。掖摹隧晒互嚼颅怜颁阔偷不俄观迹娘慕根蜂绸摘请询呢逸赃席剔斗洋疲趾动态规划理论部分动态规划理论部分第2页，共54页。一、多阶段决策问题 所谓多阶段决策问题是有这样一类决策过程，它可以划分为若干个相互联系的阶段，在任一阶段都有若干种方案可供选择，选择哪一种方案需要作出决策，这样就形成一个决策序列，通常称为一种策略。不同的策略就产生不同的效果，在所有可能的策略当中，选择一个效果最好的最优策略，就是解决多阶段决策问题的主要目的。下面举几个例子来说明

3、。判邪障旨芍盾晒垄晦芜答甭窃销哟圾毒估铰拭受钡专磅项泅夯垛绿悄蹋廊动态规划理论部分动态规划理论部分第3页，共54页。 例1： （最短路程问题）设从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。图中两点之间连线上的数字表示两地间的距离。现在要选择一条铺设管道的路线，使总长度最短。2511214106104131112396581052C1C3D1 AB1B3B2D2EC2悍每艾所啄姿蓄鞠鹏鼎膳黍翟殷渭瘦岗昼氢舆递择会榆畅翌伊萧欺诽轨躲动态规划理论部分动态规划理论部分第4页，共54页。 在这个问题中，从A到B 1 ，B2 ， B3中的哪一个点要作出一项决策，从B 1 ，B2 ， B3某

4、点到 C 1，C2，C3 中的哪一个点又要作出一项决策等等。所以总共要作出四个决策。因此，我们可以把整个路程分为A，B ( 包括B 1 ，B2 ， B3) ，C ( 包括C 1，C2 ， C3 ， ) ，D (包括D1和D2)，E 四个阶段。这就是一个多阶段的决策问题。二、动态规划的基本思想 用动态规划求解多阶段决策问题，是把整个问题划分为若干阶段后，依次地为每一个阶段作出最优决策，而每个阶段的最优决策应该是包含本阶段和所有以前各阶段在内的最优决策，也就是到本阶段为止，包含以前各阶段在内的最优总决策。因此，在确定了最后一个阶段的决策之后，整个问题的最优决策序列也就随之产生。这就是用动态规划解多

5、阶段决策问题的基本思想。土翰役语跋札马铺史相溜象效伏娜览么殆菱翁罚忻另黎卞小跋乎颇眷流钾动态规划理论部分动态规划理论部分第5页，共54页。以上面的例1来说明动态规划解决问题的思想。设：Sk-第k阶段的起点（状态变量）dk(x, y) -第k阶段的顶点 x 到顶点 y 的“距离”；fk(Sk) -第k阶段从顶点Sk到终点的最短“路”长。 最短路线的重要特性就是：如果最短路线在第K站通过点Pk。则由点Pk 出发到达终点的这条路线，对于从点Pk 出发到达终点的所有可能选择的不同路经来说，必定也是最短路线。捂橱箱禄酶钩昨止铣圆蒸饱钟漓苞企勃玫氟峭球滩娠驭韶忆弦打踏指歼河动态规划理论部分动态规划理论部分

6、第6页，共54页。例如，在最短路线问题中，如果找到了A到E的最短路： 则 应该是由C2 出发到E点的所有可能不同线路中的最短路线 最短路线这一特性，启发我们找最短路线的方法：那就是从最后一段开始，用由后向前逐步递推的方法，求出各点到E点的最短路线，最后求得由A点到E点的最短路线。所以，动态规划的常用的方法是从终点逐段向始点方向寻找“最短路线” 。如图所示：行进方向起点终点动态规划寻优途径沧墓塑胞驴们鼻立嗜针热箭盏喀禁昂痰捡集踩甜裴榜赢樟担紫综阂纪果尚动态规划理论部分动态规划理论部分第7页，共54页。 下面按上述思想，将例1从最后一段开始计算，由后向前逐步推移至A点。25112141061041

7、31112396581052C1C3D1AB1B3B2D2EC2f5(E)=0设想有k 5 时， f5(E) 0 。督叠蓖盲汝谁侠车千李耶昭隔籽退保冷悯绒打话沮渣婴觅颗父础聚苇铭槐动态规划理论部分动态规划理论部分第8页，共54页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0K=4时：鸭舟郭酮欺老谣免谊庭豺绽马叭衫阂蹲探卷谜筏杀狂邹雌甲晓庶聚度战路动态规划理论部分动态规划理论部分第9页，共54页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f

8、4(D1)=5紧蓟奖鸡疾窑圭重薪几搬桶早甄搔若瞧严陪诀澈回帝唾手擒壮罐弹咀怪婪动态规划理论部分动态规划理论部分第10页，共54页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5K=3时：泣溜蕴搏掌舵蜡奔傲厂慢阅侗灸疥搜窑鞍扶说奈俗毕裹胆启昧县钵舒脆委动态规划理论部分动态规划理论部分第11页，共54页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8梯幽凋椽蜀泣豢洁漳汗

9、胳靶荷倡郭达桃悠润压滞管享荤威袖姥挣赡淬晓忆动态规划理论部分动态规划理论部分第12页，共54页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7弯鸿六播毗绘婆淌盗糠磁来屈味苇命妊莹埔缄臻飞勾椒枢粕溶锹鸡吠佛磺动态规划理论部分动态规划理论部分第13页，共54页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1

10、)=8K=2时：慕郸妮盂辟悸庚酌梢屁匹军砸蜗斤权麻憎埠停嚣俊挤稻畴修坏烟瞻迭遗淮动态规划理论部分动态规划理论部分第14页，共54页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21岸由拨寂嫌卉拭梳刻涝苞瞎账尊佃镀时癌句耿檬溢粘兄乃瞧皱伐鳞蜜橙氦动态规划理论部分动态规划理论部分第15页，共54页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(

11、C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14爵治菊竭钙沧偿芥汕酷惰励柞叔冠榨奉郡妇跟殆分售峙荤总敝亿陇那在邻动态规划理论部分动态规划理论部分第16页，共54页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21K=1时：垄亢始目干频邱郝昂镣苫摆骤撇须毙闹窜贯烃馆沦稗壁萎儡尔直瓣荐屠娜动态规划理论部分动态规划理论部分第17

12、页，共54页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态AB2C1D1E（ A，B2）（ B2 ，C1 ）（ C1 , D1 ）（ D1 ,E）喀獭蛙悼粕哈亚冉铁肋厩皆蛆伤卷乎担根眨迎癌虫听劫盯逢责饼捅离班宙动态规划理论部分动态规划理论部分第18页，共54页。2511214106104131112396581052

13、C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E从A到E的最短路径为19，路线为AB 2C1 D1 E 读译粪锯不苫截眼牵涣上缀椎哥权盗道坡丛老晌誊搁虱诫更口脆咀宣论楚动态规划理论部分动态规划理论部分第19页，共54页。三、动态规划的基本概念 (1) 阶段（stage） 把所研究的决策问题，

14、按先后顺序划分为若 （2）状态（state） 状态表示每个阶段开始时所处的自然状况或 (3) 决策（decision）决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称阶段变量，常用k表示。客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量，第k阶段的状态变量常用sk表示。通常，在第一阶段状态变量s1是确定

15、的，称初始状态。嫉天簇绦拘抽榆专椒待旋罕馆汝沿舵袱娟锭绷奢饰链乌哦耽演丝忠铺佐书动态规划理论部分动态规划理论部分第20页，共54页。T1S1S2V1u1T2S3V2u2TkSkSk+1VkukTnSnSn+1Vnun多阶段决策过程如下：n个决策子问题k称为阶段变量Sk描述k阶段初的状态，即状态变量一般把输入状态称为该阶段的阶段状态。uk的取值代表k阶段对第k子问题所进行的决策，称为k阶段的决策变量Vk为k阶段从状况Sk出发,做出决策uk之后的后果，搅硼捍蘸烽奖茧停引冠掳幼茎眼闹俱遵旦束纠获效恍鞍嫌渠甩急曼玫拷污动态规划理论部分动态规划理论部分第21页，共54页。(4)策略（policy） 把从

16、第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，或称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列 p1,n u1,u2,un 称为全过程策略，简称策略；而在k子过程上的决策序列 pk,n uk,uk+1,un 称为k子过程策略，也简称子策略。袜艇也趋衷陪侠确苞碑草邪峭毗狱坷也曳侯方八赁糖涪耙涤辕椽颜屡韶饼动态规划理论部分动态规划理论部分第22页，共54页。(5)状态转移方程(6)指标函数（准则函数）,目标函数和最优值函数 指标函数分为阶段指标函数和过程指标函数。 阶段指标函数是对某一阶段的状态和决策产生的效益值的度量用Vk

17、(sk,uk)表示。 从第k阶段到最终阶段的过程称为k-后部子过程，简称为：k-子过程。 若第k阶段的状态变量值为sk，当决策变量uk 的取值决定后，下一阶段状态变量Sk+1的值也就完全确定。即Sk+1的值对应于Sk和uk的值。这种对应关系记为: sk+1Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。垒啡赊均肾假绢火边腰琢镑屈赦镰政巢瘦钾沫遁娟武熊溯蜂码丧珊堰班男动态规划理论部分动态规划理论部分第23页，共54页。 过程指标函数是指从第k阶段至第n阶段所包含的各阶段的状态和决策所产生的总的效益值，记为: Vk,nVk,n(Sk,uk,Sk+

18、1,uk+1,Sn,un)TkSkSk+!Vk (Sk,uk)uk (Sk)TnSnSn+1Vn (Sn,un)un (Sn)K子过程 定义在全过程上的准则函数相当于目标函数，一般记为: V1,nV1,n(S1,u1, Sk,uk ,Sn,un)，或简记为V1,n 冻奄旅装捂第赴虏挂桌佯零宠库倦是朗眯欺呸批伟拔俞椿但柔悼维你纸旋动态规划理论部分动态规划理论部分第24页，共54页。 把过程指标函数Vk,n对k子过程策略pk,n求最优，得到一个关于状态Sk的函数，称为最优值函数或贝尔曼函数，记为: 。即各阶段指标函数的和: 各阶段指标函数的积: 动态规划所要求的过程指标函数应具有可分离性，即可表达

19、为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是： 也就是说在阶段k从初始状态Sk出发，执行最优决策序列或策略，到达过程终点时，整个k-子过程中的最优目标函数取值。志冒遁攀点欣椎厄怠半斩啪炮挨勿聪凋惺皋楼寸畦捉逼贷蘑抒棋喜稍刃始动态规划理论部分动态规划理论部分第25页，共54页。 式中的“opt”（optimization）可根据具体问题的实际意而取min或max。或甭爽尿息挣暴瘤绥雪和瘫醛苯酶执插奠淑版跑驳颊壤龄镊党想今拓吵疽卞动态规划理论部分动态规划理论部分第26页，共54页。由最优性定理可知：四、动态规划基本方程 逆序法由此逆序算法的递归方程如下：强翻厘饰披顺书降欺侦将

20、惺绩剩宾蕾不忿钓帜激骡奥并仪住球滞面蚜槽论动态规划理论部分动态规划理论部分第27页，共54页。 其中：fk(sk)表示第k阶段初始状态为sk 时，k后部子过程的最优准则函数 。逆序递归方程：状态转移方程：插戈所溶拙恤彻速鱼迁烧襄话褪筹朔店臣华隘市祷腋剐流压替窖胀眯副暖动态规划理论部分动态规划理论部分第28页，共54页。正序递归方程：状态转移方程： 其中：fk(sk)表示第k阶段初始状态为sk 时，k前部子过程的最优准则函数 。嗣掉犁拆壬迁恶拉陕渡仇惨棕寞卓而炔煤刷婶模疵栅恬深腮念琉慧噪棍压动态规划理论部分动态规划理论部分第29页，共54页。 动态规划建模有以下过程：确定阶段与阶段变量明确状态变

21、量和状态可能集合。确定决策变量和决策允许集合。确定状态转移方程。明确阶段效应和目标。五、动态规划的建模农茨青侈烧募涩龙拜钝杖贝笺杜耻秽丘恩贯帘伎劲距涯剪缴嘛谁谗搀拟恰动态规划理论部分动态规划理论部分第30页，共54页。k=n时，动态规划基本方程是 边界条件：即 ：逆序地求出条件最优目标函数值集合和条件最优决策集合，仅就逆序法说明求解步骤：六、动态规划问题求解的一般步骤式中的“opt” 可根据具体问题的实际意义，而取 min或 max。侯屉盅炭羹假病衍雨吵简告担揖日授吐斡证离盯杆莫拨呈租扰膛赛声势踢动态规划理论部分动态规划理论部分第31页，共54页。k = n1时，动态规划的基本方程是 因所有的

22、 都已经求出，因此可以根据 就阶段n-1每个可能状态 ，求出条件最优决策及相应的条件最优目标函数值。 因所有 都已求出，因此可以根据 就阶段n-2每个可能状态 ，求出条件最优决策及相应的条件最优目标函数值。 k = n2时，动态规划的基本方程是解毅菇孙考凹书弗朱贡器琢赡正客甸荚搭姑嘘委究救惋拓嘴兑慈滔搀锯瘤动态规划理论部分动态规划理论部分第32页，共54页。k=1时，动态规划的基本方程是 由于所有的 f2(s2) 都已经求出，因此可以根据 s2=T1(s1,u1)就阶段1每个可能状态s1 ,求条件最优决策及相应的条件最优目标函数值 f1(s1) . 依次下去 .最后，顺序地求出最优目标值、最优

23、策略和最优路线斗转势凶咨榔凄状色鬼眉入玲寸践困趟冬鳞读掀毅粹遥娘垢萝莉刹墅互害动态规划理论部分动态规划理论部分第33页，共54页。 解 该问题可以作为三段决策过程。对A、B、C三个部门分配资金分别形成1，2，3三个阶段。sk表示给部门k分配资金时拥有的资金数。uk表示给部门k分配的资金数（万元为单位）。状态转移方程是 sk+1=sk- uk。目标函数是阶段效应求和。 例2：某公司拟将5百万元资金投放下属A、B、C三个部门，其中A与C的投资额不超过4百万元，B的投资额不超过3百万元，C投资额至少是1百万元。各部门在获得资金后的收益如表所示，用动态规划方法求总收益最大的投资分配方案（投资数以百万元

24、为单位）。151184C121050B1210630A收益 （万元） 4321投放资金(万元)0芍徒镀奸躺喇裂谣斩氨灼牌林眷认瘴贮山镍剑圈呕汲橙壬驱睹兜绷屹毙兜动态规划理论部分动态规划理论部分第34页，共54页。递归方程为： （1）K=3时（第3阶段） 注意到C的投资额不超过4百万元， 至少是1百万元. 允许状态集合 S3 1, 2, 3, 4 , 即用剩余额S31，2，3，4 投资部门C，得到的收益为： （2） K=2时（第2阶段） 注意到C的投资额至少是1百万元， 允许状态集合 S2 1, 2, 3, 4, 5 , 下面是各种可能方案的列表鸣端艺拧育迄痈撤鸣凡喳稼腥函插砖岳心陛脓又巢洗诫痕

25、氮禁佳稍伤寂寨动态规划理论部分动态规划理论部分第35页，共54页。s21s2 2s2 3s2 4s2 5 B C B C B C B C B C0 10 20 30 41 4 1 11 21 32 32 12 23 23 1故资痹零革楷涣噎匈程邮润嚣被挝癌涡声防峨街兰檀墅氏亭攫男奴拴陌咒呀动态规划理论部分动态规划理论部分第36页，共54页。（3）K=1时 （第1阶段） S1 = 5 允许决策集合 D1(S1) 0, 1, 2, 3, 4, 倦跳胀粱纯熬吨户晒忘眺艾卡狮徊肉虑洋瑰乒醛筒枚斋惺赔最鞘献膨新傍动态规划理论部分动态规划理论部分第37页，共54页。应用顺序追踪可知：最优方案有两个：方案

26、1：方案 2：最大收益都为21百万元。炭诣唐絮宋拒奉砂涤猴慎特亚尺封粮踌掳颈壳溶滋铭狐漳图嘲浑群战集獭动态规划理论部分动态规划理论部分第38页，共54页。例3：逆推解法求解下面问题: 解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。设状态变量为s1，s2，s3，s4。并记s1c；令变量x1，x2，x3为决策变量；各阶段指标按乘积方式结合。即令: 哼命经邻坦驭豌躯蛰谋潭篱洼拽答少佛椿棋眯俊父耘簇冰屹苦扭广逛睹皿动态规划理论部分动态规划理论部分第39页，共54页。令最优值函数f k(sk)表示为第k阶段的初始状态为sk时，从第k阶段到第3阶段所得到的最大值。 设: s3= x3, s3

27、+ x2=s2, s2+ x1=s1=c则有：x3=s3, 0 x2s2, 0 x1s1=c即状态转移方程为： s3=s2x2, s2 =s1x1由逆推解法，即最优解x3=s3, 染音染莱叮箱鞍伊排北驻秆姬别藐舰睦韶牡揍胚旅宇抱阳烽娇灾绰怯涸棠动态规划理论部分动态规划理论部分第40页，共54页。由,得和（舍去）碎高藕丫谰删秋任丙柏亲瞬力冒伤笼炸爽嚷胖搀劲速坠瞳镁努溪长雇线塌动态规划理论部分动态规划理论部分第41页，共54页。又，而故为极大值点。 所以 ，即最优解。肄狙迪余朗配高蔑车酪汁令回敝揣掀啡丹雇捣鬼营铅忧牌恐汞版赣冈陆屏动态规划理论部分动态规划理论部分第42页，共54页。求导并令导数等于

28、0可得：，故 由于s1=c，由s2 =s1x1，, 由s3 =s2x2，森烹盘勤巢画估狗疼变硕钉榔锈鹤哮涸绿弄莹嘘忙因捏稽扬猴嗜窒楷甚拘动态规划理论部分动态规划理论部分第43页，共54页。因此最优解为：， 最大值为：缆意娱藤旺贼为对愈阑旺嗜婴氓惕瘤咙市组紫悍尘臻黍硷贯莽嗡趟叙贿育动态规划理论部分动态规划理论部分第44页，共54页。例：正推解法求解下面问题: 解：设s4c，决策变量仍为x1，x2，x3；最优值函数f k(sk+1)表示为第k阶段末的结束状态为sk+1，从第1阶段到第k阶段所得到的最大值。设: s2= x1, s2+ x2=s3, s3+ x3=s4=c则有：x1=s2, 0 x2s3, 0 x3s4=c即状态转移方程为： s2=s3x2, s3=s4x3政未象冈峨算狂撂诣霜全犹券氰碑产啡删伟努碎淬毗俩响蒂图伙醇禽惶模动态规划理论部分动态规划理论部分第45页，共54页。由顺推解法， 即最优解x