动态规划(完整)

主要内容:§7.1多阶段决策问题§7.2动态规划的基本概念和基本原理§7.3动态规划应用举例第七章动态规划例求解最短路问题A164143333514247436342QA2TA3B1B2C2B3C1ⅠⅡⅢⅣ分阶段的最短路径•Ⅳ：C1—T3•Ⅲ--Ⅳ:B1—C1—T4•Ⅱ--Ⅲ--Ⅳ：A2—B1—C1—T7•Ⅰ--Ⅱ--Ⅲ--Ⅳ：•Q—A2—B1—C1—T11•Q--A3—B1—C1—T11•Q--A3—B2—C2—T11最短路径A164143333514247436342QA2TA3B1B2C2B3C1ⅠⅡⅢⅣ34476117811最短路径解的特点•1、可以将全过程求解分为若干阶段求解；------多阶段决策问题•2、在全过程最短路径中，将会出现阶段的最优路径；-----递推性•3、前面的终点确定，后面的路径也就确定了，且与前面的路径（如何找到的这个终点）无关；-----无后效性•3、逐段地求解最优路径，势必会找到一个全过程最优路径。-----动态规划§7.1多阶段决策问题•动态规划是解决多阶段最优决策的方法,由美国数学家贝尔曼(R.Bellman)于1951年首先提出;•1957年贝尔曼发表动态规划方面的第一部专著“动态规划”,标志着运筹学的一个新分支的创立。•动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题,采用顺序求解方法,通过解一系列小问题达到求解整个问题目的;•动态规划的各个决策阶段不但要考虑本阶段的决策目标,还要兼顾整个决策过程的整体目标,从而实现整体最优决策.动态规划的分类:•离散确定型•离散随机型•连续确定型•连续随机型动态规划的特点:•动态规划没有准确的数学表达式和定义精确的算法,它强调具体问题具体分析,依赖分析者的经验和技巧。•与运筹学其他方法有很好的互补关系,尤其在处理非线性、离散性问题时有其独到的特点。通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。具有无后效性的多阶段决策过程的特点是系统过去的历史，只能通过现阶段的状态去影响系统的未来，当前的状态就是后过程发展的初始条件。动态规划的应用•动态规划在工程技术,企业管理,军事部门有广泛的应用;可解决资源分配,生产调度,库存管理,路径优化,设备更新,投资规划,排序问题和生产过程的最优控制等问题;使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的形式,要涉及以下概念:(1)阶段(2)状态(3)决策与策略(4)状态转移方程(5)指标函数(6)基本方程§7.2动态规划的基本概念和基本思想一、基本概念(1)划分阶段把一个复杂决策问题按时间或空间特征分解为若干(n)个相互联系的阶段(stage),以便按顺序求解;阶段变量描述当前所处的阶段位置，一般用下标k表示;每阶段有若干状态(state),表示某一阶段决策面临的条件或所处位置及运动特征的量,称为状态。反映状态变化的量叫作状态变量。k阶段的状态特征可用状态变量sk描述;每一阶段的全部状态构成该阶段的状态集合Sk，并有skSk。每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段的初始状态记作sk，终止状态记为sk+1，也是下个阶段的初始状态。(2)确定状态(3)决策、决策变量所谓决策就是确定系统过程发展的方案，决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。用以描述决策变化的量称之决策变量，和状态变量一样，决策变量可以用一个数，一组数或一向量来描述．也可以是状态变量的函数，记以，表示于k阶段状态sk时的决策变量．()kkkxxs决策变量的取值往往也有一定的容许范围，称之允许决策集合．决策变量xk(sk)的允许决策集用XK(SK)表示，xk(sk)XK(SK),允许决策集合实际是决策的约束条件。(4)策略和允许策略集合策略(Policy)也叫决策序列．策略有全过程策略和k部子策略之分，全过程策略是指具有n个阶段的全部过程，由依次进行的n个阶段决策构成的决策序列，简称策略，表示为。从k阶段到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为，显然当k=1时的k部子策略就是全过程策略。1,12{,,,}nnpxxx,1{,,,}knkknpxxx(5)状态转移方程状态转移确定从一个状态到另一个状态的转移过程,由状态转移方程描述:sk+1=T(sk,xk);状态转移方程在大多数情况下可以由数学公式表达,如:sk+1=sk+xk；(6)指标函数用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。用vk(sk,xk)表示第k段处于状态sk且所作决策为xk时的指标，则它就是第k段指标函数，简记为vk。用f(sk,xk)表示第k子过程的指标函数。表示处于第k段sk状态且所作决策为xk时，从sk点到终点的距离。由此可见，f(sk,xk)不仅跟当前状态sk有关，（2）过程指标函数（也称目标函数）（1）阶段指标函数（也称阶段效应）还跟该子过程策略pk(sk)有关,严格说来，应表示为fk(sk,pk(sk))。它是由各阶段的阶段指标函数vk(sk,xk)累积形成的，对于k部子过程的指标函数可以表示为：,,11111(,,,,,,)(,)(,)(,)knknkkkknnkkkkkknnnffsxsxsxvsxvsxvsx式中，表示某种运算，可以是加、减、、乘、除、开方等．多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:(,)nkkkkikfvsu有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，(,)nkkkkikfvsu(7)最优解用fk*(sk)表示第k子过程指标函数Fk(sk,pk(sk))在状态sk下的最优值，即:()(){(,())}1,2,,kKkkkkkkkpPsfsoptFspskn称fk(sk)为第k子过程上的最优指标函数；与它相应的子策略pk(sk)称为状态sk下的最优子策略，记为pk*(sk)例用动态规划求解最短路问题A164143333514247436342QA2TA3B1B2C2B3C1最短路的求解:阶段:可分为4个阶段,k=1,...,4。状态:可用城市编号,S1={Q},S2={A1,A2,A3},S3={B1,B2,B3},S4={C1,C2},S5={T}决策:决策变量也可用城市编号;状态转移方程:sk+1=xk;阶段指标函数：过程指标（阶段递推）函数:,kkkkksxvsxc11()(,)()kkkkkkkfsminvsxfsA164143333514247436342QA2TA3B1B2C2B3C1k=4f4(C1)=3,f4(C2)=4k=3f3(B1)=min{1+f4(C1)=4*,4+f4(C2)=8}=4f3(B2)=min{6+f4(C1)=9,3+f4(C2)=7*}=7f3(B3)=min{3+f4(C1)=6*,3+f4(C2)=7}=6k=2f2(A1)=min{7+f3(B1),4+f3(B2),6+f3(B3)}=min{11*,11*,12}=11f2(A2)=min{3+f3(B1),2+f3(B2),4+f3(B3)}=min{7*,9,10}=7f2(A3)=min{4+f3(B1),1+f3(B2),5+f3(B3)}==min{8*,8*,11}=8k=1f1(Q)=min{2+f2(A1),4+f2(A2),3+f2(A3)}=min{13,11*,11*}=11最短路是：QA2B1C1T，p={A2,B1,C1,T}QA3B1C1T，p={A3,B1,C1,T}QA3B2C2T，p={A3,B2,C2,T}A164143333514247436342QA2TA3B1B2C2B3C1•整个过程的最优策略应具有这样的性质:无论过去的状态和决策如何,对前面的决策所形成的状态而言,后续的诸决策必须构成最优策略；•上一条成立的条件是阶段递推函数严格单调。二、动态规划的最优性原理在例题中，求解最短路线的计算公式可以概括写成：5511()()0()min{(,())()}4,3,2,1kkkkkkkkkkkxXsfsfsvsxsfsk其中，vk在这里表示从状态sk到由决策xk所决定的状态sk+1之间的距离。f5(s5)=0是边界条件，表示全过程到第四阶段终点结束。一般地，对于n个阶段的决策过程，假设只考虑指标函数是“和”与“积”的形式，第k阶段和第k+1阶段间的递推公式可表示如下：当过程指标函数为下列“和”的形式时()(){(,())}kKkkkkkkkpPsfsoptfsps()(,)kkkniiipPsikoptvsx相应的函数基本方程为:1111()0(){(,())()},1,,2,1kknnkkkkkkkkxXfsfsoptvsxsfsknn当过程指标函数为下列“积”的形式时()(){(,())}kKkkkkkkkpPsfsoptfsps()(,)ikiniiipPsikoptvsx相应的函数基本方程为:1111()1(){(,())()},1,,2,1kknnkkkkkkkkxXfsfsoptvsxsfsknn动态规划的优缺点动态规划的优点•可以解决线性,非线性,整数规划无法有效求解的复杂问题;•容易找到全局最优解;•可以得到一组解;动态规划的缺点：•没有标准的模型可供应用,构模依赖于个人的经验和技巧;•状态变量需满足无后效性,有较大的局限性;•动态规划的维数灾难限制了对规模较大问题的求解效率;§7.3动态规划方法应用动态规划的步骤：1.将问题按时间或空间划分为满足递推关系的若干阶段,对非时序问题可人为地引入“时段”概念;2.正确选择状态变量sk,满足:可知性:正确描述动态过程演变,可直接或间接确定状态变量的值;无后效性:后面的决策与前面的决策无关;3.确定决策变量xk以及允许决策集合Xk;4.写出状态转移方程sk+1=T(sk,xk);5.决策变量的取值范围6.写出过程指标函数（阶段函数）的递推关系,应满足:a)是定义在所有阶段上的数量函数；b)具有可分离性，并满足递推关系；c)阶段函数应严格单调。动态规划应用举例：1.最优路径问题2.资源配置问题3.生产与库存问题4.机器负荷分配问题5.复合系统工作可靠性问题6.二维背包问题7.设备更新问题8.货郎担问题9.非线性规划的求解1.最优路径问题某厂要确定一种新产品在今后五年内的价格，并已拟定只在5、6、7、8元这四种单价中进行选择。据预测，今后五年不同价格下每年盈利（万元）见下表，但是各相邻年度价格增减不得超过1元。问今后五年内每年定价各为多少，可逾七五年总利润最大。价格/元盈利/万元第一年第二年第三年第四年第五年592458675864765973887664价格/元盈利/万元第一年第二年第三年第四年第五年592458675864765973887664131411843410182223172428283037353638解：1、建立动态规划模型：阶段：以年划分阶段，k=5,4,3,2,1；状态变量sk为每个阶段初的价格，则Sk={5,6,7,8}；决策变量xk为每年所确定的价格，则Xk={5,6,7,