第6章动态规划.pptx

动态规划动态规划动动态态规规划划是是解解决决多多阶阶段段决决策策过过程程最最优优化化的的一一种种数数学学方方法法。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)当当过过程程指指标标函函数数为为“和和”的的形形式式时时，相相应应的的函函数数基本方程为基本方程为:-=[phone],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+wnxnW 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,这这种种