运筹学课件我的资源8-动态规划

Copyright2013Czhang.Allrightsreserved.,2020/5/3,张冲南京邮电大学经济与管理学院Email：zcbling,动态规划,Copyright2013Czhang.Allrightsreserved.,2020/5/3,Chapter8动态规划,动态规划问题及实例动态规划的基本概念、理论和方法动态规划的应用举例,本章主要内容：,Copyright2013Czhang.Allrightsreserved.,2020/5/3,引言,动态规划DynamicProgramming动态规划是运筹学的一个分支，是解决多阶段决策过程最优化的一种数学方法。1951年，美国数学家贝尔曼（R.E.Bellman)等人提出了“最优性原理”，即根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。从而创建了解决最优化问题的一种新的方法动态规划。Bellman在1957年出版了DynamicProgramming一书，是动态规划领域中的第一本著作。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,引言,动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。动态规划模型的分类：以“时间”角度可分成：离散型和连续型。从信息确定与否可分成：确定型和随机型。从目标函数的个数可分成：单目标型和多目标型。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,例1机器负荷分配问题（时间阶段问题）设有某种机器设备，用于完成两类工作A和B。若第k年初完好机器的数量为xk，若以数量uk用于A，余下的（xkuk）用于工作B，则该年的预期收入为g(uk)+h(xkuk)。这里g(uk)和h(xkuk)是已知函数，且g(0)=h(0)=0。又机器设备在使用中会有损坏，设机器用于工作A时，一年后能继续使用的完好机器数占年初投入量的70%；若用于工作B时，一年后能继续使用的完好机器数占年初投入量的90%。则在下一年初能继续用于A、B工作的设备数为xk+1=0.7uk+0.9(xkuk)。设第1年初完好的机器总数为1000台，问在连续5年内每年应如何分配用于A、B两项工作的机器数，使5年的总收益为最大。,多阶段决策过程及实例,Copyright2013Czhang.Allrightsreserved.,2020/5/3,相应的问题称为多阶段决策问题。,这是一个多阶段决策过程。该过程可以分为相互联系的若干阶段，每一阶段都需作出决策，从而形成全过程的决策。,第1年,u1,x2=0.7u1+0.9(x1-u1),u2,x3=0.7u2+0.9(x2-u2),u3,第4年,u4,x5=0.7u4+0.9(x4-u4),u5,多阶段决策过程及实例,Copyright2013Czhang.Allrightsreserved.,2020/5/3,例2最短路线问题（空间阶段的例子）设有一个旅行者从下图中的A点出发，途中要经过B、C、D等处，最后到达终点E。从A到E有很多条路线可以选择，各点之间的距离如图所示，问该旅行者应选择哪一条路线，使从A到达E的总的路程为最短。,1,2,3,4,决策1,决策2,决策3,决策4,可看成4阶段的决策问题。,多阶段决策过程及实例,Copyright2013Czhang.Allrightsreserved.,2020/5/3,从以上两个例子，可以知道所谓多阶段决策问题是指这样的决策问题：其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定既依赖于当前面临的状态，又影响以后总体的效果。当每一阶段的决策选定以后，就构成一个决策序列，称为一个策略，它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。,多阶段决策过程及实例,Copyright2013Czhang.Allrightsreserved.,2020/5/3,多阶段决策过程及实例,多阶段决策过程（Multi-Stagedecisionprocess）多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策过程也称为序贯决策过程。这种问题就称为多阶段决策问题。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,多阶段决策问题的特点1.各阶段的决策相互关联多阶段决策过程最优化的目的，是要达到整个活动过程的总体效果最优，而不是某个阶段“局部”的效果最优。因此，各个阶段决策的选取不是任意确定的。前一个决策的选取决定了当前状态，当前状态进行决策后又影响到下一阶段的状态和决策，以至于影响总体效果。所以决策者在每个阶段决策时，不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局而言是最优的决策。动态规划就是符合这一要求的一种最优化方法。,多阶段决策过程及实例,Copyright2013Czhang.Allrightsreserved.,2020/5/3,2.各个阶段的决策一般与“时间”有关动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各阶段的决策，从而产生一个决策序列，这就是“动态”的意思。但是，一些与时间无关的静态问题，只要在问题中人为引入“时间”因素，也可将其看成是多阶段的决策问题，用动态规划方法去处理。,多阶段决策过程及实例,Copyright2013Czhang.Allrightsreserved.,2020/5/3,多阶段决策问题的典型例子,多阶段决策问题的典型例子：1.最短路线问题：给定一个线路网络，要从A向F铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？,Copyright2013Czhang.Allrightsreserved.,2020/5/3,多阶段决策问题的典型例子,2、生产与存储问题：某工厂每月需供应市场一定数量的产品。供应需求所剩余产品应存入仓库，一般地说，某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用，要确定一个每月的生产计划，在满足需求条件下，使一年的生产与存储费用之和最小。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,多阶段决策问题的典型例子,3.生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。4.机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为g=g(u1),Copyright2013Czhang.Allrightsreserved.,2020/5/3,多阶段决策问题的典型例子,5.航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。6.线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,动态规划的基本概念和基本原理,由最短路介绍动态规划的基本概念和基本原理,例,Copyright2013Czhang.Allrightsreserved.,2020/5/3,动态规划的基本概念和基本原理,1、阶段（stage）把所给问题恰当地划分为若干个相互联系又有区别的子问题，通常根据时间顺序或空间特征来划分，以便按阶段的次序逐段解决整个过程的优化问题。描述阶段的变量叫作阶段变量，阶段变量通常用k表示（k=1，2，3，n）。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,如本例可按空间分为4个阶段来求解，k=1,2,3,4。,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,状态：每阶段初的客观条件。描述各阶段状态的变量称为状态变量，常用xk或sk表示第k阶段的状态。,例中，状态就是某阶段的出发位置。,按状态变量的取值是连续还是离散，可将动态规划问题分为离散型和连续型。,2、状态（state）,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,动态规划中的状态应满足无后效性（马尔科夫性）：所谓无后效性指系统到达某个状态前的过程的决策将不影响到该状态以后的决策。指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策（历史）无关。过程的过去历史只能通过当前的状态去影响它未来的发展例中，当某阶段的状态已选定某个点时，从这个点以后的路线只与该点有关，不受该点以前的路线的影响，所以满足状态的无后效性。,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,状态集合：状态变量xk或sk的取值集合称为状态集合，状态集合实际上是关于状态的约束条件。通常用Sk表示状态集合，xkSk。,第1阶段S1=A；第2阶段具有3个状态B1、B2和B3，故S2=B1,B2,B3。,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,当过程处于某一阶段的某状态时，可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量，常用uk(xk)表示第k阶段当状态处于xk时的决策变量，它是状态变量的函数。,例中，从第2阶段的状态B1出发，可以选择下一阶段的C1、C2、C3。如我们决定选择C1，则可表示为：u2(B1)=C1。,B1,C1,C2,C3,3、决策（decision）,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,决策集合：第k阶段当状态处于xk时决策变量uk(xk)的取值范称为决策集合，常用Dk(xk)表示。,例中，从第2阶段的状态B1出发，可以选择下一阶段的C1、C2、C3。即D2(B1)=C1、C2、C3；,B1,C1,C2,C3,决策集合实际上是决策的约束条件，uk(xk)Dk(xk)。,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,小结阶段k、状态xk、状态集合Sk、决策uk(xk)、决策集合Dk(xk)。,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,状态转移方程：从xk的某一状态值出发，当决策变量uk(xk)的取值决定后，下一阶段状态变量xk+1的取值也随之确定。描述从xk转变为xk+1的规律称为状态转移规律（方程）。,从第2阶段的状态B1出发，如我们决定选择C2（也即确定了下一阶段的状态）。,4、状态转移方程（equationofstatetransition,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,上例中，u2(B1)=C2状态转移律为：xk+1=uk(xk),一般来说，下一阶段状态变量xk+1的取值是上阶段的某一状态变量xk和上阶段决策变量uk(xk)的函数，记为xk+1=Tk(xk,uk(xk),动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,策略：由依次进行的n个阶段决策构成的决策序列就构成一个策略，用p1，n（s1）=u1(x1),u2(x2),un(xn)表示。,本例中，如p1，4(s1)=u1(A)=B1,u2(B1)=C2,u3(C2)=D1,u4(D1)=E表示其中一个策略，其总距离为2+5+6+3=16。,5、策略（policy）和子策略（subpolicy）,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,策略集合：在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列（策略），由它们组成的集合，称为策略集合，记作P1n。从策略集合中，找出具有最优效果的策略称为最优策略。,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,子策略：从k阶段到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略，表示为pk,n(sk)=uk(xk),uk+1(xk+1),un(xn),如从第3阶段的C2状态开始的一个子策略可表示：p3,4=u3(C2)=D1,u4(D1)=E,C2,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。,阶段指标函数,过程指标函数,6、指标函数（objectivefunction）,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,阶段指标函数：是指第k阶段从状态xk出发，采取决策uk时产生的效益，用vk(xk,uk)表示。,例中，指标函数是距离。如v2(B1,C2)表示由B1出发，采用决策到C2点的两点间距离，即v2(B1,C2)=5。,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,过程指标函数：是指从第k阶段的某状态xk出发，采取子策略pkn时所得到的效益，记作Vk,n=Vk,n(xk,uk,xk+1,uk+1,xn),例中，如V3,4(C2,u3(C2)=D1,D1,u4(D1)=E,E)=6+3=9,C2,动态规划的基本概念和基本原理,Copyright2013Czhang.Allrightsreserved.,2020/5/3,阶段指标函数vk(sk,uk)：从状态sk出发，选择决策uk所产生的第k阶段指标。过程指标函数Vk,n(sk,uk,sk+1,sn+1)：从状态sk出发，选择决策uk,sk+1,sn+1所产生的过程指标。动态规划要求过程指标具有可分离性，即Vk,n(sk,uk,sk+1,sn+1)=vk(sk,uk)+Vk+1(sk+1,sk+1,sn+1)称指标具有可加性，或Vk,n(sk,uk,sk+1,un)=vk(sk,uk)Vk+1(sk+1,uk+1,un)称指标具有可乘性。基本方程：最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即,Copyright2013Czhang.Allrightsreserved.,2020/5/3,对于可加性指标函数，上式可以写为对于可乘性指标函数，上式可以写为上式中“opt”表示“max”或“min”。以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。终端条件(边界条件)：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1)=0。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,小结:,指标函数形式:和、积,无后效性,Copyright2013Czhang.Allrightsreserved.,2020/5/3,解多阶段决策过程问题，求出,f1(s1),从k到终点最优策略子策略的最优目标函数值,Copyright2013Czhang.Allrightsreserved.,2020/5/3,1.划分阶段,2.正确选择状态变量,3.确定决策变量及允许决策集合,4.确定状态转移方程,5.确定阶段指标函数和最优指标函数，建立动态规划基本方程,划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。,建立动态规划模型的步骤,选择状态变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。,通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。,根据k阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。,阶段指标函数是指第k阶段的收益，最优指标函数是指从第k阶段状态出发到第n阶段末所获得收益的最优值，最后写出动态规划基本方程。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。下面我们看一个具体的例子,例机器负荷分配问题（时间阶段问题）,Copyright2013Czhang.Allrightsreserved.,2020/5/3,例机器负荷分配问题（时间阶段问题）设有某种机器设备，用于完成两类工作A和B。若第k年初完好机器的数量为xk，若以数量uk用于A，余下的（xkuk）用于工作B，则该年的预期收入为g(uk)+h(xkuk)。其中g(uk)8uk，h(xkuk)=5（xkuk）。又机器设备在使用中会有损坏，设机器用于工作A时，一年后能继续使用的完好机器数占年初投入量的70%；若用于工作B时，一年后能继续使用的完好机器数占年初投入量的90%。则在下一年初能继续用于A、B工作的设备数为xk+1=0.7uk+0.9(xkuk)。设第1年初完好的机器总数为1000台，问在连续5年内每年应如何分配用于A、B两项工作的机器数，使5年的总收益为最大。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,1.划分阶段,按年度来划分阶段，k=1,2,3,4,5,2.正确选择状态变量,状态变量xk为第k年度初拥有的完好机器数量,3.确定决策变量及允许决策集合,决策变量uk为第k年度中分配于A工作的机器数量，则xkuk为用于B工作的机器数量。,第k阶段决策集合Dk(xk)=uk|0ukxk,这里xk和uk均取连续变量，它们的非整数值可以这样理解，如xk=0.6，就表示一台机器在第k年度中正常工作时间只占6/10；uk=0.3，就表示一台机器在该年度只有3/10的时间能正常用于A工作。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,4.确定状态转移方程,状态转移方程为xk+1=0.7uk+0.9(xkuk),5.确定阶段指标函数和最优指标函数，建立动态规划基本方程,指标函数为,令最优指标函数fk(xk)表示由资源量xk出发，从第k年开始到第5年结束时所取得的最大预期收入。因而有：,fk(xk)=max,Copyright2013Czhang.Allrightsreserved.,2020/5/3,1、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。,动态规划的基本思想,Copyright2013Czhang.Allrightsreserved.,2020/5/3,2、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的.,最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。”也就是说，一个最优策略的子策略也是最优的。,3、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,多阶段决策过程及实例,请看如下典例最短路线问题,Copyright2013Czhang.Allrightsreserved.,2020/5/3,多阶段决策过程及实例,方法1：贪心算法每一步都走最短的线路：则AB2C4D3E2F2-G，长度为21。不是最优。最短的线路:AB1C2D1E2F2-G，长度为18,Copyright2013Czhang.Allrightsreserved.,2020/5/3,枚举法,方法2：枚举法列出每条可能的路线，然后算出每条路的长度，从中选择最优路线。缺点：线路太多，随点数增加很快。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,标号法是借助网络图通过分段标号来求出最优路线的一种简便、直观的方法。通常标号法采取“逆序求解”的方法来寻找问题的最优解，即从最后阶段开始，逐次向阶段数小的方向推算，最终求得全局最优解。,E,A,标号法,Copyright2013Czhang.Allrightsreserved.,2020/5/3,标号法的一般步骤：（1）给最后一段标号，该段各状态（即各始点）到终点的距离用数字分别标在各点上方的方格内，并用粗箭线连接各点和终点。（2）向前递推，给前一阶段的各个状态标号。每个状态上方方格内的数字表示该状态到终点的最短距离。将刚标号的点沿着最短距离用粗箭线连接起来，表示出各刚标号的点到终点的最短路线。（3）逐次向前递推，直到将第一阶段的状态（即起点）标号，起点方格内的数字就是起点到终点的最短距离，从起点开始连接终点的粗箭线就是最短路线。,标号法,Copyright2013Czhang.Allrightsreserved.,2020/5/3,标号法,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,该点到G点的最短距离,从G到A的解法称为逆序解法。,从A到G的解法称为顺序解法。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,最短路问题,该方法比枚举法简单，计算的路远少于枚举法计算过程分了六个阶段。每个阶段都是一个子问题，有出发点和选择，并有不同的获得。后一阶段的出发点由前阶段的出发点和选择确定前一阶段的获得不仅与本阶段的选择有关还与后一阶段的获得有关。这类问题称之为多阶段决策问题。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,用标号法求从A到E的最短路径,路线为AB2C1D1E，最短路径为19,A,B2,B1,B3,C1,C3,D1,D2,E,C2,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,练习1,1,Copyright2013Czhang.Allrightsreserved.,2020/5/3,0,3,5,4,4,8,6,11,7,8,11,从E到A的解法称为逆序解法。,从A到E的解法称为顺序解法。,练习2,Copyright2013Czhang.Allrightsreserved.,2020/5/3,练习3,下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,动态规划应用案例,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第（1）步k=5,f5(x5)=f5(E)=0这是边界条件,0,E,fk(xk)表示从第k阶段状态xk到E点的的最短距离,案例一：最短路径问题,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第（2）步k=4,状态变量x4可取两种状态D1、D2。由D1到终点E只有一条路线，路长为3，即f4(D1)=3。同理，f4(D2)=4。,3,表示由D1点至E点的最短路长为3。,4,0,D1,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第（3）步k=3,状态变量x3可取三个值：C1、C2、C3。由C1到终点E有2条路线，分别为经过D1、D2到达E点（由D1、D2到达E点的最短路长在第一步已计算得出），需加以比较，取其中最短的。,路线1v3(C1,D1)+f4(D1)=1+3=4路线2v3(C1,D2)+f4(D2)=4+4=8,则由C1到终点E的最短距离f3(C1)=minv3(C1,D1)+f4(D1),v3(C1,D2)+f4(D2)=4，同理得f3(C2)=7，f3(C3)=6，,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第（4）步k=2,状态变量x2可取三个值：B1、B2、B3。,则由C1到终点E的最短距离f2(B1)=minv2(B1,C1)+f3(C1),v2(B1,C2)+f3(C2),v2(B1,C3)+f3(C3)=min7+4,5+7,6+6=11同理，得f2(B2)=7，f2(B3)=8.,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第（5）步k=1,状态变量x1可取值：A。,则由A到终点E的最短距离f1(A)=minv1(A，B1)+f2(B1),v1(A,B2)+f2(B2),v1(A,B3)+f2(B3)=min2+11,5+7,3+8=11,因此，由A到终点E的最优解为：AB3C2D2E由点A到终点E的最优值为11。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,我们再次用例1来说明顺序解法。由于此问题的始点A与终点E都是固定的，计算由A点到E点的最短路线与由E点到A点的最短路线没有什么不同。若设fk(xk+1)表示从起点A到第k阶段末状态点xk+1的最短距离就可以由前向后逐步求出起点A到各阶段末状态点的最短距离，最后求出起点A到E点的最短距离及路线。,动态规划的目标：最优指标f4(E),Copyright2013Czhang.Allrightsreserved.,2020/5/3,第一步k=0,f0(x1)=f0(A)=0这是边界条件,0,A,fk(xk+1)表示从起点A到第k阶段末状态点xk+1的最短距离,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第二步k=1,2,3,5,0,按f1(x2)的定义有f1(B1)=v(B1,A)+f0(A)=2f1(B2)=v(B2,A)+f0(A)=5f1(B3)=v(B3,A)+f0(A)=3,B1,B2,B3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第三步k=2,2,3,5,0,按f2(x3)的定义有v(C1,B1)+f1(B1)=7+2=9f2(C1)=minv(C1,B2)+f1(B2)=3+5=8v(C1,B3)+f1(B3)=5+3=8,u2(C1)=B2或B3,8,C1,状态转移方程：xk=Tk(xk+1,uk),Copyright2013Czhang.Allrightsreserved.,2020/5/3,第三步k=2,2,3,5,0,按f2(x3)的定义有v(C2,B1)+f1(B1)=5+2=7f2(C2)=minv(C2,B2)+f1(B2)=2+5=7v(C2,B3)+f1(B3)=1+3=4,u2(C2)=B3,8,4,C2,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第三步k=2,2,3,5,0,按f2(x3)的定义有v(C3,B1)+f1(B1)=6+2=8f2(C3)=minv(C3,B2)+f1(B2)=4+5=9v(C3,B3)+f1(B3)=5+3=8,8,4,u2(C3)=B1或B3,8,C3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第四步k=3,2,3,5,0,按f3(x4)的定义有v(D1,C1)+f2(C1)=1+8=9f3(D1)=minv(D1,C2)+f2(C2)=6+4=10v(D1,C3)+f2(C3)=3+8=11,8,4,u3(D1)=C1,8,9,D1,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第四步k=3,2,3,5,0,按f3(x4)的定义有v(D2,C1)+f2(C1)=4+8=12f3(D2)=minv(D2,C2)+f2(C2)=3+4=7v(D2,C3)+f2(C3)=3+8=11,8,4,u3(D2)=C2,8,9,7,D2,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第五步k=4,2,3,5,0,按f4(x5)的定义有v(E,D1)+f3(D1)=3+9=12f4(E)=minv(E,D2)+f3(D2)=4+7=11,8,4,u4(E)=D2,8,9,7,11,E,Copyright2013Czhang.Allrightsreserved.,2020/5/3,2,3,5,0,8,4,8,9,7,即可得到最优路线。,因此，由A到终点E的最优解为：AB3C2D2E由点A到终点E的最优值为11。,11,Copyright2013Czhang.Allrightsreserved.,2020/5/3,求从A到E的最短路径,路线为AB2C1D1E，最短路径为19,A,B2,B1,B3,C1,C3,D1,D2,E,C2,5,2,14,1,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,练习1：,1,Copyright2013Czhang.Allrightsreserved.,2020/5/3,练习2：,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,最优路线为：AB1C2D1E2F2G路长18,求从A到G的最短路径,3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,现有数量为a（万元）的资金，计划分配给n个工厂,用于扩大再生产。假设：xi为分配给第i个工厂的资金数量（万元）；gi(xi)为第i个工厂得到资金后提供的利润值（万元）。问题是如何确定各工厂的资金数，使得总的利润为最大。,据此，有下式：,案例二：投资分配问题,Copyright2013Czhang.Allrightsreserved.,2020/5/3,令：fk(x)=以数量为x的资金分配给前k个工厂，所得到的最大利润值。用动态规划求解，就是求fn(a)的问题。,当k=1时，f1(x)=g1(x)（因为只给一个工厂）,当1kn时，其递推关系如下：设：y为分给第k个工厂的资金（其中0yx），此时还剩xy（万元）的资金需要分配给前k-1个工厂,如果采取最优策略，则得到的最大利润为fk1(xy),因此总的利润为：gk(y)fk1(xy),Copyright2013Czhang.Allrightsreserved.,2020/5/3,如果a是以万元为资金分配单位，则式中的y只取非负整数0，1，2，x。上式可变为：,所以，根据动态规划的最优化原理，有下式：,Copyright2013Czhang.Allrightsreserved.,2020/5/3,例1：设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。,解：依据题意，是要求f4(60)。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,按顺序解法计算。第一阶段：求f1(x)，也就第一个工厂的情况。显然有f1(x)g1(x)，得到下表,第二阶段：求f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,最优策略为（40，20），此时最大利润为120万元。,同理可求得其它f2(x)的值。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,最优策略为（30，20），此时最大利润为105万元。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,最优策略为（20，20），此时最大利润为90万元。,最优策略为（20，10），此时最大利润为70万元。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,最优策略为（10，0）或（0，10），此时最大利润为20万元。,f2(0)0。最优策略为（0，0），最大利润为0万元。得到下表,最优策略为（20，0），此时最大利润为50万元。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第三阶段：求f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,最优策略为（20，10，30），最大利润为155万元。,同理可求得其它f3(x)的值。得到下表,Copyright2013Czhang.Allrightsreserved.,2020/5/3,第四阶段：求f4(60)。即问题的最优策略。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,最优策略为（20，0，30，10），最大利润为160万元。,Copyright2013Czhang.Allrightsreserved.,2020/5/3,某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表1所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？,表1,例2,Copyright2013Czhang.Allrightsreserved.,2020/5/3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,Copyright2013Czhang.Allrightsreserved.,2020/5/3,求投资分配问题得最优策略，其中a50万元，其余资料如表所示。,练习1,Copyright2013Czhang.Allrightsreserved.,2020/5/3,某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。,x1=2，x2=1，x3=1，f3(4)=47,练习2,Copyright2013Czhang.Allrightsreserved.,2020/5/3,例1：某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月生产单位产品费用为：,每月库存j单位产品的费用为E(j)0.5j(干元)，该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第j+1个月的库存量是第j个月可销售量与该月用户需求量之差；而第i个月的可销售量是本月初库存量与产量之和。,案例三：生产与存贮问题,Copyright2013Czhang.Allrightsreserved.,2020/5/3,(1)阶段：每个月为一个阶段，k1，2，3，4。(2)状态变量:sk为第k个月初的库存量。(3)决策变量:uk为第k个月的生产量。(4)状态转移方程：sk+1=sk+uk-gk(5)最优指标函数：fk(sk)表示第k月状态为sk时，采用最佳策略生产，从本月到计划结束（第4个月末）的生产与存贮最低费用。(6)基本方程：,解：建立动态规划模型,Copyright2013Czhang.Allr