运筹学六课件

1、第七章,动 态 规 划,主要内容：,第一节 多阶段决策过程的最优化 第二节 动态规划的基本概念和基本原理 第三节 动态规划的建模与求解 第四节 动态规划在经济管理中的应用,第一节,多阶段决策过程的最优化,动态规划：是解决多阶段决策过程最优化问题的一种方法 多阶段决策过程 是指某一些特殊的活动过程，它们可以按照时间顺序划分为若干个相互联系的阶段，在每个阶段都需要进行决策。,一、多阶段决策过程的最优化的相关概念,多阶段决策过程最优化 在多阶段决策过程中，各个阶段所确定的决策就构成了一个决策序列，称为一个策略。一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多可供选择的

2、策略。在所有可供选择的策略中，对应的整体效果最好的策略称为最优策略。 把一个问题划分成若干个相互联系的阶段并选取其最优策略，这就是多阶段决策过程的最优化问题。,二、多阶段决策过程最优化的例子,生产与存贮问题 某工厂每月需供应市场一定数量的产品，并将所余产品存入仓库。一般某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用。要求确定一个逐月的生产计划，在满足需求的条件下，使一年的生产与存贮费用之和最小。 可以把该问题按月划分为12个阶段，每个阶段初决定该阶段（月）的生产数量。,设备更新问题 企业考虑n年内某种设备的更新问题。我们知道，设备使用时间越长，维修费用越高，处理价值（设备残值

3、）越低，但是如果卖去旧的买新的，则需要一次性支出较大的费用。因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。 可以把该问题按年划分为n个阶段，每个阶段（年）初都需要进行决策，决定设备是否更新。,以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。 不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决

4、。,背包问题 一位旅行者携带背包去登山，已知他所能承受的背包重量限制为a千克，现有n种物品可供他选择装入背包，第i件物品的重量为ai千克，其价值是携带数量xi的函数 。 问旅行者如何选择携带各种物品的件数，以使总价值最大。 可以把该问题按物品种类划分为n个阶段，每个阶段（种类）都需要进行决策，决定该种物品的件数。,投资问题 某公司有Q元资金用于投资，可以投资于n个项目，投资于第i个项目投资额为xi时，其收益为 ，如何分配投资额，才能使总收益最大。 可以把该问题按项目划分为n个阶段，每个阶段（项目）都需要进行决策，决定项目投资的数额。,最短路问题 求v1到v13的最短距离。,按空间划分为5各阶段

5、。,第二节,动态规划的基本概念和基本原理,一、动态规划的基本概念,1、阶段和阶段变量 将所给问题的过程，按决策进行的时间或空间上先后顺序划分为若干子过程，每个子过程称为一个阶段。 用以描述阶段的变量叫作阶段变量，一般以字母k表示。,例中：阶段k=1,2,3,4,5,2、状态、状态变量和状态集 各阶段开始时的客观条件（所处的位置、运动状态等）称为状态。 描述各阶段状态的变量叫作状态变量，一般用字母sk表示第k阶段的状态变量。 状态变量sk的取值集合称为状态集合，用字母Sk表示，有 。,例中：S1=v1,S2=v2,v3,S3=v4,v5, v6, v7,S4=v8,v9, v10,S5=v11,

6、v12,无后效性当某阶段的状态给定以后，在这阶段以后过程的发展不受这段以前各阶段的影响。,动态规划中的各阶段的状态应具有无后效性。,3、决策、决策变量和允许决策集合 当各阶段的状态取定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。 描述各阶段决策的变量称为决策变量，一般用字母 表示第k阶段状态为sk 时的决策变量。 决策变量的允许取值集合称为允许决策集合，用字母 表示第k阶段状态为sk 时的允许决策集合，有 。,例中：D1(v1)=v2,v3,D2 (v2)=v4,v5, v6,D3 (v3)=v5, v6 , v7,D4(v4)=v8, v9 ,4、策略、允

