运筹学胡运权第07章

1、|多阶段决策过程的最优化|动态规划的基本概念和基本原理|动态规划模型的建立与求解|动态规划在经济管理中的应用|马氏决策规划简介美国数学家贝尔曼（Richard. Bellman)创始时间上个世纪50年代创始人|是运筹学的一个主要分支|是解决多阶段决策过程的最优化的一种方法多阶段决策过程:资源分配问题生产计划与库存问题投资问题装载问题排序问题生产过程的最优控制等多阶段决策过程的最优化的目标:达到整个活动过程的总体效果最优主要用于解决:最优路径问题动态规划模型分类离散确定型离散随机型连续确定型连续随机型多阶段决策问题(Multi-Stage decision process)状态 x1阶段1T1决

2、策u1状态 x2决策u2阶段2T2状态 x3.状态 xk决策uk阶段kTk状态 xk+1.状态 xn决策un阶段nTn状态 xn+1 动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入“时段”因素,就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。2.多阶段决策问题举例 属于多阶段决策类的问题很多,例如: 1)1)工厂生产过程工厂生产过程:由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需

3、求情况决定生产计划安排。|例1:某厂与用户签订了如表所示的交货合同,表中数字为月底的交货量。该厂的生产能力为每月400件,该厂仓库的存货能力为300件。已知每百件货物的生产费用为10000元。在进行生产的月份,工厂还要支付经常费4000元。仓库保管费为每百件货物每月1000元。假设开始时及6月底交货后无存货。月份123456交货量（百件）125321 2) 2)设备更新问题设备更新问题: :一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长

4、、处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费因此就需要综合权衡决定设备的使用年限,使总的经济效益最好。例2:下表给出了某单位的预测数据,现决定考虑到1998年（n=5）,试作5年内的设备更新计划产品年代机龄收入额维护费新设备购置费旧设备折价199312345181616141488991050201510521994012342221201816668810503025201510199501232725242256895231262115199601229262455652332820199701302845553530199803246040 3) 3)连续生产过程的控制连

5、续生产过程的控制问题问题:一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大。 以上所举问题的发展过程都与时间因素有关,因此在这类多阶段决策问题中,阶段的划分常取时间区段来表示,并且各个阶段上的决策往往也与时间因素有关,这就使它具有了“动态”的含义,所以把处理这类动态问题的方法称为动态规划方法。 不过,实际中尚有许多不包含时间因素的一类“静态”决策问题,就其本质而言是一次决策问题,是非动态决策问题,但是也可以人为地引入阶段的概念当作多阶段决策问题,应用动态规划方法加以

6、解决。 4 4）资源分配问题）资源分配问题: :便属于这类静态问题。如:某工业部门或公司,拟对其所属企业进行稀缺资源分配,为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量,它与时间因素无关,不属动态决策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题( (后面我们将详细讨论后面我们将详细讨论这个问题这个问题) )。|例3:某工厂生产A、B、C三种产品,都使用某种原材料,现有原材料4吨。江不同数量的这种原料分配给各种产品时产生的收益如表所示,试确定使总收益最大的分配法。ABC01230101720061718081111 5

7、5）运输网络问题）运输网络问题:如图7-1所示的运输网络,点间连线上的数字表示两地距离(也可是运费、时间等),要求从A至F的最短路线。 这种运输网络问题也是静态决策问题。但是,按照网络中点的分布,可以把它分为5个阶段,而作为多阶段决策问题来研究。|多阶段决策过程的最优化|动态规划的基本概念和基本原理|动态规划模型的建立与求解|动态规划在经济管理中的应用|马氏决策规划简介 一、动态规划的基本概念一、动态规划的基本概念 使用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型,同时也为了今后叙述和讨论方便,这里需要对动态规划的下述一些基本术语进一步加以说明和定义: ( (一一) ) 阶

8、段和阶段变量阶段和阶段变量 为了便于求解和表示决策及过程的发展顺序,而把所给问题恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的阶段。一个阶段,就是需要作出一个决策的子问题,通常,阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量,一般以k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目,图71所示的最短路问题就是一个四阶段决策过程。 （二）状态、状态变量和可能状态（二）状态、状态变量和可能状态集集 1.状态与状态变量。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量,称为状态。反映状态变化的量叫做状态变量。状态变量

