第四章-动态规划.ppt

1、动态规划 Dynamic Programming（DP）,动态规划,动态规划 Dynamic Programming（DP）,引言 动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。,1951年, R.Bellman,多阶段决策问题,一系列相互联系的 单阶段决策问题,最优性原理,贝尔曼的名著动态规划于1957年出版，这成了动态规划的第一本著作。,动态规划 Dynamic Programming（DP）,引言 动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用，并且获得了显著的效果。,最优路径问题,资源分配问题,生产与库存问题,设备更新问题

2、,经济管理方面的应用,动态规划 Dynamic Programming（DP）,引言 由于动态规划的方法在众多方面的应用，使他已经成为现代企业管理中的一种重要的决策方法。 此外，许多实际问题采用动态规划方法去处理，常比线性规划或非线性规划更加有效。 特别对于离散型的问题，由于解析数学无法施展其术，而动态规划方法就成为一种非常有效的工具。,动态规划 Dynamic Programming（DP）,多阶段决策过程的最优化 多阶段决策过程： 整个决策过程可按时间或空间顺序分解成若干相互联系 的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。,多阶段决策过程最优化的目标： 达到整个活动过程的

3、总体效果最优，而非各单个阶段最优的简单总和。,动态规划 Dynamic Programming（DP）,动态规划典例 例最短路线问题,动态规划 Dynamic Programming（DP）,动态规划典例-最短路问题 寻找A点到G点的最短线路,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,该点到G点的 最短距离,动态规划 Dynamic Programming（DP）,动态规划典例-最短路问题 A点到G点的最短线路如下，最短距离18。,A,B1,C2,D1,E2,F2,G,对于以上的最短线路问题：,逆序动态递推的方法,简单的枚举方法,575次运算,43次运算,？运算量

4、,动态规划 Dynamic Programming（DP）,动态规划的基本概念 1、阶段（stage） 对整个决策过程的自然划分，通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序逐段解决整个过程的优化问题。阶段变量通常用k表示（k = 1，2，3，n）。 2、状态（state） 每个阶段开始时过程所处的自然状况或客观条件。它应能描述过程的特征并具有“无后效性”，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。 状态变量 sk（state variable） 允许状态集合 Sk（set of admissible states）,动态规划 Dynamic Prog

5、ramming（DP）,动态规划的基本概念 3、决策（decision） 当一个阶段的状态确定后，可以作出不同的决定或选择，从而演变到下一阶段的某个状态，这种决定或选择称为决策。 决策变量 uk（sk） （decision variable）简记为 uk 允许决策集合 Dk（sk）（set of admissible decision） 4、策略（policy） 一组有序的决策序列构成一个策略，从第k阶段至第n阶段的一个策略称为后部子策略记为 pk，n （uk，uk+1，un）。,动态规划 Dynamic Programming（DP）,动态规划的基本概念 5、状态转移方程（equation

6、of state transition） 在动态规划中，本阶段的状态往往是上一阶段的状态和决策共同作用的结果。当给定了上一阶段的状态sk ,以及作出了本阶段的决策uk 后,则下一阶段（K+1阶段）的状态sk+1 便完全确定。用状态转移方程反映这种状态间的演变规律，写作： sk+1 = Tk（sk，uk） k =1，2，n 6、阶段指标值-函数（objective value in a stage） 衡量在一个阶段某个状态下各决策所对应的某种数量指标或效果，通常表示为 vk（sk，uk）。,动态规划 Dynamic Programming（DP）,动态规划的基本概念 7、指标函数（objecti

7、ve function）过程指标值 衡量在选定某策略时，其优劣的数量指标。,定义在整个过程（1到n阶段）上的指标函数记为： V1，n（s1，u1，s2，sn，un）,定义在后部子 过程（k到n阶段）上的指标函数记为： Vk，n（sk，uk，sn，un），或简记为：Vk，n（sk， pk，n ）。,常见指标函数的形式： Vk，n（sk， pk，n ）= vi（si ，ui） Vk，n（sk， pk，n ）= vi（si ，ui）,动态规划 Dynamic Programming（DP）,动态规划的基本概念 8、最优指标函数（optimal value function） 从第k阶段状态 sk 出

8、发，采用最优策略 p*k，n 到终止时的后部子过程指标函数值。,fk（ sk ）= Opt Vk，n（sk， pk，n ）,pk，n Pk，n（ sk ）,动态规划 Dynamic Programming（DP）,动态规划的基本思想与原理 动态规划发展的早期，从简单逻辑分析出发给出了所谓“最优性原理”，然后在最优策略存在的前提下导出了基本动态方程，再由此方程求解最优策略。基本方程在动态规划中起着本质的作用。,下面我们利用如前的最短路线问题进一步阐明动态规划的基本方程所扮演的重要角色！,动态规划 Dynamic Programming（DP）,动态规划的基本思想与原理 求A点到G点的最短线路,第

