运筹学7动态规划.ppt

1、主要内容: 7.1 多阶段决策过程的最优化 7.2 动态规划的基本概念和基本原理 7.3 动态规划模型的建立与求解 7.4 动态规划应用举例,教学要求： 1掌握动态规划的基本概念：阶段、状态、决策、策略、状态转移方程、指标函数和最优值函数、最优策略、最优轨线 2了解动态规划的基本理论：最优性定理和最优性原理 3掌握动态规划基本思想和基本方程 4牢固掌握动态规划的顺序解法和逆序解法。会处理动态与静态规划的关系 5了解和掌握若干典型问题的动态规划模型及求解技巧：如最短路线、资源分配、生产计划、货物存储、设备更新与系统可靠性问题、背包问题、推销商问题等 6了解多维动态规划降维方法和减少离散状态点数方

2、法 7了解随机性问题的动态规划求解方法,重点：动态规划顺序解法和逆序解法；若干典型问题动态规划模型及求解技巧； 难点：建立动态规划数学模型的状态转移方程。,7.1 多阶段决策过程的最优化,动态规划（Dynamic Programming）是运筹学的一个重要分支，它是解决多阶段决策过程最优化的一种方法。美国数学家贝尔曼（R. E. Bellman）等人在50年代初提出了解决多阶段决策问题的“最优性原理”（Principle of Optimality）。1957年贝尔曼出版了专著“动态规划”，该书是动态规划的第一本著作。目前动态规划已经用于解决最优路径问题、资源分配问题、生产调度问题、设备更新问

3、题、复合系统可靠性问题及生产过程最优控制等，并且取得了显著的效果。,回本章目录,动态规划是求解问题的一种方法，而不是算法（线性规划是一种算法），因而没有标准的数学表达式，对于具体问题需要具体分析。,一、多阶段决策问题 在生产经营活动中，某些问题决策过程可以划分为若干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。由于各个阶段不是孤立的，而是有机联系的，也就是说，本阶段的决策将影响过程下一阶段的发展，从而影响整个过程效果，所以决策者在进行决策时不能够仅考虑选择的决策方案使本阶段最优，还应该考虑本阶段决策对最终目标产生的影响，从而做出对全局来讲是最优的决策。当每个阶段的决策确定以后，

4、全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题。,多阶段决策问题中，各个阶段一般是按照时间来划分的，随着时间的发展而产生各个阶段的决策，从而形成决策序列，这就是动态的含义。在一些与时间无关的静态问题中（如非线性规划等），可以人为地赋予时间的概念，使其成为一个多阶段决策问题，再用动态规划方法处理。,1,2,n,状态,决策,状态,决策,状态,状态,决策,二、多阶段决策问题举例,属于多阶段决策类的问题很多，例如：,例 1 工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求

5、情况决定生产计划安排。,例 2 设备更新问题：一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。,例 3 连续生产过程的控制问题：一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。,以上所举问题的

6、发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段,的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。,例 4 资源分配问题：便属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，

7、但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。,例 5 运输网络问题：如图7-1所示的运输网络，点间连线上的数字表示两地距离(也可是运费、时间等)，要求从fk(sk)至v10的最短路线。 这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。,图7-1 运输网络图示,（10）,（14）,（16）,（15）,（17）,（22）,（22）,（21）,（27）,特别注意： 动态规划求解的多阶段决策问题的特点： 适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效

8、性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。,7.2 动态规划的基本概念和基本原理,引言,为了说明动态规划的基本思想方法和特点，以下面的例题来讨论求最短路问题的方法。,回本章目录,第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从A到G的路程可以分为6个阶段。第一段的走法有2种，第二、三、四、五、六段的走法各6、8、6、6、2，因此共有2322248条可能的路线，分别算出各条路线的距离，最后进行比较求优。,

9、A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,最优路径长度18,第二种方法即所谓“局部最优路径”法，是说某人从k阶段出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是下图所示，全程长度是25；显然，这种方法的结果常是错误的,第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为6个阶段，每次的选择总是综合后继过程的一并最优进