9、必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后,每个阶段的状态可分为初始状态和终止状态,或称输入状态和输出状态,阶段k的初始状态记作sk,终止状态记为sk+1。但为了清楚起见,通常定义阶段的状态即指其初始状态。 2可能状态集 一般状态变量的取值有一定的范围或允许集合,称为可能状态集,或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示,skSk,可能状态集可以是一离散取值的集合,也可以为一连续的取值区间,视具体问题而定在图71所示的最短路问题中,第一阶段状态为A,状态变量s1的状态集合S1=A;第二阶段则有两个状态:B1

10、 ,B2, 状态变量s2的状态集合S2=B1 ,B2 ;第三阶段有四个状态:C1 ,C2 ,C3 ,C4状态变量s3的状态集合S3=C1 ,C2 ,C3 ,C4 ;第四阶段则有三个状态: D1 ,D ,D3 , 状态变量s4的状态集合S4=C1 ,C2 ,C3 ;第五阶段则有两个状态E1 ,E2状态变量s5的状态集合S5=E1 ,E2, （三）决策、决策变量和允许决策集合（三）决策、决策变量和允许决策集合 所谓决策,就是确定系统过程发展的方案。决策的实质是关于状态的选择,是决策者从给定阶段状态出发对下一阶段状态作出的选择。 用以描述决策变化的量称之决策变量和状态变量一样,决策变量可以用一个数,

11、一组数或一向量来描述,也可以是状态变量的函数,记以uk= uk(sk),表示于阶段k状态sk时的决策变量。 决策变量的取值往往也有一定的允许范围,称之允许决策集合。决策变量uk(sk)的允许决策集用Uk(sk)表示, uk(sk) Uk(sk)允许决策集合实际是决策的约束条件。 （四）策略和允许策略集合（四）策略和允许策略集合 策略(Policy)也叫决策序列策略有全过程策略和k部子策略之分,全过程策略是指具有n个阶段的全部过程,由依次进行的n个阶段决策构 成 的 决 策 序 列 , 简 称 策 略 , 表 示 为p1,nu1,u2,un。从k阶段到第n阶段,依次进行的阶段决策构成的决策序列称

12、为k部子策略,表示为pk,nuk,uk+1,un ,显然当k=1时的k部子策略就是全过程策略。 在实际问题中,由于在各个阶段可供选择的决策有许多个,因此,它们的不同组合就构成了许多可供选择的决策序列(策略),由它们组成的集合,称之允许策略集合,记作P1,n ,从允许策略集中,找出具有最优效果的策略称为最优策略。 （五）状态转移方程（五）状态转移方程 系统在阶段k处于状态sk,执行决策uk(sk)的结果是系统状态的转移,即系统由阶段k的初始状态sk转移到终止状态sk+1 ,或者说,系统由k阶段的状态sk转移到了阶段k+1的状态sk+1,多阶段决策过程的发展就是用阶段状态的相继演变来描述的。 对于

