运筹学7动态规划.pptx

《运筹学7动态规划.pptx》由会员分享，可在线阅读，更多相关《运筹学7动态规划.pptx（161页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、态转移方程。第2页/共161页7.1 7.1 多阶段决策过程的最优化 动态规划（Dynamic Programming）是运筹学的一个重要分支，它是解决多阶段决策过程最优化的一种方法。美国数学家贝尔曼（R.E.Bellman）等人在50年代初提出了解决多阶段决策问题的“最优性原理”（Principle of Optimality）。1957年贝尔曼出版了专著“动态规划”，该书是动态规划的第一本著作。目前动态规划已经用于解决最优路径问题、资源分配问题、生产调度问题、设备更新问题、复合系统可靠性问题及生产过程最优控制等，并且取得了显著的效果。回本章目录第3页/共161页 动态规划是求解问题的一种方

3、法，而不是算法（线性规划是一种算法），因而没有标准的数学表达式，对于具体问题需要具体分析。第4页/共161页 一、多阶段决策问题 在生产经营活动中，某些问题决策过程可以划分为若干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。由于各个阶段不是孤立的，而是有机联系的，也就是说，本阶段的决策将影响过程下一阶段的发展，从而影响整个过程效果，所以决策者在进行决策时不能够仅考虑选择的决策方案使本阶段最优，还应该考虑本阶段决策对最终目标产生的影响，从而做出对全局来讲是最优的决策。当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题

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

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

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

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

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

9、6、8、6、6、2，因此共有2322248条可能的路线，分别算出各条路线的距离，最后进行比较求优。第16页/共161页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643最优路径长度18第17页/共161页第二种方法即所谓“局部最优路径”法，是说某人从k阶段出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是下图所示，全程长度是25；显然，这种方法的结果常是错误的AB1B2C1C2C3D1D2D3E1E2E3F1F2G53136876368533842

10、2213335256643C4第18页/共161页第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为6个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。第19页/共161页一、动态规划的基本概念 运用动态规划求解多阶段决策问题，首先要将该问题写成动态规划模型，再进行求解，动态规划模型中用到的概念及符号如下：第20页/共161页12n状态决策状态决策状态状态决策12ks1u1s2u2s3skuksk+1第21页/共161页例6 最短路问题 如图7-2所示，要从A地到E地铺设管线，中

11、间需要经过三个中间站，两点之间的连线上的数字表示距离，问应该选择什么路线，使总距离最短？35256321737562254321B1AB2B3C1C2C3C4ED2D1 第22页/共161页1.阶段（stage）根据所需解决问题的特点，按照时间或空间顺序把整个过程划分为若干相互联系的阶段，以便按照一定次序求解。描述阶段的变量称为阶段变量，通常用字母k表示阶段变量。例如例6中，从A到E可以划分为四个阶段，第一阶段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

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

13、2；各阶段状态集合分别为：第25页/共161页S1=AS2=B1，B2，B3S3=C1，C2，C3，C4S4=D1，D2第26页/共161页上海A伊犁 EB1B245C1C2C3425D1D356753D243654546第一阶段第二阶段第三阶段第四阶段S1=AS2=B1,B2S3=C1,C2,C3.n个阶段的决策过程有n+1个状态变量第27页/共161页 这里状态的选取应当满足无后效性：系统从某个阶段往后的发展演变，完全由系统本阶段所处的状态及决策所决定，与系统以前的状态及决策无关。也就是说，过去的历史只能通过当前的状态去影响未来的发展，当前的状态是过去历史的一个完整总结。只有具有无后效性的

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

15、，C2，C3，C4，即允许决策集合为：D2（B2）=C1，C2，C3，C4 当决定选择C3时，可以表示为：u2（B2）=C3第29页/共161页上海A伊犁 EB1B245C1C2C3425D1D356753D243654546第一阶段S1=Au1(A)=B1 或 u1(A)=B2 ,D1(A)=B1,B2第30页/共161页4.策略（policy）当各个阶段的决策确定以后，各阶段的决策形成一个决策序列，称此决策序列为一个策略。使系统达到最优效果的策略称为最优策略。在n阶段决策过程中，从第k阶段到终止状态的过程，称为k后部子过程（或称为k子过程），k后部子过程相应的决策序列称为k后部子过程策略，

16、简称子策略，记为p k，n（sk），即：P k，n（sk）=uk（sk），uk+1（sk+1），un（sn）当k=1时，即由第一阶段某个状态出发做出的决策序列称为全过程策略，简称策略，记为p1，n（s1），即：p1，n（s1）=u1（s1），u2（s2），un（sn）第31页/共161页上海A伊犁 EB1B245C1C2C3425D1D356753D243654546P1,5(A)=A,B1,C2,D2,E P1,5(A)=A,B2,C3,D3,E P2,5(A)=B2,C2,D1,E 第32页/共161页5.状态转移方程（state transfer equation）动态规划中，本阶段的状