10、行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。,一、动态规划的基本概念,运用动态规划求解多阶段决策问题，首先要将该问题写成动态规划模型，再进行求解，动态规划模型中用到的概念及符号如下：,例6 最短路问题 如图7-2所示，要从A地到E地铺设管线，中间需要经过三个中间站，两点之间的连线上的数字表示距离，问应该选择什么路线，使总距离最短？,1.阶段（stage）,根据所需解决问题的特点，按照时间或空间顺序把整个过程划分为若干相互联系的阶段，以便按照一定次序求解。描述阶段的变量称为阶段变量，通常用字母k表示阶段变量。例如例6中，从A到E可以划分为四个阶段，第一阶

11、段k=1，从A到B（B有三种选择，B1，B2，B3）；第二阶段k=2，从B到C（C有四种选择，C1，C2，C3，C4）；第三阶段k=3，从C到D（D有两种选择，D1，D2）；第四阶段k=4，从D到E。 例6可以分为四个阶段来求解，k=1，2，3，4。,第一阶段,第二阶段,第三阶段,第四阶段,2.状态（state）,状态表示各阶段开始所处的自然状况或客观条件，它既是某阶段过程演变的起点，又是前一阶段某种决策的结果。描述状态的变量称为状态变量，常用sk表示第k阶段的状态变量。状态变量sk的取值集合称为状态集合，第k阶段的状态集合记为Sk ，例如例6中，第一阶段状态为A，第二阶段有三个状态：B1，B

12、2，B3；第三阶段有四个状态：C1，C2，C3，C4；第四阶段有两个状态：D1，D2；各阶段状态集合分别为：,S1=A S2=B1，B2，B3 S3=C1，C2，C3，C4 S4=D1，D2,第一阶段,第二阶段,第三阶段,第四阶段,S1=A,S2=B1,B2,S3=C1, C2, C3,.,n个阶段的决策过程有n+1个状态变量,这里状态的选取应当满足无后效性：系统从某个阶段往后的发展演变，完全由系统本阶段所处的状态及决策所决定，与系统以前的状态及决策无关。也就是说，过去的历史只能通过当前的状态去影响未来的发展，当前的状态是过去历史的一个完整总结。只有具有无后效性的多阶段决策过程才适合于用动态规

13、划方法求解。 例6中，当某个阶段已经选定某个点时，这个点以后的管线铺设只与该点有关，而与该点以前的管线铺设无关，所以满足无后效性。,3.决策（decision）,当各阶段的状态选定以后，可以做出不同的决定（或选择）从而确定下一个阶段的状态，这种决定（或选择）称为决策。表述决策的变量称为决策变量，常用uk（sk）表示第k阶段当状态为sk时的决策变量。实际问题中，决策变量的取值往往限制在某一范围内，此范围称为允许决策集合，常用Dk（sk）表示第k阶段从状态sk出发的允许决策集合，显然uk（sk）Dk（sk）。 例如例6中，第二阶段若从B2出发，可以选择C1，C2，C3，C4，即允许决策集合为： D

14、2（B2）=C1，C2，C3，C4 当决定选择C3时，可以表示为： u2（B2）=C3,第一阶段,S1=A,u1(A)= B1 或 u1(A)= B2 , D1(A)=B1, B2,4.策略（policy）,当各个阶段的决策确定以后，各阶段的决策形成一个决策序列，称此决策序列为一个策略。使系统达到最优效果的策略称为最优策略。在n阶段决策过程中，从第k阶段到终止状态的过程，称为k后部子过程（或称为k子过程），k后部子过程相应的决策序列称为k后部子过程策略，简称子策略，记为p k，n（sk），即： P k，n（sk）=uk（sk），uk+1（sk+1），un（sn） 当k=1时，即由第一阶段某个状

15、态出发做出的决策序列称为全过程策略，简称策略，记为p1，n（s1），即： p1，n（s1）=u1（s1），u2（s2），un（sn）,P1,5(A)=A, B1, C2 , D2 , E,P1,5(A)=A, B2, C3 , D3 , E,P2,5(A)=B2, C2 , D1 , E,5.状态转移方程（state transfer equation）,动态规划中，本阶段的状态往往是上一个阶段状态和上一个阶段决策作用的结果。设第k阶段状态为sk，做出的决策为uk（sk），则第k+1阶段的状态sk+1随之确定，他们之间的关系可以表示为： sk+1=Tk（sk，uk） 这种表示从第k阶段到第k+