13、具有无后效性的多阶段决策过程,系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定,与系统过去的状态s1,s2, ,sk-1及其决策u1(s1), u2(s2)uk-1(sk-1)无关。系统状态的这种转移,用数学公式描述即有:(7-1)(,(1kskukskTks 通常称式(7-1)为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式,但是它们的状态转移,还是有一定规律可循的。 ( (六六) ) 指标函数指标函数 用来衡量策略或子策略或决策的效果的某种数量指标,就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题,指标

14、函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用,等等。例如:图71的指标就是运费。 (1)阶段指标函数（也称阶段效应）。用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标,则它就是第k段指标函数,简记为gk 。图7-1的gk值就是从状态sk到状态sk+1的距离。譬如,gk(A,B1)=4,即A到B1的距离为3。 (2)过程指标函数（也称目标函数）。用Rk(sk,uk)表示第k子过程的指标函数。如图7-1的Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时,从sk点到终点F的距离。由此可见,Rk(sk,uk)不仅跟当前状态sk有关,还跟该子过程

15、策略pk(sk)有关,因此它是sk和pk(sk)的函数,严格说来,应表示为:)(,(kkkkspsR 不 过 实 际 应 用 中 往 往 表 示 为Rk(sk,uk)或Rk(sk)。还跟第k子过程上各段指标函数有关,过程指标函数Rk(sk)通常是描述所实现的全过程或k后部子过程效果优劣的数量指标,它是由各阶段的阶段指标函数gk(sk,uk)累积形成的,适于用动态规划求解的问题的过程指标函数（即目标函数）,必须具有关于阶段指标的可分离形式对于部子过程的指标函数可以表示为: 式中,表示某种运算,可以是加、减、乘、除、开方等。 (7-2),()1,1(1),(),1,1,(,nunsngkukskg

16、kukskgnunskukskuksnkRnkR 多阶段决策问题中,常见的目标函数形式之一是取各阶段效应之和的形式,即: (7-3) 有些问题,如系统可靠性问题,其目标函数是取各阶段效应的连乘积形式,如: (7-4) 总之,具体问题的目标函数表达形式需要视具体问题而定。nkiiuisigkR),(nkiiiikusgR),( ( (七七) ) 最优解最优解 用fk(sk)表示第k子过程指标函数 在状态sk下的最优值,即 称fk(sk)为第k子过程上的最优指标函数;nkspsRoptsfkkkksPpkkkKk, 2 , 1),(,()()(式中“OPT”表示最优化,视具体问题取max或min。

17、)(,(kkkkspsR 最优化原理 （贝尔曼最优化原理） 作为一个全过程的最优策略具有这样的性质:对于最优策略过程中的任意状态而言,无论其过去的状态和决策如何,余下的诸决策必构成一个最优子策略。该原理的具体解释是,若某一全过程最优策略为:)(),(,),(),()(221111nnkksususususp 则对上述策略中所隐含的任一状态而言,第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1*中,即为)(,),(),()(11nnkkkkkksusususp 二二. .动态规划求解的多阶段决策问题的特点动态规划求解的多阶段决策问题的特点 通常多阶段决策过程的发展是通过状态的一

18、系列变换来实现的。一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,还可能与系统过去经历的状态和决策有关。因此,问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即具有“无后效性”的多阶段决策过程。所谓无后效性,又称马尔柯夫性,是指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策所决定,与系统以前经历的状态和决策(历史)无关。 例例4 4: :为了说明动态规划的基本思想方法和特点,下面以图7-1所示为例讨论的求最短路问题的方法。 第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果,再对它们一一进行比较,求出

19、最优方案。这里从A到F的路程可以分为5个阶段。第一段的走法有两种,第二段的走法有三种,第三四段的走法各两种,第五段走法一种,因此共有2322124条可能的路线,分别算出各条路线的距离,最后进行比较,可知最优路线。 显然,当组成交通网络的节点很多时,用穷举法求最优路线的计算工作量将会十分庞大,而且其中包含着许多重复计算 第二种方法即所谓“局部最优路径”法,是说某人从k出发,他并不顾及全线是否最短,只是选择当前最短途径,“逢近便走”,错误地以为局部最优会致整体最优,在这种想法指导下,所取决策必是AB1C1D1E1F,全程长度是18;显然,这种方法的结果常是错误的 第三种方法是动态规划方法。动态规划

20、方法寻求该最短路问题的基本思想是,首先将问题划分为5个阶段,每次的选择总是综合后继过程的一并最优进行考虑,在各段所有可能状态的最优后继过程都已求得的情况下,全程的最优路线便也随之得到。 为了找出所有可能状态的最优后继过程,动态规划方法总是从过程的最后阶段开始考虑,然后逆着实际过程发展的顺序,逐段向前递推计算直至始点。 具体说,此问题先从F开始,因为F是终点。再无后继过程,故可以接着考虑第5阶段上所有可能状态E1,E2的最优后续过程。因为从E1 ,E2到F的路线是唯一的,所以E1,E2的最优决策和最优后继过程就是到F,它们的最短距离分别是4和3。 接 着 考 虑 阶 段 4 上 可 能 的 状

21、态D1,D2,D3 到F的最优决策和最优后继过程在状态D1上,到E1是3,到E2是5,综合考虑后继过程整体最优,取最优决策是到E1,最优后继过程是D1E1F ,最短距离是7。同理,状态D2的最优决策是至E2 ;D3的最优决策是到E1。 同样,当阶段4上所有可能状态的最优后继过程都已求得后,便可以开始考虑阶段3上所有可能状态的最优决策和最优后继过程,如C1的最优决策是到D1,最优路线是C1D1E1F ,最短距离是12依此类推,最后可以得到从初始状态A的最优决策是到F最优路线是AB1C2D2E2 F ,全程的最短距离是17。图71中粗实线表示各点到的最优路线,每点上方括号内的数字表示该点到终点的最

22、短路距离。的距离到表示从的最短距离到表示从令ykykkkvvgFvf,53246minmin73543minmin303404022,211,2222, 111, 1110,2210, 11EEDEEDDEEDEEDDFEEFEEFfgfgffgfgffgffgff85453minmin105574minmin125875minmin53341minmin33, 322, 3322,211,2222, 111, 1122, 311, 33DDCDDCCDDCDDCCDDCDDCCEEDEEDDfgfgffgfgffgfgffgfgf17155134min22,11,min159787108mi

23、n34,223,212,2min21386103122min33, 122, 111, 1min195458min33,422,4min4BfBAgBfBAgAfCfCBgCfCBgCfCBgBfCfCBgCfCBgCfCBgBfDfDCgDfDCgCf 综上所述可见,全枚举法虽可找出最优方案,但不是个好算法,局部最优法则完全是个错误方法,只有动态规划方法属较科学有效的算法。它的基本思想是,把一个比较复杂的问题分解为一系列同类型的更易求解的子问题,便于应用计算机。整个求解过程分为两个阶段,先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值,然后再顺序地求出整个问题的最优

24、策略和最优路线。计算过程中,系统地删去了所有中间非最优的方案组合,从而使计算工作量比穷举法大为减少。|多阶段决策过程的最优化|动态规划的基本概念和基本原理|动态规划模型的建立与求解|动态规划在经济管理中的应用|马氏决策规划简介 1应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的,或者在经由静态的数学规划模型转换为动态规划模型时,常取静态规划中变量的个数n,即k=n。2正确地定义状态变量sk,使它既能正确地描述过程的状态,又能满足无后效性动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的,动态规划中的状态变量必须具备以下三个特征: (1)要能够正确地描

25、述受控过程的变化特征。(2)要满足无后效性。即如果在某个阶段状态已经给定,那么在该阶段以后,过程的发展不受前面各段状态的影响,如果所选的变量不具备无后效性,就不能作为状态变量来构造动态规划的模型。(3)要满足可知性。即所规定的各段状态变量的值,可以直接或间接地测算得到。一般在动态规划模型中,状态变量大都选取那种可以进行累计的量。此外,在与静态规划模型的对应关系上,通常根据经验,线性与非线性规划中约束条件的个数,相当于动态规划中状态变量sk的维数而前者约束条件所表示的内容,常就是状态变量sk所代表的内容。3正确地定义决策变量及各阶段的允许决策集合Uk(sk),根据经验,一般将问题中待求的量,选作

26、动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时,常取前者的变量xj为后者的决策变量uk。4. 能够正确地写出状态转移方程,至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值,则该段的决策变量uk一经确定,第k+1段的状态变量sk+1的值也就完全确定,即有sk+1=Tk(sk ,uk)5根据题意,正确地构造出目标与变量的函数关系目标函数,目标函数应满足下列性质: (1)可分性,即对于所有k后部子过程,其目标函数仅取决于状态sk及其以后的决策uk ,uk+1,un,就是说它是定义在全过程和所有后部子过程上的数量函数。 (2)要满足递推关系,即

27、(3)函数 对其变元Rk+1来说要严格单调。),(,111nkkkkkssRus),(,),(111111,nkkkkknkkkknkssRussususR6写出动态规划函数基本方程 例如常见的指标函数是取各段指标和的形式 其中 表示第i阶段的指标,它显然是满足上述三个性质的。所以上式可以写成 :nkiiiikkusgsR),()(),(),(111nkkkkkkssRusgR),(iiiusg例5 （资源分配问题）某公司有资金10万元,拟投资于3个项目,已知对第i个项目投资xi万元,收益为g i (xi),问应如何分配资金可使总收益最大?其中,解:阶段k=1,2, 3决策变量uk：第k个项目

28、的投资额状态变量sk：在第k阶段时可以用于投资 第k到第3个项目的资金数指标函数Vk,n3kiiiug：:第k阶段可分配的资金数为sk时,第k至第3个项目的最大总收益状态转移方程：sk+1 = sk -uk0|kkkksuuUkksf最优值函数 af1求边界条件:044sf资源分配问题的动态规划基本方程: 01 , 2 , 3max44110sfksfugsfkkkksukkkk建立递推公式:kksu 0maxkksfk=3,2,1kkug11kksf:在第k阶段分配的资金数为sk时,第k至第3个项目的最大总收益 kksf最优值函数顺序解法(前向动态规划方法)动态规划的求解有两种基本方法:逆序

29、解法(后向动态规划方法)顺序解法的寻优方向与过程的行进方向相同,计算时从第一段开始逐段向后递推,计算后一阶段要用到前一阶段的求优结果,最后一段计算的结果就是全过程的最优结果。顺序解法与逆序解法本质上并无区别,一般地说,当初始状态给定时可用逆序解法,当终止状态给定时可用顺序解法。|两种解法区别1.状态转移方式不同 2.指标函数的定义不同逆序：顺序：sk+1=Tk(sk ,uk)sk=Tk(sk+1,uk)3.基本方程形式不同当指标函数为阶段指标和形式,逆序解法顺序解法解法离散型连续型:分段穷举法:解析方法或线性规划方法没有固定的方法具体模型具体分析要求:经验、技巧、灵活难!连续变量的离散化解法高

30、维问题的降维法及疏密格子点法|用逆序解法解例52323x03322max)(33sxsfsk=3时k=2时)(*29max)(9max)(2222x0332x0222222xsxsfxsfss令2222222)(*29)x,(shxsx由0) 1(*)(*49dxdh2222xs解得）是极小点（因为0449222222dxhdsx222s极大值只可能在0,s2端点取得，f2(0)=f2(s2)=9s2222sk=1时23221x0112)(4max)(11ssfxsfs2*22222*222222222x),()0(2/90 x),()0(2/92/9)()0(ssffssffsssff此时，

31、时，此时，时，当时，解得当同理可求出x1=s1-1是极小点20010010, 011）（时，两个端点，比较fx0401010*1111xfx）（时，)2/9(102*112sxss再由状态转移方程顺推101003*3*223*2sxxssx，所以最优投资方案为全部资金投于第三个项目,可得最大收益200万元。|多阶段决策过程的最优化|动态规划的基本概念和基本原理|动态规划模型的建立与求解|动态规划在经济管理中的应用|马氏决策规划简介 学习方法建议: 第一步 先看问题,充分理解问题的条件、情况及求解目标。 第二步 结合前面讲到的理论和解题过程,考虑如何着手进行求解该问题的工作。分析针对该动态规划问

32、题的“四大要素、一个方程”这一步在开始时会感到困难,但是一定要下决心去思考,在思考过程中深入理解前文讲到的概念和理论。 第三步 动手把求解思路整理出来,或者说,把该问题作为习题独立的来做。 第四步 把自己的求解放到一边,看书中的求解方法,要充分理解教材中的论述。 第五步 对照自己的求解,分析成败。 1.动态规划的四大要素 状态变量及其可能集合xkXk 决策变量及其允许集合ukUk 状态转移方程xk+1=Tk (xk,uk) 阶段效应rk (xk,uk) 2. 动态规划基本方程 fn+1(xn+1) = 0 (边界条件) fk(xk) = opt urk ( xk , uk ) + fk+1(x

33、k+1) k = n,1602021/3/171 .阶 段k: 第k次 装 载 第k种 物 品（k=1,2,n）2.状态变量sk+1:在第k次开始时,背包中允许装入前k种物品的重量;3.决策变量xk:第k次装载第k种物品的件数;采用动态规划顺序解法建模求解s.t4. 决策允许集合:Dk(xk)=dk|0dksk+1/wk,dk为整数;5. 状态转移方程:sk=sk+1-wkxk6. 阶段指标:vk=ckxk7. 递推方程 fk(sk)=maxckxk+fk-1(sk) =maxckxk+fk-1(sk+1-wkxk)8. 终端条件:f0(s1)=04max)(4302121xxfsx 对于k=

34、1332221110001212888444000f1(s2)109876543210s2*1x)4(50max)(23124/3232xsfxsxxf对于k=21021011000013121098554000f2(s3)101312109121098985854544000c2+f2210210210101010100000 x2109876543210s3*2x13012, 56 ,13max0(5),126),10max5-106max)10(22232321033）（）（，fffxfxfx对于k=3, 0 x, 1x, 2x*3*2*1最大值为13库存问题662021/3/17例8

35、某工厂生产并销售某种产品,已知今后四个月市场需求预测如表7-7,又每月生产j单位产品费用为: C(j)= 0(j=0) 3+j(j=1,2,6)(千元) 每月库存j单位产品的费用为E(j)=0.5j(千元),该厂最大库存容量为3单位,每月最大生产能力为6单位,计划开始和计划期末库存量都是零。试制定四个月的生产计划,在满足用户需求条件下总费用最小。假设第i+1个月的库存量是第i个月可销售量与该月用户需求量之差;而第i个月的可销售量是本月初库存量与产量之和。阶段k状态变量sk决策变量uk状态转移方程阶段指标终端条件月份,k=1,2,3,4;第k个月初（发货以前）的库存量;第k个月的生产量;sk+1

36、=sk+uk-gk;gk(sk ,dk)=ckuk;f8(s8)=0,x8=0;最优指标函数fk(sk)125 . 58 ; 5u67 ; 4u5 . 66 ; 3u75 ; 2umin)2(0*5 . 0)3(min)0(f3333343523ufusu整数)()()(min)(f3334335233guSfsEuCssu整数递推方程对于u3 max(0,2-s3)u3min(6,5-s3,6-s3),其中s3的取值范围为0,1,2,3当s3=0时2)0(u*3对于K=3u*3(s3)f3( s3)C+E+f4u3(s3)00128811.5121211.5812.51211.581312.

37、51211.513.51312.5122103210432154323210s3对于K=2u*2(s2)f2( s2)C+E+f3u2(s2) 3 4 513.5 15 15.5 1614.51713.5161517.51716.515.51817.5171618.5182104321543265433 2 10s2315.50u*1(s1)f1( s1)C+f2u1(s1)221.52221.52154320s121对于K=1得出最佳生产计划为,第一个月生产2单位,第二个月生产5单位,第三个月不生产,第四个月生产4个单位。总结此类生产存贮问题的基本方程为:0)()()()(min)(f111

38、knnkkkkkkuksfguSfsEuCsk1,.,1,nnk若最大库存量为q,每月最大生产能力为p.则状态集合为:)(,minks011nkjkjjjgpgq允许决策集合为:,minku), 0(maxnkjksqkgksjgpkskg采购与销售问题732021/3/17例9某商店在未来的四个月里,准备利用商店的一个仓库来专门经销某种商品,仓库最大容量为这种商品1000单位。假定商店每月只能卖出仓库现有的货物。当商店在某月购货时,下月初才能到货。预测该商店未来四个月的买卖价格如 下表,假定商店在1月开始经销时,仓库贮有该商品500单位,试问,如何制定这四个月的订购与销售计划,使获利最大（不

39、计库存费）。 1 10 12 2 8 9 3 11 13 4 15 17月份（k）购买单价 （ck）销售单价 （pk）解： k=1，2，3，4状态变量skxk第k月卖出的货物数量yk第k月订购的货物数量状态转移方程:sk+1 = sk + yk -xk pk xk+fk+1（sk+1）,求f1（500）-ck yk0 xk sk 0yk 1000-(sk -xk )已知:仓库最大容量为1000单位。商店每月只卖出仓库 现有的货物。当商店在某月购货时,下月初才能到 货。 1月开始经销 时,仓库贮有该商品500单位,如何制定四个月的订 购与销售计划,使获利最大（不计库存费）。第k月的购买单价ck,

40、销售单价pk,fk（sk）=第k月初库存为时sk ， 从第k月到第4月末所获得的最大利润 =max ,0 xk sk ,0yk 1000-(sk -xk )（ sk + yk xk）决策变量:s1=500 ,0sk1000 k=2，3，4第k个月的库存量（含上月的定货）基本方程:f5（s5）=0求f1（500）fk（sk）= max pk xk 0 xk sk -ck yk0yk 1000-(sk -xk )+fk+1 （sk+yk-xk)k=4,3,2,1f4（s4）=maxp4 x4 0 x4 s4 -c4 y40y4 1000-(s4 x4 )=p4 s4=17 s4x*4= s4y*4

41、= 0当k=4时当k=3时f3（s3）=maxp3 x3 0 x3 s3 -c3 y30y3 1000-(s3 x3 )+f4 （s3+y3-x3)=max13 x3 0 x3 s3 -11 y30y3 1000-(s3 x3 )+17 （s3+y3-x3),0s41000 ,0s31000 当k=3时f3（s3）=max13 x3 0 x3 s3 -11 y30y3 1000-(s3 x3 )+17 （s3+y3-x3)=max-4 x3 0 x3 s3 +6 y30y3 1000-(s3 x3 )+17 s3求maxZ=-4 x3+6 y3 +17s30 x3 s3 0y3 1000-(s

42、3 x3 )取Z=-4 x3+6 y3 +17s3x3 s3 - x3 +y3 1000-s3 x3, y30 求maxZ=-4 x3+6 y3 +17s3,0s31000 x*3= s3y*3=100 0=6000+13s3x3 + x1 =s3 - x3 +y3 + x2= 1000-s3 maxZ=-4 x3+6 y3 +17s3 x1,x2,x3, y30 x3 y3 x1 x2-4 6 0 0Z- 17s3 x1 1 0 1 0s3x2-1 1 0 11000-s3x3 y3 x1 x22 0 0 -6Z-6000-11s3 x1 1 0 1 0s3y3-1 1 0 11000-s3

43、x3 y3 x1 x20 0 -2 -6Z-6000-13s3 x3 1 0 1 0s3y3 0 1 1 11000 x*3= s3y*3=100 0最优值 Z=6000+13s3x3 s3 - x3 +y3 1000-s3 x3, y30 求maxZ=-4 x3+6 y3 +17s3标准型:最优解:fk（sk）= max pk xk 0 xk sk -ck yk0yk 1000-(sk -xk )+fk+1 （sk+yk-xk)f3（s3）=x*3= s3,y*3=100 06000+13s3当k=2时f2（s2）=maxp2 x2 0 x2 s2 -c2 y20y2 1000-(s2 x2

44、 )+f3 （s2+y2-x2),0s21000 =max9 x2 0 x2 s2 -8 y20y2 1000-(s2 x2 )+6000+13 （s2+y2-x2)=max-4 x2 0 x2 s2 +5 y20y2 1000-(s2 x2 )+13 s2+6000 x*2= 0=11000+8s2，y*2=1000-s2fk（sk）= max pk xk 0 xk sk -ck yk0yk 1000-(sk -xk )+fk+1 （sk+yk-xk)当k=1时f1（s1）=maxp1 x1 0 x1 s1 -c1 y10y1 1000-(s1 x1 )+f2 （s1+y1-x1),s1=500 x*1= 500=17000,y*1=0f2（s2）=x*2= 011000+8s2，y*2=1000-s2=max12 x1 0 x1