第8章动态规划第1,2节.ppt

《第8章动态规划第1,2节.ppt》由会员分享，可在线阅读，更多相关《第8章动态规划第1,2节.ppt（79页珍藏版）》请在三一文库上搜索。

1、1,第1节 多阶段决策过程及实例 第2节 动态规划的基本概念和基本方程,运筹学 （第三版） 运筹学教材编写 组 第8章 动态规划的基本方法 清华大学出版社,2,第8章 动态规划的基本方法,第1节 多阶段决策过程及实例 第2节 动态规划的基本概念和基本方程 第3节 动态规划的最优性原理和最优性定理 第4节 动态规划和静态规划的关系,3,动态规划（Dynamic Programming）是运筹学的一个重要分支，它是解决多阶段决策过程最优化的一种方法。美国数学家贝尔曼（R. E. Bellman）等人在50年代初提出了解决多阶段决策问题的“最优性原理”（Principle of Optimality

2、）。1957年贝尔曼出版了专著“动态规划”，该书是动态规划的第一本著作。目前动态规划已经用于解决最优路径问题、资源分配问题、生产调度问题、设备更新问题、复合系统可靠性问题及生产过程最优控制等，并且取得了显著的效果。,4,动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。 需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。,5,第1节 多阶段决策过程及实例,在生产经营活动中，某些问

3、题决策过程可以划分为若干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。,6,各个阶段不是孤立的，而是有机联系的，也就是说，本阶段的决策将影响过程下一阶段的发展，从而影响整个过程效果，所以决策者在进行决策时不能够仅考虑选择的决策方案使本阶段最优，还应该考虑本阶段决策对最终目标产生的影响，从而做出对全局来讲是最优的决策。 多阶段决策问题中，各个阶段一般是按照时间来划分的，随着时间的发展而产生各个阶段的决策，从而形成决策序列，这就是动态的含义。,7,在一些与时间无关的静态问题中（如非线性规划等），可以人为地赋予时间的概念，使其成为一个多阶段决策问题，再用动态规划方法处理。 当每个阶段

4、的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题。,8,例1 最短路线问题,给定一个线路网络，两点之间连线上的数字表示两点之间的距离（或费用），试求一条由A到G的铺管线路，使总距离为最短（或总费用最小）。,9,例2. 机器负荷分配问题,某种机器可以在高低两种不同的负荷下进行生产。 在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为g=g(u1)，这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终完好的机器就为au, 0a1。 在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为 h=h(u2)，相

