动态规划简介课件

动态规划动态规划本章内容重点本章内容重点多阶段决策过程的最优化多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法的基本步骤动态规划方法应用举例动态规划方法应用举例 动态规划动态规划动态规划是解决多阶段决策过程最优化的一种数学方动态规划是解决多阶段决策过程最优化的一种数学方法。法。1951年美国数学家贝尔曼等人根据一类多阶段决策问年美国数学家贝尔曼等人根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系的单题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。贝尔曼的阶段问题，然后逐个加以解决。贝尔曼的动态规划动态规划于于1957年出版。年出版。动态规划方法与动态规划方法与“时间时间”关系很密切，随着时间过程关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是的发展而决定各时段的决策，产生一个决策序列，这就是“动态动态”的意思。然而它也可以处理与时间无关的静态问的意思。然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入题，只要在问题中人为地引入“时段时段”因素，就可以将其因素，就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方转化为一个多阶段决策问题。在本章中将介绍这种处理方法。法。动态规划动态规划所谓多阶段决策问题是指这样的决策问题所谓多阶段决策问题是指这样的决策问题:其过程可分其过程可分为若干个相互联的阶段，每一阶段都对应着一组可供选择为若干个相互联的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。当每一阶段的决策选定以后，就构成响以后总体的效果。当每一阶段的决策选定以后，就构成一个决策序列，称为一个策略，它对应着一个确定的效果。一个决策序列，称为一个策略，它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。多阶段决策问题就是寻找使此效果最好的策略。状态状态 x1阶段阶段1T1决策决策u u1 1状态状态 x2决策决策u u2 2阶段阶段2T2状态状态 x3.状态状态 xk决策决策u uk k阶段阶段kTk状态状态 xk+1.状态状态 xn决策决策u un n阶段阶段nTn状态状态 xn+1多阶段决策问题多阶段决策问题工厂生产过程工厂生产过程:由于市场需求是一随着时间而变化的因素，由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。划安排。设备更新问题设备更新问题:一般企业用于生产活动的设备，刚买来时故一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综合权衡决旧的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。定设备的使用年限，使总的经济效益最好。多阶段决策问题多阶段决策问题连续生产过程的控制问题连续生产过程的控制问题:一般化工生产过程中，常包含一一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此应该如何根据各工序的运行工况，工序设备的输入，因此应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。控制生产过程中各设备的输入和输出，以使总产量最大。资源分配问题资源分配问题:资源分配问题属于静态问题。如某工业部门资源分配问题属于静态问题。如某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题。和顺序，从而使其变成一个多阶段决策问题。动态规划求解的特点动态规划求解的特点 通常多阶段决策过程的发展是通过状态的一系列变换来通常多阶段决策过程的发展是通过状态的一系列变换来实现的。实现的。一般情况下，系统在某个阶段的状态转移除与本一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。状态和决策有关。适合于用动态规划方法求解的只是一类特殊的多阶段决适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有策问题，即具有“无后效性无后效性”的多阶段决策过程。的多阶段决策过程。无后效性无后效性(又称马尔柯夫性又称马尔柯夫性)是指系统从某个阶段往是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策决定，与系统以前经历的状态和决策(历史历史)无关。无关。A 动态规划问题实例动态规划问题实例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643例例6-1 给定一个线路网络，要从给定一个线路网络，要从A向向F铺设一条输油管，铺设一条输油管，各点间连线上的数字表示距离，问应选择什么路线，可各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？使总距离最短？A 动态规划动态规划C4C2D3D2GB2B1C1C3D1E3E2E1F2F15313687668353384221233355266431.阶段与阶段变量阶段与阶段变量 为了便于求解和表示决策及过程的发展顺序，为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称为多段决策问题的阶段。区别的子问题，称为多段决策问题的阶段。描述阶段的变量称为阶段变量，常用描述阶段的变量称为阶段变量，常用k表示。表示。阶段的划分，一般是根据时间和空间的自然特征阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。来进行的，但要便于问题转化为多阶段决策。动态规划的基本概念动态规划的基本概念 动态规划的基本概念动态规划的基本概念2.状态、状态变量与可能状态集状态、状态变量与可能状态集 描述事物描述事物(或系统或系统)在某特定的时间与空间域中所处在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量包含在给定的阶段上确定全部允做状态变量。状态变量包含在给定的阶段上确定全部允许决策所需要的信息。许决策所需要的信息。每个阶段的状态可分为初始状态和终止状态，或称每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段输入状态和输出状态，阶段k的初始状态记作的初始状态记作sk，终止状，终止状态记为态记为sk+1。通常定义阶段的状态即指其初始状态。通常定义阶段的状态即指其初始状态。一般状态变量的取值有一定的范围或允许集合，称一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母的大写字母Sk表示，表示，skSk，。，。A 动态规划问题实例动态规划问题实例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643第第1阶段阶段第第2阶段阶段第第3阶段阶段第第4阶段阶段第第5阶段阶段状态状态1状态状态2状态状态3状态状态4状态状态5状态状态6第第6阶段阶段状态状态7 动态规划的基本概念动态规划的基本概念3.决策决策 当一阶段的状态确定后，可以作出不同的选择从而当一阶段的状态确定后，可以作出不同的选择从而演变到下一阶段的某个状态，这种选择手段称为决策。演变到下一阶段的某个状态，这种选择手段称为决策。在最优控制问题中也称为控制。在最优控制问题中也称为控制。描述决策的变量，称为决策变量。决策变量的允许描述决策的变量，称为决策变量。决策变量的允许取值的范围称为允许决策集合。决策变量是状态变量的取值的范围称为允许决策集合。决策变量是状态变量的函数。用函数。用uk(sk)表示第表示第K阶段处于状态阶段处于状态sk时的决策变量；时的决策变量；Dk(sk)表示表示sk的允许决策集合。的允许决策集合。A 动态规划问题实例动态规划问题实例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643第第1阶段阶段第第2阶段阶段第第3阶段阶段第第4阶段阶段第第5阶段阶段状态状态1状态状态2状态状态3状态状态4状态状态5状态状态6第第6阶段阶段状态状态7u2(B2)=C2D2(B2)=C2,C3,C4 动态规划的基本概念动态规划的基本概念4.策略策略 一个按顺序排列的决策组成的集合。由过程的一个按顺序排列的决策组成的集合。由过程的第第K阶段开始到终止阶段为止的过程称为问题的后阶段开始到终止阶段为止的过程称为问题的后部子过程。由每段的决策按顺序排列组成的决策部子过程。由每段的决策按顺序排列组成的决策函数序列函数序列uk(sk),un(sn)称为称为K子过程策略，简称子过程策略，简称子策略，记为子策略，记为pk,n(sk)。当当K=1时，此决策函数序列称为全过程的一时，此决策函数序列称为全过程的一个策略，简称策略，记为个策略，简称策略，记为p1,n(s1)，即，即:p1,n(s1)=u1(s1),u2(s2),un(sn)A 动态规划问题实例动态规划问题实例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643状态状态1状态状态2状态状态3状态状态4状态状态5状态状态6状态状态7p3,6(C2)=u3(C2),u4(D2),u5(E3),u6(F1)p1,6(A)=u1(A),u2(B1),u3(C2),u4(D2),u5(E3),u6(F1)动态规划的基本概念动态规划的基本概念5.状态转移方程状态转移方程 确定过程由一个状态到另一个状态的演变过程。若确定过程由一个状态到另一个状态的演变过程。若给定第给定第K阶段的状态变量阶段的状态变量sk的值，如果该阶段的决策变的值，如果该阶段的决策变量量uk一经确定，第一经确定，第K+1阶段的状态变量阶段的状态变量sk+1的值也就完全的值也就完全确定。即确定。即sk+1的值随的值随sk和和uk的值变化而变化。这种确定的的值变化而变化。这种确定的对应关系记为对应关系记为:sk+1=Tk(sk,uk(sk)工厂工厂1工厂工厂2工厂工厂3工厂工厂4投资投资x1投资投资x2投资投资x3投资投资x4状态状态s2状态变量状态变量sk:可用于第可用于第k,k+1,n个工厂的投资额。个工厂的投资额。决策变量决策变量xk:第第 k 阶段对第阶段对第 k 个工厂的投资额。个工厂的投资额。状态转移方程状态转移方程:sk+1=sk-xks1=600状态状态s3状态状态s4状态状态s5s2=s1-x1s3=s2-x2s4=s3-x3 动态规划的基本概念动态规划的基本概念6.指标函数和最优值函数指标函数和最优值函数 用来衡量策略或子策略或决策的效果的某种数量指标，用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用用、成本、产值、利润、产量、耗量、距离、时间、效用等等。等等。1)阶段指标函数阶段指标函数(阶段效应阶段效应)用用gk(sk,uk)表示第表示第k段处于段处于sk状态且所作决策为状态且所作决策为uk(sk)时的时的指标，则它就是第指标，则它就是第k段指标函数，简记为段指标函数，简记为gk。动态规划的基本概念动态规划的基本概念 (2)过程指标函数过程指标函数(目标函数目标函数)用用Vk(sk,uk)表示第表示第k子过程的指标函数指标函数，不仅跟子过程的指标函数指标函数，不仅跟当前状态当前状态sk有关，还跟该子过程策略有关，还跟该子过程策略pk(sk)有关，因此它是有关，因此它是sk和和pk(sk)的函数，严格说来，应表示为的函数，严格说来，应表示为:Vk(sk,pk(sk)，实际，实际应用中上式可表示为应用中上式可表示为:Vk(sk,uk)或或Vk(sk)。过程指标函数过程指标函数Vk(sk,uk)通常是描述所实现的全过程或通常是描述所实现的全过程或 k 后部子过程效果优劣的数量指标，它是由各阶段的阶段指后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数标函数 gk(sk,uk)累积形成的。累积形成的。动态规划的基本概念动态规划的基本概念 适于用动态规划求解的问题的过程指标函数适于用动态规划求解的问题的过程指标函数(即目标函即目标函数数)，必须具有关于阶段指标的可分离形式对于，必须具有关于阶段指标的可分离形式对于k部子过程部子过程的指标函数可以表示为的指标函数可以表示为:Vk,n=Vk,n(sk,uk,sk+1,uk+1,sn,un)=gk(sk,uk)gk+1(sk+1,uk+1)gn(sn,un)多阶段决策问题中，常见的目标函数形式之一是取各多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即阶段效应之和的形式，即:=nkiiuisigkV),(有些问题，如系统可靠性问题，其目标函数是取各阶有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如段效应的连乘积形式，如:=nkiiiikusgV),(动态规划的基本概念动态规划的基本概念 指标函数的最优值称为最优值函数，记为指标函数的最优值称为最优值函数，记为fk(sk)。它表示从第它表示从第K阶段的状态开始到第阶段的状态开始到第n阶段的终止状态阶段的终止状态的过程，采取最优策略所得到的指标函数值。的过程，采取最优策略所得到的指标函数值。),()(1,+=nkknkuukksusVoptsfnkLLLL 相应的子策略称为相应的子策略称为sk状态下的最优子策略，记为状态下的最优子策略，记为pk*(sk)；而构成该子策赂的各段决策称为该过程上的；而构成该子策赂的各段决策称为该过程上的最优决策，记为最优决策，记为:uk*(sk),uk+1*(sk+1),un*(sn)。特别当特别当k=1且且s1取值唯一时，取值唯一时，f1(s1)就是问题的最就是问题的最优值，而优值，而p1*就是最优策略。但若取值不唯一就是最优策略。但若取值不唯一,则问题则问题的最优值记为的最优值记为f0有有:)()(11111011*=ssfsfoptfSs 动态规划的基本概念动态规划的基本概念7.多阶段决策问题的数学模型多阶段决策问题的数学模型 综上所述，适于应用动态规划方法求解的一类多综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式的数学模型呈以下形式:=+nkUuSsusTsstusususVVoptfkkkkkkkknnuun,2,1),(),(122111LLLLA 最短路径问题最短路径问题C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643例例6-2:用动态规划求解最短路径。用动态规划求解最短路径。将问题分成五个阶段，第将问题分成五个阶段，第k阶段到达的具体地点用状态变阶段到达的具体地点用状态变量量sk表示，例如表示，例如:s2=B2表示第二阶段到达位置表示第二阶段到达位置B2。这里状态变。这里状态变量取字符值而不是数值。量取字符值而不是数值。将决策定义为到达下一站所选择的路径，例如目前的状将决策定义为到达下一站所选择的路径，例如目前的状态是态是s2=B2，这时决策允许集合包含三个决策，它们是，这时决策允许集合包含三个决策，它们是D2(s2)=D2(B2)=B2C2，B2 C3，B2 C4。最优指标函数最优指标函数 fk(xk)表示从目前状态到表示从目前状态到E的最短路径。终的最短路径。终端条件为端条件为:f7(s7)=f7(G)=0其含义是从其含义是从G到到G的最短路径为的最短路径为0。递推方程为递推方程为:)(),()(11)(+=kkkkksDukksfusVMinsfkkk 最短路径问题最短路径问题贝尔曼最优化原理贝尔曼最优化原理作为一个全过程的最优策略具有这样的性质作为一个全过程的最优策略具有这样的性质:对于最对于最优策略过程中的任意状态而言，无论其过去的状态和决优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为该原理的具体解释是，若某一全过程最优策略为:p1*(s1)=u1*(s1),u2*(s2),un*(sn)则对上述策略中所隐含的任一状态而言，第则对上述策略中所隐含的任一状态而言，第k子过子过程上对应于该状态的最优策略必然包含在上述全过程最程上对应于该状态的最优策略必然包含在上述全过程最优策略优策略p1*中，即为中，即为:pk*(sk)=uk*(sk),uk+1*(sk+1),un*(sn)贝尔曼最优化原理贝尔曼最优化原理基于贝尔曼最优化原理，提出了一种逆序递推法；基于贝尔曼最优化原理，提出了一种逆序递推法；该法的关键在于给出一种递推关系。一般把这种递推关该法的关键在于给出一种递推关系。一般把这种递推关系称为系称为动态规划的函数基本方程动态规划的函数基本方程。对于求最小的加法的计算公式为对于求最小的加法的计算公式为:-=+=+1,2,1,),()(,(min)(0)(11)(11LLnnksfsusgsfsfkkkkkksUukknnkkk贝尔曼最优化原理贝尔曼最优化原理(1)当过程指标函数为当过程指标函数为“和和”的形式时，相应的函数的形式时，相应的函数基本方程为基本方程为:-=+=+1,2,1,),()(,()(0)(1111LLnnksfsusgoptsfsfkkkkkkUukknnkk(2)当过程指标函数为当过程指标函数为“和和”的形式时，相应的函数的形式时，相应的函数基本方程为基本方程为:-=+12111111,n,nk)s(f)s(u,s(gopt)s(f)s(fkkkkkkUukknnkkLL动态规划方法的基本步骤动态规划方法的基本步骤用函数基本方程逆推求解是常用的方法用函数基本方程逆推求解是常用的方法:首先要有效首先要有效地建立动态规划模型地建立动态规划模型,然后再递推求解然后再递推求解,最后得出结论。最后得出结论。正确地建立一个动态规划模型正确地建立一个动态规划模型,是解决问题的关键。是解决问题的关键。正确的动态规划模型正确的动态规划模型,应该满足下列条件应该满足下列条件:1.应将实际问题恰当地分割成应将实际问题恰当地分割成n个子问题个子问题(n个阶段个阶段)通常是根据时间或空间而划分的，或者在经由静态的通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变数学规划模型转换为动态规划模型时，常取静态规划中变量的个数量的个数n。动态规划方法的基本步骤动态规划方法的基本步骤2.正确地定义状态变量正确地定义状态变量sk，使它既能正确地描述过程的状，使它既能正确地描述过程的状态，又能满足无后效性态，又能满足无后效性。要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。要满足无后效性。即如果在某个阶段状态已经给定，要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。作为状态变量来构造动态规划的模型。要满足可知性。即所规定的各段状态变量的值，可要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。状态变量大都选取那种可以进行累计的量。在解静态规划模型时，线性与非线性规划中约束条在解静态规划模型时，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量件的个数，相当于动态规划中状态变量sk的维数约束的维数约束条件所表示的内容，就是状态变量条件所表示的内容，就是状态变量sk 所代表的内容。所代表的内容。动态规划方法的基本步骤动态规划方法的基本步骤3.正确地定义决策变量及各阶段的允许决策集合正确地定义决策变量及各阶段的允许决策集合Uk(sk)一般将问题中待求的量，选作动态规划模型中的决策一般将问题中待求的量，选作动态规划模型中的决策变量，或者在把静态规划模型变量，或者在把静态规划模型(如线性与非线性规划如线性与非线性规划)转换转换为动态规划模型时，常常取前者的变量为动态规划模型时，常常取前者的变量xj为后者的决策变为后者的决策变量量 uk。4.正确地写出状态转移方程正确地写出状态转移方程要能正确反映状态转移规律。如果给定第要能正确反映状态转移规律。如果给定第k阶段状态阶段状态变量变量 sk 的值，则该段的决策变量的值，则该段的决策变量 uk 一经确定，第一经确定，第k+1段段的状态变量的状态变量sk+1的值也就完全确定，即有的值也就完全确定，即有:sk+1=Tk(sk,uk)动态规划方法的基本步骤动态规划方法的基本步骤5.正确地写出目标函数正确地写出目标函数。要满足要满足可分性，即对于所有可分性，即对于所有k后部子过程，其目标函数后部子过程，其目标函数仅取决于状态仅取决于状态sk及其以后的决策及其以后的决策:uk,uk+1,un。即。即它它是定义在全过程和所有后部子过程上的数量函数。是定义在全过程和所有后部子过程上的数量函数。要满足递推关系要满足递推关系。即即:Vk,n(sk,uk,sk+1,uk+1,sn+1)=ksk,uk,Vk+1(sk+1,sn+1)函数严格单调。即函数严格单调。即:ksk,uk,Vk+1(sk+1,sn+1)对变元对变元Rk+1来说要严格单调来说要严格单调。动态规划方法的基本步骤动态规划方法的基本步骤动态规划的四大要素动态规划的四大要素状态变量及其可能集合状态变量及其可能集合skSk决策变量及其允许集合决策变量及其允许集合 uk Uk 状态转移方程状态转移方程 sk+1=Tk(sk,uk)阶段效应阶段效应 Vk(sk,uk)动态规划基本方程动态规划基本方程 -=+=+1,2,1,),()(,()(0)(1111LLnnksfsusgoptsfsfkkkkkkUukknnkk逆推解法逆推解法设已知初始状态为设已知初始状态为s1,并假定最优值函数并假定最优值函数fk(sk)表示第表示第k阶段的初始阶段的初始状态为状态为sk，从，从k阶段到阶段到n阶段所得到的最大效益。阶段所得到的最大效益。从第从第n阶段开始，则有阶段开始，则有:),(max)()(nnnsDxnnxsvsfnnn=解该问题，得到最优解解该问题，得到最优解xn=xn(sn)和最优值和最优值fn(sn)。在第在第n阶段，有阶段，有)(),(max)(111)(1111nnnnnsDxnnsfxsvsfnnn*=-在第在第k阶段，有阶段，有)(),(max)(11)(1+*=kkkkksDxkksfxsvsfkkk如此类推，直到第一阶段有如此类推，直到第一阶段有)(),(max)(22111)(11111sfxsvsfsDx*=由于初始状态由于初始状态s1已知已知,故故x1=x1(s1)和和f1(s1)是确定的，从而是确定的，从而s2=T1(s1,x1)也就可以确定，于是也就可以确定，于是x2=x2(s2)和和f2(s2)也可确定。按照上述递推过程也可确定。按照上述递推过程相反的顺序推算，就可逐步确定每阶段的决策和效益。相反的顺序推算，就可逐步确定每阶段的决策和效益。逆推解法逆推解法例例6-3:用逆推法求解下面问题。用逆推法求解下面问题。0,max3213213221=+=xxxcxxxxxxz按照变量个数划分阶段，该问题是一个三阶段决策问题。按照变量个数划分阶段，该问题是一个三阶段决策问题。状态变量为状态变量为s1,s2,s3,且且s1=c决策变量即为问题中的变量决策变量即为问题中的变量x1,x2,x3各阶段指标函数按乘积方式各阶段指标函数按乘积方式最优值函数最优值函数fk(sk)表示从第表示从第k阶段初始状态阶段初始状态sk 到第到第3阶段所得最大值。阶段所得最大值。设设s1=c，s2+x1=s1,s3+x2=s2,s3=x3则有则有x3=s3，0 x2 s2，0 x1 s1顺推解法顺推解法设已知终止状态为设已知终止状态为sn+1,并假定最优值函数并假定最优值函数fk(sk)表示第表示第k阶段末的阶段末的结束状态为结束状态为sk，从，从1阶段到阶段到k n阶段所得到的最大效益。阶段所得到的最大效益。从第从第1阶段开始，则有阶段开始，则有:),(max)()(111sDx11xsvsf111=解该问题，得到最优解解该问题，得到最优解x1=x1(s2)和最优值和最优值f1(s2)。在第在第n阶段，有阶段，有)(),(max)()(1nn-1nnnsDxnnsfxsvsfnnn*=+由于终止状态由于终止状态sn+1已知已知,故故xn=xn(sn+1)和最优值和最优值fn(sn+1)是确定的，是确定的，按照上述递推过程相反的顺序推算，就可逐步确定每阶段的决按照上述递推过程相反的顺序推算，就可逐步确定每阶段的决策和效益。策和效益。得到最优解得到最优解xn=xn(sn+1)和最优值和最优值fn(sn+1)。例例6-4:用顺推法求解下面问题。用顺推法求解下面问题。0,max3213213221=+=xxxcxxxxxxz最优值函数最优值函数fk(sk+1)表示从第表示从第k阶段末的结束状态阶段末的结束状态sk+1，从第，从第1阶阶段到段到k阶段所得最大值。阶段所得最大值。设设 s2=x1,s3+x2=s3,s3+x3=s4=c则有则有x1=s2，0 x2 s3，0 x3 s4顺推解法顺推解法资源分配问题资源分配问题(离散型离散型)例例6-5:设有设有6万元资金用于万元资金用于4个工厂的扩建，已知每个工厂个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？定对这四个工厂的投资额，使总利润增长额最大？投资额投资额(j)工厂工厂(i)0 100 200 300 400 500 600 10 20 42 60 75 85 90 20 25 45 57 65 70 73 30 18 39 61 78 90 95 40 28 47 65 74 80 85 表表1 利润增长额利润增长额gi(xj)单位单位:百元百元资源分配问题资源分配问题(离散型离散型)解解:把对四个工厂的投资依次看成把对四个工厂的投资依次看成4个阶段的决策过程，确个阶段的决策过程，确定对第定对第k个工厂的投资额看成第个工厂的投资额看成第k个阶段的决策，个阶段的决策，k=1,2,3,4。工厂工厂1工厂工厂2工厂工厂3工厂工厂4投资投资x1投资投资x2投资投资x3投资投资x4状态状态s2状态变量状态变量sk:可用于第可用于第k,k+1,n个工厂的投资额。个工厂的投资额。决策变量决策变量xk:第第 k 阶段对第阶段对第 k 个工厂的投资额。个工厂的投资额。允许决策集允许决策集Dk:100,200,sk状态转移方程状态转移方程:sk+1=sk-xk，s1=600阶段指标函数阶段指标函数 gk:第第 k 阶段投资阶段投资xk元时所产生的利润。元时所产生的利润。最优指标函数最优指标函数 fk(sk):第第 k 阶段状态为阶段状态为sk且采取最佳投资且采取最佳投资策略，从第策略，从第 k 个工厂以及以后的最大总利润。个工厂以及以后的最大总利润。s1=600状态状态s3状态状态s4状态状态s5s2=s1-x1s3=s2-x2s4=s3-x3 =+=+0)()()(max)(55110sfsfsgsfkkkksxkkkk资源分配问题资源分配问题(离散型离散型)投资额投资额(j)工厂工厂(i)0 100 200 300 400 500 60030 28 47 65 74 80 85k=4时，第时，第4个工厂投资时，还有资金个工厂投资时，还有资金s4，若投资于第，若投资于第4个工厂的资金为个工厂的资金为x4，则最大利润为，则最大利润为:)(max)()(max)(44055440444444xgsfxgsfsxsx =+=x4 g4(x4)s4f4(s4)x4*01002003004005006000000028100281000284720047200028476530065300028476574400744000284765748050080500028476574808560085600资源分配问题资源分配问题(离散型离散型)投资额投资额(j)工厂工厂(i)0 100 200 300 400 500 60030 18 39 61 78 90 95k=3时，第时，第3个工厂投资时，还有资金个工厂投资时，还有资金s3，若投资于第，若投资于第3个工厂的资金为个工厂的资金为x3，则最大利润为，则最大利润为:x3 g3+f4 s3f3(s3)x3*01002003004005006000+00000+2818+01002800+47 18+28 39+02004700+65 18+47 39+28 61+0300652000+74 18+65 39+47 61+28 78+0400893000+80 18+74 39+65 61+47 78+28 90+05001083000+85 18+80 39+74 61+65 78+47 90+28 95+0600126300)()(max)()(max)(33433044330334433xsfxgsfxgsfsxsx-+=+=资源分配问题资源分配问题(离散型离散型)投资额投资额(j)工厂工厂(i)0 100 200 300 400 500 6002f3(s3)0 25 45 57 65 70 73 0 28 47 67 89 108 126k=2时，第时，第2个工厂投资时，还有资金个工厂投资时，还有资金s2，若投资于第，若投资于第2个工厂的资个工厂的资金为金为x2，则最大利润为，则最大利润为:x2 g2+f3 s2f2(s2)x2*01002003004005006000+00000+2825+01002800+47 25+28 45+0200531000+67 25+47 45+28 57+0300732000+89 25+67 45+47 57+28 65+040092100,2000+108 25+89 45+67 57+47 65+28 70+05001141000+12625+10845+89 57+67 65+47 70+28 73+0600134200)()(max)()(max)(22322033220222222xsfxgsfxgsfsxsx-+=+=资源分配问题资源分配问题(离散型离散型)投资额投资额(j)工厂工厂(i)0 100 200 300 400 500 6001f2(s2)0 20 42 60 75 85 90 0 28 53 73 92 114 134k=1时，时，s1=600，若投资于第，若投资于第1个工厂的资金为个工厂的资金为x1，则最大利润为，则最大利润为:x1 g1+f2 s1f3(s3)x1*01002003004005006000+13420+11442+92 60+73 75+53 85+28 90+06001340,100,200)()(max)()(max)600()(1121160002211600011111xsfxgsfxgfsfxx-+=+=此时对应最大值此时对应最大值134的有三个值的有三个值，所对应的最优策略分别为所对应的最优策略分别为x1*=0,100,200，再由状态转移方程可得到其它最优策略再由状态转移方程可得到其它最优策略:x1*=0,x2*=200,x3*=300,x4*=100,x1*=100,x2*=100,x3*=300,x4*=100 x1*=200,x2*=100,x3*=200,x4*=100,x1*=200,x2*=200,x3*=0,x4*=200背包问题背包问题设有设有n种物品，每一种物品数量无限。第种物品，每一种物品数量无限。第i种物品每件种物品每件重量为重量为wi，每件价值，每件价值ci。现有一只可装载重量为。现有一只可装载重量为W的背包，的背包，求各种物品应各取多少件放入背包，使背包中物品的价值求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设第最高。这个问题可以用整数规划模型来描述。设第i种物种物品取品取xi件件(i=1,2,n，xi为非负整数为非负整数)，背包中物品的价值，背包中物品的价值为为z，则，则 则则 Max z=c1x1+c2x2+cnxn w1x1+w2x2+wnxn W x1,x2,xn为正整数为正整数1.阶段阶段k:第第k次装载第次装载第k种物品种物品(k=1,2,n)2.状态变量状态变量sk:第第k次装载时背包还可以装载的重量次装载时背包还可以装载的重量3.决策变量决策变量xk:第第k次装载第次装载第k种物品的件数种物品的件数4.决策允许集合决策允许集合:Dk(sk)=xk|0 xk sk/wk，xk为整数为整数；5.状态转移方程状态转移方程:sk+1=sk-wkxk6.阶段指标阶段指标:vk=ckxk7.递推方程递推方程fk(sk)=maxckxk+fk+1(sk+1)=maxckxk+fk+1(sk-wkxk)8.终端条件终端条件:fn+1(sn+1)=0背包问题背包问题例例6-6:已知已知c1=65,c2=80,c3=30,w1=2,w2=3,w3=1,W=5,f4(x4)=0背包问题背包问题k=3时时:k=2时时:k=2时时:)30max)(max)(3/04433/033333333xsfxcsfwsxwsx =+=)3(80max)(max)(2232/03322/022222222xsfxsfxcsfwsxwsx-+=+=)2(65max)(max)(1121/02211/011111111xsfxsfxcsfwsxwsx-+=+=应取第一种物品应取第一种物品2件件,第三种物品第三种物品1件件,最高价值为最高价值为160元元,背背包没有余量。由包没有余量。由f1(x1)得列表可以看出，如果背包得容量为得列表可以看出，如果背包得容量为W=4，W=3，W=2和和W=1时，相应的最优解立即可以得到。时，相应的最优解立即可以得到。设有某种资源总数量为设有某种资源总数量为s1,可投入用于生产可投入用于生产A、B产品。产品。第一年若以数量第一年若以数量u1投入生产投入生产A，剩下的，剩下的s1-u1就投入生产就投入生产B，则可得到收入为则可得到收入为g(u1)+h(s1-u1),其中其中g(u1)和和h(u1)为已知函数，为已知函数，且且g(0)+h(0)=0,这种资源在投入这种资源在投入A、B产品生产后，年终还可产品生产后，年终还可回收再投入生产。设年回收率分别为回收再投入生产。设年回收率分别为0a1和和0b1，则在，则在第一年生产后，回收的资源量合计为第一年生产后，回收的资源量合计为s2=au1+bh(s1-u1)。第二。第二年再将资源数量年再将资源数量s2中的中的u2和和s2-u2分别投入分别投入A、B产品生产，则产品生产，则又可得到收入为又可得到收入为g(u2)+h(s2-u2)。如此进行。如此进行n年，试问应当如年，试问应当如何决定每年投入何决定每年投入A生产的资源量生产的资源量u1,u2,un,才能使总的收入才能使总的收入最大？最大？资源分配问题资源分配问题(连续型连续型)MaxZ=g(u1)+h(s1-u1)+g(u2)+h(s2-u2)+g(un)+h(sn-un)s2 =au1+bh(s1-u1)s3 =au2+bh(s2-u2)sn+1 =aun+bh(sn-un)0uisi+1，i=1，2，n1.状态变量状态变量sk:第第k阶段可投入阶段可投入A、B两种生产的资源量两种生产的资源量2.决策变量决策变量uk:第第k阶段可投入阶段可投入A生产的资源量，则生产的资源量，则sk-uk投入投入B生产的资源量生产的资源量3.状态转移方程状态转移方程:sk+1=auk+b(sk-uk)资源分配问题资源分配问题(连续型连续型)-+=-+-+=+)()(max)()()()(max)(010nnnsunnkkkkkkksukkushugsfusbaufushugsfnnkk例例6-7:某公司有某公司有500辆运输卡车，在超负荷运输辆运输卡车，在超负荷运输(即每天满载即每天满载行驶行驶500km以上以上)情况下，年利润为情况下，年利润为25万元万元/辆，这时卡辆，这时卡车的年损坏率为车的年损坏率为0.3；在低负荷下运输；在低负荷下运输(即每天行驶即每天行驶300km以下以下)情况下，年利润为情况下，年利润为16万元万元/辆。年损坏率为辆。年损坏率为0.1。现要制定一个。现要制定一个5年计划，问每年年初应如何分配在年计划，问每年年初应如何分配在两种不同的负荷下完好车辆运输的卡车数量，使两种不同的负荷下完好车辆运输的卡车数量，使5年内年内的总利润最大？的总利润最大？1.状态变量状态变量sk:第第k年初年初完好卡车数量，其中完好卡车数量，其中s1=5002.决策变量决策变量xk:第第k年初年初分配给超负荷运输的卡车数量分配给超负荷运输的卡车数量，则，则分配给低负荷的卡车数为分配给低负荷的卡车数为 sk-uk3.状态转移方程状态转移方程:sk+1=(1-0.3)xk+(1-0.1)(sk-xk)=0.9sk-0.2xk4.阶段指标函数阶段指标函数 gk(xk):表示第表示第 k 年度利润年度利润,即即 gk(xk)=25xk+16(sk-xk)=16sk+9xk设备负荷分配问题设备负荷分配问题5.最优指标函数最优指标函数fk(sk):第第k年度初完好车辆数为年度初完好车辆数为sk时，时，采用最优策略到第采用最优策略到第 5 年末所产生的最大利润。年末所产生的最大利润。设备负荷分配问题设备负荷分配问题 =+=+0)(1,2,3,4,5)()(max)(66110sfksfxgsfkkkksxkkkk第一年初第一年初:500辆车全部用于低负荷运输。辆车全部用于低负荷运输。第二年初第二年初:还有还有450辆完好的车，也全部用于低负荷运输。辆完好的车，也全部用于低负荷运输。第三年初第三年初:还有还有405辆完好的车，全部用于超负荷运输。辆完好的车，全部用于超负荷运输。第四年初第四年初:还有还有238.5辆完好的车，全部用于超负荷运输。辆完好的车，全部用于超负荷运输。第五年初第五年初:还有还有198.45辆完好的车，全部用于超负荷运输。辆完好的车，全部用于超负荷运输。到第五年末，即第六年初，还剩余到第五年末，即第六年初，还剩余138.15辆完好的车。辆完好的车。实现最大利润约实现最大利润约3.74亿元。亿元。课堂思考课堂思考:某公司有某公司有1000辆运输卡车，在超负荷运输辆运输卡车，在超负荷运输(即即每天满载行驶每天满载行驶500km以上以上)情况下，年利润为情况下，年利润为25万元万元/辆，辆，这时卡车的年损坏率为这时卡车的年损坏率为0.3；在低负荷下运输；在低负荷下运输(即每天行即每天行驶驶300km以下以下)情况下，年利润为情况下，年利润为16万元万元/辆。年损坏率辆。年损坏率为为0.1。现要制定一个。现要制定一个5年计划，问每年年初应如何分配年计划，问每年年初应如何分配在两种不同的负荷下完好车辆运输的卡车数量，使在第在两种不同的负荷下完好车辆运输的卡车数量，使在第5年年末剩余的完好卡车数量为年年末剩余的完好卡车数量为500台，并且使在台，并且使在5年内年内的总利润最大？的总利润最大？设备负荷分配问题设备负荷分配问题例例6-8:某工厂要对一种产品制定今后四个时期的生产计划，据某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的数量如下表所示。估计在今后四个时期内，市场对于该产品的数量如下表所示。该厂生产每批产品的固定成本为该厂生产每批产品的固定成本为3千元，若不生产为千元，若不生产为0；每单位；每单位产品成本为产品成本为1千元；每个时期生产能力所允许的最大生产批量千元；每个时期生产能力所允许的最大生产批量为不超过为不超过6个单位；每个时期末未售出的产品，每单位需支付个单位；每个时期末未售出的产品，每单位需支付存储费用存储费用0.5千元。假定在第一个时期的库存为千元。假定在第一个时期的库存为0，第四个时期，第四个时期库存量为库存量为0。该厂应如何安排各个时期的生产与库存，才能在。该厂应如何安排各个时期的生产与库存，才能在满足市场需要的条件下，成本最小？满足市场需要的条件下，成本最小？时期时期1234需求量需求量2324生产计划问题生产计划问题状态变量状态变量sk:第第k阶段结束时的产品库存量。阶段结束时的产品库存量。决策变量决策变量xk:xk为第为第k阶段该产品的生产量。阶段该产品的生产量。状态转移方程状态转移方程:设设dk为第为第k阶段对产品的需求量，则阶段对产品的需求量，则 sk=sk-1+xk-dkck(xk)表示第表示第k阶段生产产品阶段生产产品xk时的成本费用。时的成本费用。hk(sk)表示第表示第k阶段结束时有库存量阶段结束时有库存量sk所需的存储费用所需的存储费用顺序递推关系为顺序递推关系为:生产计划问题生产计划问题 =+=+=-0)(),min(),()()(max)(00110sfmdssfshxcsfkkkkkkkkkxkkkks ss s设备更新问题设备更新问题企业中经常会遇到一台设备应该使用多少年更新最合企业中经常会遇到一台设备应该使用多少年更新最合算的问题。一般来说，一台设备在比较新时，年运转量大，算的问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费用少，但随着使用年限的增经济收入高，故障少，维修费用少，但随着使用年限的增加，年运转量减少因而收入减少，故障变多，维修费用增加，年运转量减少因而收入减少，故障变多，维修费用增加。如果更新可提高年净收入，但是当年要支出一笔数额加。如果更新可提高年净收入，但是当年要支出一笔数额较大的购买费。较大的购买费。设备更新的一般提法为：在已知一台设备的效益函数设备更新的一般提法为：在已知一台设备的效益函数r(t)，维修费用函数，维修费用函数u(t)及更新费用函数及更新费用函数c(t)条件下，要求条件下，要求在在n年内的每年年初作出决策，是继续使用旧设备还是更年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使使换一台新的，使使n年总效益最大。年总效益最大。设备更新问题设备更新问题例例6-9:某台新设备的年效益及年均维修费、更新净费用如某台新设备的年效益及年均维修费、更新净费用如表所示。试确定今后表所示。试确定今后5年内的更新策略，使总收益最大。年内的更新策略，使总收益最大。役龄役龄项目项目012345效益效益r(t)54.543.7532.5维修费维修费u(t)0.511.522.53更新费更新费c(t)0.51.52.22.533.5设备更新问题设备更新问题阶段阶段k：运行年份；：运行年份；状态变量状态变量sk：第：第k年初，设备已使用过的年数，称役龄年初，设备已使用过的年数，称役龄决策变量决策变量xk：状态转移方程：状态转移方程：=年初继续使用年初继续使用第第年初更新年初更新第第kKkRxk =+=+KxsRxskkkk111阶段指标函数：阶段指标函数：=-=-=RxscurKxsusrxgkkkkkkkkkkkk)()0()0()()()(最优指标函数最优指标函数fk(sk)：第：第k年初，使用一台已用了年初，使用一台已用了sk年的年的设备，到第设备，到第5年末的最大效益，有年末的最大效益，有：=+-=+-=+RxfscurKxsfsusrsfkkkkkkkkkkkkkkk)1()()0()0()()()(max)(111设备更新问题设备更新问题阶段阶段k：运行年份；：运行年份；状态变量状态变量sk：第：第k年初，设备已使用过的年数，称役龄年初，设备已使用过的年数，称役龄决策变量决策变量xk：状态转移方程：状态转移方程：=年初继续使用年初继续使用第第年初更新年初更新第第kKkRxk =+=+KxsRxskkkk111阶段指标函数：阶段指标函数：=-=-=RxscurKxsusrxgkkkkkkkkkkkk)()0()0()()()(最优指标函数最优指标函数fk(sk)：第：第k年初，使用一台已用了年初，使用一台已用了sk年的年的设备，到第设备，到第5年末的最大效益，有年末的最大效益，有：=+-=+-=+RxfscurKxsfsusrsfkkkkkkkkkkkkkkk)1()()0()0()()()(max)(111设备更新问题设备更新问题x5s5g5(x5)f5x*5KR13.533.5K22.52.32.5K31.7522R40.51.51.5R役龄役龄项目项目012345r(t)54.543.7532.5(t)0.511.522.53c(t)0.51.52.22.533.5x4s4g4+f5f4x*4KR166.56.5R24.55.85.8R33.255.55.5Rx3s3g3+f4f3x*3KR19.39.59.5R298.88.8Rx2s2g2+f3f2x*2KR112.312.5 12.5R