7、许策略集合 当各阶段的决策确定以后，整个问题的决策序列就够成一个策略，用 表示。 策略的允许取值集合称为允许策略集合，记作 。 从k阶段到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为 。 允许策略集合中，效果最优的策略称为最优策略。,例中：p1,nv3,v5,v8,v11,v13为一个策略。,共有24个策略。,5、状态转移方程 动态规划中，某阶段的状态是上一阶段的状态和上一阶段的决策的结果。 如果给定了第k阶段的状态sk,该阶段的决策为 ，则第k+1阶段的状态sk+1也就完全确定，它们的关系可用下式表示：,例中：sk+1=uk(sk),6、指标函数和最优指标函数 用来衡量策

8、略效果的某种数量指标，称为指标函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。 (1)阶段指标函数（也称阶段效应）。 表示第k段处于sk状态、所作决策为uk(sk)时的指标就是第k段指标函数，记为dk(sk ,uk )。,例中：阶段指标函数为距离。 d(v1,v3)表示在v1,选择v3的距离。,初始状态为s1，采取策略p1,n的全过程的指标函数。,初始状态为sk，采取策略pk,n的后部子过程的指标函数。,(2)过程指标函数,例中：V2,5(v3)表示从V3到V13的距离。,V1,5(v1)表示从V1到V13的距离。,过程指标函数形式之一是取各阶段

9、指标之和的形式，即: 有些问题，如系统可靠性问题，其过程指标函数是取各阶段指标的连乘积形式，如： 总之，具体问题的过程指标函数表达形式需要视具体问题而定。,(3)最优指标函数,表示在第k阶段，状态为sk时，采取最优策略p*k,n到最终阶段的指标函数。,即为全过程最优指标函数。,例中：f3(v5)表示从V5到V13的最短距离。,f1(v1)表示从V1到V13的最短距离。,二、动态规划的基本原理,最优化原理 （贝尔曼最优化原理） 作为一个全过程的最优策略具有这样的性质：无论初始状态和初始决策如何，对于先前决策所形成的状态而言，其后的所有决策必构成一个最优子策略。,第三节,动态规划模型的建立与求解,

10、一、动态规划模型的建立,（1）划分阶段 分析问题，识别问题的多阶段特点，按时间或空间的先后顺序划分为满足递推关系的若干阶段，对非时序的“静态”问题，要人为地赋予“阶段”概念。 （2）正确选择状态变量 动态规划中状态变量要具有无后效性和可知性。 可知性，即所规定的各段状态变量的值，可以直接或间接地测算得到。,（3）正确定义决策变量 根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。 （4）正确写出状态转移方程 （5）写出指标函数 （6）写出基本方程,二、动态规划模型的求解（逆序解法和顺序解法）,例1：逆序解法求以下最短路问题,状态变量sk：第k阶段初所处的位置；,决策变量uk：第k阶

11、段初所做的决策；,状态转移方程：sk+1=uk；,阶段指标函数d (sk,uk)：从第k阶段初所处的位置，采取决策到下一阶段的距离；,阶段k：取1,2,3,4,5；,过程指标函数： ，表示从第k阶段初所处的位置，采取一系列决策到终点的距离；,最优指标函数fk(sk):表示从第k阶段初所处的位置，采取一系列决策到终点的最短距离；,基本方程为：,（1）当k=5时，,（2）当k=4时，,（3）k=3时，,（4）k=2时，,（5）k=1时，,顺藤摸瓜，找出最优决策序列（最优策略）：,最短路线为：v1 v2 v5 v9 v12 v13,最短路距离为：f1(v1)=17,例2：用逆序法求如下投资问题,某公

12、司有10万元资金投资于i(i=1,2,3)，投资于第i个项目投资额为xi时，其收益分别为g1(x1)=4x1,g2(x2)=9x2,g3(x3)=2x32，如何分配投资额，才能使总收益最大。,该问题的静态模型为：,该问题的动态规划求解过程为：,状态变量sk：可以用于投资到第k到n个项目的资金数；,决策变量xk：投入到第k个项目的资金；,状态转移方程：sk+1=sk-xk；,阶段指标函数gk (xk)：投入第k个项目xk获得的收益；,阶段k：取1,2,3；,过程指标函数： ，表示投入项目k到n个项目获得的收益；,最优指标函数fk(sk):表示可投资金为sk时，投资第k到n个项目所获得的最大收益；

