《运筹学(六)剖析.》由会员分享，可在线阅读，更多相关《运筹学(六)剖析.（94页珍藏版）》请在金锄头文库上搜索。
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 = sk+1-akxk,允许决策集合 ： Dk (sk+1)= xk|0xksk+1/ak,