16、1阶段状态转移规律的方程称为状态转移方程，它反映了系统状态转移的递推规律。例如例6中，上一阶段的决策就是下一阶段的状态，所以状态转移方程为： sk+1= uk（sk） 状态转移方程是建立动态规划数学模型的难点之一。,一旦某阶段的状态和决策为已知，下阶段的状态便完全确定无后效性。,6.指标函数和最优指标函数,衡量所选策略优劣的数量指标称为指标函数。它定义在全过程和所有后部子过程，常用Vk，n表示，即： Vk，n=Vk，n（sk，uk，sk+1，sn+1） 当k=1时，V1，n表示初始状态为s1，采用策略p1，n时的指标函数值。 V1，n=V1，n（s1，u1，s2，sn+1） 动态规划数学模型的

17、指标函数应该具有可分离性，并满足递推关系，即： Vk，n（sk，uk，sk+1，sn+1）=ksk，uk，Vk+1，n（sk+1，sn+1） 在阶段k状态为sk，决策为uk（sk）时得到的反映第k阶段的数量指标vk（sk，uk）称为k阶段的指标函数。,常见的指标函数形式有两种：,（1）任一后部子过程的指标函数是它所包含的各阶段指标的和，即： Vk,n（sk，uk，sn+1）= 写成递推关系： Vk,n（sk，uk，sn+1）= vk（sk，uk）+ Vk+1,n（sk+1，uk+1，sn+1）,（2）任一后部子过程的指标函数是它所包含的各阶段指标的积，即： Vk,n（sk，uk，sn+1）=

18、写成递推关系： Vk,n（sk，uk，sn+1）= vk（sk，uk）Vk+1,n（sk+1，uk+1，sn+1）,指标函数的最优值记为fk（sk），它表示从第k阶段状态sk出发，采取最优策略p*k，n（sk）到第n阶段的终止状态时的最佳指标函数值，即： opt 是英文optimization（优化）的缩写，根据问题的性质取max或min。,当k=1时，f1（s1）就是从初始状态s1出发到终止状态的最优函数。在不同的问题中，指标函数可以是利润、成本、距离、产品质量或资源消耗等。在最短路线问题中，第k阶段的指标函数vk（sk，uk）通常也用dk（sk，uk）表示。 例如例6中，d2（B2，C3）

19、表示第二阶段中由点B2到点C3的距离，fk（sk）表示从第k阶段点sk到终点E的最短距离，f1（A）就是所求从A到E的最短距离。,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,则不论前面A如何到达B，B又如何到达C2，对于C2来说：,二、最优化原理,一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略，即一个最优策略的子策略也是最优的。,A,B1,B2,C1,

20、C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,k=4,3,2,1,k=5，出发点E1、E2、E3,k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3,u5(E2)=F2,u6(F2)=G,最优策略 路长18,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3

21、,动态规划方法明显优于穷举法 （计算次数及结果数量）,1、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。,结论：,2、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是

22、从全局来考虑的，与该段的最优选择答案一般是不同的。,3、在求整个问题的最优策略时，由于边界（初始或结果）状态是已知的，而每段的决策都是该段状态的函数，故最优策略便可通过逆序（或顺序）递推逐段变换得到，从而确定最优路线。（请看下例）,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,例：请用顺序法求解下列最短路问题,两种方式在本质上没有什么不同： 通常情况下，当初始状态给定时用逆序解法较方便。 当终止状态给定时用顺序解法较方便。 但若初

23、始状态虽已给定，然而终点状态较多（需比较到达不同终点状态的各个路径） 及指标函数值以选取总效益最佳的终点状态时,以使用顺序解法比较方便。 两种方法的差异（状态转换方式，指标函数、递推方式等）在做题中体会。,顺序解法与逆序解法的异同,三、动态规划的基本思想与基本原理,下面求解例6,k=4时，状态变量s4可取两种状态D1，D2，他们到终点E的最短路长为： f4（D1）= d4（D1，E）=3 u4（D1）=E f4（D2）= d4（D2，E）=5u4（D2）=E,k=3时，状态变量s3可取四种状态C1，C2，C3，C4，当s3= C1时，到达点可以有两种选择：D1或D2，则： u3（C1）=D1