9、一阶段,第二阶段,第三阶段,第四阶段,第五阶段,第六阶段,动态规划 Dynamic Programming（DP）,动态规划的基本思想与基本原理 在上图中,以各阶段的起点作为状态,所选择箭线的终点作为决策 ,以及下一阶段的起点。 箭线旁的数值即为阶段目标值如：d（C2，D1）= 3。 并定义过程指标函数 fk（sk） 第k阶段，以sk 为起点至终点G的最短距离。 我们从第六阶段开始,采用逆序递推求解：,动态规划 Dynamic Programming（DP）,动态规划的基本思想与基本原理 第一步 k = 6, 状态变量 s6 可取两种状态F1 ,F2 , 其到G点的路线长分别为4, 3 。由于

10、从F1 ，F2出发到G点分别只有唯一一条路线，而唯一的就是最优的。即： f6（ F1 ）= 4， u6*（ F1 ）= G ； f6（ F2 ）= 3， u6*（ F2 ）= G 。,动态规划 Dynamic Programming（DP）,动态规划的基本思想与基本原理 第二步 k = 5, 状态变量 s5 可取三种状态E1 ，E2 ，E3 , 这是经过一个中途点到达终点G的两级决策问题，从E1 到G 有两条路线，因而需要加以比较，取其中最短的，即： f5（ E1 ）= min,= 7， u5*（ E1 ）= F1,即：第5阶段，如果从状态E1出发到G点，最优决策应该选择下一步到F1 点。从E

11、1 到终点 G 的最短路线为： E1 F1 G,动态规划 Dynamic Programming（DP）,动态规划的基本思想与基本原理 第二步 k = 5, 从E2 到G 有两条路线，加以比较，取其中最短的，即： f5（ E2 ）= min,= 5， u5*（ E2 ）= F2,即：第5阶段，如果从状态E2 出发到G点，最优决策应该选择下一步到F2 点。从E2 到终点 G 的最短路线为： E2 F2 G,动态规划 Dynamic Programming（DP）,动态规划的基本思想与基本原理 第二步 k = 5, 从E3 到G 有两条路线，加以比较，取其中最短的，即： f5（ E3 ）= min

12、,= 9， u5*（ E3 ）= F2,即：第5阶段，如果从状态E3 出发到G点，最优决策应该选择下一步到F2 点。从E3 到终点 G 的最短路线为： E3 F2 G,动态规划 Dynamic Programming（DP）,动态规划的基本思想与基本原理 类似如分析可求得： k = 4, 状态变量 s4 可取三种状态D1 ，D2 ，D3 , f4（ D1 ）= 7， u4*（ D1 ）= E2 f4（ D2 ）= 6， u4*（ D2 ）= E2 f4（ D3 ）= 8， u4*（ D3 ）= E2 k = 3, 状态变量 s3 可取三种状态C1 ，C2 ，C3 ，C4 ， f3（ C1 ）=

13、 13， u3*（ C1 ）= D1 f3（ C2 ）= 10， u3*（ C2 ）= D1 f3（ C3 ）= 9， u3*（ C3 ）= D2 f3（ C4 ）= 12， u3*（ C3 ）= D3,动态规划 Dynamic Programming（DP）,动态规划的基本思想与基本原理 k = 2, 状态变量 s2 可取三种状态B1 ，B2 ， f2（ B1 ）= 13， u2*（ B1 ）= C2 f2（ B2 ）= 16， u2*（ B2 ）= C3 k = 1, 此时状态变量 s1 只有一种状态点A，则： f1（ A ）= min,即：第1阶段，从状态 A 出发到G点，最优决策应选择

14、下一步到B1点。从A 到终点 G 的最短路线为： A B1 C2 D1 E2 F2 G,动态规划 Dynamic Programming（DP）,动态规划的基本思想与原理 基本思想总结：例最短路线问题 1、划分阶段。 2、求解从边界条件开始，逆向逐段递推。 3、每段的最优是从全局考虑的，并非仅考虑本阶段。 Bellman 最优化原理：,“一个过程的最优策略具有这样的性质，即无论开始的状态及初始的决策如何，对先前决策所形成的状态而言，其以后所有的决策必构成最优策略后部子过程最优。”,动态规划 Dynamic Programming（DP）,动态规划的基本思想与基本原理 从以上分析、计算的过程，可