5、应的机器年完好率b, 0 b1。 假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。,10,第2节 动态规划的基本概念和基本方程,11,例1 图8-2 p.192,12,当某阶段的始点给定时，它直接影响后面各阶段的进行路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各阶段线路的影响。(无后效性） 问题要求：在各阶段中选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其路程最短。 穷举法 2*3*2*2*2*1=48,13,2.1 动态规划的基本概念,1 阶段

6、（Stage) 根据所需解决问题的特点，按照时间或空间顺序把整个过程划分为若干相互联系的阶段，以便按照一定次序求解。 描述阶段的变量称为阶段变量，通常用k表示。,14,2. 状态(State) 状态表示各阶段开始所处的自然状况或客观条件，它既是某阶段过程演变的起点，又是前一阶段某种决策的结果。 描述状态的变量称为状态变量，常用Sk表示第k阶段的状态变量。 S1=A S2=B1，B2 S3=C1，C2，C3，C4 无后效性(即马乐科夫性） 系统从某个阶段往后的发展演变，完全由系统本阶段所处的状态及决策所决定，与系统以前的状态及决策无关。 只有具有无后效性的多阶段决策过程才适合于用动态规划方法求解

7、。,15,3. 决策(Decision),当各阶段的状态选定以后，可以做出不同的决定（或选择）从而确定下一个阶段的状态，这种决定（或选择）称为决策。 表述决策的变量称为决策变量 uk（sk）表示第k阶段当状态为sk时的决策变量。 允许决策集合 决策变量的取值范围，Dk（sk） uk（sk） Dk（sk） 如D2（B1）C1,C2,C3，若从B1出发选取C2，则C2是状态B1在决策u2(B1)作用下的一个新的状态，记为u2(B1)=C2,16,4. 策略(Policy),策略 是一个按顺序排列的决策组成的集合。当各个阶段的决策确定以后，各阶段的决策形成的一个决策序列 最优策略 使系统达到最优效果

8、的策略 k后部子过程（或称为k子过程） 在n阶段决策过程中，从第k阶段到终止状态的过程 k后部子过程策略，简称子策略 k后部子过程相应的决策序列，记为pk，n（sk）， 即：pk，n（sk）=uk（sk），uk+1（sk+1），un（sn） 全过程策略，简称策略， 当k=1时，即由第一阶段某个状态出发做出的决策序列 记为p1，n（s1）即：p1，n（s1）=u1（s1），u2（s2），un（sn）,17,5.状态转移方程（State Transfer Equation）,状态转移方程 表示从第k阶段到第k+1阶段状态转移规律的方程，它反映了系统状态转移的递推规律。 设第k阶段状态为sk，做出的

9、决策为uk(sk)，则第k+1阶段的状态sk+1随之确定，即：sk+1=Tk（sk，uk） Tk称为状态转移函数 确定状态转移方程是建立动态规划的难点之一。,18,图示如下：,状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定，第k+1阶段状态变量sk+1的值也就确定。,其状态转移方程如下（一般形式）,能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。,19,如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。,动态规划中能 处理的状态转移 方程的形式。,状态具有无后效性

10、的多阶段决策过程的状态转移方程如下,无后效性(马尔可夫性),如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；,过程的过去历史只能通过当前的状态去影响它未来的发展；,构造动态规划模型时，要充分注意是否满足无后效性的要求；即状态变量要满足无后效性的要求；,20,6.指标函数和最优指标函数,指标函数 衡量所选策略优劣的数量指标。它是定义在全过程和所有后部子过程上确定的数量函数，常用Vk，n表示，即： Vk，n=Vk，n（sk，uk，sk+1， uk+1 ,，sn+1） 动态规划数学模型的指标函数应该具有可分离性，并满足递推关系，即： Vk，n（sk，uk，sk+1，

11、uk+1 ,，sn+1）=ksk，uk，Vk+1，n（sk+1， uk+1 ,，sn+1）,21,常见的指标函数形式有两种,（1）任一后部子过程的指标是它所包含的各阶段指标的和，即：Vk，n（sk，uk，sn+1）= 写成递推关系： Vk，n（sk，uk，sn+1）= vk（sk，uk）+ Vk+1，n（sk+1，uk+1，sn+1） 其中vk（sk，uk）为第j阶段的阶段指标 （2）任一后部子过程的指标是它所包含的各阶段指标的积，即： Vk，n（sk，uk，sn+1） = 写成递推关系： Vk，n（sk，uk，sn+1）= vk（sk，uk） Vk+1，n（sk+1，uk+1，sn+1）,2

12、2,最优值函数 指标函数的最优值，记为fk（sk），它表示从第k阶段状态sk出发到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值，即： opt 是英文optimization（优化）的缩写，可根据题意取max或min。 在不同的问题中，指标函数可以是利润、成本、距离、产品质量或资源消耗等。 在最短路线问题中，第k阶段的指标函数vk（sk，uk）通常也用dk（sk，uk）表示。,23,小结:,指标函数形式:,和、,积,无后效性,可递推,24,2.2动态规划的基本思想与基本原理,结合例1的最短路线问题来阐述动态规划的基本思想。,25,最短路线重要特性,如果由A点经B点到C点是一条最短路线

13、，那么从B点到C点的这条子路线必定是从B点到C点的所有路线中最短的一条路线。 所以求解最短路问题，就可以从最后一段开始，由后向前逐步递推，逐段求各点到终点的最短路线，每段都要用到上一步得到的最短路线，一直到求出从始点到终点的最短路线。,26,最优化原理,作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。”也就是说，一个最优策略的子策略也是最优的。,27,f6(F1)=4, u6(F1)=G. f6(F2)=3, u6(F2)=G,28,29,30,逆序标号法 图84,0,31,逆序标号法 图84,32,顺序标号法

14、 图85,33,顺序标号法 图85,34,动态规划优点（相对穷举法）,（1）减少了计算量 （2）丰富了计算结果,35,动态规划的基本思想,1、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。 必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。 即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。,36,2、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把

15、当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的.,37,3、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。,38,构造动态规划模型基础 在建立动态规划模型时，应注意以下几点： 将原问题转化为由若干阶段的决策问题； 正确地选择状态变量 ，使之既描述过程又无后效性； 确定决策变量 及允许决策集合 ； 正确地写出状态转移方程 ； 正确地写出阶段效益函数 ； 正确地写出指标函数 它应满足： 是定义在 子过程上的数量函数； 满足递推关系

16、： 对于其变化 是单调的。,39,第3节 动态规划应用举例,1、非线性规划转化为动态规划 2、资源分配问题 3、生产和存储问题 4、排序问题 5、背包问题 6、货郎担问题 7、复合系统工作可靠性问题 8、设备更新问题,40,动态规划的两种方法,逆序解法 顺序解法,41,逆序解法,设已知初始状态S1和边界条件fn+1(sn+1)=0或1,解得最优解x1=x1(s1)和最优值f1(s1) 。,于是s2=T1(s1,x1)和f2(s2),顺序推算确定每阶段决策和效益。,42,顺序解法,设已知终止状态Sn+1和边界条件f0(s1)=0或1,解得最优解xn=xn(sn+1)和最优值fn(sn+1) 。,

17、于是sn=Trn(sn+1,xn)和fn-1(sn),逆序推算确定每阶段决策和效益。,43,1、非线性规划转化为动态规划(P204),例3 用逆推解法求下列非线性规划问题,44,按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1，2，3,45,设状态变量为s1，s2，s3，s4并记s1=c 取问题中的变量x1，x2，x3为决策变量 状态转移方程为： s3=x3 s3+x2=s2 s2+x1=s1=c 允许决策集合为： x3=s3 0x2s2 0x1s1 各阶段指标函数为：v1（x1）=x1 v2（x2）=x22 v3（x3）=x3 ，各指标函数以乘积方式结合,46,最优指标函数fk（

18、sk）表示从第k阶段初始状态sk出发到第3阶段所得到的最大值，则动态规划基本方程为：,47,状态转移方程为： s3=x3 s3+x2=s2 s2+x1=s1=c 指标函数为： v1（x1）=x1 v2（x2）=x22 v3（x3）=x3,48,49,例4 将例3用顺推解法解之（自学）,50,2、资源分配问题(P213),资源分配问题就是将一定数量的一种或若干种资源（原材料、资金、设备等）恰当地分配给若干使用者，而使目标函数为最优。 一种资源的分配问题称为一维资源分配问题，两种资源的分配问题称为二维资源分配问题。,51,假设有一种资源，数量为a，将其分配给n个使用者，分配给第i个使用者数量xi时

19、，相应的收益为gi（xi），问如何分配使得总收入最大？这就是一维资源分配问题，该问题的数学模型为：,52,按变量个数划分阶段，k=1，2，n； 设决策变量uk=xk，表示分配给第k个使用者的资源数量； 设状态变量为sk，表示分配给第k个至第n个使用者的总资源数量； 状态转移方程：sk+1=skxk，其中s1=a； 允许决策集合：Dk（sk）=xk|0xksk 阶段指标函数：vk（sk，uk）=gk（xk）表示分配给第k个使用者数量xk时的收益； 最优指标函数fk（sk）表示以数量sk的资源分配给第k个至第n个使用者所得到的最大收益，则动态规划基本方程为：,由后向前逐段递推，f1（a）即为所求问

20、题的最大收益。,53,P213 例1,某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表所示。问如何分配，才能使国家盈利最大。,54,55,状态变量Sk:表示分配给第k到第n个工厂设备的台数； 决策变量xk:表示分配给第k个工厂设备的台数， k=3,2,1; 则sk1=sk-xk 为分配给第k1到第n个工厂设备的台数； Pk (xk)表示为xk 台设备分配到第k个工厂所得盈利值； fk（sk）表示为sk台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值 指标函数的递推方程为：,56,57,58,按计算表

21、格的顺序反推算，可得两个最优方案,方案(1) x*1=0, s2=s1-x*1=5 x*2=2, s3=s2-x*2=3 x*3=s3=3,方案(2) x*1=2, s2=s1-x*1=3 x*2=2, s3=s2-x*2=1 x*3=s3=1,59,3、生产和存储问题,60,P225 例3 生产计划问题,某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库

22、存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。,61,按时期划分为四个阶段，状态变量为期末库存Vk，决策变量为每期生产量xk。,状态转移方程为： vk-1+ xk- dk= vk,62,每期生产量x k ： 每期生产量不超过生产能力6（用m表示）； 又因为 v k-1 +x k -d k = v k, 所以v k-1 = v k+ d k-x k 0, 即 x k v k+ d k; 0 x kMin v k+ d k,6 = k 每期期末库存量v k： 不大于今后各期需求量之和 不大于m- d k 。,63,64,65,66,67,68,按计算顺序反向推算得最优解

23、,69,4、排序问题,本书所论及的问题是： 假定有N个零件，都要先经机器A，再经机器B进行加工。各零件在机器A、B上的加工时间固定，但可互不相同。问这些零件应以怎样的次序进入加工，可使从第 1 个零件进入加工开始到最后一个零件加工完毕为止这一段时间最短？这个问题已经得到了完满的解决。 我们这里只介绍结论，而不涉及获得结论的推理过程。,70,P 240排序规则（Johnson 1954),（2）找出矩阵M中的最小元素（如有多个，任取一个）；若它在上行，则相应工件应排在最前加工；如在下行则相应工件应排在最后加工。 （3） 将排定位置的工件从M中划去，其余下的工件重复按（2）进行，其次序在原已排定次