24、说明C1点至终点E的最短距离是5，最短路线为：C1D1E。,同理，从C2，C3，C4出发，有： u3（C2）=D2 u3（C3）=D1 f3（C4）= d3（C4，D2）+ f4（D2）=7+5=12u3（C4）=D2,k=2时，类似地有： u2（B1）=C1 u2（B2）=C3 u2（B3）=C3,k=1时，有： u1（A）=B3 于是得到从A点到E点的最短距离为10，按计算顺序反向追踪，得到最优决策序列uk，即，u1（A）=B3，u2（B3）=C3，u3（C3）=D1，u4（D1）=E；最优路线为： AB3C3D1E,从上面计算过程可以看出，在各阶段求解中，都用到了第k阶段和第k+1阶段的

25、递推关系： 这种递推关系称为动态规划的基本方程。其中（7.1b）式称为边界条件，（7.1b）也可以写作，f4（s4）= d4（s4，E）,上述计算最短路线的过程也可以直接在图上直观表示出来，如图7-3，节点上方方格内数字表示该点到E点的最短距离。各点到E点之间的连线表示最短路线，这种直接在图上求解的方法称为标号法，这种方法的最大优点是不仅可以得到从点A到点E的最短路，而且得到了中间任意一点到E点的最短路，即得到了一族最优解，这对于许多实际问题来讲是很有意义的。,图7-3,如果规定从A点到E点为顺行方向，则由E点到A点为逆行方向，图7-3是由E点开始，由后向前标号，这种以A为始端，E为终端，从E

26、到A的解法称为逆序解法。 标号也可以由A点开始，从前向后标号，如图7-4，这种以E为始端，A为终端，从A到E的解法称为顺序解法。方格内数字表示该点到A点的最短距离。连接A点和该点的折线表示该点到起点A的最短路线。,图7-4,动态规划的基本思想概括归结如下： 1. 将多阶段决策问题按照空间或时间顺序划分成相互联系的阶段，即把一个大问题分解成一族同类型的子问题，选取恰当的状态变量和决策变量，写出状态转移方程，定义最优指标函数，写出递推关系式和边界条件。 2. 从边界条件开始，由后向前逐段递推寻找最优，在每一个阶段的计算中都要用到前一阶段的最优结果，依次进行，求得最后一个子问题的最优解就是整个问题的

27、最优解。 3. 在多阶段决策过程中，确定阶段k的最优决策时，不是只考虑本阶段最优，而是要考虑本阶段及其所有后部子过程的整体最优，也就是说，它是把当前效益和未来效益结合起来考虑的一种方法。,R. Bellman等人在深入研究多阶段决策问题的基础上，提出了著名的最优性原理：“作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。”也就是说，一个最优策略的子策略也是最优的。这一原理是动态规划方法的核心，根据最优原理可以将一个多阶段决策过程化为若干个单阶段决策过程，当然这种转化要满足两个基本条件，这就是前文所述的指标函数的可

28、分离性和状态变量的无后效性。,一、动态规划问题的解法 二、动态规划的数学模型,7.3 动态规划模型的建立与求解,回本章目录,一、动态规划问题的解法,解法,离散型,连续型,：分段穷举法（最短路问题的求解）（可以借助表格法来求解P218）,：利用解析方法、线性规划方法、 非线性规划方法、其他数值计算方法 计算机上用的连续型的离散化解法。,没有固定的方法；具体模型具体分析。（下面例子的建模型与解法一起讲）,要求：经验,、技巧、灵活,难！,总的来讲有两类方式：顺序法与逆序法,二、动态规划的数学模型,1、理论依据-最优化原理,最优化原理：一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对

29、于先前决策所形成的状态而言，其以后的所有决策必构成最优策略。,2、动态规划模型的几个要素：,1)阶段数k,2)状态变量sk Sk,3)决策变量uk( sk) Uk,4)指标函数Vk,n,状态转移方程,5)最优值函数fk(sk),6）动态规划的基本方程 动态规划的基本方程是建立动态规划模型的关键。设第k阶段处于状态sk，决策是uk(sk)，状态转移方程为sk+1=Tk（sk，uk），k阶段和k+1阶段的递推关系式可以写为：,式(7.2a)中运算符号*表示加“”或乘“”。当运算符号取加法时，边界条件fn+1（sn+1）=0，当运算符号取乘法时，边界条件fn+1（sn+1）=1。求解时，根据边界条件