13、,基本方程为：,（1）当k=3时，,（2）当k=2时，,（3）当k=1时，,顺藤摸瓜，找出最优决策序列（最优策略）：,例3：顺序解法求以下最短路问题,状态变量sk+1：第k阶段末所处的位置；,决策变量uk：第k阶段末所做的决策；,状态转移方程：sk=uk；,阶段指标函数d (sk+1,uk)：从第k阶段末所处的位置，采取决策到k阶段初的距离；,阶段k：取1,2,3,4,5；,过程指标函数： ，表示从第k阶段末所处的位置，采取一系列决策到起点的距离；,最优指标函数fk(sk+1):表示从第k阶段末所处的位置，采取一系列决策到起点的最短距离；,基本方程为：,（1）当k=1时，,（2）k=2时，,（

14、3）当k=3时，,（4）k=4时，,（5）k=5时，,顺藤摸瓜，找出最优决策序列（最优策略）：,最短路线为：v1 v2 v5 v9 v12 v13,最短路距离为：f1(v1)=17，与逆序法结论相同。,例4：用顺序法求如下投资问题,某公司有10万元资金投资于i(i=1,2,3)，投资于第i个项目投资额为xi时，其收益分别为g1(x1)=4x1,g2(x2)=9x2,g3(x3)=2x32，如何分配投资额，才能使总收益最大。,该问题的静态模型为：,该问题的动态规划求解过程为：,状态变量sk+1：可以用于投资到第1到k个项目的资金数；,决策变量xk：投入到第k个项目的资金；,状态转移方程：sk=s

15、k+1-xk；,阶段指标函数gk (xk)：投入第k个项目xk获得的收益；,阶段k：取1,2,3；,过程指标函数： ，表示投入项目1到k个项目获得的收益；,最优指标函数fk(sk+1):表示可投资金为sk+1时，投资第1到k个项目所获得的最大收益；,基本方程为：,（1）当k=1时，,（2）当k=2时，,（3）当k=3时，s4=10,顺藤摸瓜，找出最优决策序列（最优策略）：,三、顺序法与逆序法的不同点,两种方法本质是相同的。主要区别如下： 状态转移方式不同 指标函数的定义不同 基本方程形式不同,逆序法：,顺序法：,逆序法：,顺序法：,f1(s1)是整体最优函数值,fn(sn+1)是整体最优函数值

16、,第四节,动态规划在经济管理中的应用,一、背包问题,一位旅行者携带背包去登山，已知他所能承受的背包重量限制为a千克，现有n种物品可供他选择装入背包，第i件物品的重量为ai千克，其价值是携带数量xi的函数 。问旅行者如何选择携带各种物品的件数，以使总价值最大。,设xi为第i种物品携带的数量，该问题的整数规划模型如下：,用动态规划的顺序解法建模求解，过程如下：,阶段k：将可装入物品按1，2，n 排序，每种物品按一个阶段，共n个阶段。K=1，2，n。,状态变量sk+1：在第k阶段开始时，可以装入前k种物品的总重量。,决策变量xk：在第k阶段开始时，装入第k种物品的件数。,状态转移方程 ： sk =

17、sk+1-akxk,允许决策集合 ： Dk (sk+1)= xk|0 xksk+1/ak, xk为整数,最优指标函数 fk (sk+1)：在第k阶段初，可以装入前k种物品的总重量为sk+1时，选择最优策略装前k种物品的价值。,基本方程：,例：有一辆货运量为10t的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如下表所示。应如何装载可使装载总价值最大？,解：设第i种货物装入xi件，该问题可表示为：,建立动态规划模型（顺序解法）：,阶段k：将可装入物品按1，2，3 排序，每种物品按一个阶段，共3个阶段。K=1，2，3。,状态变量sk+1：在第k阶段开始时，可以装入前k种物品的总重量。,决

18、策变量xk：在第k阶段开始时，装入第k种物品的件数。,状态转移方程 ： sk = sk+1-akxk （a1=3，a2=4，a3=5）,允许决策集合 ： Dk (sk+1)= xk|0 xksk+1/ak, xk为整数,最优指标函数 fk (sk+1)：在第k阶段初，可以装入前k种物品的总重量为sk+1时，选择最优策略装前k种物品的价值。,基本方程：,（1）当K=1时,s2,0,1,2,3,4,5,6,7,8,9,10,f1(s2),0,x1*,0,0,0,0,0,4,1,4,1,4,1,8,2,8,2,8,2,12,3,12,3,（2）当K=2时,s3,0,1,2,3,4,5,6,7,8,9