15、以看出，都利用了第k段和第k+1段的动态递推关系：,这种递推关系称为动态规划基本方程，或基本模型。,如何才能够正确、顺利地分析问题，建立动态规划基本模型？,建立 DP 模型与求解 建立动态规划的模型，就是分析问题并建立问题的动态规划基本方程，成功地应用动态规划方法的关键，在于识别问题本身的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题，或者说正确地建立具体问题的基本方程，这不仅需要经验和技巧，也需要对实际问题敏锐的动察力。而正确建立基本递推关系方程的关键又在于正确选择状态变量 sk+1 = Tk（sk，uk），这是建立动态规划的模型的两个要点。,动态规划 Dynamic Prog

16、ramming（DP）,建立 DP 模型与求解 建立动态规划的模型的十步曲： 1、正确、明确地划分阶段 k， k =1，2，3，n。依据决策过程的时间和空间的顺序关系。 2、正确选择并确定状态变量 sk 及状态集合 Sk 。状态变量的确定有时并非显而易见，要确定它，通常可对问题作如下分析而帮助确定状态变量 a. 什么关系将各个阶段联系在一起？ b. 为了决定今后的最优（子）策略，需要事件现状的哪些信息？,动态规划 Dynamic Programming（DP）,建立 DP 模型与求解 3、确定决策变量 uk 及决策集合 Dk（sk）。 4、写出状态转移方程 sk+1 = Tk（sk，uk）。

17、5、定义阶段指标值（函数） vk（sk，uk）。 6、定义第 k至 n 阶段（后部子过程）的最优指标（目标）函数 fk（sk）。 7、作出动态规划结构图：,sk,sk+1 = Tk（sk，uk）,k阶段,fk（sk）,k+1阶段,fk+1（sk+1）,opt,（ ，）,vk（sk，uk）,uk Dk（sk）,动态规划 Dynamic Programming（DP）,建立 DP 模型与求解 8、建立动态规划基本方程：（逆序递推方程）,或 k=n，n-1，1,动态规划 Dynamic Programming（DP）,建立 DP 模型与求解,9、逆序递推求解动态规划基本方程。,求出最优决策序列 u*

18、n，u*n-1，u*2，u*1,10、顺序确定最优策略。 p*1n = u*1，u*2，u*n ,s1,u*1,u*2,u*n,sn,s2 = T2（s2，u2）,动态规划 Dynamic Programming（DP）,下面我们再以一例，进一步学习、掌握DP建模与求解方法！,建立 DP 模型与求解 例 分配投资问题 某公司有资金 10 万元，若投资于项目 k （k = 1，2，3）的投资额为 uk 时，其收益分别为 g1（u1）= 4u1 ， g2（u2）= 9u2 ， g3（u3）= 2u32 ，问应该如何分配投资数额才能使总收益最大？ 该问题表面上看与时间无明显关系，其静态模型：,Max

19、 z = 4u1 + 9u2 + 2u32 u1 + u2 + u3 = 10 ui 0 （i = 1，2，3）,动态规划 Dynamic Programming（DP）,建立 DP 模型与求解 如何应用动态规划方法求解此类静态规划问题？一般我们可以人为地给它赋予“时段”的概念，将投资项目按任意顺序进行排序，如首先考虑项目1 的投资，然后考虑项目2 的投资 ，即将问题人为划分为若干个阶段，每个阶段只决定对一个项目应投资的金额。这样，可以将上述问题转化为一个 n 阶段决策过程。 分配投资问题的分析求解如下：,动态规划 Dynamic Programming（DP）,建立 DP 模型与求解 阶段

20、k = 1，2，3，分别表示项目1，2，3 状态变量 sk ：第 k 段初拥有的投资资金总量（既分配给第 k 至第 3 个项目的资金数量， s1 = 10） 决策变量 uk ：第 k 段的投资分量（分配给第 k 个项目的资金数量），决策集合 Dk（sk）= uk 0 uk sk 状态转移方程 sk+1 = sk - uk 阶段指标值（函数） vk（sk，uk）= gk（uk） 定义fk（sk）：第 k 段初拥有的资金总量为 sk 时，第 k 至第 3 段按最优投资策略所获得的第 k 至第 3 段的总收益。,动态规划 Dynamic Programming（DP）,建立 DP 模型与求解 动态规

