动态规划问题的研究

动态规划问题的研究09理学研470920622 王庆权动态规划所研究的对象是多阶段决策问题， 所谓多阶段决策问题是指一类活动过程， 它可以分为若干个互相联系的阶段， 在每个阶段都需要作出决策。这个决策不仅决定决定这一阶段的利益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称之为策略。多阶段决策问题就是 求一个策略，使各阶段的效益的总和达到最优。问题的提出多阶段决策问题在日常生活中是经常遇到的，下面举两个例子：问题一、最短路径问题给出一个网络(如下图)，从Ao点铺设一条煤气管道到A6点，必须经过五个中间站，第一站可以在a,Bi中选择。类似地，第二、三、四、五站可以在A2,B2,C2,D2、A3,B3,C3、A4，B4，C4、和A5，Bs中选择。能用管道连接的两站之间的距离已经给定，两点之间没有连线的表示这两点之间不能铺设管道。要求选择一条由 人到Aj铺设管线，使总距离最短。问题二、多阶段资源分配问题设有数量为x的某种资源，将它投入两种生产方式 A和B中，以数量y投入生产方式A，剩下的量投入生产方式B,则可得到收入g(y)•h(x-y)，其中g(y)和h(y)是已知函数，并且g(0)=h(0)=0。再假设以y与x-y分别投入两种生产方式A,B后可以回收再生产，回收率分别a与b(0乞a乞1,0乞b乞1)。因此在第一阶段生产后回收的总资源为为=ay•b(x-y)。我们再将捲投入生产方式A和b,和第一阶段一样，若以％与为-％分别投入生产方式A和B，则又可得到收入g(y,)h(x^yj，回收资源x2^ay!匕(为-yj。因此，两个阶段的总收入为 g(y)h(^y)-g(yjh(x^yj如果上面的过程进行n个阶段，希望选择y,y1,y2JH,ynJ，使n个阶段的总收入最大，则我们的问题就变成：求yy,y2,IH,yn□，使g(y)h(x-y)g(yjh(x“—yj川g(ynj)hg-y.」)达到最大，且满足条件,=ay+b(x_y)X2=ayi+b(xi_yjJIIIIHIIXn」=ayn/+b(Xn/—%/)[0兰yWx,oWyi兰x,i=1,2，川，n—1问题的解决首先，我们来分析一下上面的两个问题，我们可以将上面的问题描述成如下：有一个系统，可以分成若干个阶段，任意阶段 k，系统的状态可以用兀表示(xk可以是数量、向量、集合等)。在每一阶段k的每一个状态Xk都有一个决策集合Qk(xJ，在Qk(xk)中选定一个决策qk•Qk(xk)，状态xk就转移到新的状态xk1.=Tk(xk,qk)，并且得到效益R<(xk，qk)。我们的目的就是在每一个阶段都在它的决策集合中选择一个决策， 使所有阶段的总效益Rk(xk,qk)达到最大。这样的多阶段决策问题称为动态规划，它表示是一个k多步最优解问题。我们来分析问题一，首先这显然是一个多决策问题，从 人至人可以分为6个阶段。从A出发到A或B!为第一阶段，这时有两个选择：走到A或者走到B。若我们选择走到A的决策，则A就是下一阶段的起始点。在下一阶段，我们从 A点出发，有一个可供选择的决策集合｛A,B2,C2｝，很明显，前面各阶段的决策如何选择，直接影响着其余各阶段的行进路线，我们的目的就是在每个阶段选择一个决策，使它们决定的总路程最短。下面我们来球此问题的最短路线，并以此来说明处理多阶段决策问题的基本思想一一最优化原理。先引入一下几个符号：令n表示由某点至终点A6之间的阶段数。例如A0至A是6个阶段，令s表示在任一阶段所处的状态，s称为状态变量，例如在第三阶段的开始点是a2，则称所处的状态为 。令Xn（S）为决策变量，它表示当状态处于S，还有n个阶段时所选择的一个决策。 令fn（S）表示现在处在状态s还有n个阶段时，由s至终点A的最短距离。令d（s,Xn）表示s点到点焉的距离。我们从最后一个阶段开始计算并逐步推移至 A0点。由定义，讯人）表示由A至A的最短距离。故人（人）=4，同理fi（B5）=3。现计算最后两个阶段，n=2,若从A出发，则有两个选择，一是至A，一是至B5，所以f2（A0=min{d（A4,A5）仏阳小代泯）£假）}=min{34,53}=7这说明由A至终点Ae的最短距离是乙其最短路线是A4—A^—Ae.X2（A4）=A5。如果从b4出发，则f2（B4）=min{d（B4，A5）仏人）8厲也）「d）}=min{54,23}=5X2（B4）=B5，最短路线是B4>B5>A6，最短路程是5。同理我们可得f2G）=min{dGA）fi（A）,d（C4,B5）fid）}=min{64,63}=9X2（C4）=B5，最短路线是C4>B5>Ae，最短路程是9。现在讨论n=3的情况，我们分别以A3,B3,C3为出发点来计算。f3（A3）=min{d（A3，A』彳乂⑴“他也）f?®』}=min{27,25^7X3（Aj）=B4，最短路线是A3rB4—B5—As，最短路程是7。上式表示由A出发有两种选择，到A或b4，如果选A，那么到达A以后，一定要走a4到A6的最短路线；如果这一步选 B4，那么到达B4以后，一定走B4到A最短路线。所以A>A的最短路线就是这两条中较短的一条。同理f3（B3）=min{d（B3,B4）fzQ）}=min{15,29}=6X3（BJ=B4，最短路线是B3>B4>B5、A，最短路程是6。f3（C3）=min{d（C3,B4）f2（B4）,dG,C4）f2（C4）}=min{35,39^8X3（C3）=B4，最短路线是C3>B4>B5、A，最短路程是&n=4的情况完全类似，我们可以得到门心仏人)73(阳戍宀尼)n{67,86}=13x4(A)二A同理f4(B2)=10,X4(B2)=A.f4(C2)=9,X4(C2)=B3.f4(D2)=12,X4(D2)当n=5时，有人启两点，在A处有3个决策A2,B>,C2供选择，如果选择A2，那么从A出发一定是走由A到A6的最短路线；同样，如果选择B2，那么从B2点以后一定是走由B2到A的最短路线；选C2点也是如此，所以只要在这三条路线中选一条最短路线， 就是A到A6的最短路线。f5(A)=min{d(AA)f4(A),d(A,B2)f/BjaAO f/C?)}-min{2 13,310,69}=13x5(A)=B2，最短路线是AtB2tAtB4tB5tA，同样f5(BJ=min{d(B1,B2)f^),d(B,G)彳心^宀口)f^)}=min{810,79,1612}=16X^BJ=C2，最短路线是BrC2rB^B4rB5rA。当n=6时，出发点只有一个A点，有两种选择，因此f6(Ao)=min{d(Ao,A)f5(A),d(Ao,BJf5(BJ}=min{513,1316}=18凤(人)=A至此，上图的最短路线已经求得，为 A)>A,>B2-A^-B4—•Bs—•A。从上面的计算过程，我们可以看出，在求解的各个阶段，我们利用了n阶段的最优值与n-1阶段的最优值之间的如下关系 ：fn(s)=min{d(s,Xn(s))fn4(Xn(s))},n=2,3|||6,£(s)=d(s,As)最优化原理动态规划就是根据上述递推关系求得问题的解的， 这种递推关系是根据动态规划的最优化原理而推到出来的。我们给出动态规划最优化原理的描述一个过程的最优策略具有这样的性质，即无论其初始状态及其出事决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而言，必须构成最优策略。动态规划最优化原理的直接解释：如下图，如果I ----n是从A到C的最优路线，那么路线n—定是从B到C的最优路线，这是很容易用反证法来证明的。如果n不是从 B到C的最优路线。 n'是比n好的从B到C的路线，那么I--n就是比1----n更好的从a到C的路线，这与I---n是最优路线矛盾。下面我们利用动态规划最优化原理给出问题二多资源分配问题的递推公式令fk(x)表示有资源，再进行k个阶段生产并采取最优分配策略后得到的最大总收入。当k=1时，f,x)二max{g(y)•h(x-y)}，当k=2时，由于前一个阶段分别以 y、x-y投0应兰入A、B,生产以后可以回收％=ay，b(x-y)作为下一阶段开始时可以投入生产的资源数量，若采取最优方式投入生产，由最优化原理，后一个阶段的收入是 f'xj，所以f2(x)=max{g(y)h(x-y)fi(ayb(x-y))}0空空对任意的k，2乞k乞n，同样的分析可得fk(x)=嬲汝9(丫)h(x-y)fk」(ayb(x-y))}因此，我们得到递推关系如下：f1(x^r^a)<{g(y)h(x-y)}fk(x) h(x-y)f」ayb(x-y))},k一2从对阶段决策问题的数学模型可以看到， 一个多阶段决策过程的极值函数可以看作是过程的初始状态与阶段数目的函数。 任意给定一个决策序列， 如果是最优的，那么从后面最后k阶段开始，对由这个策略形成的后面k阶段的初始状态组成的k阶段问题而言，这个策略的后面的k个决策一定是这个 k阶段问题的最优策略，与这 k阶段以前的决策无关。木兰辞：唧唧复唧唧，木兰当户织。不闻机杼声，惟闻女叹息。问女何所思，问女何所忆。女亦无所思，女亦无所忆。昨夜见军帖，可汗大点兵，军书十二卷，卷卷有爷名。阿爷无大儿,木兰无长兄。愿为市鞍马，从此替爷征。愿为市鞍马，从此替爷征。-东市买骏马，西市买鞍鞘，南市买辔头，北市买长鞭。旦辞爷娘去，暮宿黄河边，不闻爷娘唤女声，但闻黄河流水鸣溅溅。旦辞黄河去,暮至黑山头，不闻爷娘唤女声，但闻