19、,10,f2(s3),x2*,x2,5x2 +f1(s2),0,0,0,0,0,1,0,1,0,1,0,1,0,1,2,2,0,1,2,0,1,0,0,0,0,0,0,0,0,0,4,4,0,4,5,5,1,4,5,5,1,8,5,8,0,8,9,9,1,8,9,10,10,2,12,9,10,12,0,12,13,10,13,1,（3）当K=3时 ，s4=10,s4,10,f3(s4),x3*,x3,6x2 +f2(s3),0,1,2,13,11,12,13,0,二、生产与存贮问题,例：某工厂生产并销售某种产品，已知今后四个月市场需求预测如下表，又每月生产j单位产品费用为：,每月库存j单位产

20、品的费用为E(j)=0.5j（千元），该厂最大库存量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第i+1个月的库存量是第i个月可销售量与该月用户需求量之差；而第i个月的可销售量是本月初库存量与产量之和。,解：用动态规划的逆序解法建模求解，过程如下：,阶段k：每个月为一个阶段，共4个阶段。k=1，2，3，4。,状态变量sk：第k阶段（月）初的库存量。,决策变量uk：第k阶段的生产量。,状态转移方程 ： sk+1 = sk+uk-gk,最优指标函数 fk (sk)：在第k月初库存量为sk时，选择最优策略生产，从本月

21、到第4个月末的最低生产、库存费用之和。,（1）当k=4时，,首先确定s4的允许集合。,考虑到最大库存量3：s43。,考虑到最大生产能力6：s43*6-（2+3+2）。,考虑到期末库存量为0：s44。,综上，有：s43，即s4 可以取0，1，2，3。,s4,0,f4(s4),u4*,u4,C4 +E4,1,2,3,4,3,2,1,7+0,7,4,6+0.5,6.5,3,5+1,6,2,4+1.5,5.5,3,（2）当k=3时，,首先确定s3的允许集合。,考虑到最大库存量3：s33。,考虑到最大生产能力6：s32*6-（2+3）。,考虑到期末库存量为0：s32+4。,综上，有：s33，即s3 可以

22、取0，1，2，3。,然后确定u3允许集合。,考虑到最大库存量3：s3+u3g33，即u33+2-s3。,考虑到最大生产能力6：u36。,考虑到期末库存量为0：s3+u3-g34，即u34+2-s3,考虑到本月需求量g3为2：s3+u32，即u3 2-s3,综上，有： max0，2-s3 u35-s3,s3,0,f3(s3),u3*,u3,C3 +E3 +f4,1,2,3,2,3,4,5,1,2,3,4,0,1,2,3,0,1,2,12,12.5,13,13.5,12,2,11.5,12,12.5,13,11.5,1,8,11.5,12,12.5,8,0,8,11.5,12,8,0,（3）当k=

23、2时，,首先确定s2的允许集合。,考虑到最大库存量3：s23。,考虑到最大生产能力6：s26-2。,考虑到期末库存量为0：s23+2+4。,综上，有：s23，即s2 可以取0，1，2，3。,然后确定u2允许集合。,考虑到最大库存量3：s2+u2g23，即u23+3-s2。,考虑到最大生产能力6：u26。,考虑到期末库存量为0：s2+u2-g2g3+g4，即u22+4+3-s3,考虑到本月需求量g2为3：s2+u23，即u2 3-s2,综上，有： max0，3-s2 u27-s2,s2,0,f2(s2),u2*,u2,C2 +E2+f3,1,2,3,3,4,5,6,2,3,4,5,1,2,3,4