17、态往往是上一个阶段状态和上一个阶段决策作用的结果。设第k阶段状态为sk，做出的决策为uk（sk），则第k+1阶段的状态sk+1随之确定，他们之间的关系可以表示为：sk+1=Tk（sk，uk）这种表示从第k阶段到第k+1阶段状态转移规律的方程称为状态转移方程，它反映了系统状态转移的递推规律。例如例6中，上一阶段的决策就是下一阶段的状态，所以状态转移方程为：sk+1=uk（sk）状态转移方程是建立动态规划数学模型的难点之一。第33页/共161页12ks1u1s2u2s3skuksk+1一旦某阶段的状态和决策为已知，下阶段的状态便完全确定无后效性。第34页/共161页6.指标函数和最优指标函数衡量所

18、选策略优劣的数量指标称为指标函数。它定义在全过程和所有后部子过程，常用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）动态规划数学模型的指标函数应该具有可分离性，并满足递推关系，即：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阶段的指标函数。第35页/共161页常见的指标函数形式有两种：（1）任一后部子过程的指标函数

19、是它所包含的各阶段指标的和，即：Vk,n（sk，uk，sn+1）=写成递推关系：Vk,n（sk，uk，sn+1）=vk（sk，uk）+Vk+1,n（sk+1，uk+1，sn+1）第36页/共161页（2）任一后部子过程的指标函数是它所包含的各阶段指标的积，即：Vk,n（sk，uk，sn+1）=写成递推关系：Vk,n（sk，uk，sn+1）=vk（sk，uk）Vk+1,n（sk+1，uk+1，sn+1）第37页/共161页指标函数的最优值记为fk（sk），它表示从第k阶段状态sk出发，采取最优策略p*k，n（sk）到第n阶段的终止状态时的最佳指标函数值，即：opt 是英文optimization

20、（优化）的缩写，根据问题的性质取max或min。第38页/共161页当k=1时，f1（s1）就是从初始状态s1出发到终止状态的最优函数。在不同的问题中，指标函数可以是利润、成本、距离、产品质量或资源消耗等。在最短路线问题中，第k阶段的指标函数vk（sk，uk）通常也用dk（sk，uk）表示。例如例6中，d2（B2，C3）表示第二阶段中由点B2到点C3的距离，fk（sk）表示从第k阶段点sk到终点E的最短距离，f1（A）就是所求从A到E的最短距离。第39页/共161页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643则不论前面

21、A如何到达B，B又如何到达C2，对于C2来说：第40页/共161页二、最优化原理 一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略，即一个最优策略的子策略也是最优的。第41页/共161页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643k=4,3,2,1第42页/共161页E1E2E3F1F2G33525664k=6,F1 G f6(F1)=4F2 G,f6(F2)=3k=5，出发点E1、E2、E3u5(E1)=F1E1 F1 Gu5(E2)=F2E

22、2 F2 Gu5(E3)=F2E3 F2 G第43页/共161页k=4，f4(D1)=7 u4(D1)=E2f4(D2)=6 u4(D2)=E2f4(D3)=8 u4(D3)=E2D1D2D3E1E2E3F1F2G22213335256643第44页/共161页k=2,f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2f3(C1)=13 u3(C1)=D1f3(C2)=10 u3(C

23、2)=D1f3(C3)=9 u3(C3)=D1f3(C4)=12 u3(C4)=D3k=3,第45页/共161页u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2 u5(E2)=F2u6(F2)=G最优策略 路长18AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643第46页/共161页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G537363421333264动态规划方法明显优于穷举法（计算次数及结果数量）第47页/共161页1、动态规划方法的关键在于正确地写出基本的递推递推关系式和恰当的边

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

25、的选取是从全局来考虑的，与该段的最优选择答案一般是不是从全局来考虑的，与该段的最优选择答案一般是不同的同的。3、在求整个问题的最优策略时，由于边界（初始或结果）状态是已知的，而每段的决策都是该段状态的函数，故最优策略便可通过逆序（或顺序）逆序（或顺序）递推逐段变换得到，从而确定最优路线。（请看下例）第49页/共161页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643例：请用顺序法求解下列最短路问题123456第50页/共161页第51页/共161页两种方式在本质上没有什么不同：两种方式在本质上没有什么不同：通常情况下，当初

