1、第七章第七章动动 态态 规规 划划主要内容：主要内容：第一节第一节 多阶段决策过程的最优化多阶段决策过程的最优化第二节第二节 动态规划的基本概念和基本原理动态规划的基本概念和基本原理第三节第三节 动态规划的建模与求解动态规划的建模与求解第四节第四节 动态规划在经济管理中的应用动态规划在经济管理中的应用第一节第一节多阶段决策过程的最优化多阶段决策过程的最优化o 动态规划：动态规划：是解决是解决多阶段决策过程最优化问题多阶段决策过程最优化问题的一种方法的一种方法o 多阶段决策过程多阶段决策过程 是指某一些特殊的活动过程，它们可以按照是指某一些特殊的活动过程，它们可以按照时间顺序划分为若干个相互联系
2、的阶段，在每时间顺序划分为若干个相互联系的阶段，在每个阶段都需要进行决策。个阶段都需要进行决策。一、多阶段决策过程的最优化的相关概念一、多阶段决策过程的最优化的相关概念o 多阶段决策过程最优化多阶段决策过程最优化 在多阶段决策过程中，各个阶段所确定的决在多阶段决策过程中，各个阶段所确定的决策就构成了一个决策序列，称为一个策就构成了一个决策序列，称为一个策略策略。一。一般来说，由于每一阶段可供选择的决策往往不般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多可止一个，因此，对于整个过程，就会有许多可供选择的策略。在所有可供选择的策略中，对供选择的策略。在所有可供选择的
3、策略中，对应的整体效果最好的策略称为应的整体效果最好的策略称为最优策略最优策略。把一个问题划分成若干个相互联系的阶段把一个问题划分成若干个相互联系的阶段并选取其最优策略，这就是多阶段决策过程的并选取其最优策略，这就是多阶段决策过程的最优化问题。最优化问题。二、多阶段决策过程最优化的例子二、多阶段决策过程最优化的例子o 生产与存贮问题生产与存贮问题 某工厂每月需供应市场一定数量的产品，某工厂每月需供应市场一定数量的产品，并将所余产品存入仓库。一般某月适当增加产并将所余产品存入仓库。一般某月适当增加产量可降低生产成本，但超产部分存入仓库会增量可降低生产成本，但超产部分存入仓库会增加库存费用。要求确
4、定一个逐月的生产计划，加库存费用。要求确定一个逐月的生产计划，在满足需求的条件下，使一年的生产与存贮费在满足需求的条件下，使一年的生产与存贮费用之和最小。用之和最小。可以把该问题可以把该问题按月按月划分为划分为12个阶段，每个阶段，每个阶段初决定该阶段（月）的生产数量。个阶段初决定该阶段（月）的生产数量。o 设备更新问题设备更新问题 企业考虑企业考虑n n年内某种设备的更新问题。我们年内某种设备的更新问题。我们知道，设备使用时间越长，维修费用越高，处知道，设备使用时间越长，维修费用越高，处理价值（设备残值）越低，但是如果卖去旧的理价值（设备残值）越低，但是如果卖去旧的买新的，则需要一次性支出较
5、大的费用。因此买新的，则需要一次性支出较大的费用。因此就需要综合权衡决定设备的使用年限，使总的就需要综合权衡决定设备的使用年限，使总的经济效益最好。经济效益最好。可以把该问题可以把该问题按年按年划分为划分为n个阶段，每个阶个阶段，每个阶段（年）初都需要进行决策，决定设备是否更段（年）初都需要进行决策，决定设备是否更新。新。以上所举问题的发展过程都与时间因素有以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了策往往
6、也与时间因素有关，这就使它具有了“动态动态”的含义，所以把处理这类动态问题的的含义，所以把处理这类动态问题的方法称为动态规划方法。方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的不过，实际中尚有许多不包含时间因素的一类一类“静态静态”决策问题，就其本质而言是一次决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。用动态规划方法加以解决。o 背包问题背包问题 一位旅行者携带背包去登山，已知他所能承一位旅行者携带背包去登山，已知他
7、所能承受的背包重量限制为受的背包重量限制为a a千克，现有千克，现有n n种物品可供种物品可供他选择装入背包，第他选择装入背包，第i i件物品的重量为件物品的重量为a ai i千克，千克，其价值是携带数量其价值是携带数量x xi i的函的函数数 。问旅行者如何选择携带各种物品的件数，以问旅行者如何选择携带各种物品的件数，以使总价值最大。使总价值最大。可以把该问题可以把该问题按物品种类按物品种类划分为划分为n个阶段，个阶段，每个阶段（种类）都需要进行决策，决定该种每个阶段（种类）都需要进行决策，决定该种物品的件数。物品的件数。nixcii,2,1 )(o 投资问题投资问题 某公司有某公司有Q Q
8、元资金用于投资，可以投资于元资金用于投资，可以投资于n n个个项目，投资于第项目，投资于第i i个项目投资额为个项目投资额为x xi i时，其收益时，其收益为为 ，如何分配投资额，才能使，如何分配投资额，才能使总收益最大。总收益最大。可以把该问题可以把该问题按项目按项目划分为划分为n个阶段，每个个阶段，每个阶段（项目）都需要进行决策，决定项目投资阶段（项目）都需要进行决策，决定项目投资的数额。的数额。nixgii,2,1 )(o 最短路问题最短路问题 求求v1v1到到v13v13的最短距离。的最短距离。v1v2v3v4v5v6v7v8v9v12v10v11v135455544442368778
9、38362313第1阶段第2阶段第3阶段第4阶段第5阶段按空间按空间划分为划分为5各阶段。各阶段。第二节第二节动态规划的基本概念和基本原理动态规划的基本概念和基本原理一、动态规划的基本概念一、动态规划的基本概念1、阶段和阶段变量、阶段和阶段变量 将所给问题的过程，按决策进行的时间将所给问题的过程，按决策进行的时间或空间上先后顺序划分为若干子过程，每个或空间上先后顺序划分为若干子过程，每个子过程称为一个子过程称为一个阶段阶段。用以描述阶段的变量叫作用以描述阶段的变量叫作阶段变量阶段变量，一，一般以字母般以字母k k表示。表示。例中：阶段例中：阶段k=1,2,3,4,5 2、状态、状态变量和状态集
10、、状态、状态变量和状态集 各阶段开始时的客观条件（所处的位置、各阶段开始时的客观条件（所处的位置、运动状态等）称为运动状态等）称为状态状态。描述各阶段状态的变量叫作描述各阶段状态的变量叫作状态变量状态变量，一，一般用字母般用字母sk表示第表示第k阶段的状态变量。阶段的状态变量。状态变量状态变量sk的取值集合称为状态集合，的取值集合称为状态集合，用字母用字母Sk表示，有表示，有 。Sskk 例中：例中：S1=v1S2=v2,v3S3=v4,v5,v6,v7S4=v8,v9,v10S5=v11,v12无后效性无后效性当某阶段的状态给定以后，在这当某阶段的状态给定以后，在这阶段以后过程的发展不受这段
11、以前各阶段的影阶段以后过程的发展不受这段以前各阶段的影响。响。动态规划中的各阶段的状态应具有无后效性。动态规划中的各阶段的状态应具有无后效性。3、决策、决策变量和允许决策集合、决策、决策变量和允许决策集合 当各阶段的状态取定以后，就可以作出不当各阶段的状态取定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状同的决定（或选择），从而确定下一阶段的状态，这种决定称为态，这种决定称为决策决策。描述各阶段决策的变量称为描述各阶段决策的变量称为决策变量决策变量，一，一般用字母般用字母 表示第表示第k阶段状态为阶段状态为sk 时的决时的决策变量。策变量。决策变量的允许取值集合称为决策变量的允许取
12、值集合称为允许决策集允许决策集合合，用字母，用字母 表示第表示第k阶段状态为阶段状态为sk 时的时的允许决策集合，有允许决策集合，有 。)(kksu )(kksD )()(kkkksDsu 例中：例中：D1(v1)=v2,v3D2(v2)=v4,v5,v6D3(v3)=v5,v6,v7D4(v4)=v8,v9 4、策略、允许策略集合、策略、允许策略集合 当各阶段的决策确定以后，整个问题的决策当各阶段的决策确定以后，整个问题的决策序列就够成一个序列就够成一个策略策略，用用 表示。表示。策略的允许取值集合称为策略的允许取值集合称为允许策略集合允许策略集合，记作记作 。从从k阶段到第阶段到第n阶段，
13、依次进行的阶段决策阶段，依次进行的阶段决策构成的决策序列称为构成的决策序列称为k部子策略部子策略,表示为表示为 。允许策略集合中，效果最优的策略称为允许策略集合中，效果最优的策略称为最最优策略优策略。)(,),(),(2211,1nnnsususup,1 nP )(,),(),(11,nnkkkknksususup 例中：例中：p1,nv3,v5,v8,v11,v13为一个策略。为一个策略。共有共有24个策略。个策略。5、状态转移方程、状态转移方程 动态规划中，某阶段的状态是上一阶段的状动态规划中，某阶段的状态是上一阶段的状态和上一阶段的决策的结果。态和上一阶段的决策的结果。如果给定了第如果给
14、定了第k阶段的状态阶段的状态sk,该阶段的决该阶段的决策为策为 ，则第，则第k+1阶段的状态阶段的状态sk+1也就完也就完全确定，它们的关系可用下式表示：全确定，它们的关系可用下式表示：)(kksu),(1kkkkusTs 例中：例中：sk+1=uk(sk)6、指标函数和最优指标函数、指标函数和最优指标函数 用来衡量策略效果的某种数量指标，称为指用来衡量策略效果的某种数量指标，称为指标函数。对不同问题，指标函数可以是诸如费用、标函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、成本、产值、利润、产量、耗量、距离、时间、效用，等等。效用，等等。(1)(1)阶段指
15、标函数阶段指标函数（也称阶段效应）。（也称阶段效应）。表示第表示第k k段处于段处于sk状态、所作决策为状态、所作决策为u uk k(s sk k)时时的指标就是第的指标就是第k段指标函数，记为段指标函数，记为d dk k(s sk k ,u uk k )。例中：阶段指标函数为距离。例中：阶段指标函数为距离。d(v1,v3)表示在表示在v1,选择选择v3的距离。的距离。),(,11,1nnpsV),(,nkknkpsV初始状态为初始状态为s1，采取策略，采取策略p1,n1,n的全过程的全过程的指标函数。的指标函数。初始状态为初始状态为sk，采取策略，采取策略pk,nk,n的后部子的后部子过程的
16、指标函数。过程的指标函数。(2)过程指标函数过程指标函数例中：例中：V2,5(v3)表示从表示从V3到到V13的距离。的距离。V1,5(v1)表示从表示从V1到到V13的距离。的距离。过程指标函数形式之一是取各阶段指标之和的形过程指标函数形式之一是取各阶段指标之和的形式，即式，即:有些问题，如系统可靠性问题，其过程指标函数有些问题，如系统可靠性问题，其过程指标函数是取各阶段指标的连乘积形式，如：是取各阶段指标的连乘积形式，如：总之，具体问题的过程指标函数表达形式需要视总之，具体问题的过程指标函数表达形式需要视具体问题而定。具体问题而定。nkiiiinkusdV),(,nkiiiinkusdV)
17、,(,(3)(3)最优指标函数最优指标函数 ),(),()(,*,nkknkPpnkknkkkpsVoptpsVsfnknk 表示在第表示在第k阶段，状态为阶段，状态为sk时时，采取最优策略，采取最优策略p*k,nk,n到最终阶段到最终阶段的指标函数。的指标函数。)(11sf即为全过程最优指标函数。即为全过程最优指标函数。例中：例中：f3(v5)表示从表示从V5到到V13的最短距离。的最短距离。f1(v1)表示从表示从V1到到V13的最短距离。的最短距离。二、动态规划的基本原理二、动态规划的基本原理o 最优化原理最优化原理（贝尔曼最优化原理）（贝尔曼最优化原理）作为一个全过程的最优策略具有这样
18、的作为一个全过程的最优策略具有这样的性质：无论初始状态和初始决策如何，对于性质：无论初始状态和初始决策如何，对于先前决策所形成的状态而言，其后的所有决先前决策所形成的状态而言，其后的所有决策必构成一个最优子策略。策必构成一个最优子策略。第三节第三节动态规划模型的建立与求解动态规划模型的建立与求解一、动态规划模型的建立一、动态规划模型的建立 （1）划分阶段）划分阶段 分析问题，识别问题的多阶段特点，按时间或分析问题，识别问题的多阶段特点，按时间或空间的先后顺序划分为满足递推关系的若干阶段，空间的先后顺序划分为满足递推关系的若干阶段，对非时序的对非时序的“静态静态”问题，要人为地赋予问题，要人为地
19、赋予“阶段阶段”概念。概念。（2）正确选择状态变量）正确选择状态变量 动态规划中状态变量要具有动态规划中状态变量要具有无后效性无后效性和和可知性。可知性。可知性可知性，即所规定的各段状态变量的值，可以，即所规定的各段状态变量的值，可以直接或间接地测算得到。直接或间接地测算得到。（3）正确定义决策变量）正确定义决策变量 根据经验，一般将问题中待求的量，选作动根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。态规划模型中的决策变量。（4）正确写出状态转移方程）正确写出状态转移方程 （5）写出指标函数）写出指标函数 （6）写出基本方程）写出基本方程 二、动态规划模型的求解二、动态规划模型
20、的求解（逆序解法和顺序解法）（逆序解法和顺序解法）例例1：逆序解法求以下最短路问题：逆序解法求以下最短路问题v1v2v3v4v5v6v7v8v9v12v10v11v13545554444236877838362313状态变量状态变量sk：第：第k阶段初所处的位置；阶段初所处的位置；决策变量决策变量uk：第：第k阶段初所做的决策；阶段初所做的决策；状态转移方程状态转移方程：sk+1=uk；阶段指标函数阶段指标函数d(sk,uk)：从第：从第k阶段初所处的位置，阶段初所处的位置，采取决策到下一阶段的距离采取决策到下一阶段的距离；阶段阶段k：取：取1,2,3,4,5；过程指标函数过程指标函数：，表示
21、从第，表示从第k阶段初所处阶段初所处的位置，采取一系列决策到终点的距离的位置，采取一系列决策到终点的距离；55,),(kiiiikusdV最优指标函数最优指标函数fk(sk):表示从第表示从第k阶段初所处的位置，阶段初所处的位置，采取一系列决策到终点的最短距离采取一系列决策到终点的最短距离；基本方程为：基本方程为：0)()(),()(6611minsfsfusdsfkkkkkDukkkk （1）当）当k=5时，时，40),()(1311115 vvdvf,12115vvS 30),()(1312125 vvdvf （2）当）当k=4时，时，,10984vvvS 73543min)(),()()
22、,(min)(12512811511884 vfvvdvfvvdvf118*4)(vvu 53246min)(),()(),(min)(12512911511994 vfvvdvfvvdvf129*4)(vvu 53341min)(),()(),(min)(12512101151110104 vfvvdvfvvdvf1110*4)(vvu （3）k=3时，时，,76543vvvvS 125875min)(),()(),(min)(9494848443 vfvvdvfvvdvf84*3)(vvu 105574min)(),()(),(min)(9495848553 vfvvdvfvvdvf95*
23、3)(vvu 85453min)(),()(),(min)(104106949663 vfvvdvfvvdvf96*3)(vvu 95458min)(),()(),(min)(104107949773 vfvvdvfvvdvf107*3)(vvu （4）k=2时，时，,232vvS 1386103122min)(),()(),()(),(min)(63625352434222 vfvvdvfvvdvfvvdvf52*2)(vvu 159787108min)(),()(),()(),(min)(73736363535332 vfvvdvfvvdvfvvdvf63*2)(vvu （5）k=1时，时
24、，11vS 17155134min)(),()(),(min)(3231222111 vfvvdvfvvdvf21*1)(vvu 顺藤摸瓜，找出最优决策序列（最优策略）：顺藤摸瓜，找出最优决策序列（最优策略）：21*1)(vvu 52*2)(vvu 95*3)(vvu 129*4)(vvu 1312*5)(vvu 最短路线为：最短路线为：v1 v2 v5 v9 v12 v13 最短路距离为：最短路距离为：f1(v1)=17例例2：用逆序法求如下投资问题：用逆序法求如下投资问题 某公司有某公司有1010万元资金投资于万元资金投资于i(ii(i=1,2,3)=1,2,3)，投资于第投资于第i i个
25、项目投资额为个项目投资额为x xi i时，其收益分别时，其收益分别为为g g1 1(x x1 1)=4x)=4x1 1,g,g2 2(x(x2 2)=9x)=9x2 2,g,g3 3(x(x3 3)=2x)=2x3 32 2，如何分，如何分配投资额，才能使总收益最大。配投资额，才能使总收益最大。该问题的静态模型为：该问题的静态模型为：2321294maxxxxZ )3,2,1(010321ixxxxi该问题的动态规划求解过程为：该问题的动态规划求解过程为：状态变量状态变量sk：可以用于投资到第：可以用于投资到第k到到n个项目的资金数；个项目的资金数；决策变量决策变量xk：投入到第：投入到第k个
26、项目的资金；个项目的资金；状态转移方程状态转移方程：sk+1=sk-xk；阶段指标函数阶段指标函数gk(xk)：投入第：投入第k个项目个项目xk获得的收益获得的收益；阶段阶段k：取：取1,2,3；过程指标函数过程指标函数：，表示投入项目，表示投入项目k到到n个项个项目获得的收益目获得的收益；33,)(kiiikxgV最优指标函数最优指标函数fk(sk):表示可投资金为表示可投资金为sk时，投资第时，投资第k到到n个项目所获得的最大收益个项目所获得的最大收益；基本方程为：基本方程为：0)()()()(44110maxsfsfxgsfkkkksxkkkk （1）当）当k=3时，时，23234423
27、3322)(2)(maxmax3333sxsfxsfsxsx 3*3sx （2）当）当k=2时，时，29)(232022max22sxsfsx )(2922220max22xsxsx 2)49(22222220max22sxsxsx 数数为开口向上的抛物线函为开口向上的抛物线函2222222)49(2sxsx 两端取得两端取得，在在因此该函数极大值只能因此该函数极大值只能02s222222)(0ssfx 时，当222229)(ssfsx时，当29922222sss时，当,s9s229s2222 时，时，因此，有：因此，有：，时，时，2222s9s229s （3）当）当k=1时，时，10),(4
28、)(1221011max11 ssfxsfsxx5s91110 x2/11max1 ,)29s(s9)s(f2222时时即即当当 x9s9x4)10(f11110 x2/111max1 2/125 2/11x *1 此时，此时，0,2 )(sf *22222xs2*2222,9s)(sf sx 200 x36x21212/11x0max1 ,)29s(s2)s(f22222时时即即当当 )x10(2x4)10(f2112/11x01max1 数数为开口向上的抛物线函为开口向上的抛物线函200362221 xx两端取得两端取得，在在因此该函数极大值只能因此该函数极大值只能2/110200)10(
29、011 fx时，时，当当200)10(1 f因此因此0*1 x2162)10(f2/11x11 时，时，当当 顺藤摸瓜，找出最优决策序列（最优策略）：顺藤摸瓜，找出最优决策序列（最优策略）：0*1 x2/9102 s0*2 x10*223*3 xssx.200310万万中中，收收益益最最大大，为为万万资资金金都都投投入入到到项项目目因因此此，当当200)10(f,2/1252001 所以所以因为因为0*1 x例例3：顺序解法求以下最短路问题：顺序解法求以下最短路问题v1v2v3v4v5v6v7v8v9v12v10v11v13545554444236877838362313状态变量状态变量sk+
30、1：第：第k阶段末所处的位置；阶段末所处的位置；决策变量决策变量uk：第：第k阶段末所做的决策；阶段末所做的决策；状态转移方程状态转移方程：sk=uk；阶段指标函数阶段指标函数d(sk+1,uk)：从第：从第k阶段末所处的位置，阶段末所处的位置，采取决策到采取决策到k阶段初的距离阶段初的距离；阶段阶段k：取：取1,2,3,4,5；过程指标函数过程指标函数：，表示从第，表示从第k阶段末所处阶段末所处的位置，采取一系列决策到起点的距离的位置，采取一系列决策到起点的距离；kiiiikusdV11,1),(最优指标函数最优指标函数fk(sk+1):表示从第表示从第k阶段末所处的位置，阶段末所处的位置，
31、采取一系列决策到起点的最短距离采取一系列决策到起点的最短距离；基本方程为：基本方程为：0)()(),()(10111minsfsfusdsfkkkkkDukkkk （1）当）当k=1时时，40),()(1221 vvdvf,322vvS 50),()(1331 vvdvf（2）k=2时，时，,76543vvvvS 642min)(),(min)(212442 vfvvdvf24*2)(vvu 75843min)(),()(),(min)(3135212552 vfvvdvfvvdvf25*2)(vvu 105746min)(),()(),(min)(3136212662 vfvvdvfvvdv
32、f26*2)(vvu 1257min)(),(min)(313772 vfvvdvf37*2)(vvu （3）当）当k=3时，时，,10984vvvS 117465min)(),()(),(min)(5258424883 vfvvdvfvvdvf548*3)(vvvu或或 121281037568min)(),()(),()(),()(),(min)(727962695259424993 vfvvdvfvvdvfvvdvfvvdvf59*3)(vvu 14124104min)(),()(),(min)(7371063610103 vfvvdvfvvdvf610*3)(vvu （4）k=4时，时
33、，,12115vvS （5）k=5时，时，136vS 17143144min)(),()(),(min)(12412131141113135 vfvvdvfvvdvf1213*5)(vvu 14141126113min)(),()(),()(),(min)(10310119391183811114 vfvvdvfvvdvfvvdvf811*4)(vvu 14143122115min)(),()(),()(),(min)(10310129391283812124 vfvvdvfvvdvfvvdvf912*4)(vvu 顺藤摸瓜，找出最优决策序列（最优策略）：顺藤摸瓜，找出最优决策序列（最优策略）
34、：1213*5)(vvu 912*4)(vvu 59*3)(vvu 25*2)(vvu 12*1)(vvu 最短路线为：最短路线为：v1 v2 v5 v9 v12 v13 最短路距离为：最短路距离为：f1(v1)=17，与逆序法结论相同。，与逆序法结论相同。例例4：用顺序法求如下投资问题：用顺序法求如下投资问题 某公司有某公司有1010万元资金投资于万元资金投资于i(ii(i=1,2,3)=1,2,3)，投资于第投资于第i i个项目投资额为个项目投资额为x xi i时，其收益分别时，其收益分别为为g g1 1(x x1 1)=4x)=4x1 1,g,g2 2(x(x2 2)=9x)=9x2 2
35、,g,g3 3(x(x3 3)=2x)=2x3 32 2，如何分，如何分配投资额，才能使总收益最大。配投资额，才能使总收益最大。该问题的静态模型为：该问题的静态模型为：2321294maxxxxZ )3,2,1(010321ixxxxi该问题的动态规划求解过程为：该问题的动态规划求解过程为：状态变量状态变量sk+1：可以用于投资到第：可以用于投资到第1到到k个项目的资金数；个项目的资金数；决策变量决策变量xk：投入到第：投入到第k个项目的资金；个项目的资金；状态转移方程状态转移方程：sk=sk+1-xk；阶段指标函数阶段指标函数gk(xk)：投入第：投入第k个项目个项目xk获得的收益获得的收益
36、；阶段阶段k：取：取1,2,3；过程指标函数过程指标函数：，表示投入项目，表示投入项目1到到k个项个项目获得的收益目获得的收益；kiiikxgV1,1)(最优指标函数最优指标函数fk(sk+1):表示可投资金为表示可投资金为sk+1时，投资时，投资第第1到到k个项目所获得的最大收益个项目所获得的最大收益；基本方程为：基本方程为：0)()()()(10101max1sfsfxgsfkkkksxkkkk （1）当）当k=1时，时，)(4)(10121max21sfxsfsx 41max21xsx 24s 2*1sx （2）当）当k=2时，时，)(9)(212032max32sfxsfsx 4922
37、0max32sxsx )(492320max32xsxsx 45320max32sxsx 39s 3*2sx （3）当）当k=3时，时，s4=10)(2)(3223043max43sfxsfsx 923230max43sxsx )(9234230max43xsxsx )10(92323100max3xxx 9092323100max3 xxx数数为开口向上的抛物线函为开口向上的抛物线函9092323 xx两端取得两端取得，在在因此该函数极大值只能因此该函数极大值只能10090)10(031 fx时，时，当当200)10(3 f因此因此10*3 x200)10(1033 fx时，时，当当 顺藤摸
38、瓜，找出最优决策序列（最优策略）：顺藤摸瓜，找出最优决策序列（最优策略）：01010*343*2 xssx000*232*1 xssx三、顺序法与逆序法的不同点三、顺序法与逆序法的不同点 两种方法本质是相同的。主要区别如下：两种方法本质是相同的。主要区别如下：o 状态转移方式不同状态转移方式不同o 指标函数的定义不同指标函数的定义不同o 基本方程形式不同基本方程形式不同逆序法：逆序法：顺序法：顺序法：逆序法：逆序法：顺序法：顺序法：),(1kkkkusTs ),(1kkkkusTs 程最优效益值。程最优效益值。出发，到终点后部子过出发，到终点后部子过阶段从状态阶段从状态表示第表示第kkksks
39、f)(程最优效益值。程最优效益值。出发，到起点前部子过出发，到起点前部子过阶段从状态阶段从状态表示第表示第11)(kkksksff1(s1)是整体是整体最优函数值最优函数值fn(sn+1)是整是整体最优函数值体最优函数值第四节第四节动态规划在经济管理中的应用动态规划在经济管理中的应用一、一、背包问题背包问题 一位旅行者携带背包去登山，已知他所能承受的背包一位旅行者携带背包去登山，已知他所能承受的背包重量限制为重量限制为a千克，现有千克，现有n种物品可供他选择装入背包，种物品可供他选择装入背包，第第i件物品的重量为件物品的重量为ai千克，其价值是携带数量千克，其价值是携带数量xi的函的函数数 。
40、问旅行者如何选择携带各种物品。问旅行者如何选择携带各种物品的件数，以使总价值最大。的件数，以使总价值最大。nixcii,2,1 )(设设xi为第为第i种物品携带的数量，该问题的整数规划模种物品携带的数量，该问题的整数规划模型如下：型如下：)(max1 niiixcZ nixxainiii,2,1 0a 1且为整数且为整数 用动态规划的顺序解法建模求解，过程如下：用动态规划的顺序解法建模求解，过程如下：阶段阶段k：将可装入物品按将可装入物品按1，2，n 排序，每种物品排序，每种物品按一个阶段，共按一个阶段，共n个阶段。个阶段。K=1，2，n。状态变量状态变量sk+1：在第在第k阶段开始时，可以装
41、入前阶段开始时，可以装入前k种物品种物品的总重量。的总重量。决策变量决策变量xk：在第在第k阶段开始时，装入第阶段开始时，装入第k种物品的件数。种物品的件数。状态转移方程状态转移方程：sk=sk+1-akxk允许决策集合允许决策集合：Dk(sk+1)=xk|0 xksk+1/ak,xk为整数为整数最优指标函数最优指标函数 fk(sk+1)：在第：在第k阶段初，可以装入前阶段初，可以装入前k种种物品的总重量为物品的总重量为sk+1时，选择最优策略装前时，选择最优策略装前k种物品的价值。种物品的价值。基本方程基本方程：0)s(f)s(f)x(c)s(f10k1kkka/s x01kkmaxk1kk
42、且为整数且为整数 例：有一辆货运量为例：有一辆货运量为10t10t的卡车，用以装载的卡车，用以装载3 3种货物，种货物，每种货物的单位重量及相应单位价值如下表所示。应如每种货物的单位重量及相应单位价值如下表所示。应如何装载可使装载总价值最大？何装载可使装载总价值最大？货物编号货物编号123单位重量（单位重量（t）345单位价值单位价值456 解：设第解：设第i i种货物装入种货物装入x xi i件，该问题可表示为：件，该问题可表示为：321654maxxxxZ 且且为为整整数数 0,10543321321xxxxxx 建立动态规划模型（顺序解法）：建立动态规划模型（顺序解法）：阶段阶段k：将可
43、装入物品按将可装入物品按1，2，3 排序，每种物品按一排序，每种物品按一个阶段，共个阶段，共3个阶段。个阶段。K=1，2，3。状态变量状态变量sk+1：在第在第k阶段开始时，可以装入前阶段开始时，可以装入前k种物品种物品的总重量。的总重量。决策变量决策变量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阶段初，可以装入前阶段初，可以装
44、入前k种种物品的总重量为物品的总重量为sk+1时，选择最优策略装前时，选择最优策略装前k种物品的价值。种物品的价值。基本方程基本方程：0)()()()(101/01max1sfsfxcsfkkkkasxkkkkk且为整数且为整数（1）当）当K=1时时3/404)(213/021max21sxsfsx 且为整数且为整数s2012345678910f1(s2)0 x1*000004141418282821231233/2*1sx （2）当）当K=2时时)4(5)(23124/032max32xsfxsfsx 且为整数且为整数s3012345678910f2(s3)x2*x25x2+f1(s2)00
45、000 1 01010 1 0 1 220 12010000000004404 551455185808 9918 9 1010212 9 1012012 1310131（3）当）当K=3时时，s4=100*3 x21:*1*2 xx，逆推，得逆推，得.13最最大大价价值值为为s410f3(s4)x3*x36x2+f2(s3)012)5(6)(34235/043max43xsfxsfsx 且为整数且为整数131112130二、生产与存贮问题二、生产与存贮问题 例：例：某工厂生产并销售某种产品，已知今后四个月市某工厂生产并销售某种产品，已知今后四个月市场需求预测如下表，又每月生产场需求预测如下表
46、，又每月生产j j单位产品费用为：单位产品费用为：千元千元 ,6)1,2,(j j30)(j 0)(jC 每月库存每月库存j j单位产品的费用为单位产品的费用为E(jE(j)=0.5j)=0.5j（千元），该（千元），该厂最大库存量为厂最大库存量为3 3单位，每月最大生产能力为单位，每月最大生产能力为6 6单位，计划单位，计划开始和计划期末库存量都是零。试制定四个月的生产计划，开始和计划期末库存量都是零。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第在满足用户需求条件下总费用最小。假设第i+1i+1个月的库存个月的库存量是第量是第i i个月可销售量与该月用户需求量之差；而第个月
47、可销售量与该月用户需求量之差；而第i i个月个月的可销售量是本月初库存量与产量之和。的可销售量是本月初库存量与产量之和。解：用动态规划的解：用动态规划的逆序解法逆序解法建模求解，过程如下：建模求解，过程如下：阶段阶段k：每个月为一个阶段，共每个月为一个阶段，共4个阶段。个阶段。k=1，2，3，4。状态变量状态变量sk：第第k阶段（月）初的库存量。阶段（月）初的库存量。决策变量决策变量uk：第第k阶段的生产量。阶段的生产量。状态转移方程状态转移方程：sk+1=sk+uk-gk最优指标函数最优指标函数 fk(sk)：在第：在第k月初库存量为月初库存量为sk时，选择最优时，选择最优策略生产，从本月到
48、第策略生产，从本月到第4个月末的最低生产、库存费用之和。个月末的最低生产、库存费用之和。i（月）1234gi（需求）2324 （1）当）当k=4时，时，)()4()()()()(445544444max44sEsCsfsEuCsfsu 首先确定首先确定s4的允许集合。的允许集合。考虑到最大库存量考虑到最大库存量3：s43。考虑到最大生产能力考虑到最大生产能力6：s43*6-（2+3+2）。）。考虑到期末库存量为考虑到期末库存量为0：s44。综上，有：综上，有：s43，即，即s4 可以取可以取0，1，2，3。s40f4(s4)u4*u4C4+E412343217+0746+0.56.535+16
49、24+1.55.53 （2）当）当k=3时，时，)()()()(443333max33sfsEuCsfDu 首先确定首先确定s3的允许集合。的允许集合。考虑到最大库存量考虑到最大库存量3：s33。考虑到最大生产能力考虑到最大生产能力6：s32*6-（2+3）。考虑到期末库存量为考虑到期末库存量为0：s32+4。综上，有：综上，有：s33，即，即s3 可以取可以取0，1，2，3。然后确定然后确定u3允许集合。允许集合。考虑到最大库存量考虑到最大库存量3：s3+u3g33，即，即u33+2-s3。考虑到最大生产能力考虑到最大生产能力6：u36。考虑到期末库存量为考虑到期末库存量为0：s3+u3-g
50、34，即，即u34+2-s3 考虑到本月需求量考虑到本月需求量g3为为2：s3+u32，即，即u3 2-s3 综上，有：综上，有：max0，2-s3 u35-s3s30f3(s3)u3*u3C3+E3+f412323451234 012301212705)220(5.00)23(4 f12 12.55.125.606)230(5.00)33(4 f13 13.512211.55.1175.04)211(5.01)13(4 f12 12.5 1311.518 11.5 1212.5808 11.5 1280 （3）当）当k=2时，时，)()()()(332222max22sfsEuCsfDu 首