30、从k=n开始，由后向前逆推，逐步求得各段最优决策和相应的最优值，最后求得f1（s1），得到整个问题的最优解。这种由后向前计算最优解的方法称为逆序解法（backward induction method），相应的基本方程称为逆序解法基本方程。,3、建立动态规划模型的步骤,（1）划分阶段： 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 （2）正确选择状态变量 sk, 满足: 可知性: 正确描述动态过程演变, 可直接或间接确定状态变量的值; 无后效性: 后面的决策与前面

31、的决策无关;,（3）确定决策变量uk及允许决策集合Dk（sk） 通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。 （4）确定状态转移方程 根据k阶段状态变量sk和决策变量uk（sk）写出k+1阶段状态变量sk+1，即sk+1=Tk（sk，uk），状态转移方程应当具有递推关系。 （5）确定阶段指标函数和最优指标函数，建立动态规划基本方程,阶段指标函数vk（sk，uk）是指第k阶段的收益，最优指标函数fk（sk）是指从第k阶段状态sk出发到第n阶段末所获得收益的最优值，最后写出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型

32、与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。,学习方法建议： 第一步 先看问题，充分理解问题的条件、情况及求解目标。 第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素，一个方程”这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。,第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。 第四步 把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。 第五步 对照自己的求解，分析成败。,1.

33、动态规划的四大要素 状态变量及其可能集合 sk Sk 决策变量及其允许集合 uk Uk 状态转移方程 sk+1= Tk (sk ,uk ) 阶段效应 rk ( sk , uk ) 2. 动态规划基本方程 fn+1(sn+1) = 0 or 1 (边界条件) fk(sk) = opt udk ( sk , uk ) + fk+1(sk+1) k = n,1,例7 有某种机床，可以在高低两种不同的负荷下进行生产，在高负荷下生产时，产品的年产量为 g ，与年初投入生产的机床数量 u1 的关系为 g=g(u1)=8u1 ，这时，年终机床完好台数将为，au1 ( a为机床完好率， 0 a 1 ，设 a=

34、0.7 )。在低负荷下生产时，产品的年产量为 h ，和投入生产的机床数量的关系为 h=h(u2)=5u2 ，相应的机床完好率为 b ( 0b2 ，设 b= 0.9 )，一般情况下 ( a b )。,假设某厂开始有 x1=1000 台完好的机床，现要制定一个五年生产计划，问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为最高。,解：首先构造这个问题的动态规划模型。,1分阶段：设阶段变量 k 表示年度，因此，阶段总数 n = 5 。,2. 状态变量：用 sk 表示第 k 年度初拥有的完好机床台数，同时也是第 k-1 年度末时的完好机床数量。,3. 决策变量：

35、用 uk 表示第 k 年度中分配于高负荷下生产的机床台数。于是 sk-uk 便为该年度中分配于低负荷下生产的机床台数。,4状态转移方程为：,决策变量的取值：在第 k 段为,6条件最优目标函数递推方程,令 fk(sk ) 表示由第 k 年的状态 sk 出发，采取最优分配方案到第5年度结束这段时间的产品产量，根据最优化原理有以下递推关系:,下面采用逆序递推计算法,从第5年度开始递推计算,K=5 时有,显然，当 u5*=s5 时，f5(s5) 有最大值，相应的有 f5(s5) = 8s5 。,K=4 时有：,因此，当 u4*= s4 时，有最大值 f4(s4)=13.6s4,K=3 时有：,可见，当

36、 u3*= s3 时，有最大值 f3(s3) =17.55s3 。,K=2 时有：,此时，当 u2*= 0 时有最大值，即 f2(s2)=20.8s2,其中 s2=0.7u1+0.9(s1-u1),K=1 时有：,当 u1*= 0 时, 有最大值，即 f1(s1)=23.7s1 , 因为 s1=1000 , 故 f1(s1)=23700 个产品。,按照上述计算顺序寻踪得到下述计算结果：,上面所讨论的最优决策过程是所谓始端状态固定，终端状态自由如果终端也附加上一定的约束条件，那么计算结果将会与之有所差别例如，若规定在第五个年度结束时，完好的机床数量为500台(上面只有278台)，问应该如何安排五