26、始状态给定时用逆序解法较方便。当终止状态给定时用顺序解法较方便。但若初始状态虽已给定，然而终点状态较多（需比较到达不同终点状态的各个路径）及指标函数值以选取总效益最佳的终点状态时,以使用顺序解法比较方便。两种方法的差异（状态转换方式，指标函数、递推方式两种方法的差异（状态转换方式，指标函数、递推方式等）在做题中体会。等）在做题中体会。顺序解法与逆序解法的异同第52页/共161页三、动态规划的基本思想与基本原理 下面求解例6 35256321737562254321B1AB2B3C1C2C3C4ED2D1第53页/共161页k=4时，状态变量s4可取两种状态D1，D2，他们到终点E的最短路长为：

27、f4（D1）=d4（D1，E）=3 u4（D1）=Ef4（D2）=d4（D2，E）=5u4（D2）=E第54页/共161页k=3时，状态变量s3可取四种状态C1，C2，C3，C4，当s3=C1时，到达点可以有两种选择：D1或D2，则：u3（C1）=D1说明C1点至终点E的最短距离是5，最短路线为：C1D1E。第55页/共161页同理，从C2，C3，C4出发，有：u3（C2）=D2u3（C3）=D1f3（C4）=d3（C4，D2）+f4（D2）=7+5=12u3（C4）=D2第56页/共161页k=2时，类似地有：u2（B1）=C1u2（B2）=C3u2（B3）=C3第57页/共161页k=1时

28、，有：u1（A）=B3于是得到从A点到E点的最短距离为10，按计算顺序反向追踪，得到最优决策序列uk，即，u1（A）=B3，u2（B3）=C3，u3（C3）=D1，u4（D1）=E；最优路线为：AB3C3D1E第58页/共161页从上面计算过程可以看出，在各阶段求解中，都用到了第k阶段和第k+1阶段的递推关系：这种递推关系称为动态规划的基本方程。其中（7.1b）式称为边界条件，（7.1b）也可以写作，f4（s4）=d4（s4，E）第59页/共161页上述计算最短路线的过程也可以直接在图上直观表示出来，如图7-3，节点上方方格内数字表示该点到E点的最短距离。各点到E点之间的连线表示最短路线，这种

29、直接在图上求解的方法称为标号法，这种方法的最大优点是不仅可以得到从点A到点E的最短路，而且得到了中间任意一点到E点的最短路，即得到了一族最优解，这对于许多实际问题来讲是很有意义的。第60页/共161页3523275253B1AB2B3C1C2C3C4ED2D1075853510121010图7-3第61页/共161页如果规定从A点到E点为顺行方向，则由E点到A点为逆行方向，图7-3是由E点开始，由后向前标号，这种以A为始端，E为终端，从E到A的解法称为逆序解法。标号也可以由A点开始，从前向后标号，如图7-4，这种以E为始端，A为终端，从A到E的解法称为顺序解法。方格内数字表示该点到A点的最短距

30、离。连接A点和该点的折线表示该点到起点A的最短路线。第62页/共161页3213254321B1AB2B3C1C2C3C4ED2D1100213765476图7-4第63页/共161页动态规划的基本思想概括归结如下：1.将多阶段决策问题按照空间或时间顺序划分成相互联系的阶段，即把一个大问题分解成一族同类型的子问题，选取恰当的状态变量和决策变量，写出状态转移方程，定义最优指标函数，写出递推关系式和边界条件。2.从边界条件开始，由后向前逐段递推寻找最优，在每一个阶段的计算中都要用到前一阶段的最优结果，依次进行，求得最后一个子问题的最优解就是整个问题的最优解。3.在多阶段决策过程中，确定阶段k的最优

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

32、/共161页一、动态规划问题的解法动态规划问题的解法二、动态规划的数学模型二、动态规划的数学模型7.3 动态规划模型的建立与求解回本章目录第66页/共161页一、动态规划问题的解法一、动态规划问题的解法解法离散型离散型连续型连续型：分段穷举法（最短路问题的求解）（可以借助表格法来求解：分段穷举法（最短路问题的求解）（可以借助表格法来求解P218P218）：利用解析方法、线性规划方法、：利用解析方法、线性规划方法、非线性规划方法、其他数值计算方法非线性规划方法、其他数值计算方法计算机上用的连续型的离散化解法。计算机上用的连续型的离散化解法。没有固定的方法；具体模型具体分析。（下面例子的建模型与解