21、划结构图,sk,sk+1 = sk - uk,k阶段,fk（sk）,k+1阶段,fk+1（sk+1）,max,（ ）,gk（uk）,0 uk sk,8. 建立动态规划基本方程：（逆序递推方程）,动态规划 Dynamic Programming（DP）,建立 DP 模型与求解 逆序递推求解动态规划基本方程 k = 3,f3 *（s3）= 2s32 ， uk* = s3,Max z = 4u1 + 9u2 + 2u32 u1 + u2 + u3 = 10 ui 0 （i = 1，2，3）,动态规划 Dynamic Programming（DP）,建立 DP 模型与求解 k = 2,= Max 9u

22、2 + 2（s2 u2 ）2 ,可以证明极大值只可能当 u2 在决策区间 0， s2 的端点取得，即： 当u2 = 0 时，f2（s2）= 2s22 ；当u2 = s2 时，f2（s2）= 9s2 令 2s22 = 9s2 ，解得 s2 = 9/2，则 当s2 9/2 时， 2s22 9s2 ，此时 u2* = s2 ，f2（s2）= 9s2 当s2 9/2 时， 2s22 9s2 ，此时 u2* = 0， f2（s2）= 2s22,Max z = 4u1 + 9u2 + 2u32 u1 + u2 + u3 = 10 ui 0 （i = 1，2，3）,动态规划 Dynamic Programm

23、ing（DP）,建立 DP 模型与求解 k = 1，s1 = 10,当s2 9/2时 ，f2（s2 ）= 9s2,= 90 ， u1* = 0,但此时 s2 = s1 u1 =10 - 0 9/2 与 s2 9/2 矛盾，故舍去此解。,Max z = 4u1 + 9u2 + 2u32 u1 + u2 + u3 = 10 ui 0 （i = 1，2，3）,= Max 4u1 + 9（10 u1） = Max - 5u1 + 90 ,动态规划 Dynamic Programming（DP）,建立 DP 模型与求解 k = 1,容易证明上式中，极大值只可能在端点取得，比较两个端点： u1 = 0 时

24、，f1（10）= 200 ； u1 = 10 时，f1（10）= 40 所以 u1* = 0 由此我们得到该问题的最优投资分配策略为：,当s2 9/2 时， f2（s2）= 2s22,= Max 4u1 + 2（10 u1）2 ,Max z = 4u1 + 9u2 + 2u32 u1 + u2 + u3 = 10 ui 0 （i = 1，2，3）,动态规划 Dynamic Programming（DP）,建立 DP 模型与求解 10、顺序确定最优策略。,s1= 10,u1* = 0,s2 = s1 u1* = 10 9/2,u2* = 0,s3 = s2 u2* = 10,u3* = 10,答

25、：最优投资方案为，全部资金投资于第 3 个项目，可获 最大收益 200 。,Max z = 4u1 + 9u2 + 2u32 u1 + u2 + u3 = 10 ui 0 （i = 1，2，3）,动态规划 Dynamic Programming（DP）,动态规划求解方法 逆序递推法（Backward Induction Method） 将寻优过程看做连续递推的过程，从最终阶段开始，逆着实际决策过程的进展方向逐段求解，在每一段求解中都要利用刚刚求解完那段的结果，直到初始阶段求出结果回到始点为止。 顺序递推法（Forward Induction Method） 从初始阶段向前递推，直到最终阶段为止

26、。 顺序递推法本质上并无新的建树，只是对某些实际问题的求解，应用起来较为简便而已。,动态规划 Dynamic Programming（DP）,动态规划求解方法 连续变量的离散化 当 sk 与 uk 都是连续变量，各阶段的指标 没有特殊性质而较为复杂时，要求出 会比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把连续变量离散化的办法求其数值解。具体做法如下： 令 sk = 0，2 ，m = a ，把区间 0，a 进行分割， 的大小可依据问题所要求的精度以及计算机的容量确定。 规定状态变量 sk 以及决策变量 uk 只在离散点 0，2 ，m 上取值，相应的函数就被定义在这些离散点上。

27、逐步递推求解。,动态规划 Dynamic Programming（DP）,动态规划求解方法 高维问题的降维法 以多维资源分配问题为例，若资源种类增加（即问题的维数增加）或所分配的产品增加（即阶段数增加）都会使得计算量成指数倍增长。这就是动态规划的 “维数灾难”。为计算可行，可利用计算机速度快的特点，采用以时间换空间的办法，对问题进行降维或简化以求其解或近似解。常用方法有： 拉格朗日乘子法 逐步逼近法 疏密格子点法,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 例1资源分配问题 资源分配问题是动态规划的典型问题之一，它的一般提法是：有某种资源，总量为 a