37、年的生产，使之在满足这一终端要求的情况下产量最高？,解：由状态转移方程,有,由此式得,当 k=5 时有,当 k=4 时有,显然，只有取 u4*=0 , 有最大值 f4(s4)=21.4s4-7500,当 k=3 时有:,显然，只有取 u3*=0 , f3(s3) 有最大值 f3(s3)=24.5s3-7500 。,当 k=2 时有:,显然，只有取 u2*=0 , f2(s2) 有最大值 f2(s2)=27.1s2-7500 。,当 k=1 时有:,显然，只有取 u1*=0 , f1(s1) 有最大值 f1(s1)=29.4s1-7500 。,例8 某公司拥有资金 10 万元，若投资于项目 i

38、(i1，2，3) 的投资额为 xi 时，其收益分别为 g1(x1)=4x1 , g2(x2)=9x2 , g3(x3)=2x32 ,问应如何分配投资数额才能使总收益最大?,这是一个与时间无明显关系的静态最优化问题，可列出其静态模型为：,求 x1 , x2 , x3 的值使,满足,我们可以人为地赋予它“时段”的概念，用动态规划方法求解,解：（解法1）首先用逆序构造动态规划模型。,1分阶段：设阶段变量 k 表示依次对第 k 个项目投资，因此，阶段总数 n = 3。 ( k = 1 , 2 , 3 ),2. 状态变量：用 sk 表示已经对第 1 至 第 k-1 个项目投资后的剩余资金；即第 k 段初

39、拥有的可以分配给第 k 到第3个项目的资金额 （单位：万元） 。,3. 决策变量：用 xk 表示对第 k 个项目投资 的资金数量（单位：万元）。,决策变量的取值： 0 xk sk,4状态转移方程为：,6. 基本方程为：,最优指标函数 fk(sk) 表示第 k 阶段，初始状态为 sk 时，从第 k 到第 3 个项目所获最大收益,当 k=3 时：,当 k=2 时：,极大值只可能在 0 ，s2 端点取得，,当 k=1 时：,矛盾，所以舍去 sk 9/2,故 极大值只能在 0，10 的端点取得，比较0，10两个端点的函数值,即全部资金投于第3个项目,(解法2) 用顺序解法,1. 阶段划分: （同上）

40、和决策变量,2. 状态变量: 用 sk 表示可用于第1到第 k-1个项目投资的金额，即对第 k 个项目到第3个项目投资后的剩余资金数量。,3. 决策变量: （同上）,4. 状态转移方程:,5. 决策变量的取值范围：,6. 最优指标函数：,令 fk(sk+1) 表示第 k 段投资额 sk+1 为时，第1到第 k 项目所获的最大收益，此时顺序解法的基本方程为：,当 k=1 时，有,当 k=2 时，有,当 k3 时，有, x3 = 9/4 为极小点。,极大值应在0，s4 0，10 端点取得,再由状态转移方程逆推：,动态规划的优点,可以解决线性, 非线性, 整数规划无法有效求解的复杂问题; 容易找到全

41、局最优解; 可以得到一组解;,动态规划的缺点,没有标准的模型可供应用, 构模依赖于个人的经验和技巧; 状态变量需满足无后效性, 有较大的局限性; 动态规划的维数灾难限制了对规模较大问题的求解效率;,7.4 动态规划应用举例,1. 资源配置问题 2. 生产与库存问题 3. 复合系统工作可靠性问题 4. 二维背包问题 5. 设备更新问题 6. 货郎担问题,回本章目录,1. 资源配置问题,如何将有限的资源分配给若干种生产活动，并使资源利用的收益最大是经济活动中常见的问题，动态规划可以求解一些线性规划无法解决的资源配置问题。,一般的资源分配问题可以描述为如下的规划问题： max: z = g1(x1)

42、 + g2(x2) + . . . + gn(xn) x1 + x2 + . . . + xn = a xi 0 i = 1, . . ., n,例: 某工厂有4台设备要投到三种生产线上，投到不同生产线的预期收入的函数关系如下： g1(x1) = 7x1+2 (x10); g1(x1) = 0 (x1= 0) g2(x2) = 3x2+7 (x20); g2(x2) = 0 (x2= 0) g3(x3) = 4x3+5 (x30); g3(x3) = 0 (x3= 0) 设备如何分配可使工厂的收益最大？,分析： 1.阶段与生产线相联系, 阶段 k 只考虑分配到生产线 k 的设备台数; 2.状态