33、法没有固定的方法；具体模型具体分析。（下面例子的建模型与解法一起讲）一起讲）要求要求：经验：经验、技巧、灵活、技巧、灵活难！难！总的来讲有两类方式：顺序法与逆序法总的来讲有两类方式：顺序法与逆序法第67页/共161页二、动态规划的数学模型二、动态规划的数学模型1、理论依据-最优化原理 最优化原理：一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略。第68页/共161页2、动态规划模型的几个要素：1)阶段数k2)状态变量sk Sk3)决策变量uk(sk)Uk4)指标函数Vk,n 状态转移方程5)最优值函数fk(sk)第69

34、页/共161页6）动态规划的基本方程 动态规划的基本方程是建立动态规划模型的关键。设第k阶段处于状态sk，决策是uk(sk)，状态转移方程为sk+1=Tk（sk，uk），k阶段和k+1阶段的递推关系式可以写为：第70页/共161页式(7.2a)中运算符号*表示加“”或乘“”。当运算符号取加法时，边界条件fn+1（sn+1）=0，当运算符号取乘法时，边界条件fn+1（sn+1）=1。求解时，根据边界条件从k=n开始，由后向前逆推，逐步求得各段最优决策和相应的最优值，最后求得f1（s1），得到整个问题的最优解。这种由后向前计算最优解的方法称为逆序解法（backward induction meth

35、od），相应的基本方程称为逆序解法基本方程。第71页/共161页3、建立动态规划模型的步骤（1）划分阶段：划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。（2）正确选择状态变量 sk,满足:可知性:正确描述动态过程演变,可直接或间接确定状态变量的值;无后效性:后面的决策与前面的决策无关;第72页/共161页（3）确定决策变量uk及允许决策集合Dk（sk）通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。（4）确定状态转移方程

36、根据k阶段状态变量sk和决策变量uk（sk）写出k+1阶段状态变量sk+1，即sk+1=Tk（sk，uk），状态转移方程应当具有递推关系。（5）确定阶段指标函数和最优指标函数，建立动态规划基本方程第73页/共161页阶段指标函数vk（sk，uk）是指第k阶段的收益，最优指标函数fk（sk）是指从第k阶段状态sk出发到第n阶段末所获得收益的最优值，最后写出动态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。第74页/共161页 学习方法建议：第

37、一步 先看问题，充分理解问题的条件、情况及求解目标。第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素，一个方程”这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。第75页/共161页第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。第四步 把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。第五步 对照自己的求解，分析成败。第76页/共161页 1.动态规划的四大要素 状态变量及其可能集合 sk Sk 决策变量及其允许集合 uk Uk 状态转移方程 sk+1=Tk(

38、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 第77页/共161页例例7 7 有某种机床，可以在高低两种不同的负荷下进行生产，在高负荷下生产时，产品的年产量为 g，与年初投入生产的机床数量 u1 的关系为 g=g(u1)=8u1，这时，年终机床完好台数将为，au1 (a为机床完好率，0 a 1，设 a=0.7)。在低负荷下生产时，产品的年产量为 h，和投入生产的机床数量的关系为 h=h(u2)=5u2，相应的机床完好率为 b(0b2，设 b=0.9)，一般

39、情况下(a b )。第78页/共161页假设某厂开始有 x1=1000 台完好的机床，现要制定一个五年生产计划，问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为最高。解：解：首先构造这个问题的动态规划模型。1分阶段：设阶段变量 k 表示年度，因此，阶段总数 n=5。第79页/共161页2.状态变量：用 sk 表示第 k 年度初拥有的完好机床台数，同时也是第 k-1 年度末时的完好机床数量。3.决策变量：用 uk 表示第 k 年度中分配于高负荷下生产的机床台数。于是 sk-uk 便为该年度中分配于低负荷下生产的机床台数。第80页/共161页4状态转移方程

40、为：决策变量的取值：在第 k 段为 第81页/共161页6条件最优目标函数递推方程令 fk(sk)表示由第 k 年的状态 sk 出发，采取最优分配方案到第5年度结束这段时间的产品产量，根据最优化原理有以下递推关系:第82页/共161页下面采用逆序递推计算法,从第5年度开始递推计算K=5 时有显然，当 u5*=s5 时，f5(s5)有最大值，相应的有 f5(s5)=8s5。第83页/共161页K=4 时有：第84页/共161页 因此，当 u4*=s4 时，有最大值 f4(s4)=13.6s4K=3 时有：可见，当 u3*=s3 时，有最大值 f3(s3)=17.55s3 。K=2 时有：第85页

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

42、解：解：由状态转移方程第88页/共161页有由此式得当 k=5 时有当 k=4 时有第89页/共161页显然，只有取 u4*=0,有最大值 f4(s4)=21.4s4-7500第90页/共161页当 k=3 时有:显然，只有取 u3*=0,f3(s3)有最大值 f3(s3)=24.5s3-7500 。第91页/共161页当 k=2 时有:显然，只有取 u2*=0,f2(s2)有最大值 f2(s2)=27.1s2-7500 。第92页/共161页当 k=1 时有:显然，只有取 u1*=0,f1(s1)有最大值 f1(s1)=29.4s1-7500 。第93页/共161页第94页/共161页 例例

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

44、1 至 第 k-1 个项目投资后的剩余资金；即第 k 段初拥有的可以分配给第 k 到第3个项目的资金额（单位：万元）。3.决策变量：用 xk 表示对第 k 个项目投资 的资金数量（单位：万元）。决策变量的取值：0 xk sk 4状态转移方程为：第97页/共161页6.基本方程为：最优指标函数 fk(sk)表示第 k 阶段，初始状态为 sk 时，从第 k 到第 3 个项目所获最大收益 第98页/共161页当 k=3 时：当 k=2 时：第99页/共161页极大值只可能在 0，s2 端点取得，第100页/共161页当 k=1 时：第101页/共161页矛盾，所以舍去 sk 0);g1(x1)=0(

45、x1=0)g2(x2)=3x2+7(x20);g2(x2)=0(x2=0)g3(x3)=4x3+5(x30);g3(x3)=0(x3=0)设备如何分配可使工厂的收益最大？第116页/共161页分析：1.阶段与生产线相联系,阶段 k 只考虑分配到生产线 k 的设备台数;2.状态变量 sk 表示 k 生产线可分配的设备数;3.决策变量 xk 表示决定在 k 生产线上使用的设备数;4.状态转移方程:sk+1=sk-xk;5.损益函数:fk(sk)=max gk(xk)+fk+1(sk+1)第117页/共161页s3 f3(s3)x3*0 f3(0)=maxx3=0 0 =0 01 f3(1)=max