28、，用于 n 个项目，若分配数量 ui 用于第 i 个项目，则第 i 个项目所产生的效果（收益）为 gi（ui）。问题是如何分配资源总量 a 才能获得 n 个项目所产生的总效果（收益）最优（ max ）？ 静态规划问题,max Z = g1（u1）+ g2（u2）+ + gn（un） u1 + u2 + + un （=）a ui 0,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 某公司新引进了 6 台高效率生产设备，该设备可用于生产 4 种不同的产品，当生产每种产品所投入的设备数量不同时所带来的利润也不相同。其详细资料如下：,利润表 单位：万元,动态规划

29、Dynamic Programming（DP）,动态规划在经济管理中的应用 该公司这 6 台设备在 4 种产品的生产中能够发挥最大的效益，应该如何分配这 6 台设备，才能获得最大的总利润？ 分析、建模 此决策问题如按 4 种产品的一种顺序（可以任意排列，不妨按产品的自然顺序），将产品 1 分配的设备数量作为第一阶段需作出的决策，将产品 2 分配的设备数量作为第二阶段需作出的决策，将产品 3 分配的设备数量作为第三阶段需作出的决策，将产品 4 分配的设备数量作为第四阶段需作出的决策，这显然就是一个多阶段决策问题。因此有：,动态规划 Dynamic Programming（DP）,动态规划在经济管

30、理中的应用 1、阶段 k ：第 k 种产品，k=1，2，3，4 2、状态变量 sk ：当按顺序应第 k 种产品分配设备时所余有的总量。 3、决策变量 uk ：分配给第 k 种产品的设备数量。 Dk（sk）= uk | uk =0，1，2， sk 4、状态转移方程： sk+1 = sk - uk 5、定义阶段指标值（函数） vk（sk，uk）= vk（ uk ）：即分配给第 k 种产品的设备数量为 uk 时，第 k 种产品所创造的利润（如利润表）。,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 6、定义 fk（sk）：第 k 种产品分配设备时所余有的设备数

31、量为 sk ，第 k 种产品至第四种产品按最优分配策略分配所余有的设备，第 k 种产品至第四种产品所创造的利润总和 。（第 k 种产品至第四种产品按某种设备分配策略所创造的最大总利润 。 7、作出动态规划结构图：,sk,sk+1 = sk - uk,k阶段,fk（sk）,k+1阶段,fk+1（sk+1）,max,（ ）,vk（ uk）,uk =0，1，2， sk,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 8、建立动态规划基本方程：（逆序递推方程）,9、逆序递推求解动态规划基本方程。,动态规划 Dynamic Programming（DP）,动态规划在

32、经济管理中的应用 k= 4 时，状态集合 S4= 0，1，2，3，4，5，6 f4（s4）= max v4（ u4）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 k= 3 时，状态集合 S3= 0，1，2，3，4，5，6 f3（s3）= max v3（ u3）+ f4（s4）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 k= 2 时，状态集合 S2= 0，1，2，3，4，5，6 f2（s2）= max v2（ u2）+ f3（s3）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中

33、的应用 k= 1 时，状态集合 S1= 6 f1（s1）= max v1（ u1）+ f2（s2）,10、顺序确定最优策略之一。,s2= 6,s1= 6,u1= 0,u4= 1,u2= 2,u3= 3,s4= 1,s3= 4,动态规划 Dynamic Programming（DP）,答：该公司可分别在产品1、2、3、4上分配投入0，2，3，1台设备。能够获得最大总利润134万元 。,动态规划在经济管理中的应用 该公司设备分配的所有最优方案：,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 例2机器负荷分配问题 某种机器可在两种负荷下进行生产。在高负荷下生产

34、的产量函数为 g = 8 u （ u 为投入的机器数量），年完好率为 a = 0.7 ；在低高负荷下生产的产量函数为 h = 5y （y 为投入的机器数量），年完好率为 b = 0.9 。开始生产时完好机器数量 s1 = 1000台，问每年如何分配机器在两种负荷下进行生产，使五年内生产的产品总产量最高。,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 建立动态规划模型： 阶段 k ：生产年度，k = 1，2，3，4，5 状态变量 sk ：第 k 年度初安排时拥有的完好机器数量，（此也为第 k-1 年度末时的完好机器数量）。 决策变量 uk ：第 k年度初安

35、排在高负荷下进行生产的机器数量，于是 sk-uk 为该年度中安排在低负荷下进行生产的机器数量。决策集合 Dk（sk）= uk | 0 uk sk 状态转移方程： sk+1 = 0.7 uk + 0.9（ sk - uk ） 定义阶段指标值（函数） vk（sk，uk）= 8 uk + 5 （ sk - uk ）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 定义 fk（sk）：第 k 年度初拥有的完好机器数量为 sk 时，将其安排（分配）于第 k 至第 5 年中两种负荷下进行生产时所生产的最大产量。 作出动态规划结构图：,sk,sk+1 = 0.7 uk

