第6章-动态规划.pptx

第第6章章 动态规划动态规划学习目标学习目标了解动态决策问题的特点及其类型；了解动态决策问题的特点及其类型；理解并掌握理解并掌握Bellman最优化原理及其在动态最优化原理及其在动态规划中的应用；规划中的应用；掌握常见的动态决策问题的建模及其求解，掌握常见的动态决策问题的建模及其求解，如最短路线问题、资源分配问题、背包问如最短路线问题、资源分配问题、背包问题、仓库存贮问题、生产与存贮问题等。题、仓库存贮问题、生产与存贮问题等。动态决策问题动态决策问题决策过程具有阶段性或时序性（与时间有决策过程具有阶段性或时序性（与时间有关），即决策过程可划分为明显的阶段；关），即决策过程可划分为明显的阶段；按数据给出的形式可分为：离散型动态决按数据给出的形式可分为：离散型动态决策问题和连续型动态决策问题；策问题和连续型动态决策问题；按决策过程演变的性质可分为：确定型动按决策过程演变的性质可分为：确定型动态决策问题和随机型动态决策问题。态决策问题和随机型动态决策问题。动态规划的基本概念动态规划的基本概念 AB1B2B3FC1C2C3D1D2D3E1E235495435171584642544269721ABCDEF12345阶段（阶段（k）：一般把所给问题按时间或空间）：一般把所给问题按时间或空间上的顺序划分互译序贯相连的几个阶段。上的顺序划分互译序贯相连的几个阶段。阶段的划分，一般根据时间和空间的自然特征阶段的划分，一般根据时间和空间的自然特征来划分。来划分。上例中上例中k=1,2,3,4,5，其中第一个阶段的起点为，其中第一个阶段的起点为A，终点为，终点为B1、B2或或B3状态（状态（Sk）：指阶段的出发位置，即阶段的）：指阶段的出发位置，即阶段的起点，如：起点，如：S1=A，S2=B1,B2,B3,决策（决策（uk(Sk)）：指从一个阶段某状态演）：指从一个阶段某状态演变到下一阶段某状态的选择，即阶段的终变到下一阶段某状态的选择，即阶段的终点构成的决策集点构成的决策集uk(Sk)。如：。如：u1(S1)=u1(A)=B1,B2,B3u2(S2)=u2(B1),u2(B2),u2(B3)=C1,C2;C1,C2,C3;C2,C3=C1,C2,C3策略：全过程各个阶段的决策策略：全过程各个阶段的决策uK组成的有序总体组成的有序总体uK，如：，如：AB2C1D1E2F如果从如果从A到到F有有38种走法，或种走法，或38条路线，则有条路线，则有38个策略。个策略。子策略：子策略：由过程的第由过程的第k阶段开始到终止状态为止的过程，称为问阶段开始到终止状态为止的过程，称为问题的后部子过程，也称为题的后部子过程，也称为k子过程。子过程。与之相对应的决策序列与之相对应的决策序列uk(sk),uk+1(sk+1),un(sn)称为称为k子过程策略，简称为子过程策略，简称为k子策略。如：子策略。如：C1D1E2F 状态转移方程：确定过程由一个状态到另状态转移方程：确定过程由一个状态到另一个状态的演变过程。如果给定第一个状态的演变过程。如果给定第k阶段的阶段的起始状态起始状态sk与决策变量与决策变量uk(sk)，则第，则第k+1阶阶段的状态段的状态sk+1也就确定了。这种关系可用公也就确定了。这种关系可用公式：式：sk+1=Tk(sk,uk)表示，表明了由表示，表明了由k到到k+1阶段状态转移的规阶段状态转移的规律。律。指标函数：是评价动态规划决策结果优劣的数量指标函数：是评价动态规划决策结果优劣的数量指标，它定义了全过程和所有后部子过程上确定指标，它定义了全过程和所有后部子过程上确定的数量函数，一般以的数量函数，一般以Vk,n表示。指标函数可以是时表示。指标函数可以是时间、效率、利润、成本或产量等。间、效率、利润、成本或产量等。Vk,n=Vk,n(sk,uk,sn,un)一般而言，指标函数满足如下递推关系：一般而言，指标函数满足如下递推关系：Vk,n(sk,uk,sn,un)=ksk,uk,Vk+1,n(sk+1,un)最优指标函数：记为最优指标函数：记为fk(sk),表示从第表示从第k阶段的状阶段的状态态sk开始，到第开始，到第n阶段的终止状态的过程，采取阶段的终止状态的过程，采取最优策略所得到的指标函数值，即：最优策略所得到的指标函数值，即：其中，其中，opt表示最优的意思，可以是表示最优的意思，可以是max或或min。V是函数关系，可以表示是函数关系，可以表示加法关系加法关系，也可以表示，也可以表示乘法关系乘法关系或其它。或其它。在最短路线问题中，指标函数在最短路线问题中，指标函数Vk,n就表示在第就表示在第k阶阶段由点段由点sk至终点至终点F的距离，用的距离，用dk(sk,uk)=vk(sk,uk)表示第表示第k阶段由点阶段由点sk到点到点sk+1=uk(sk)的距离。例如，的距离。例如，d4(D3,E2)=5，表示在第，表示在第4阶段，由点阶段，由点D3到点到点E2的的距离为距离为5。fk(sk)表示从第表示从第k阶段点阶段点sk到终点到终点F的最短距离。如的最短距离。如 f4(D2)就表示从第就表示从第4阶段中的点阶段中的点D2到点到点F的最短距离的最短距离最优化原理最优化原理贝尔曼最优化原理：贝尔曼最优化原理：作为整个过程的最优策略，无论过去的状态和作为整个过程的最优策略，无论过去的状态和决策如何，对前面的决策所形成的状态而言，决策如何，对前面的决策所形成的状态而言，余下的诸决策必构成最优策略。余下的诸决策必构成最优策略。即：若即：若M是从是从A到到B最优路线上的任一点，则从最优路线上的任一点，则从M到到B的路线也是最优路线。的路线也是最优路线。MAB整个问题整个问题将最后一阶段将最后一阶段问题最优化问题最优化将最后两阶段将最后两阶段问题最优化问题最优化整个问题最整个问题最优化优化指标函数递推方程指标函数递推方程贝尔曼最优化原理可以导出指标函数递推方程：贝尔曼最优化原理可以导出指标函数递推方程：f*n(Sn)为从第为从第n个阶段到终点的最短距离，个阶段到终点的最短距离，f*n+1(Sn+1)为从第为从第n+1个阶段到终点的最短距离，个阶段到终点的最短距离，dn(Sn,Xn)为第为第n个阶段的距离，个阶段的距离，f*5(S5)为递推的起为递推的起点，通常为已知的。点，通常为已知的。求解过程求解过程由最后一个阶段的优化开始，按逆向顺序逐步由最后一个阶段的优化开始，按逆向顺序逐步向前一阶段扩展，并将后一阶段的优化结果带向前一阶段扩展，并将后一阶段的优化结果带到扩展后的阶段中去，以此逐步向前推进，直到扩展后的阶段中去，以此逐步向前推进，直至得到全过程的优化结果。至得到全过程的优化结果。AB1B2E495648768935623143ABCDE1234例：最短线路问题例：最短线路问题B3C1C2C3D1D2解：解：(1)k=4，起始状态集合为：，起始状态集合为：s4=D1,D2 当当s4=D1时，从时，从D1到到E的路线只有一条，其的路线只有一条，其距离距离d(D1,E)=4，所以，所以f4(D1)=4;当当s4=D2时，从时，从D2到到E的路线只有一条，其的路线只有一条，其距离距离d(D2,E)=3，所以，所以f4(D2)=3;(2)k=3，起始状态集合为：，起始状态集合为：s3=C1,C2,C3 当当s3=C1时，从时，从C1到到E的路线有两条，的路线有两条，C1D1 E或或C1D2 E。我们要在这两条路线中选择一条最短路线，即：我们要在这两条路线中选择一条最短路线，即：其最短路线是其最短路线是C1D1 E，相应的决策变量是，相应的决策变量是u3(C1)=D1 当当s3=C2时，从时，从C2到到E的路线也有两条，的路线也有两条，C2D1 E或或C2D2 E。其最短路线是其最短路线是C2D2 E，相应的决策变量是，相应的决策变量是u3(C2)=D2 当当s3=C3时，从时，从C3到到E的路线也有两条，的路线也有两条，C3D1 E或或C3D2 E。其最短路线是其最短路线是C3D1 E，相应的决策变量是，相应的决策变量是u3(C3)=D1(3)k=2，起始状态集合为：，起始状态集合为：s2=B1,B2,B3 当当s2=B1时，从时，从B1出发的线路有两条出发的线路有两条B1C1和和B1C2。可以计算得：可以计算得：其最短路线是其最短路线是B1C2 D2 E，相应的决策变，相应的决策变量是量是u2(B1)=C2 当当s2=B2时，从时，从B2出发的线路有三条出发的线路有三条B2C1、B2C2和和B2C3。可以计算得：可以计算得：其最短路线是其最短路线是B2C3 D1 E，相应的决策变，相应的决策变量是量是u2(B2)=C3 当当s2=B3时，从时，从B3出发的线路有两条出发的线路有两条B3C2和和B3C3。可以计算得：可以计算得：最短路线是最短路线是B3C2 D2 E，相应的决策变量，相应的决策变量是是u2(B3)=C2(4)k=1，起始状态集合为：，起始状态集合为：s1=A。从。从A出发的出发的线路有三条线路有三条AB1、AB2和和AB3。可以计算得：可以计算得：其最短路线是其最短路线是A B1C2 D2 E，相应的决，相应的决策变量是策变量是u1(A)=B1因此，最优策略序列是：因此，最优策略序列是：u1(A)=B1,u2(B1)=C2,u3(C2)=D2,u4(D2)=E动态规划的基本思想：动态规划的基本思想：关键在于正确地写出基本的递推关系式和恰当关键在于正确地写出基本的递推关系式和恰当的边界条件（基本方程）的边界条件（基本方程）在多阶段决策过程中，动态规划方法是既把当在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法效益结合起来考虑的一种最优化方法在求整个问题的最优策略时，由于初始状态是在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线。到，从而确定了最优路线。AB1B2E495648768935623143ABCDE1234动态规划的标号法动态规划的标号法B3C1C2C3D1D2437559111313动态规划的表格计算动态规划的表格计算从最后一个阶段开始：从最后一个阶段开始：n=4时，这一步数据为已知，是递推的起点：时，这一步数据为已知，是递推的起点：u4 s4d(u4)f4(s4)u4*ED144ED233En=3时：第时：第3阶段到终点分两步走：第阶段到终点分两步走：第3阶段到终阶段到终点的距离等于第点的距离等于第3阶段的距离加上第阶段的距离加上第4阶段到终点阶段到终点的最短距离，其计算如下：的最短距离，其计算如下：u3 s3d(u3)+f4 f3(s3)u3*D1D2C13+4=75+3=87D1C26+4=102+3=55D2C31+4=53+3=65D1n=2时：第时：第2阶段到终点分两步走：第阶段到终点分两步走：第2阶段到终阶段到终点的距离等于第点的距离等于第2阶段的距离加上第阶段的距离加上第3阶段到终点阶段到终点的最短距离，其计算如下：的最短距离，其计算如下：u2 s2d(u2)+f3 f2(s2)u2*C1C2C3B16+7=13 4+5=9-9C2B28+7=15 7+5=12 6+5=11 11C3B3-8+5=13 9+5=14 13C2n=1时：第时：第1阶段到终点分两步走：第阶段到终点分两步走：第1阶段到终阶段到终点的距离等于第点的距离等于第1阶段的距离加上第阶段的距离加上第2阶段到终点阶段到终点的最短距离，其计算如下：的最短距离，其计算如下：u1 s1d(u1)+f2 f1(s1)u1*B1B2B3A4+9=139+11=205+13=18 13B1因此，可以得到从因此，可以得到从A到到E的最短路线（即最优策略）的最短路线（即最优策略）为：为：AB1C2D2EA到到E的最短距离为：的最短距离为：f1(s1)13课堂练习课堂练习AB1B2B3FC1C2C3D1D2D3E1E235495435171584642544269721ABCDEF12345动态规划的逆序解法与顺序解法动态规划的逆序解法与顺序解法逆序（递推）解法：即由最后一段到第一段逐步逆序（递推）解法：即由最后一段到第一段逐步求出各点到终点的最短路线求出各点到终点的最短路线,最后求出最后求出A点到点到E点的点的最短路线。运用逆序递推方法的好处是可以始终最短路线。运用逆序递推方法的好处是可以始终盯住目标盯住目标,不致脱离最终目标。不致脱离最终目标。顺序解法：其寻优方向与过程的行进方向相同，顺序解法：其寻优方向与过程的行进方向相同，求解时是从第一段开始计算逐段向后推进，计算求解时是从第一段开始计算逐段向后推进，计算后一阶段时要用到前一段求优的结果，最后一段后一阶段时要用到前一段求优的结果，最后一段的计算结果就是全过程的最优结果。的计算结果就是全过程的最优结果。动态规划的优点动态规划的优点减少计算量；减少计算量；丰富计算结果。丰富计算结果。动态规划模型的建立动态规划模型的建立所研究的问题必须能够分成几个相互联系的阶段，所研究的问题必须能够分成几个相互联系的阶段，且在每个阶段都具有需要进行决策的问题；且在每个阶段都具有需要进行决策的问题；在每一阶段都必须有若干个与该阶段相关的状态，在每一阶段都必须有若干个与该阶段相关的状态，识别每一阶段的状态是建立动态规划模型的关键识别每一阶段的状态是建立动态规划模型的关键内容。状态的选取要注意以下几个要点：内容。状态的选取要注意以下几个要点：在所研究问题的各阶段，都能直接或间接确定状态变在所研究问题的各阶段，都能直接或间接确定状态变量的数值；量的数值；状态的后无效性：即以第状态的后无效性：即以第k阶段的状态阶段的状态sk为出发点的后为出发点的后部子过程的最优策略应与部子过程的最优策略应与sk状态之前的过程无关。状态之前的过程无关。具有明确的指标函数具有明确的指标函数Vk,n，且阶段指标值，且阶段指标值dk(sk,uk)可以计算。可以计算。动态规划的求解步骤动态规划的求解步骤将问题合理分成阶段。设阶段总数为将问题合理分成阶段。设阶段总数为n，给，给 界条件界条件fn(sn)，然后从最后一个阶段，然后从最后一个阶段n的优化的优化开始，逐步向前一阶段推进，直至第一阶开始，逐步向前一阶段推进，直至第一阶段为止。在每一阶段都进行如下的步骤：段为止。在每一阶段都进行如下的步骤：列出本阶段所有可能的状态变量列出本阶段所有可能的状态变量sk对每一个状态对每一个状态sk列出可能的决策变量列出可能的决策变量uk(sk)对每一对对每一对sk,uk(sk),计算本阶段的指标值计算本阶段的指标值dk(sk,uk)利用状态转移方程利用状态转移方程sK+1T(sk,uk)，对每对，对每对sk,uk(sk)求出求出Sk+1的值；的值；计算每一对计算每一对sk,uk(sk)的指标值的指标值dk(sk,uk)+fk+1(sk+1)将上一步中各指标值进行比较，取最优者（极将上一步中各指标值进行比较，取最优者（极大或极小）为从本阶段大或极小）为从本阶段sk状态开始的后部子过状态开始的后部子过程的最优指标程的最优指标fk(sk)，相应的决策即是本阶段，相应的决策即是本阶段以以sk为起始状态的最优决策为起始状态的最优决策uk*(sk)在第一阶段的最优决策确定之后，第一阶段的在第一阶段的最优决策确定之后，第一阶段的最优初始最优初始s1*即可确定，然后根据状态转移方程即可确定，然后根据状态转移方程确定下一阶段的最优状态。这样，最优策略所确定下一阶段的最优状态。这样，最优策略所经过的各阶段最优状态即可逐次得到，从而确经过的各阶段最优状态即可逐次得到，从而确定了最优策略的状态变化路线。定了最优策略的状态变化路线。动态规划应用实例动态规划应用实例定价问题定价问题：某公司考虑为某新产品定价，该产品的单价拟某公司考虑为某新产品定价，该产品的单价拟从每件从每件5元、元、6元、元、7元、元、8元这四个价格中选取元这四个价格中选取其中之一，每年年初允许变动价格，但幅度不其中之一，每年年初允许变动价格，但幅度不能超过能超过1元。该公司预计该产品畅销只有五年，元。该公司预计该产品畅销只有五年，五年后将被淘汰。另据销售情况的预测，在价五年后将被淘汰。另据销售情况的预测，在价格不同的情况下，各年的预计利润额如下表。格不同的情况下，各年的预计利润额如下表。现在问公司将如何为产品定价，以实现五年内现在问公司将如何为产品定价，以实现五年内的利润最大化？的利润最大化？预计利润额预计利润额单价单价(元元)第第1年年第第2年年第第3年年第第4年年第第5年年5678101214161213141515161615202018142524181410121520251213162024141416181816151514145元元6元元7元元8元元动态规划的表格计算动态规划的表格计算从最后一个阶段开始：从最后一个阶段开始：n=5时，这一步数据为已知，是递推的起点：时，这一步数据为已知，是递推的起点：u5 s5d5 f5(s5)u5*E1E2E3E4E12525E1E22424E2E31818E3E41414E4n=4时：第时：第4阶段到终点分两步走：第阶段到终点分两步走：第4阶段的利阶段的利润等于第润等于第4阶段的利润加上第阶段的利润加上第5阶段的最大利润，阶段的最大利润，其计算如下：其计算如下：u4 s4d4+f5 f4(s4)u4*E1E2E3E4D120+2520+2445E1D220+2520+2420+1845E1D318+2418+1818+1442E2D414+1814+1432E3n=3时：第时：第3阶段到终点分两步走：第阶段到终点分两步走：第3阶段的利阶段的利润等于第润等于第3阶段的利润加上第阶段的利润加上第4阶段以后的最大利阶段以后的最大利润，其计算如下：润，其计算如下：u3 s3d3+f4 f3(s3)u3*D1D2D3D4C115+4515+4560D1,D2C216+4516+4516+4261D1,D2C316+4516+4216+3261D2C415+4215+3257D3n=2时：第时：第2阶段到终点分两步走：第阶段到终点分两步走：第2阶段的利阶段的利润等于第润等于第2阶段的利润加上第阶段的利润加上第3阶段以后的最大利阶段以后的最大利润，其计算如下：润，其计算如下：u2 s2d2+f3 f2(s2)u2*C1C2C3C4B112+6012+6173C2B213+6013+6113+6174C2,C3B314+6114+6114+5775C2,C3B415+6115+5776C3n=1时：第时：第1阶段到终点分两步走：第阶段到终点分两步走：第1阶段的利阶段的利润等于第润等于第1阶段的利润加上第阶段的利润加上第2阶段以后的最大利阶段以后的最大利润，其计算如下：润，其计算如下：u1 s1d1+f2 f1(s1)u1*B1B2B3B4A110+7310+7484B2A212+7312+7412+7587B3A314+7414+7514+7690B4A416+7516+7692B4可知，为获得最大利润，各年的定价策略可知，为获得最大利润，各年的定价策略为：为：A4B4C3D2E1，即：，即：第一年：第一年：8元；元；第二年：第二年：8元；元；第三年：第三年：7元；元；第四年：第四年：6元；元；第五年：第五年：5元元资源分配问题资源分配问题某种资源总量为某种资源总量为a,用于生产用于生产n种产品。设分配数种产品。设分配数量量xi用于生产第用于生产第i种产品，第种产品，第i种产品的收益为种产品的收益为gi(xi)。问如何分配才使总收益最大？。问如何分配才使总收益最大？模型为：模型为：Max Z=g1(x1)+gn(xn)S.t.x1+x2+xn=a,xj0这是静态决策问题，我们可以将其化为动态模这是静态决策问题，我们可以将其化为动态模型来求解。型来求解。例：某有色金属公司拟拔出例：某有色金属公司拟拔出50万元对所属万元对所属三家冶炼厂进行技术改造。若以三家冶炼厂进行技术改造。若以10万元为万元为最小分割单位，各厂收益与投资的关系如最小分割单位，各厂收益与投资的关系如下表所示。问对三个工厂如何分配这下表所示。问对三个工厂如何分配这50万万元，才能使总收益达到最大？元，才能使总收益达到最大？投资额投资额(单位：十万元单位：十万元)技术改造后收益技术改造后收益工厂工厂1工厂工厂2工厂工厂301234504.57.09.010.512.002.04.57.511.015.005.07.08.010.013.0思路：首先对工厂思路：首先对工厂1进行分配，余下的工厂进行分配，余下的工厂2进行进行分配，最后余下的分配给工厂分配，最后余下的分配给工厂3.建立如下动态规建立如下动态规划数学模型：划数学模型：工厂工厂1工厂工厂2工厂工厂3阶段阶段k(工厂工厂)：1,2,3状态状态sk(可供分配的资金量可供分配的资金量)：s1=5;s2=s1-u1,s3=s2-u2决策决策uk(可供分配的资金量可供分配的资金量)：0u1s1,0u2s2,0u3s3状态转移方程：状态转移方程：sk+1=sk-uk指标函数指标函数(收益收益)：d1(u1)=0,4.5,7,9,10.5,12,d2(u2)=0,2,4.5,7.5,11,15,d3(u3)=0,5,7,8,10,13指标递推方程：指标递推方程：fk(sk)=max dk(uk)+fk+1(sk+1),k=1,2 f3(s3)=max d3(u3),利用表格进行计算，从最后一个阶段开始利用表格进行计算，从最后一个阶段开始 k=3,u3=s3 u3 s3d3f3(s3)u3*0123450000155127723883410104513135 k=2时，时，0u2s2，s3=s2-u2 u2 s2d2+f3f2(s2)u2*01234500+0=00010+5=52+0=25020+7=72+5=74.5+0=4.570,130+8=82+7=94.5+5=9.57.5+0=7.59.5240+10=102+8=104.5+7=11.57.5+5=12.511+0=1112.5350+13=132+10=124.5+8=12.57.5+7=14.511+5=1615+0=15164 k=1时，时，0u1s1，s2=s1-u1 u1 s1d1+f2f1(s1)u1*01234550+16=164.5+12.5=177+9.5=16.59+7=1610.5+5=15.512+0=12171 可见，当可见，当s1=5，此时，此时u1*=1，s2=s1-u1*=4,u2*=3;s3=s2-u2*=1,u3*=1最优策略为：最优策略为：P=u1*,u2*,u3*=1,3,1即给工厂即给工厂1分配分配10万元，工厂万元，工厂2分配分配30万元，万元，工厂工厂3分配分配10万元，可使总收益达到最大为万元，可使总收益达到最大为17万元。万元。背包问题背包问题假设一个徒步旅行者，有假设一个徒步旅行者，有n种物品供他选择后种物品供他选择后装入背包中。设这装入背包中。设这n种物品编号为种物品编号为1,2,j,n，并已知一件第，并已知一件第j种物品的重量为种物品的重量为wj千克，这一千克，这一件物品对他的使用价值为件物品对他的使用价值为cj。又知这位旅行者。又知这位旅行者本身所能承受的总重量不能超过本身所能承受的总重量不能超过W千克。问该千克。问该旅行者如何选择这旅行者如何选择这n种物品的件数，以对他来种物品的件数，以对他来说使用价值最大？说使用价值最大？一般的数学模型：一般的数学模型：背包问题的动态规划模型求解：背包问题的动态规划模型求解：用状态变量用状态变量sk表示背包中可装进第表示背包中可装进第k种至第种至第n种种物品的总重量物品的总重量(即从即从k阶段开始，还可以装入的阶段开始，还可以装入的总重量总重量)；用决策变量用决策变量xk表示背包中装进第表示背包中装进第k种物品的种物品的件数件数，则背包中装进第则背包中装进第k种至第种至第n种物品后的总重量为种物品后的总重量为sk=wkxk,sk+1=sk-wkxk。用用fk(sk)表示背包装入第表示背包装入第k种至第种至第n种商品所得的种商品所得的最大使用价值。则根据最优化原理，有如下递最大使用价值。则根据最优化原理，有如下递推方程：推方程：例：解背包问题例：解背包问题Max Z=8x1+5x2+12x32x1+2x2+5x35 x1,x2,x30且为整数且为整数物品物品A物品物品B物品物品C123阶段阶段(物品物品)k状态状态(第第k阶段时，背包可装入的重量阶段时，背包可装入的重量)sk:s1=5,s2=s1-w1x1=1,3,5,s3=s2-w2x2=1,3,5决策决策(装入背包的物品件数装入背包的物品件数)xk:0 x1 s1/w1,0 x2 s2/w2,0 x3s3/w3 x1=0,1,2,x2=0,1,2,x3=0,1状态转移方程：状态转移方程：sk+1=sk-wkxk阶段指标函数阶段指标函数(价值价值)：d1(x1)=8x1,d2(x2)=5x2,d3(x3)=12x3指标递推方程：指标递推方程：利用表格进行计算，从最后一个阶段开始利用表格进行计算，从最后一个阶段开始 k=3,x3=0,s3/w3=0,s3/5=0,1 x3 s3v3(s3)f3(s3)u3*01100030005012121 k=2时，时，x2=0,s2/w2=0,s2/2=0,1,2 s3=s2-w2x2=s2-2x2 x2 s2v2(s2,x2)+f3(s3)f2(s2)u2*01210+0030+05+05150+125+010+0120 k=1时，时，x1=0,s1/w1=0,s1/2=0,1,2 s2=s1-w1x1=5-2x1 x1 s1v1(s1,x1)+f2(s2)f1(s1)u1*01250+128+516+0162可见，当可见，当s1=5，此时，此时x1*=2，s2=s1-2x1*=1,x2*=0;s3=s2-2x2*=1,x3*=0最优策略为：最优策略为：P=u1*,u2*,u3*=2,0,0即带两件即带两件A物品，不带物品，不带B物品和物品和C物品，可物品，可使总效用达到最大为使总效用达到最大为16。设备更新问题设备更新问题问题：一台设备应在多少年后进行更新为问题：一台设备应在多少年后进行更新为最恰当，即更新的最佳策略应该如何，从最恰当，即更新的最佳策略应该如何，从而使在某一时间内的总收入达到最大（总而使在某一时间内的总收入达到最大（总费用达到最小）？费用达到最小）？记号：记号：Ij(t)：在第：在第j年机器役龄为年机器役龄为t年的一台机器运行所得的收入；年的一台机器运行所得的收入；Oj(t)：在第：在第j年机器役龄为年机器役龄为t年的一台机器运行时所需的运年的一台机器运行时所需的运行费用；行费用；Cj(t)：在第：在第j年机器役龄为年机器役龄为t年的一台机器更新时所需更新年的一台机器更新时所需更新净费用；净费用；：折扣因子：折扣因子T：在第一年开始时，正在使用的机器的役龄；：在第一年开始时，正在使用的机器的役龄；n：计划的年限总数；：计划的年限总数；gj(t)：在第：在第j年开始使用一个役龄为年开始使用一个役龄为t年的机器时，从第年的机器时，从第j年年到第到第n年的最佳收入；年的最佳收入；xj(t)：给出：给出gj(t)时，在第时，在第j年开始时的决策（保留或更新）年开始时的决策（保留或更新）递推关系式：递推关系式：其中，其中，j=1,2,n，t=1,2,j-1,j+T-1gn+1(t)=0对于对于g1()来说，允许的来说，允许的t值只能是值只能是T，因为当进入计，因为当进入计划进程时，机器必然已使用了划进程时，机器必然已使用了T年。年。假设假设n=5,=1,T=1,其有关数据如下表，试制其有关数据如下表，试制定定5年中的设备更新策略，使在年中的设备更新策略，使在5年内的总收年内的总收入达到最大。入达到最大。第一年第一年第二年第二年第三第三年年第四第四年年第第五五年年期前期前0 1 2 3 40 1 2 30 1 20 101 2 3 4 5收入收入运行运行费用费用更新更新费用费用22 21 20 18 166 6 8 8 1027 29 32 34 3727 25 24 225 6 8 929 31 34 3629 26 245 5 631 32 3330 284 532 333243418 16 16 14 148 8 9 9 1032 34 36 36 38解：符号的意思见解：符号的意思见P168当当j=5时时 u5 td5f5(s5)u5*RK1-52323K2-51818K313K46K54K当当j=4时时 u4 td4f4(s4)u4*RK1173939K229K316K413R当当j=3时时 u3 td3f3(s3)u3*RK1324848K231R327R当当j=2时时 u2 td2f2(s2)u2*RK1414646K2363536R当当j=1时时 u1 td1f1(s1)u1*RK1304646K利用动态规划解决非线性规划问题利用动态规划解决非线性规划问题例：用逆推解法求解下面问题：例：用逆推解法求解下面问题：解：设状态变量为解：设状态变量为s1,s2,s3,并记并记s1=c；取问；取问题中的变量题中的变量x1,x2,x3为决策变量，各阶段指为决策变量，各阶段指标函数按乘积方式结合。标函数按乘积方式结合。令最优值函数令最优值函数fk(sk)表示为第表示为第k阶段的初始状阶段的初始状态为态为sk，从，从k阶段到阶段到3阶段所得的最大值。阶段所得的最大值。设设s3=x3;s3+x2=s2;s2+x1=s1=c则：则：x3=s3;0 x2 s2;0 x1 s1=c根据逆推解法，从后向前依次有：根据逆推解法，从后向前依次有：最优解为：最优解为：令令 ，可得，可得，和和x2=0(舍去舍去)又又 ，故此为点极大值点，故此为点极大值点得：得：令令 ，可得，可得，由于由于s1=c，按计算顺序反推算，得各阶段，按计算顺序反推算，得各阶段的最优决策和目标函数的最优值：的最优决策和目标函数的最优值：即最优解为：即最优解为：利用动态规划解决非线性规划问题利用动态规划解决非线性规划问题例：用顺推解法求解下面问题：例：用顺推解法求解下面问题：解：记初始状态为解：记初始状态为s0，sk表示第表示第k（k=1,2,3）阶段末的结束状态为）阶段末的结束状态为sk，则，则s3=c。令最优值函数。令最优值函数fk(sk)表示从表示从1阶段到阶段到k阶段的最大值。阶段的最大值。设设s1=x1;s1+x2=s2;s2+x3=s3=c则：则：x1=s1;0 x2 s2;0 x3 s3=c根据顺推解法，从前向后依次有：根据顺推解法，从前向后依次有：最优解为：最优解为：由于由于s3=c，故得最优解为：，故得最优解为：相应的最大值为：相应的最大值为：利用动态规划解决非线性规划问题利用动态规划解决非线性规划问题例：用动态规划求解下面问题：例：用动态规划求解下面问题：解：设状态变量为解：设状态变量为s0,s1,s2,s3,并记并记s3 9；取；取x1,x2,x3为各阶段的决策变量，各阶段指标为各阶段的决策变量，各阶段指标函数按加法方式结合。函数按加法方式结合。令最优值函数令最优值函数fk(sk)表示第表示第k阶段的结束状态阶段的结束状态为为sk，从第，从第1阶段到第阶段到第k阶段的最大值。阶段的最大值。设设3x1=s1;s1+2x2=s2;s2+x3=s3 9则：则：x1=s1/3;0 x2 s2/2;0 x3 s3 9根据顺推解法，从前向后依次有：根据顺推解法，从前向后依次有：最优解为：最优解为：令令 ，可得，可得，因该点不在允许的决策集合内，故无须判别。因因该点不在允许的决策集合内，故无须判别。因而，而，h2(s2,x2)的最大值必在两个端点上选取。的最大值必在两个端点上选取。容易看出，容易看出，h2的最大值点在的最大值点在x2=0处，得到：处，得到：令令 ，可得，可得，在该点的二阶导数大于在该点的二阶导数大于0，故该点为极小值，故该点为极小值点。而点。而故故h3在在x3=s3处取得最大值，相应地：处取得最大值，相应地：显然，对于显然，对于f3来说，当来说，当s3=9时，时，f3取到最大取到最大值：值：29212174根据计算的顺序反推算，求得问题的最优根据计算的顺序反推算，求得问题的最优解为：解为：即最优解为：即最优解为：