chap7_动态规划

《chap7_动态规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章动态规划动态规划问题的基本概念和基本原理动态规划模型的建立与求解应用举例马氏决策规划例1：问题的引出例1：某运输公司有500辆运输卡车，超负荷运输（每天满载行驶500km以上）时，年利润25万元/辆，卡车的年损坏率为0.3；低负荷运输（每天行驶300km以下），年利润16万元/辆，年损坏率为0.1。现要求制定5年计划，如何分配不同负荷下的卡车数量，使5年的总利润最大。例1的线性规划模型s.t.特点：递归性动态规划的应用对象应用对象：多阶段决策优化包括：1）不同时间段的规划问题动态规划的原意2）可化为不同地段、步骤的静态规划问题美国数学家R.Bellman于50年代提

2、出动态规划例2：最短路线问题沿着线路网络，在A、E之间铺设一条管路，如何使总长度最小。AB1B3B2C1C2D1D3D2E321431335253142315动态规划的类型根据变量的类型，动态规划可化分为：1）离散确定型：2）连续确定型：2）离散随机型：Markov链3）连续随机型：Markov随机过程动态规划的基本概念1。阶段：2。状态3。决策和策略4。状态转移方程5。指标函数阶段1。阶段：问题过程，按时间、空间的特征分解成若干相互联系的阶段。AB1B3B2C1C2D1D3D2E321431335253142315状态2。状态：各阶段开始时的客观条件，叫做状态。常用sk代

3、表第k阶段的状态变量，其允许范围为Sk。如例2中，S1={A}S2={B1，B2，B3}S3={C1，C2}S4={D1，D2，D3}决策3。决策：对取定的状态，就可以作出不同的决定，以确定下一阶段的状态，称为决策。表示决策的变量，称为决策变量，用uk(sk)表示。决策变量的集合，称为允许决策集合。用Dk(sk)表示。决策举例例2中：D1(A)={B1，B2，B3}u1(A)=BiAB1B3B2C1C2D1D3D2E321431335253142315状态转移方程给定第k阶段的决策uk(sk)，则第k+1阶段的状态也完全确定，这一关系即状态转移方程：sk+1=Tk(sk,u

4、k(sk))状态转移方程给出了一种递推关系。在例2中：sk+1=uk(sk)状态的无后效性动态规划要求问题具有无后效性：给定某阶段的状态sk，则以后各阶段的状态sl（l>k）都只受sk的影响，与之前的状态无关。策略策略：各阶段决策构成的决策序列。p1,n={u1(s1),u2(s2),…,un(sn)}例2中：策略的总数为：3231=18动态规划的目的是要选择最优的一种策略指标函数用Vk,n(sk,pk,n)表示从状态sk出发，沿策略pk,n到达状态sn+1时的指标函数值从k阶段开始规划的最优指标函数值fk(sk)有如下关系：系统优化指标为：指标函数举例AB1B3B2

5、C1C2D1D3D2E321431335253142315V4,4(D1,p4,4)=V4,4(D1,u4,)=v4(D1,E)=3指标函数的可分离性指标函数具有可分离性k是Vk+1,n(sk+1,pk+1,n)的单调函数。该要求为了满足动态规划的求解需要。指标函数的常见形式k的常见的形式有：阶段指标函数指标函数的常见形式最优化原理最优化原理：最优策略具有如下性质：无论初始状态及初始决策如何，对于先前形成的状态，余下的决策的决策序列应构成子问题的最优策略。最优化原理只是策略最优的一个必要条件最优化定理最优化定理：策略p*1,n是最优决策序列的充要条件是，对于所有的k，都

6、有：f1(s1)fk(sk)最优化定理的推论由最优化定理可以得到一个递推关系：或者：逆序解法逆序解法：T1s1s2u1…v1(s1,u1)Tksksk+1ukvk(sk,uk)…Tnsnsn+1unvn(sn,un)分治思想将原问题分解为子问题，只考虑最优子问题所在的分枝，类似于分枝定界法减少重复计算例2：逆序法解沿着线路网络，在A、E之间铺设一条管路，如何使总长度最小。AB1B3B2C1C2D1D3D2E321431335253142315第1步AB1B3B2C1C2D1D3D2E321431335253142315S4={D1，D2，D3}，u4(s4)={E},f4(

7、s4)=min{v4(s4,u4)+f5(s5)}u4D4(s4)f4(D1)=v4(D1,E)=3,f4(D2)=1,f4(D3)=5第2步S3={C1，C2}f3(s3)=min{v3(s3,u3)+f4(s4)}u3D3(s3)D3(C1)={D1，D2，D3};D3(C2)={D1，D2，D3}AB1B3B2C1C2D1D3D2E321431335253142315第2步（1）AB1B3B2C1C2D1D3D2E321431335253142315第2步（2）AB1B3B2C1C2D1D3D2E3214