36、+ 0.9（ sk - uk ）,k阶段,fk（sk）,k+1阶段,fk+1（sk+1）,max,（ ）,8 uk + 5 （ sk - uk ）,0 uk sk,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 建立动态规划基本方程：（逆序递推方程）,fk（sk）= max 8 uk + 5（ sk - uk ）+ fk+1（sk+1），k= 4，3，2，1,f5（s5）= max 8 u5 + 5 （ s5 - u5 ）,逆序递推求解动态规划基本方程。,0 uk sk,0 u5 s5,k = 5,f5（s5）= max 8 u5 + 5 （ s5 - u

37、5 ） = max 3u5 + 5s5 = 8s5,0 u5 s5,u*5（s5）= s5,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用,k = 4,f4（s4）= max 8 u4 + 5（ s4 - u4 ）+ f5（s5）,0 u4 s4,= max 8 u4 + 5（ s4 - u4 ）+ 8s5 ,= max 8 u4 + 5（ s4 - u4 ）+ 8（ 0.7 u4 + 0.9（ s4 - u4 ）,= max 1.4 u4 + 12.2 s4 = 13.6s4 u*4（s4）= s4,k = 3,f3（s3）= max 8 u3 + 5（

38、 s3 - u3 ）+ f4（s4）,0 u3 s3,= max 8 u3 + 5（ s3 - u3 ）+ 13.6s4 ,= max 8 u3 + 5（ s3 - u3 ）+ 13.6（ 0.7 u3 + 0.9（ s3 - u3 ）,= max 0.28 u3 + 17.24 s3 17.5s3 u*3（s3）= s3,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用,k = 2,f2（s2）= max 8 u2 + 5（ s2 - u2 ）+ f3（s3）,0 u2 s2,= max 8 u2 + 5（ s2 - u2 ）+ 17.5s3 ,= max

39、 8 u2 + 5（ s2 - u2 ）+ 17.5（ 0.7 u2 + 0.9（ s2 - u2 ）,= max - 2.5 u2 + 20.75 s2 20.8s2 u*2（s2）= 0,k = 1,f1（s1）= max 8 u1 + 5（ s1 - u1 ）+ f2（s2）,0 u1 s1,= max 8 u1 + 5（ s1 - u1 ）+ 20.8s2 ,= max 8 u1 + 5（ s1 - u1 ）+ 20.8（ 0.7 u1 + 0.9（ s1 - u1 ）,= max -1.16 u1 + 23.72 s1 23.7s1 u*1（s1）= 0,动态规划 Dynamic P

40、rogramming（DP）,动态规划在经济管理中的应用,顺序确定最优策略。 p*15 = u*1，u*2，u*5 ,s1=1000,s2=900,s5 397,s3=810,s4=567,u*1= 0,u*2= 0,u*3= 810,u*4= 567,u*5= 397,答：按上述决策，即五年中，前两年所有机器都在低负荷下进行生产。从第三年开始，每年所有机器都在高负荷下进行生产。这样才能获得最大产量 f1（s1=1000）= 23700 ，且五年生产期结束时（即第六年初还剩余）有完好机器 s6 = 0.7 397 = 278（台）,动态规划 Dynamic Programming（DP）,动态

41、规划在经济管理中的应用 例3生产与存储问题 某厂经过调查知在未来四个月中每月市场对该厂产品的需求量如表，该厂每批产品的生产准备费（固定成本）为 3 千元，若不生产则为零。每件产品的生产成本（可变成本）为 1千元。该厂最大生产能力为每批不超过 6 件，每件产品每月的库存费用为 0.5 千元，第一月初该厂没有此产品的库存，并要求第四月末也无库存剩余。该厂每月初应如何计划产品的生产量及库存量，才能既满足市场对该厂产品的需求又使其总费用最低。 产品需求表,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 建立动态规划模型： 阶段 k ：第 k月，k = 1，2，3，

42、4 状态变量 sk ：第 k月初（k-1月末）的库存量，已知 s1 = s5 = 0。 决策变量 uk ：第 k月的生产量。 根据条件有： 0 uk 6 ， min（sk+1） sk+1 max（ sk+1 ） 状态转移方程： sk+1 = sk + uk - dk 因此，决策集合 Dk（sk）= uk | 0 uk 6， min（sk+1） sk+1 max（ sk+1 ） = uk | max 0，dk - sk + min（sk+1） uk min 6，dk - sk + max（sk+1） ,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 阶段指标