43、变量 sk 表示 k 生产线可分配的设备数; 3.决策变量 xk 表示决定在 k 生产线上使用的设备数; 4.状态转移方程: sk+1 = sk - xk; 5.损益函数: fk(sk)=max gk(xk)+fk+1(sk+1),s3 f3(s3) x3* 0 f3(0) = maxx3=0 0 = 0 0 1 f3(1) = maxx31 4x3+5 = 9 1 2 f3(2) = maxx32 4x3+5 = 13 2 3 f3(3) = maxx33 4x3+5 = 17 3 4 f3(4) = maxx34 4x3+5 = 21 4,求解： k = 3: g3(x3) = 4x3 +

44、 5,k = 2: g2(x2) = 3x2 + 7 s3 = s2 - x2,k = 1:g1(x1) = 7x1 + 2 s2 = s1 - x1,因此得到：x1 = 2 , x2 = 1 , x3 = 1,离散的时间段内如何安排生产与库存。 生产成本为: C(xt) = k + cxt (xt 0) 或 C(xt) = 0 (xt = 0), k为开工所需费用, c 是变动成本, xt为 t 期的生产数量; 库存成本为：H(yt) = hyt, h为单位库存成本，yt为 t 期期初库存数量。,2. 生产与库存问题,例: 假定k = 250, c = 2, h = 1, y1 = 0, T

45、 = 5, 需求数据如下表, 如何安排生产才能使总成本最小?,t 1 2 3 4 5 需求(dt)280220360140270,分析: 阶段可按周期 t 划分, t = 1, 2, 3, 4, 5 每周期期初的库存量为该阶段的状态, 状态变量 st 表示 t 周期期初库存； 决策变量 xt 表示 t 期的生产数量; 状态转移方程为: st+1 = st + xt - dt,递推函数: ft(st) = min Ct(xt) + Ht(st) + ft+1(st+1) 以库存表示系统状态会大大增加系统状态数量, 然而, 上述问题的最优决策必须使每一阶段库存或者为零, 或者为后续一或几个周期需求

46、之和。,t= 5: f5(0) = k+cx5+hs5 = 250+2270+10 = 790 (x5= 270) f5(270) = k+cx5+hs5 = 0+20+1270 = 270 (x5= 0) t = 4: f4( 0 ) = min 250+2140+ f5(0), 250+2410+ f5(270)= min 1320*, 1340 = 1320 (x4= 140) f4(140) = 1140+ f5(0) = 140 + 790 = 930 (x4= 0) f4(410) = 1410+ f5(270) = 410 + 270 = 680 (x4= 0),t = 3: f

47、3(0) = min250+2360+f4(0), 250+2500 + f4(140), 250+2770+ f4(410) = min 2290, 2180*, 2470 = 2180 (x3= 500) f3(360)=1360+f4(0)=360+1320=1680 (x3=0) f3(500)=1500+f4(140)=500+930=1430 (x3= 0) f3(770)=1770+f4(410) = 770+680 = 1450 (x3= 0),t = 2: f2(0)=min250+2220+f3(0),250+2580+f3(360), 250+2720+f3(500),

48、250+2990+ f3(770) = min2870*,3090,3120,3680=2870(x2=220) f2(220)=1220+f3(0) = 220+2180 = 2400 (x2= 0) f2(580)=1580+f3(360)=580+1680=2260 (x2= 0) f3(720)=1720+f3(500)=720+1430=2150 (x2= 0),t = 1: f1(0)=min250+2280+f2(0),250+2500+f2(220),250+2860+ f2(580), 250+21000+ f2(720) =min3800,3650*,4290,4400=3

49、650 (x1= 500) 最优解为： x1= 500, x2= 0, x3= 500, x4= 0, x5= 270 简单判断方法：只要固定费用大于后面发生的库存费用，就值得一次生产满足一或几个周期的需求。,3. 复合系统的工作可靠性问题 例: 为保证设备可靠运行, 一些关键部件往往由多个器件并联运行, 如果器件 i 的失效概率为 pi, 则 xi 个器件并联工作的可靠性为(1 - pixi), 假定每个器件的采购费用为 ci, 在满足总采购费用不超过预算限制 C 的前提下, 使设备可靠性最高的规划问题可以描述为:,该问题为整数非线性规划，可以用动态规划求解，设关键器件数n = 3，总费用为

