运筹学---动态规划课件.ppt

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

1、动态规划是一种研究多阶段决策问题的理论和方法。这种方法把一个多阶段决策问题转化成一系列相互联系的单阶段决策问题来求解。动态规划主要应用于最短路问题、装载问题、库存问题、资源分配、生产过程最优化问题。动态规划模型可以分为离散确定性、离散随机性、连续确定性、连续随机性四种决策过程。其中最基本的是离散确定性过程。第6章动态规划第6章动态规划§1多阶段的决策问题§2最优化原理与动态规划的数学模型§3动态规划应用举例§1多阶段的决策问题多阶段决策问题：可以分为若干个互相联系的阶段，在每个阶段分别对应着一组可以选取的决策，当每个阶段的决策选定以后，过程也就随之确定。多阶段

2、决策问题，就是要在所有可能采取的策略中间选取一个最优的策略，是在预定的标准下得到最好的效果。[例1]最短路线问题。设有一旅行者从下图中的A点出发，途中要经过B、C、D等处，最后到达终点E。从A到E有很多条路可以选择，各点之间的距离如图所示，问该旅行者应选择哪一条路线，使从A到E的总路程最短？AB3B2B1C3C2C1D2D1E22351535657633414343用穷举法的计算量:如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-1×2条路径；计算各路径长度总共要进行(k+1)3k-1×2次加法以及3k-1×2-1次比较。随着k的值增加时，需

3、要进行的加法和比较的次数将迅速增加；例如当k=20时，加法次数为4.2550833966227×1015次，比较1.3726075472977×1014次。若用1亿次/秒的计算机计算需要约508天。[例2]设有某种机器设备，用于完成两类工作A和B.若k年初完好机器的数量为sk，若以数量xk用于A，余下的(sk-xk)用于工作B，则该年的预期收入为g(xk)+h(sk-xk).这里g(xk)和h(sk-xk)是已知函数，且g(0)=h(0)=0.又机器设备在使用中会有损坏，设机器用于工作A时，一年后能继续使用的完好机器数占年初投入量的a%；若用于B项工作时，一年

4、后能继续使用的完好机器数占年初投入量的b%，即下一年初能继续用于完成这两项工作的设备数为sk+1=axk+b(sk-xk).设第一年初完好的机器总数为s0，问在连续三年内每年应如何分配用于A、B两项工作的机器数，使三年的总收益最大？[例3]将一个数c(c>0)分成n个部分c1,c2,...,cn之和，且ci>0(i=1,...,n)，问应如何分割使其乘积为最大？§2最优化原理与动态规划的数学模型动态规划问题的解题思路动态规划的基本概念最优化原理与动态规划的数学模型逆序解法与顺序解法动态规划模型的分类2.1动态规划问题的解题思路基本思路：是将一个n阶段的决策问

5、题转化为依次求解n个具有递推关系的单阶段的决策问题，从而简化计算过程。在例1中，这种转化的实现是从终点E出发一步步进行反推，这种算法称为逆序算法。[例1]最短路线问题。设有一旅行者从下图中的A点出发，途中要经过B、C、D等处，最后到达终点E。从A到E有很多条路可以选择，各点之间的距离如图所示，问该旅行者应选择哪一条路线，使从A到E的总路程最短？AB3B2B1C3C2C1D2D1E22351535657633414343按逆序推算，例1的计算步骤为：从D出发，f(D1)=3;f(D2)=4。从C出发，f(C1)=4;f(C2)=7;f(C3)=6。从B出发，f(

6、B1)=11;f(B2)=7;f(B3)=8。从A出发，f(A)=11。2.2动态规划的基本概念1、阶段(stage).是指一个问题需要做出决策的步数。如例1中旅行者需要在A、B、C、D四个阶段做出下一步的决策。通常用k来表示问题包含的阶段数，称为阶段变量。2、状态(state).这是动态规划中最关键的参数，它既反映前面各阶段决策的结局，又是本阶段做出决策的出发点和依据。状态是动态规划问题各阶段信息的传递点和结合点，第k阶段的状态通常用状态变量sk来描述。在例1中第2阶段的状态s2=(B1,B2,B3)。3、决策(decision).是指某阶段初从给定的状态出

7、发，决策者在面临的若干种不同方案中做出的选择。用Dk(sk)表示k阶段状态为sk时决策允许的取值范围，xk(sk)表示第k阶段状态为sk时对方案的选择。如例1中D2(B1)={C1,C2,C3}。4、策略(policy)和子策略(subpolicy).动态规划问题各阶段决策组成的序列总体称作一个策略。如：{x1(s1),x2(s2),...,xn(sn)}。把从某一阶段开始到过程最终的决策序列称为问题的子过程策略或子策略。如：{xk(sk),xk+1(sk+1),...,xn(sn)}。5、状态转移律，也称状态转移方程.从sk的某一状态值出发，当决策变量xk(

8、sk)的取值决定后，下一阶段状态变量s