水资源系统分析-第5章动态规划.

2008.2.29第5章动态规划5.1动态规划的基本原理许多问题属于动态系统，随时间或空间变化。1951年美国Bellman提出了最优化原理。动态规划-DP是解决多阶段决策问题的一种方法：根据问题的空间或时间特性将过程分为若干阶段,在每一阶段中都需作出决策,这种连续不断的作出的多阶段决策,构成一个策略。动态规划特点在于，它可以把一个n维决策问题变换为几个一维最优化问题，从而简化问题。动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再求解。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643例最短输水路径问题解：整个过程分三个阶段，从最后一个阶段开始。第一步（C→D）：C有三条路线到终点D。AB1B2C1C2C3D24333321114显然有f1(C1)=1；f1(C2)=3；f1(C3)=4例d(B1,C1)+f1(C1)3+1f2(B1)=mind(B1,C2)+f1(C2)=min3+3d(B1,C3)+f1(C3)1+44=min6=45第二步（B→C）：B到C有六条路线。AB1B2C1C2C3D24333321114DC1C2C3(最短路线为B1→C1→D)d(B2,C1)+f1(C1)2+1f2(B2)=mind(B2,C2)+f1(C2)=min3+3d(B2,C3)+f1(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3(最短路线为B2→C1→D)f2(B1)=4第三阶段（A→B）：A到B有二条路线。∴f3(A)=min=min｛6,7｝=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路线为A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2AB1B2C1C2D24333321114DC1C2C3B1B2A最短路线为A→B1→C1→D路长为6(C1,4)(D,3)(D,4)(D,1)(C1,3)(B1,6)AEHFIGKB416553446432课堂练习AEHFIGKB416553446432(4,B)(3,B)(5,G)(6,G)(11,F)(9,F)(14,H)问题复杂度AB1B2C1C2D24333321114DC1C2C3B1B2A(C1,4)(D,3)(D,4)(C1,3)(B1,6)(D,1)如果枚举所有路径，共（2*3*1）=6条路径需要计算3*（2*3*1）=18次加5次比较动态规划：2*3+2=8次加2*（3-1）+1=5次比较123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643如果枚举所有路径，路径数：2*3*2*2*2=48条路径计算6*48=288次加和47次比较动态规划：3*2+3*2+4*2+2*3+2=22次加3+3+4+2*2+1=15次比较动态规划有更多成果AB1B2C1C2D24333321114DC1C2C3B1B2A(C1,4)(D,3)(D,4)(C1,3)(B1,6)(D,1)动态规划不仅得到A-D的最佳路径，中间结点的最佳路径也同时得到，比如B1-D的最佳路径。枚举法只能得到A-D的最佳路径，如果要得到所有中间最有路径，需要更多的排序计算。1、阶段：把一个问题的过程分为若干个相互联系的阶段，以便于按一定的次序去求解。描述阶段的变量称为阶段变量。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。年、月、路段5.2动态规划的基本概念2、状态：表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述过程状态的变量称为状态变量。状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。3、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。描述决策的变量，称为决策变量。决策变量是状态变量的函数。可用一个数、一组数或一向量来描述。在实际问题中决策变量的取值往往在某一范围之内，称为允许决策集合。状态转移方程确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量uk一经确定，第k+1阶段状态变量sk+1的值也就确定。4、状态转移方程),,,,,,(),,,(),(221112211231112kkkkusususTsususTsusTs图示如下：12ks1u1s2u2s3skuksk+1能用动态规划方法求解的是一类特殊的多阶段决策过程，即具有无后效性(马尔可夫性)的多阶段决策过程。如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来的发展。有后效性的例子678))(,())(,())(,(12222311112kkkkksusTssusTssusTs动态规划中能处理的状态转移方程的形式。状态具有无后效性的多阶段决策过程的状态转移方程如下：状态变量要满足无后效性的要求：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为允许策略集合。5、策略)(),...,(),...,(),(2211nnkksusususu)()(kkkksDsu从允许策略集合中找出达到最优效果的策略称为最优策略。用来衡量所实现过程优劣的一种数量指标，为指标函数。动态规划模型的指标函数，应具有可分离性，并满足递推关系。分为阶段指标函数与过程指标函数，6、指标函数例：水库优化调度问题一年调节水库，起调水位（枯水期末）与最终水位均为死水位，相应的蓄水量为死库容，调度期分为N个阶段，以一年内总效益最大为目标的动态规划模型如下：(1)阶段变量：t=1,2,…,N；表示调度期内的第t时段(月、旬)(2)决策变量：第t阶段水库供水量xt(3)状态变量：阶段初期水库的蓄水量VtNtEWSxPQVVttttttt,2,1,1(4)状态转移方程：(5)指标函数：t阶段的指标函数为该阶段的供水效益，如发电效益,可表示为rt(vt,xt).)(),(max1xHgxVrZNtttt(7)约束条件：max,min,max,min,ttttttxxxVVVdnVVV11)(),,(max)(1*1*ttttttttVRQxVrVR(8)基本方程：最优化原理与DP模型Bellman最优化原理：作为整个过程的最优策略具有这样的性质：无论初始的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就是说，一个最优策略的子策略也是最优的。oABCDEF注意避免歧义AB1B2C1C2D24333321114DC1C2C3B1B2A(C1,4)(D,3)(D,4)(C1,3)(B1,6)(D,1)相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。B1-C1-D不是阶段2到阶段4的最佳路径，但对于A来说，B1-C1-D形成最优子策略。)(),()(),(11)(,kkkkksDukknkiiiinksfusvusvVoptsfkkk),(iiiiusvv)().,()(),(11)(,kkkkksDukknKiiiinksfusvusvVoptsfkkk指标的最优化d(B2,C1)+f1(C1)2+1f2(B2)=mind(B2,C2)+f1(C2)=min3+3d(B2,C3)+f1(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3(最短路线为B2→C1→D)f2(B1)=41、正确选择状态变量选择变量既要能确切描述过程演变又要满足无后效性。2、确定决策变量及允许决策集合通常选择所求解问题的关键控制变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。DP建模要点4、确定状态转移方程根据k阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。5、确定阶段指标函数和最优指标函数，建立动态规划基本方程阶段指标函数是指第k阶段的收益，最优指标函数是指从第k阶段状态出发到第n阶段末所获得收益的最优值，最后写出动态规划基本方程。按过程演变的特征，动态规划模型划分为确定性模型和随机性模型两大类。根据状态变量的取值是离散还是连续，它们又可区分为连续和离散两类。因此有离散确定性模型，连续确定性模型，离散随机性模型和连续随机性模型四大类。-例用动态规划求解非线性规划问题-0122332max321321ixxxxxxxz解：x1,x2,x3三变量依次取值，所以可划分出3个阶段,k=1,2,3；xk为决策变量；3132132maxkkkxxxxz偶然的1223321xxx递推方程：s1=12;x1s2=s1-x1;x2s2/3s3=s2-3x2;x3s3/2)(max)(11)(kkksDxkkxfkxxfkkk基本方程：-状态转移方程与基本方程--设状态变量为sk，表示阶段决策变量的取值范围基本方程的具体形式3132132maxkkkxxxxz模型：)(max)(11)(kkksDxkkxfkxxfkkk基本：)(max)()(2max)(3max)(2211113322233312233sfxsfsfxsfxsfDxDxDx具体：2,233max)(3*3332/03333sxsxsfsx　当k=3时：2/0,3/0,12033221sxsxx　　x的取值范围：s1=12;x1s2=s1-x1;x2s2/3s3=s2-3x2;x3s3/2逆推：相对于前面状态的最优x的取值范围：6,4)3(232max)(2max)(2*2222223/03323/0222222sxsxsxsfxsfsxsx　2/0,3/0,12033221sxsxx　　当k=3时：2233*33333,2,23)(xsssxssf　-当k=2时---：1122*22222,6,4)(xsssxssf　2/0,3/0,12033221sxsxx　　当k=2时：当k=1时：4,64)(41max)(max)(*1211112011211201111xxsxxsfxsfxx　x的取值范围：2,233max)(6,4)(4,64)(3*3332/0332*22222*11133sxsxsfsxssfxsfsx　　　2,4,34,8*33*22xsxs　1231112223sxssxss回溯例用动态规划求解0,1823122453max21212121xxxxxxxxz　0,1823122453max21212121xxxxxxxxz　2;32;123;18;4222112222122112112111sxxsssxssxsxs)(max),,(11)(,3,2,1kkkkRDxkkkksfxcsssfkkk状态转移：解：状态变量为k阶段约束条件，用s11,s12,s21，s22表示状态，xk表示决策变量当k=2时，),(21min),(25min5max),(2221*222212)2,2min(02221222212ssxssxssfssx当k=1时，)31