24、,0,1,2,18,18.5,16,17,16,5,17.5,18,15.5,16.5,15.5,4,17,17.5,15,16,15,3,13.5,17,14.5,13.5,0,3,15.5,（4）当k=1时，,s1=0。,然后确定u1允许集合。,考虑到最大库存量3：s1+u1g13，即u13+2-s1。,考虑到最大生产能力6：u26。,考虑到期末库存量为0： s1+u1-g1g2+g3+g4，即u13+2+4+2-s1,考虑到本月需求量g1为2：s1+u12，即u1 2-s1,综上，有： max0，2-s1 u15-s1,即： 2 u15,s1,0,f1(s1),u1*,u1,C1 +E1

25、 +f2,2,3,4,5,21,21.5,22,21.5,21,2,u1*=2,s2=2+2-0=0,u2*=5,s3=0+5-3=2,u3*=0,s4=2+0-2=0,u4*=4,设最大能力为p，最大库存量为q。,允许决策集合为:,允许状态集合为：,此类生产与库存问题的基本方程为：,最大库存限制,期末库存量为0的限制,最大生产能力的限制,最大生产能力限制,期末库存量为0的限制,最大库存限制,本月需求的限制,三、采购与销售问题,例：某商店在未来的4个月里，准备利用它的一个仓库来专门经销某种商品，仓库最大容量能贮存该种商品1000单位。假定该商店每月只能出卖仓库现有的货物。当商店在某月购货时，下

26、月初才能到货。预测该商店未来四个月的买卖价格如下表所示，假定商店在1月开始经销时，仓库存有该商品500单位。试问若不计较库存费用，该商店应如何制定1月至4月的订购与销售计划，使预期获利最大。,解：用动态规划的逆序解法建模求解，过程如下：,阶段k：每个月为一个阶段，共4个阶段。k=1，2，3，4。,状态变量sk：第k阶段（月）初的库存量（含上月订货量）。,决策变量：xk第k月的出售量；yk第k月的订货量。,状态转移方程 ： sk+1 = sk+yk-xk,最优指标函数 fk (sk)：在第k月初库存量为sk时，选择最优策略，获得的从本月初到第4个月末的利润。,基本方程为：,（1）当k=4时,（2

27、）当k=3时,求解一个线性规划问题,（3）当k=2时,求解一个线性规划问题,（4）当k=1时，s1=500,四、设备更新问题,已知一台设备的效益函数为r(t)，维修费用函数为u(t)，更新费用函数为c(t)，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年总效益最大。,设： rk(t):在第k年设备已使用过t年（或称役龄为t年），再 使用一年的经济效益。,uk(t):在第k年设备役龄为t年，再使用一年的维修费用。,ck(t):在第k年卖掉一台役龄为t年的设备，买进一台新设备的更新净费用。,（01） :折扣因子。表示一年以后单位收入价值相当于现年的单位 。,建立动态规划模

28、型如下（逆序解法）：,阶段k：每年为一个阶段，共n个阶段。k=1，2，n。,状态变量sk：第k年初，设备已使用过的年数（即役龄）。,决策变量xk ：表示第k年初是保留（keep）使用旧设备，还是更新（replacement）旧设备，分别用K和R表示。,状态转移方程 ：,过程指标函数：,阶段指标函数：,最优指标函数 fk (sk)：在第k年初拥有一台役龄为sk的设备，选择最优策略，获得的从年到第n年末的收益。,基本方程为：,即：,例：设某台新设备的年效益及年均维修费、更新净费用如下表所示。试确定今后5年内的更新策略，使总收益最大。设=1。,役龄,项目,单位：万元,解：如前建立动态规划模型。,（1

29、）当k=5时，s5可以取1，2，3，4,（2）当k=4时，s4可以取1，2，3,（3）当k=3时，s3可以取1，2,（4）当k=2时，s2取值为1,（5）当k=1时，s1为0,所以，第1年初购买新设备后，于第2，3，4年分别更新设备。,五、复合系统工作可靠性问题,某种复合系统由n个部件串联而成：,部件i装有zi个备用元件，它正常工作的概率为pi(zi)；,系统正常工作的概率为：,部件i装一个备用元件的费用为ci，系统总费用不得超过c；,求可以使得p达到最大的zi的选取方法。,该问题的静态模型为：,例：,某厂设计一种电子设备，由三种元件D1,D2,D3组成，已知这三种元件的价格及可靠性如下表。要求在设计中所使用元件的费用不超过105元，试问如何