《[经济学]第七章 动态规划》由会员分享，可在线阅读，更多相关《[经济学]第七章 动态规划（105页珍藏版）》请在金锄头文库上搜索。
1、运筹学,教学要求：,了解动态规划的基本思想,掌握一维离散动态规划的建模和求解方法应用,会运用动态规划方法解决一些基本应用问题。,第一节 动态规划原理和模型,在生产和经营活动中，经常遇到这样的问题，它们包含若干个相互联系的阶段，而且，在每一阶段都要做出决策，一个阶段的决策除影响该阶段本身的效果之外，还影响到下一阶段的起始状态，从而影响到整个过程的效果最优 因此不但要考虑这一阶段，还要把它看成是整个过程决策链中的一个链环，这种过程称为多阶段决策过程，如企业在生产过程中，由于需求是随时间变化的，因此为了获得全年的最佳效益，就要逐月或逐季度地根据库存和需求决定生产计划。,动态规则是将一个较复杂的多阶段
2、决策问题分解为若干相互关联的较容易求解的子(单）决策问题。 而每一个子决策问题都有多种选择 当一个子决策问题确定以后，将影响另一个子决策问题 从而影响到整个问题的决策,第一节 动态规划原理和模型,例1、最小费用问题：某运输公司拟将一批货物从A地运往E地，其间的交通系统网络如下图所示。图上节点表示地点，边表示两地之间的道路，边上的数字表示两地间的运输费用，求运输费用最低的运输路线。,第2阶段,第3阶段,第4阶段,第1阶段 的状态,第2阶段的状态,第1阶段,第一节 动态规划原理和模型,一、动态规则的实例,例2、机器负荷分配问题：年初完好机器数为u台，其中有u1台用于高负荷生产，产品的年产量为s1=
3、g(u1)，年终完好机器数为au1(a称完好率, 0a1)，另外有u2台机器用于低负荷生产，产品的年产量为s2=g(u2)，年终完好机器数为bu2(0b1)，试制定一个五年计划，使产品产量最高。,即用最快的方法从2*2*2*2*2=32种方案中找到最优方案,一般先保守生产 后风险生产可使产量最大,第一节 动态规划原理和模型,例某运输公司有500辆运输卡车，在超负荷运输(即每天满载行驶500km以上)情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3，在低负荷运输(即每天行驶300KM以下)情况下，年利润为16万元/辆、年损坏率为0.1，现在要求制订一个5年运输计划，问每年年初应如何分配完
4、好车辆在两种不同负荷下运输的卡车数量，使在5年内总利润最大？,第一节 动态规划原理和模型,例3、排序问题：有5个零件需要在A、B两台机床上加工，每个零件都必须经过先A后B的加工顺序，加工时间如下表，问应如何安排加工顺序，使总的加工时间最少？,第一节 动态规划原理和模型,以上问题的一个共同特点是问题的过程可以分解成相互联系的若干阶段，在每个阶段均需要作出决策，各个阶段的决策取决于目前的状态，它又将影响到以后的发展，当各个阶段的决策确定之后，就构成一个决策序列，我们的目的就是要在决策系列中，寻找最优的决策序列 二、动态规则的分类 离散确定性 离散随机性 连续确定性 连续随机性,第一节 动态规划原理
5、和模型,三、动态规则的基本概念 1、阶段 将所给问题，按时间或空间特性分解成若干互相联系的部分，用字母K表示阶段变量,第一节 动态规划原理和模型,4个阶段 多种选择,5个阶段 2种选择,2、状态 状态就是每个阶段的起始位置，它既是该阶段某支路的起点，又是前一阶段某支路的终点,通常一个阶段包含若干个状态，第K阶段的状态就是该阶段所有始点集合 状态变量：描述各阶段状态的变量，用sk表示 状态集合：状态变量sk的取值集合,S1=A, S2=B1,B2,B3 S3=C1,C2,C3 S4=D1,D2,第一节 动态规划原理和模型,3、决策 从一个阶段给定状态出发，到下阶段某一状态的选择 决策变量：描述决
6、策的变量，常用uk(xk)表示第k阶段状态xk的决策变量,第一节 动态规划原理和模型,若第2阶段从状态B1出发到第3阶段时选定的状态为C1,则有u2(B1)=C1,允许的决策集合：第K阶段某给定状态xk的决策变量uk(xk)的允许取值范围 常用Dk(xk)表示,D2(B1)=C1,C3 D2(B2)=C1,C2,C3,第一节 动态规划原理和模型,4、策略 由第一阶段开始到最后阶段终点的全过程的每一阶段的决策ui(xj)(i,j=1,2,3,)组成的决策序列， 记为P1,n(X)=u1(x1),u2(x2),.un(xn) 称Pk,n(X)=uk(xk),uk+1(xk+1),.un(xn)为由
7、第k阶段开始到最后阶段的一个子策略,第一节 动态规划原理和模型,A-B1-C2-D1-E A-B2-C1-D2-E 均为策略,允许策略集合：可供选择策略的范围 最优策略：允许策略集合中最优的一个策略 在例1中最优策略为： A-B1-C3-D2-E,第一节 动态规划原理和模型,5、状态转换方程 它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用sk+1=Tk(sk,uk)表示， 该方程描述了由第k阶段到第k+1阶段的状态转换规律，又称状态转换函数 例1中，前一阶段的终点就是后一阶段的起点，所以状态转换方程为： Sk+1=uk(sk),第一节 动态规划原理和模型,6、指标函数 衡量多
8、阶段决策过程优劣的一种数量指标，一个n阶段决策过程，从1到n称为问题的原过程, 对于任意一个给定的k，从第k阶段到第n阶段的过程称为原过程的一个后部子过程， 用V1,n(s1,p1,n)表示初始状态为s1，采用策略p1,n时，原过程的指标函数值 如V1,4(A,P1,4) 而Vk,n(sk,pk,n)表示在第k 阶段，状态为 sk采用策略pk,n时，后部子过程的指标函数值， V2,4(B1,P2,4),第一节 动态规划原理和模型,从第k阶段状态 sk 采用最优策略pk*,n到过程终止时的最佳效益值，称为最优指标函数 记 fk(sk)=Vk,n(sk,pk*,n)=optimumpk,nVk,n
9、(sk,pk,n) 在例1中，每阶段所走的距离为指标函数， 如 V2,4(B1) 表示在第2阶段，状态为B1时，从B1到E的距离 而f2(B1)则表示从B1到E最短距离，本问题所要求的目标是距离之和的最小值，即 f1(A),第一节 动态规划原理和模型,四、动态规划贝尔曼的最优化原理 最优决策具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略 贝尔曼的最优化原理 如果最短路线在第k 阶段通过状态xk，则这条最短路线在由xk 出发到达终点的这段线段，对于从xk出发到终点的所有其它线路来说仍然是最优的,第一节 动态规划原理和模型,第一节 动态规划
10、原理和模型,例如：上例的最优策略为：A-B1-C3-D2-E B1-C3-D2-E仍然是从B1出发到终点的所有线路中最短的一条 B1-C1-D1-E 17 B1-C1-D2-E 13 B1-C3-D2-E 12,一、动态规划求解的思想 逆序法：是从过程的最后一阶段开始，用逆序递推方法求解，逐步求出各阶段各点到终点E的最短路线，最后求得A到E点的最短路线 顺序法：是从过程的第一阶段开始，用顺序递推的方法求解，逐步求出各阶段各点到起点最短路线，最后求得A到E点的最短路线。,第二节 动态规划求解方法,第二节 动态规划求解方法,利用逆序法求解例1： （1）k=4，第四阶段 在第四阶段，有两个初始状态：
11、D1，D2，而全过程的最短路径究竟是经过D1，D2中哪一点，目前无法肯定，因此只能将各种可能都考虑， 若全过程的最短路径经过D1，则从D1到终点的最短路径距离为f4(D1)=5, 若全过程的最短路径经过D2，则从D2到终点的最短路径距离为f4(D2)=3, S4D1,D2 f4(D1)=d4(D1,E)=5 最优策略u4(D1)=E f4(D2)=d4(D2,E)=3 最优策略u4(D2)=E,第二节 动态规划求解方法,第二节 动态规划求解方法,(2) k=3 第三阶段 第三阶段有三个初始状态，同样我们无法确定最短路径是经过哪个状态，因此，也要考虑所有的情况 ，若经过C1，则C1到E有两条支路
12、：C1- D1-E 和 C1-D2-E， 对于C1-D1-E，其最短路径应为：从C1-D1的距离d3(C1,D1)，再加上D1-E的最短距离f4(D1),故有 C1-D1-E： d3(C1,D1)+ f4(D1)=9+5=14 C1-D2-E: d3(C1,D2)+ f4(D2)=8+3=11 又因为若全过程最短路径经过C1,，则从C1到终点E应是一切可能路径中最短路径，即：,最小费用路线为C1D2E 相应的最优决策u3(C1)=D2,第二节 动态规划求解方法,同理，对于C2，有：,第二节 动态规划求解方法,第二节 动态规划求解方法,(3) k=2，第二阶段，有三种初始状态 S2=B1,B2,
13、B3,第二节 动态规划求解方法,最小费用路线为A-B1-C3D2E 相应的最优决策u1(A)=B1 所以整个问题的最小费用路线为A-B1-C3-D2-E 最优策略为u1(A)=B1,u2(B1)=C3,u3(C3)=D2,u4(D2)=E 每一阶段的求解都利用了第k阶段和第k+1阶段的如下关系求解： fk(sk)=mindk(sk,uk)+fk+1(sk+1),k=4,3,2,1 f5(s5)=0 这种关系称为动态规划的基本方程， dk(sk,uk)表示第k阶段由状态sk点出发，采用策略uk到下一阶 段sk+1点时的两点间的距离,(4) S1=A,第二节 动态规划求解方法,第二节 动态规划求解
14、方法,1、逆序标号法求最短路径,0,5,3,10,13,8,12,14,16,16,由上图可知，最优策略为：A-B1-C3-D2-E 最短路长度为16,第二节 动态规划求解方法,练习 利用逆序标号法求最短路径,第二节 动态规划求解方法,0,4,3,8,7,6,14,11,13,15,所以最短路径为：A-B2-C1-D2-E 最短路程为：15,第二节 动态规划求解方法,利用逆序标号法求最长路径,第二节 动态规划求解方法,0,4,3,9,8,6,16,13,16,19,所以最长路径为：A-B3-C2-D2-E 最长路程为19,第二节 动态规划求解方法,顺序递推(前向法) 顺序递推是由过程的始点向终
15、点逐段递推，其阶段变量的设置与状态变量的设置次序与逆序法相同，而最优值函数fk(xk+1)表示第 k阶段末的结束状态为xk+1时，从第1阶段到第k阶段所得到的最大收益，因此顺序递推是相对始点而言的收益，故一般选择第k阶段末(即第k+1阶段初的状态)作为第k阶段的状态变量,第二节 动态规划求解方法,动态规划用顺序递推(前向法)时的基本方程如下： fk(xk+1)=minvk(xk+1,uk)+fk-1(xk),k=1,2,n 始端条件f0(x1)=0 其状态转换方程为： Xk=Tk(xk+1,uk) 上式中，fk(xk+1)是指第k阶段状态为xk+1时，相对于始点的最优指标函数值 而vk(xk+
16、1,uk)表示第k阶段状态为xk+1取决策为uk时对本阶段的阶段效益值 一般来说，当过程给定终点时，用顺序递推法比较方便，若一个多阶段决策问题，有一个固定的过程始点和一个固定的过程终点，则顺序递推和逆序递推会得到相同的最优结果,第二节 动态规划求解方法,第二节 动态规划求解方法,用顺序递推法求例1 当k=1时，由基本方程f1(x2)=minv1(x2,u1)+f0(x1) 而f0(x1)=0 且x2有三种可能的取值：B1,B2,B3，故有 f1(B1)=mind(B1,A)+f0(A)=4 f1(B2)=mind(B2,A)+f0(A)=3 f1(B3)= mind(B3,A)+f0(A)=11,第二节 动态规划求解方法,当k=2时，f2(x3)=minv2(x3,u2)+f1(x2) 当x3=C1时，u2有三种取值。故有 d2(C1,B1)+f1(B1) f2(c1)=min d