43、值（函数）： vk（sk，uk）= uk + 3 ( uk ) + 0.5sk ，,其中 ( uk ) =,0 当 uk = 0 1 当 uk 0,定义 fk（sk）：第 k月初库存量为 sk 时，第 k月至第 四月末的最低总费用。,作出动态规划结构图：,sk,sk+1 = sk + uk - dk,k 阶段,fk（sk）,k+1阶段,fk+1（sk+1）,min,（ ）,uk + 3 ( uk ) + 0.5sk,uk Dk（sk）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 动态方程：（逆序递推方程）,fk（sk）= min uk + 3 ( uk

44、 ) + 0.5sk + fk+1（sk+1），k= 4，3，2，1,f5（s5）= f5（ 0 ）= 0 因为第 5月计划期已结束，没有费用产生了。,uk Dk（sk）,逆序递推求解动态规划方程。,k = 4， s4 取值集合为 0，1，2，3，4。 因 min s5 = max s5 = 0,D4（s4）= u4 | max 0， d4 - s4 u4 min 6， d4 - s4 = u4 | u4 = d4 - s4 = 4 - s4 ,f4（s4）= min u4 + 3 ( u4 ) + 0.5s4 + 0 ,动态规划 Dynamic Programming（DP）,动态规划在经济

45、管理中的应用 f4（s4）= min u4 + 3 ( u4 ) + 0.5s4 + 0 ,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 k = 3， s3 取值集合为 0，1，2，3，4，5，6。 min s4 = 0，max s4 = 4 D3（s3）= u3 | max 0， d3 - s3 + min（s4） u3 min 6，d3 s3 + max （s4 ） = u3 | max 0，2 - s3 u3 min 6，6 - s3 f3（s3）= min u3 + 3 ( u3 ) + 0.5s3 + f4（s4 = s3 + u3 - d3

46、）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 f3（s3）= min u3 + 3 ( u3 ) + 0.5s3 + f4（s4 = s3 + u3 - d3 ）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 k = 2， s2 取值集合为 0，1，2，3，4。 min s3 = 0，max s3 = 6 D2（s2）= u2 | max 0， d2 s2 + min（s3） u2 min 6，d2 s2 + max （s3） = u2 | max 0，3 s2 u2 min 6，9 s2 f2（s2）= mi

47、n u2 + 3 ( u2 ) + 0.5s2 + f3（s3 = s2 + u2 d2 ）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 f2（s2）= min u2 + 3 ( u2 ) + 0.5s2 + f3（s3 = s2 + u2 d2 ）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 k = 1， s1 取值集合为 0 。 min s2 = 0，max s2 = 4 D1（s1）= u1 | max 0， d1 s1 + min（s2） u1 min 6， d1 s1 + max （s2 ） = u1

48、 | max 0，2 s1 u1 min 6，6 s1 = u1 | 2 u1 6 f1（s1）= min u1 + 3 ( u1 ) + 0.5s1 + f2（s2 = s1 + u1 d1 ）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 f1（s1）= min u1 + 3 ( u1 ) + 0.5s1 + f2（s2 = s1 + u1 d1 ）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 顺序确定最优策略。 p*14 = u*1 ，u*2 ， u*3 ，u*4 ,s1= 0,s2= 3,s3= 0,s4

49、= 4,u*1= 5,u*2= 0,u*3= 6,u*4= 0,该厂按以上生产与库存方案计划其总费用将是最低的，为 20.5 千元。,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 例4复合系统可靠性问题,pk表示系统中第 k 个部件的可靠度，即在给定标准下正常工作的概率。根据系统可靠性理论知，提高整个系统可靠性的一种十分有效的方法是采用冗余（储备并联）技术。当系统中第k个部件的冗余数量为 uk 时，则系统中第k个部件的可靠度提高为： pk（uk）= 1 -（1 - pk）1+ uk,动态规划 Dynamic Programming（DP）,动态规划在经济

50、管理中的应用 当系统中第 k 个部件（1，2，n）的冗余数量为 uk 时，从而整个系统的可靠度为： P = pk（uk） 下面研究一个简单例子,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 一台机器的三个重要部件对整台机器的正常运行起着至关重要的作用，他们的可靠度及成本分别为： p1 = 0.9， p2 = 0.7， p3 = 0.6； c1 = 2， c2 = 1， c3 = 3； （单位：万元） 如果采用冗余技术来提高整台机器的可靠度，而提供的冗余经费仅有 3 万元，这三个重要部件应该怎样冗余才能使整台机器的可靠度最高。 这实际上是一个 3 万元如何