24、序的工件之间，取最前或最后。如此反复，直到所有工件加工次序都排定为止。,基本思路：尽是减少在机床B上的等待加工时间。因此在机床B上加工时间长的工件先加工，在B上加工时间短的后加工。 （1）先作工件加工时间的工时矩阵,71,P240 例9,设有5个工件需在机床A、B上加工，加工顺序是先A后B，每个工件所需加工时间如表所示。部如何安排加工顺序，使机床连续加工完成所有工作的加工时间最少？并求出总加工时间。,72,73,74,5、背包问题(P233),有人携带背包上山，其可携带物品的重量限度为a公斤，现有n种物品可供选择，设第i种物品的单件重量为wi公斤，其在上山过程中的价值是携带数量xi的函数ci（

25、xi），问应如何安排携带各种物品的数量，使总价值最大。这就是背包问题，类似的货物装载问题，下料问题都等同于背包问题。,75,数学模型,它是一个整数规划问题。如果xi只取0或1，又称0-1背包问题。,76,用动态规划求解（顺序解法）,按照装入物品的种类划分阶段，k=1，2，n； 状态变量w表示装入第1种至第k种物品的总重量； 决策变量xk表示装入第k种物品的件数； 状态转移方程为：,逐步计算fi(w)和xi(w),最后得fn(a)，反向推算最优策略,77,6、货郎担问题(P244),设有n个城市，分别以1,2,n记之。以dij表示从城市i 到城市j之间的距离。一个推销员从城市1出发经过每城市一次而后又回到城市1，问应如何选择路径，可使所走的路程最短？ 当城市个数不太大时，这类问题可用动态规划方法求解。,78,7、复合系统工作可靠性问题,略,79,8、设备更新问题,略,