50、120万元。器件的单价与可靠性如下表：,分析： 阶段与器件挂钩，第 i 阶段仅考虑器件 i 的采购数量; si 表示 i 阶段可使用的采购费用; xi 表示 i 阶段决定购买 i 器件的数量； 状态转移方程: si+1 = si - ci xi； 递推损益函数: fi(si) = max ( 1 - pixi ) fi+1(si+1)。,i = 1 f1(120) = max1x130.9f2(90), 0.99f2(60), 0.999f2(30) = max0.90.84*, 0.990.4, 0.9990 = 0.756 i = 2 f2(90) = max0.8f3(75) , 0.9

51、6f3(60) , 0.992f3(45) , 0.9984f3(30) = max0.80.875 , 0.960.875* , 0.9920.75 , 0.99840.5 = 0.84,f2(60) = max 0.8f3(45), 0.96f3(30) = max 0.80.75*, 0.960.5 = 0.6 f2(30) = max 0.8f3(15), 0f3(30) = 0 f3(75) = 0.875, f3(60) = 0.875, f3(45) = 0.75, f3(30) = 0.5, 因此, 最优解为: x1 = 1, x2 = 2, x3 = 3,4 背包问题,（1）

52、一维背包问题 有人携带背包上山，其可携带物品的重量限度为a公斤，现有n种物品可供选择，设第i种物品的单件重量为ai公斤，其在上山过程中的价值是携带数量xi的函数ci（xi），问应如何安排携带各种物品的数量，使总价值最大。这就是背包问题，类似的货物装载问题，下料问题都等同于背包问题。,背包问题的数学模型为：,下面用动态规划方法求解： 按照装入物品的种类划分阶段，k=1，2，n； 状态变量sk表示装入第k种至第n种物品的总重量； 决策变量xk表示装入第k种物品的件数； 状态转移方程为： sk+1=skakxk,允许决策集合为： 其中 表示不超过 的最大整数；,阶段指标函数ck（xk）表示第k阶段装

53、入第k种商品xk件时的价值； 最优指标函数fk（sk）表示第k阶段装入物品总重量为sk时的最大价值，动态规划基本方程为：,（2）二维背包问题,当背包问题中有两个限制条件时(如重量和体积限制), 所形成的问题为 二维背包问题, 问题的一般形式为: max z = i ci xi s.t.i ai xi b xi 0 且为整数,例: 卡车的最大运货重量为 12 吨, 容积为 10 立方米, 现有A , B 两种货物, 重量分别为 3 吨和 4 吨, 体积分别为 1 和 5 立方米, 运费分别为 2 和 3 元, 如何装载使所得运费最大。 由资源条件可知最多可装载 4 件 A 或 2 件 B。,分析

54、: 阶段可按货物种类划分, k = 1, 2 每阶段剩余的载货能力(重量与容积)为该阶段的状态, 状态变量 sk = (s1k, s2k); 决策变量 xk 表示 k 阶段资源的占用量; 状态转移方程: sk+1= sk-akxk , ak=(a1k, a2k) 损益函数为: fk(sk)=maxckxk+fk+1(sk+1),k = 2 f2(12, 10) = maxx2=0,1,2f1(12,10), 3+ f1(8, 5), 6+f2(4, 0) = max 8, 3+4, 6+0 = 8 k = 1 f1(12,10) = maxx14 2x1 = 8 f1( 8, 5) = maxx12 2x1 = 4 f1( 4, 0) = 0,动态规划的维数增加时, 求解的复杂程度也会增加。如果状态变量的维数为 m, 离散的决策变量有 n 个取值, 则在每个阶段需要存储 nm 个数据, 这就是所谓的维数灾难。,5 设备更新问题,设备在使用全过程中会遭受磨损, 使用一段时间后就要维修, 而且使用的时间越长, 维修费用越高, 设备使用多少时间在经济上最合算, 就是设备更新问题。,分析： 阶段 k = 1, 2, 3, 4, 5; sk 表示 k 年初设备已使用