51、分配使用在这三个重要部件冗余的资源分配问题，其动态规划结构图如下：,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 动态规划结构图：,sk,sk+1 = sk + ckuk,k阶段,fk（sk）,k+1阶段,fk+1（sk+1）,max,（ ）,pk（uk）,0 uk sk /ck 且为整数,动态方程：（逆序递推方程）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 逆序递推求解动态规划方程。 k = 3 s2 取值集合为： 0 sk 3 f3（s3）= max 1 -（1 - p3）1+ u3 * f4（s4） f3

52、（ 0 s3 3 ）= max 1 -（1 - 0.6）1 * 1 = 0.6 u*3（ s3 3 ）= 0 f3（ s3 = 3 ）= max 1 -（1 - 0.6）1+1 * 1 = 0.84 u*3（ s3 = 3 ）= 1,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 k = 2 s2 可能取值集合为： 1，3,f2（1）= max,（1 - 0.3）* f3（1） （1 - 0.32）* f3（0）,= max,0.7 * 0.6 0.91 * 0.6,=0.546,u*2（1）= 1,f2（3）= max,（1 - 0.3）* f3（3）

53、（1 - 0.32）* f3（2） （1 - 0.33）* f3（1） （1 - 0.34）* f3（0）,= max,0.7 * 0.84 0.91 * 0.6 0.973 * 0.6 0.992 * 0.6,=0.595,u*2（3）= 3,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 k = 1 s1可能取值集合为： 3,= 0.541,= max,f1（3）= max,（1 - 0.1）* f2（3） （1 - 0.12）* f2（1）,0.9 * 0.595 0.99 * 0.546,u*1（3）= 1,顺序确定最优策略。,s1= 3,s2=

54、1,s3= 0,u*1= 1,u*2= 1,u*3= 0,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 例5设备更新问题 在工业和交通运输企业中，经常会遇到因设备陈旧或部分损坏需要更新的问题。那么，从经济上分析，一台（一批）设备应该使用多少年后进行更新最为恰当，或合理的更新年限是多少？从而使在某一时间内的总收入达到最大（或总成本达到最小）。这是设备更新问题所要研究的。,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 设备更新问题的一般性描述： 已知一台设备的效益函数r（t），维修费用函数u（t），更新费用函数c（t）

55、，在n 年内，每年年初都须作出决策，是继续使用（Keep）旧设备还是更换（Replacement）一台新的设备，使在n年内总净效益最大。 设： r k（t）在第k 年初设备已使用了t 年（或称役龄为t年）的 设备在第k 年再使用的效益。 u k（t）在第k 年初设备已使用了t 年时继续使用的第k 年 中的维修费用。 c k（t）在第k 年初设备已使用了t 年时的更新费用。 为折扣因子（0 1），表示一年以后的单位收入 的价值视为现年的 单位。,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 建立动态规划模型： 阶段 k ：表计划使用设备的年数，k=1，2，

56、n 状态变量 sk ：第 k 年初，设备已使用过的年数（役龄）。 决策变量 xk ：第 k 年初更新设备，或保留使用旧设备。 Dk（sk）= xk | xk =R ，K 状态转移方程： sk+1 = 1 （当 xk =R ） sk+1 = sk + 1 （当xk = K ） 阶段指标值（函数） vk（sk，xk）=,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 定义 fk（sk）：第 k 年初，设备已使用了 sk 年时，第 k 年至第 n 年末的最大效益。 动态规划结构图：,sk,1,sk + 1,R: r k（0）- u k（0）- c k（ sk ）

57、 + fk（1 ）,K: r k（ sk ）- u k（ sk ） + fk+1（sk+1）,第k 年,第k+1年,第k+1年,fk（sk）,fk+1（1 ）,fk+1（sk+ 1）,Max （）,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 动态方程：（逆序递推方程）,fn+1(sn+1) = 0 k = n，2，1,逆序递推求解动态规划方程。,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 某台新设备的年效益及年均维修费、更新净费用如表所示。试确定今后 5 年内的更新策略，使总收益最大。（ 取 = 1） 单位：万元,动态规划 Dynamic Programming（DP）,动态规划在经济管理中的应用 k = 5 s5 取值集合为：1，2，3，4,f5( 1 ) = Max,R: r5( 0 ) - u5( 0 ) c5( 1 )+ 0 K: r5( 1 ) u5( 1 ) + 0,= Max,R: 5 0.5