46、x3 1 4x3+5=9 12 f3(2)=maxx3 2 4x3+5=13 23 f3(3)=maxx3 3 4x3+5=17 34 f3(4)=maxx3 4 4x3+5=21 4求解：求解：k k=3:=3:g g3 3(x x3 3)=4)=4x x3 3+5+5第118页/共161页 k k=2:=2:g g2 2(x x2 2)=3)=3x x2 2+7 +7 s s3 3=s s2 2-x x2 2第119页/共161页k=1:g1(x1)=7x1+2 s2=s1-x1因此得到：x1=2,x2=1,x3=1第120页/共161页离散的时间段内如何安排生产与库存。生产成本为:C(x

47、t)=k+cxt(xt 0)或 C(xt)=0(xt=0),k为开工所需费用,c 是变动成本,xt为 t 期的生产数量;库存成本为：H(yt)=hyt,h为单位库存成本，yt为 t 期期初库存数量。2.生产与库存问题第121页/共161页例:假定k=250,c=2,h=1,y1=0,T=5,需求数据如下表,如何安排生产才能使总成本最小?t 1 2 3 4 5需求(dt)280 220 360 140 270第122页/共161页分析分析:阶段可按周期 t 划分,t=1,2,3,4,5每周期期初的库存量为该阶段的状态,状态变量 st 表示 t 周期期初库存；决策变量 xt 表示 t 期的生产数量

48、;状态转移方程为:st+1=st+xt-dt第123页/共161页 递推函数递推函数:ft(st)=min Ct(xt)+Ht(st)+ft+1(st+1)以库存表示系统状态会大大增加系统状态数量,然而,上述问题的最优决策必须使每一阶段库存或者为零,或者为后续一或几个周期需求之和。第124页/共161页 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

49、 (x4=140)f4(140)=1140+f5(0)=140+790=930 (x4=0)f4(410)=1410+f5(270)=410+270=680 (x4=0)第125页/共161页 t=3:f3(0)=min 250+2 360+f4(0),250+2 500+f4(140),250+2 770+f4(410)=min 2290,2180*,2470=2180 (x3=500)f3(360)=1 360+f4(0)=360+1320=1680 (x3=0)f3(500)=1 500+f4(140)=500+930=1430 (x3=0)f3(770)=1 770+f4(410)=7

50、70+680=1450 (x3=0)第126页/共161页t=2:f2(0)=min 250+2 220+f3(0),250+2 580+f3(360),250+2 720+f3(500),250+2 990+f3(770)=min2870*,3090,3120,3680=2870(x2=220)f2(220)=1 220+f3(0)=220+2180=2400(x2=0)f2(580)=1 580+f3(360)=580+1680=2260(x2=0)f3(720)=1 720+f3(500)=720+1430=2150(x2=0)第127页/共161页t=1:f1(0)=min 250+2