动态规划问题的研究.doc
- 文档编号:1880356
- 上传时间:2023-05-02
- 格式:DOC
- 页数:5
- 大小:438KB
动态规划问题的研究.doc
《动态规划问题的研究.doc》由会员分享,可在线阅读,更多相关《动态规划问题的研究.doc(5页珍藏版)》请在冰点文库上搜索。
动态规划问题的研究
09理学研470920622王庆权
动态规划所研究的对象是多阶段决策问题,所谓多阶段决策问题是指一类活动过程,它可以分为若干个互相联系的阶段,在每个阶段都需要作出决策。
这个决策不仅决定决定这一阶段的利益,而且决定下一阶段的初始状态。
每个阶段的决策确定以后,就得到一个决策序列,称之为策略。
多阶段决策问题就是求一个策略,使各阶段的效益的总和达到最优。
问题的提出
多阶段决策问题在日常生活中是经常遇到的,下面举两个例子:
问题一、最短路径问题
给出一个网络(如下图),从点铺设一条煤气管道到点,必须经过五个中间站,第一站可以在中选择。
类似地,第二、三、四、五站可以在、、、和中选择。
能用管道连接的两站之间的距离已经给定,两点之间没有连线的表示这两点之间不能铺设管道。
要求选择一条由到铺设管线,使总距离最短。
问题二、多阶段资源分配问题
设有数量为的某种资源,将它投入两种生产方式A和B中,以数量投入生产方式A,剩下的量投入生产方式B,则可得到收入,其中和是已知函数,并且。
再假设以与分别投入两种生产方式A,B后可以回收再生产,回收率分别与。
因此在第一阶段生产后回收的总资源为。
我们再将投入生产方式A和B,和第一阶段一样,若以与分别投入生产方式A和B,则又可得到收入,回收资源。
因此,两个阶段的总收入为
如果上面的过程进行个阶段,希望选择,使个阶段的总收入最大,则我们的问题就变成:
求,使
达到最大,且满足条件
问题的解决
首先,我们来分析一下上面的两个问题,我们可以将上面的问题描述成如下:
有一个系统,可以分成若干个阶段,任意阶段,系统的状态可以用表示(可以是数量、向量、集合等)。
在每一阶段的每一个状态都有一个决策集合,在中选定一个决策,状态就转移到新的状态,并且得到效益。
我们的目的就是在每一个阶段都在它的决策集合中选择一个决策,使所有阶段的总效益达到最大。
这样的多阶段决策问题称为动态规划,它表示是一个多步最优解问题。
我们来分析问题一,首先这显然是一个多决策问题,从至可以分为6个阶段。
从出发到或为第一阶段,这时有两个选择:
走到或者走到。
若我们选择走到的决策,则就是下一阶段的起始点。
在下一阶段,我们从点出发,有一个可供选择的决策集合,很明显,前面各阶段的决策如何选择,直接影响着其余各阶段的行进路线,我们的目的就是在每个阶段选择一个决策,使它们决定的总路程最短。
下面我们来球此问题的最短路线,并以此来说明处理多阶段决策问题的基本思想——最优化原理。
先引入一下几个符号:
令表示由某点至终点之间的阶段数。
例如至是6个阶段,令表示在任一阶段所处的状态,称为状态变量,例如在第三阶段的开始点是,则称所处的状态为。
令为决策变量,它表示当状态处于,还有个阶段时所选择的一个决策。
令表示现在处在状态还有个阶段时,由至终点的最短距离。
令表示点到点的距离。
我们从最后一个阶段开始计算并逐步推移至点。
由定义,表示由至的最短距离。
故,同理。
现计算最后两个阶段,,若从出发,则有两个选择,一是至,一是至,所以
这说明由至终点的最短距离是7,其最短路线是。
如果从出发,则
,最短路线是,最短路程是5。
同理我们可得
,最短路线是,最短路程是9。
现在讨论的情况,我们分别以为出发点来计算。
,最短路线是,最短路程是7。
上式表示由出发有两种选择,到或,如果选,那么到达以后,一定要走到的最短路线;如果这一步选,那么到达以后,一定走到最短路线。
所以的最短路线就是这两条中较短的一条。
同理
,最短路线是,最短路程是6。
,最短路线是,最短路程是8。
的情况完全类似,我们可以得到
同理
当时,有两点,在处有3个决策供选择,如果选择,那么从出发一定是走由到的最短路线;同样,如果选择,那么从点以后一定是走由到的最短路线;选点也是如此,所以只要在这三条路线中选一条最短路线,就是到的最短路线。
,最短路线是,同样
,最短路线是。
当时,出发点只有一个点,有两种选择,因此
至此,上图的最短路线已经求得,为。
从上面的计算过程,我们可以看出,在求解的各个阶段,我们利用了阶段的最优值与阶段的最优值之间的如下关系:
最优化原理
动态规划就是根据上述递推关系求得问题的解的,这种递推关系是根据动态规划的最优化原理而推到出来的。
我们给出动态规划最优化原理的描述
一个过程的最优策略具有这样的性质,即无论其初始状态及其出事决策如何,其以后诸决策对以第一个决策所形成的状态作为初始状态而言,必须构成最优策略。
动态规划最优化原理的直接解释:
如下图,如果Ⅰ----Ⅱ是从A到C的最优路线,那么路线Ⅱ一定是从B到C的最优路线,这是很容易用反证法来证明的。
如果Ⅱ不是从B到C的最优路线。
Ⅱ’是比Ⅱ好的从B到C的路线,那么Ⅰ--Ⅱ’就是比Ⅰ----Ⅱ更好的从A到C的路线,这与Ⅰ---Ⅱ是最优路线矛盾。
下面我们利用动态规划最优化原理给出问题二多资源分配问题的递推公式
令表示有资源,再进行个阶段生产并采取最优分配策略后得到的最大总收入。
当时,,当时,由于前一个阶段分别以、投入A、B,生产以后可以回收作为下一阶段开始时可以投入生产的资源数量,若采取最优方式投入生产,由最优化原理,后一个阶段的收入是,所以
对任意的,,同样的分析可得
因此,我们得到递推关系如下:
从对阶段决策问题的数学模型可以看到,一个多阶段决策过程的极值函数可以看作是过程的初始状态与阶段数目的函数。
任意给定一个决策序列,如果是最优的,那么从后面最后阶段开始,对由这个策略形成的后面阶段的初始状态组成的阶段问题而言,这个策略的后面的个决策一定是这个阶段问题的最优策略,与这阶段以前的决策无关。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 问题 研究