运筹学动态规划(I)

《运筹学动态规划(I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划引言□动态规划是解决多阶段决策过程最优化的一种方法。□该方法是由美国数学家贝尔曼（R.E.Bellman）等人在20世纪50年代初提出的。并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。Bellman在1957年出版了《DynamicProgramming》一书，是动态规划领域中的第一本著作。□动态规划与其他规划方法的不同之处在于：动态规划是求解某类问题（多阶段决策问题）的一种方法，是考察问题的一种途径，而不是一种特定算法。因此，它不像线性规划那样有一个标准的数学表达式和明确定义的一组（

2、算法）规则，而必须对具体问题进行具体分析处理。因此，学习动态规划时，除对基本概念和基本方法正确理解外，还应在一定经验积累基础上，以丰富的想像力去建立模型，用创造性的技巧去求解。提纲1动态规划实例2动态规划的基本概念3动态规划的基本思想与基本原理4逆序解法与顺序解法学习目标：1明确什么是多阶段的决策问题，特别要注意没有明显的时段背景的问题如何化归为多阶段的决策问题。1动态规划实例例机器负荷分配问题（时间阶段问题）◎设有某种机器设备，用于完成两类工作A和B。若第k年初完好机器的数量为xk，若以数量uk用于A，余下的（xk－uk）用于工作B，则该

3、年的预期收入为g(uk)+h(xk－uk)。这里g(uk)和h(xk－uk)是已知函数，且g(0)=h(0)=0。◎又机器设备在使用中会有损坏，设机器用于工作A时，一年后能继续使用的完好机器数占年初投入量的70%；若用于工作B时，一年后能继续使用的完好机器数占年初投入量的90%。则在下一年初能继续用于A、B工作的设备数为xk+1=0.7uk+0.9(xk－uk)。◎设第1年初完好的机器总数为1000台，问在连续5年内每年应如何分配用于A、B两项工作的机器数，使5年的总收益为最大。1动态规划实例□相应的问题称为多阶段决策问题。□这是一个多阶段

4、决策过程。□该过程可以分为相互联系的若干阶段，每一阶段都需作出决策，从而形成全过程的决策。第1年x1=1000u1第2年x2=0.7u1+0.9(x1-u1)u2第3年x3=0.7u2+0.9(x2-u2)u3第4年u4第5年x5=0.7u4+0.9(x4-u4)u5x4=0.7u3+0.9(x3-u3)x6例最短路线问题（空间阶段的例子）设有一个旅行者从下图中的A点出发，途中要经过B、C、D等处，最后到达终点E。从A到E有很多条路线可以选择，各点之间的距离如图所示，问该旅行者应选择哪一条路线，使从A到达E的总的路程为最短。25375632

5、455114633334C1C3D1AB1B3B2D2EC21234状态1决策1状态2状态3状态4状态5决策2决策3决策4□可看成4阶段的决策问题。□从以上两个例子，可以知道所谓多阶段决策问题是指这样的决策问题：其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定既依赖于当前面临的状态，又影响以后总体的效果。当每一阶段的决策选定以后，就构成一个决策序列，称为一个策略，它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。多阶段决策过程的特点1.各阶段的决策相互关联□多阶段决策过程最优化的目的，是要

6、达到整个活动过程的总体效果最优，而不是某个阶段“局部”的效果最优。因此，各个阶段决策的选取不是任意确定的。□前一个决策的选取决定了当前状态，当前状态进行决策后又影响到下一阶段的状态和决策，以至于影响总体效果。所以决策者在每个阶段决策时，不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局而言是最优的决策。□动态规划就是符合这一要求的一种最优化方法。2.各个阶段的决策一般与“时间”有关□动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各阶段的决策，从而产生一个决策序列，这就是“动态”的意思。□但是，一些与时间无关的静态问题

7、，只要在问题中人为引入“时间”因素，也可将其看成是多阶段的决策问题，用动态规划方法去处理。学习目标：1准确、熟练地掌握动态规划的基本概念、特别是状态变量、决策变量、状态转移律、指标函数、基本方程等。2动态规划的基本概念□为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题。□通常，阶段是按决策进行的时间或空间上先后顺序划分的。□描述阶段的变量称为阶段变量，常记为k，k=1,2,…,n。□如本例可按空间分为4个阶段来求解，k=1,2,3

8、,4。（1）阶段（stage）□状态：每阶段初的客观条件。描述各阶段状态的变量称为状态变量，常用xk表示第k阶段的状态。（2）状态（state）□例1中，状态就是某阶段的出发位置