第七章 动态规划

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

2、ulti-stage decision process) 状态 x1 阶段1 t1 决策u1 状态 x2 决策u2 阶段2 t2 状态 x3 . 状态 xk 决策uk 阶段k tk 状态 xk+1 . 状 态 xn 决策un 阶段n tn 状 态 xn+1 1.多阶段决策过程的最优化 动态规划方法与“时间”关系很密切， 随着时间过程的发展而决定各时段的决策， 产生一个决策序列，这就是“动态”的意思。 然而它也可以处理与时间无关的静态问题， 只要在问题中人为地引入“时段”因素，就 可以将其转化为一个多阶段决策问题。在本 章中将介绍这种处理方法。 2.多阶段决策问题举例 属于多阶段决策类的问题很多

3、， 例如： 1)1)工厂生产过程工厂生产过程：由于市场需求 是一随着时间而变化的因素，因此， 为了取得全年最佳经济效益，就要在 全年的生产过程中，逐月或者逐季度 地根据库存和需求情况决定生产计划 安排。 |例1：某厂与用户签订了如表所示 的交货合同，表中数字为月底的交 货量。该厂的生产能力为每月400 件，该厂仓库的存货能力为300件。 已知每百件货物的生产费用为 10000元。在进行生产的月份，工 厂还要支付经常费4000元。仓库保 管费为每百件货物每月1000元。假 设开始时及6月底交货后无存货。 月份 123456 交货量 （百件） 125321 2) 2)设备更新问题：设备更新问题：一

4、般企业 用于生产活动的设备，刚买来时故障 少，经济效益高，即使进行转让，处 理价值也高，随着使用年限的增加， 就会逐渐变为故障多，维修费用增加， 可正常使用的工时减少，加工质量下 降，经济效益差，并且，使用的年限 越长、处理价值也越低，自然，如果 卖去旧的买新的，还需要付出更新 费因此就需要综合权衡决定设备的 使用年限，使总的经济效益最好。 例2：下表给出了某单位的预测数据， 现决定考虑到1998年（n=5），试作5 年内的设备更新计划 产品年代机龄收入额维护费新设备购置费旧设备折价 1993 1 2 3 4 5 18 16 16 14 14 8 8 9 9 10 50 20 15 10 5

5、2 1994 0 1 2 3 4 22 21 20 18 16 6 6 8 8 10 50 30 25 20 15 10 1995 0 1 2 3 27 25 24 22 5 6 8 9 52 31 26 21 15 1996 0 1 2 29 26 24 5 5 6 52 33 28 20 1997 0 1 30 28 4 5 55 35 30 199803246040 3) 3)连续生产过程的控制连续生产过程的控制 问题问题：一般化工生产过程中， 常包含一系列完成生产过程的设 备，前一工序设备的输出则是后 一工序设备的输入，因此，应该 如何根据各工序的运行工况，控 制生产过程中各设备的输入

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

7、方案。这 种问题原本要求一次确定出对各企业的 资源分配量，它与时间因素无关，不属 动态决策，但是，我们可以人为地规定 一个资源分配的阶段和顺序，从而使其 变成一个多阶段决策问题( (后面我们将后面我们将 详细讨论这个问题详细讨论这个问题) )。 |例3：某工厂生产a、b、c三种产品， 都使用某种原材料，现有原材料4吨。 江不同数量的这种原料分配给各种 产品时产生的收益如表所示，试确 定使总收益最大的分配法。 abc 0 1 2 3 0 10 17 20 0 6 17 18 0 8 11 11 5 5）运输网络问题）运输网络问题：如图7-1所 示的运输网络，点间连线上的数字 表示两地距离(也可是

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

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

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

11、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, （三）决策、决策变量和允许决策集合（三）决策、决策变量和允许决策集合 所谓决策，就是确定系统过程发展的方案。 决策的实质是关于状态的选择，是决策者从给定 阶段状态出发对下一阶段状态作出的选择。 用以描述决策变化的量称之决策变量和状态 变量一样，决策变量可

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

13、次进 行的阶段决策构成的决策序列称为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，多阶

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

15、某种数量指标，就称为指标函数。 它是定义在全过程或各子过程或各阶段 上的确定数量函数。对不同问题，指标 函数可以是诸如费用、成本、产值、利 润、产量、耗量、距离、时间、效用， 等等。例如：图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)表示处于

16、第k段sk状态且所作决 策为uk时，从sk点到终点f的距离。由此可见， rk(sk,uk)不仅跟当前状态sk有关，还跟该子 过程策略pk(sk)有关，因此它是sk和pk(sk)的 函数，严格说来，应表示为:)(,( kkkk spsr 不 过 实 际 应 用 中 往 往 表 示 为 rk(sk,uk)或rk(sk)。还跟第k子过程上 各段指标函数有关，过程指标函数 rk(sk)通常是描述所实现的全过程或k 后部子过程效果优劣的数量指标，它 是由各阶段的阶段指标函数gk(sk,uk) 累积形成的，适于用动态规划求解的 问题的过程指标函数（即目标函数）， 必须具有关于阶段指标的可分离形 式对于部子

17、过程的指标函数可以表 示为： 式中，表示某种运算，可以是加、减、乘、 除、开方等。 (7-2) ),() 1 , 1 ( 1 ),( ), 1 , 1 ,( , n u n s n g k u k s k g k u k s k g n u n s k u k s k u k s nk r nk r 多阶段决策问题中，常见的目标函 数形式之一是取各阶段效应之和的形式， 即: (7-3) 有些问题，如系统可靠性问题，其 目标函数是取各阶段效应的连乘积形式， 如： (7-4) 总之，具体问题的目标函数表达形 式需要视具体问题而定。 n ki i u i s i g k r),( n ki iiik

18、 usgr),( ( (七七) ) 最优解最优解 用fk(sk)表示第k子过程指标函数 在状态sk下的最优值,即 称fk(sk)为第k子过程上的最优指标函数； nkspsroptsf kkkk spp kk kkk , 2 , 1),(,()( )( 式中“opt”表示最优化，视具体问题取max 或min。 )(,( kkkk spsr 最优化原理 （贝尔曼最优化原理） 作为一个全过程的最优策略具有这样 的性质：对于最优策略过程中的任意状态 而言，无论其过去的状态和决策如何，余 下的诸决策必构成一个最优子策略。该原 理的具体解释是，若某一全过程最优策略 为： )(),(,),(),()( 22

19、1111nnkk sususususp 则对上述策略中所隐含的任一状态而 言，第k子过程上对应于该状态的最优策 略必然包含在上述全过程最优策略p1*中， 即为 )(,),(),()( 11nnkkkkkk susususp 二二. .动态规划求解的多阶段决策问题的特点动态规划求解的多阶段决策问题的特点 通常多阶段决策过程的发展是通过状 态的一系列变换来实现的。一般情况下， 系统在某个阶段的状态转移除与本阶段的 状态和决策有关外，还可能与系统过去经 历的状态和决策有关。因此，问题的求解 就比较困难复杂。而适合于用动态规划方 法求解的只是一类特殊的多阶段决策问题， 即具有“无后效性”的多阶段决策过

20、程。 所谓无后效性，又称马尔柯夫性，是指系 统从某个阶段往后的发展，仅由本阶段所 处的状态及其往后的决策所决定，与系统 以前经历的状态和决策(历史)无关。 例例4 4：为了说明动态规划的基本思想方法和特 点，下面以图7-1所示为例讨论的求最短路问题 的方法。 第一种方法称做全枚举法或穷举法。它的 基本思想是列举出所有可能发生的方案和结果， 再对它们一一进行比较，求出最优方案。这里 从a到f的路程可以分为5个阶段。第一段的走法 有两种，第二段的走法有三种，第三四段的走 法 各 两 种 ， 第 五 段 走 法 一 种 ， 因 此 共 有 2322124条可能的路线，分别算出各 条路线的距离，最后进

21、行比较，可知最优路线。 显然，当组成交通网络的节点很 多时，用穷举法求最优路线的计算工作 量将会十分庞大，而且其中包含着许多 重复计算 第二种方法即所谓“局部最优路径” 法，是说某人从k出发，他并不顾及全 线是否最短，只是选择当前最短途径， “逢近便走”，错误地以为局部最优会 致整体最优，在这种想法指导下，所取 决策必是ab1c1d1e1f，全程 长度是18；显然，这种方法的结果常是 错误的 第三种方法是动态规划方法。动 态规划方法寻求该最短路问题的基本 思想是，首先将问题划分为5个阶段， 每次的选择总是综合后继过程的一并 最优进行考虑，在各段所有可能状态 的最优后继过程都已求得的情况下， 全

22、程的最优路线便也随之得到。 为了找出所有可能状态的最优后 继过程，动态规划方法总是从过程的 最后阶段开始考虑，然后逆着实际过 程发展的顺序，逐段向前递推计算直 至始点。 具体说，此问题先从f开始，因为f是 终点。再无后继过程，故可以接着考虑 第5阶段上所有可能状态e1，e2的最优后 续过程。因为从e1 ,e2到f的路线是唯一 的，所以e1，e2的最优决策和最优后继过 程就是到f，它们的最短距离分别是4和 3。 接着考虑阶段4上可能的状态d1，d2， d3 到f的最优决策和最优后继过程在 状态d1上，到e1是3，到e2是5，综合考 虑后继过程整体最优，取最优决策是到 e1,最优后继过程是d1e1

23、f ，最短距 离是7。同理，状态d2的最优决策是至 e2 ；d3的最优决策是到e1。 同样，当阶段4上所有可能状态的最 优后继过程都已求得后，便可以开始考 虑阶段3上所有可能状态的最优决策和最 优后继过程，如c1的最优决策是到d1,最 优路线是c1d1e1f ，最短距离是12 依此类推，最后可以得到从初始状态a的 最 优 决 策 是 到f最 优 路 线 是 ab1c2d2e2 f ，全程的最短距离是 17。图71中粗实线表示各点到的最优路 线，每点上方括号内的数字表示该点到 终点的最短路距离。 的距离到表示从 的最短距离到表示从 令 ykyk kk vvg fvf , 5 32 46 minm

24、in 7 35 43 minmin 303 404 0 22,2 11,2 2 22, 1 11, 1 1 10,22 10, 11 eed eed d eed eed d fee fee f fg fg f fg fg f fgf fgf f 8 54 53 minmin 10 55 74 minmin 12 58 75 minmin 5 33 41 minmin 33, 3 22, 3 3 22,2 11,2 2 22, 1 11, 1 1 22, 3 11, 3 3 ddc ddc c ddc ddc c ddc ddc c eed eed d fg fg f fg fg f fg fg

25、 f fg fg f 17 155 134 min 22, 11, min 15 97 87 108 min 34,2 23,2 12,2 min 2 13 86 103 122 min 33, 1 22, 1 11, 1 min 1 9 54 58 min 33,4 22,4 min 4 b f ba g b f ba g a f c f cb g c f cb g c f cb g b f c f cb g c f cb g c f cb g b f d f dc g d f dc g c f 综上所述可见，全枚举法虽可找出最 优方案，但不是个好算法，局部最优法 则完全是个错误方法，只有动

26、态规划方 法属较科学有效的算法。它的基本思想 是，把一个比较复杂的问题分解为一系 列同类型的更易求解的子问题，便于应 用计算机。整个求解过程分为两个阶段， 先按整体最优的思想逆序地求出各个子 问题中所有可能状态的最优决策与最优 路线值，然后再顺序地求出整个问题的 最优策略和最优路线。计算过程中，系 统地删去了所有中间非最优的方案组合， 从而使计算工作量比穷举法大为减少。 |多阶段决策过程的最优化 |动态规划的基本概念和基本原理 |动态规划模型的建立与求解 |动态规划在经济管理中的应用 |马氏决策规划简介 1应将实际问题恰当地分割成n个子问题 (n个阶段)。通常是根据时间或空间而划 分的，或者在

27、经由静态的数学规划模型 转换为动态规划模型时，常取静态规划 中变量的个数n，即k=n。 2正确地定义状态变量sk，使它既能正 确地描述过程的状态，又能满足无后效 性动态规划中的状态与一般控制系统 中和通常所说的状态的概念是有所不同 的，动态规划中的状态变量必须具备以 下三个特征： (1)要能够正确地描述受控过程的变化特征。 (2)要满足无后效性。即如果在某个阶段状态已经 给定，那么在该阶段以后，过程的发展不受前 面各段状态的影响，如果所选的变量不具备无 后效性，就不能作为状态变量来构造动态规划 的模型。 (3)要满足可知性。即所规定的各段状态变量的值， 可以直接或间接地测算得到。一般在动态规划

28、 模型中，状态变量大都选取那种可以进行累计 的量。此外，在与静态规划模型的对应关系上， 通常根据经验，线性与非线性规划中约束条件 的个数，相当于动态规划中状态变量sk的维 数而前者约束条件所表示的内容，常就是状 态变量sk所代表的内容。 3正确地定义决策变量及各阶段的允许 决策集合uk(sk)，根据经验，一般将问 题中待求的量，选作动态规划模型中的 决策变量。或者在把静态规划模型(如 线性与非线性规划)转换为动态规划模 型时，常取前者的变量xj为后者的决策 变量uk。 4. 能够正确地写出状态转移方程，至少 要能正确反映状态转移规律。如果给定 第k阶段状态变量sk的值，则该段的决策 变量uk一

29、经确定，第k+1段的状态变量 s k+ 1 的 值 也 就 完 全 确 定 ， 即 有 sk+1=tk(sk ,uk) 5根据题意,正确地构造出目标与变量的函 数关系目标函数，目标函数应满足下 列性质： (1)可分性，即对于所有k后部子过程， 其目标函数仅取决于状态sk及其以后的决 策uk ,uk+1,un,就是说它是定义在全过 程和所有后部子过程上的数量函数。 (2)要满足递推关系，即 (3)函数 对其变元 rk+1来说要严格单调。 ),(, 111nkkkkk ssrus ),(,),( 111111, nkkkkknkkkknk ssrussususr 6写出动态规划函数基本方程 例如常

30、见的指标函数是取各段 指标和的形式 其中 表示第i阶段的指标， 它显然是满足上述三个性质的。所 以上式可以写成 ： n ki iiikk usgsr),()( ),(),( 111 nkkkkkk ssrusgr ),( iii usg 例5 （资源分配问题）某公司有资金10万元，拟 投资于3个项目，已知对第i个项目投资xi万元，收 益为g i (xi)，问应如何分配资金可使总收益最大？ 其中， 解：阶段k=1,2, 3 决策变量uk ：第k个项目的投资额 状态变量sk：在第k阶段时可以用于投资 第k到第3个项目的资金数 指标函数vk,n 3 ki ii ug： ：第k阶段可分配的资金 数为s

31、k时，第k至第3个项 目的最大总收益 状态转移方程： sk+1 = sk -uk 0| kkkk suuu kk sf最优值函数 af1求 边界条件：0 44 sf 资源分配问题的动态规划基本方程： 0 1 , 2 , 3max 44 11 0 sf ksfugsf kkkk su kk kk 建立递推公式： kk su 0max kk sf k=3,2,1 kk ug 11 kk sf ：在第k阶段分配的资金 数为sk时，第k至第3个项目 的最大总收益 kk sf最优值函数 顺序解法(前向动态规划方法) 动态规划的求解有两种基本方法： 逆序解法(后向动态规划方法) 顺序解法的寻优方向与过程的

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

33、法 高维问题的降维法及疏密格子点法 |用逆序解法解例5 2 3 2 3 x0 33 22max)( 33 sxsf s k=3时 k=2时 )(*29max )(9max)( 2 222 x0 332 x0 22 22 22 xsx sfxsf s s 令 2 222222 )(*29)x,(shxsx 由 0) 1(*)(*49 dx dh 22 2 2 xs 解得）是极小点（因为04 4 9 2 2 2 2 22 dx hd sx 2 2 2s 极大值只可能在0,s2端点取得，f2(0)= f2(s2)=9s2 2 2 2s k=1时 2 3221 x0 11 2)(4max)( 11 s

34、sfxsf s 2 * 22222 * 22222 2222 x),()0(2/9 0 x),()0(2/9 2/9)()0( ssffs sffs ssff 此时，时， 此时，时，当 时，解得当 同理可求出x1=s1-1是极小点 20010010, 0 11 ）（时，两个端点，比较fx 0 401010 * 1 11 1 x fx）（时， )2/9(10 2 * 112 sxss再由状态转移方程顺推 10100 3 * 3 * 223 * 2 sxxssx，所以 最优投资方案为全部资金投于第三个项 目，可得最大收益200万元。 |多阶段决策过程的最优化 |动态规划的基本概念和基本原理 |动态

35、规划模型的建立与求解 |动态规划在经济管理中的应用 |马氏决策规划简介 学习方法建议： 第一步 先看问题，充分理解问题 的条件、情况及求解目标。 第二步 结合前面讲到的理论和解 题过程，考虑如何着手进行求解该问题的 工作。分析针对该动态规划问题的“四大 要素、一个方程”这一步在开始时会 感到困难，但是一定要下决心去思考，在 思考过程中深入理解前文讲到的概念和理 论。 第三步 动手把求解思路整理出 来，或者说，把该问题作为习题独立的 来做。 第四步 把自己的求解放到一边， 看书中的求解方法，要充分理解教材中 的论述。 第五步 对照自己的求解，分析 成败。 1.动态规划的四大要素 状态变量及其可能

36、集合xkxk 决策变量及其允许集合ukuk 状态转移方程xk+1=tk (xk,uk) 阶段效应rk (xk,uk) 2. 动态规划基本方程 fn+1(xn+1) = 0 (边界条件) fk(xk) = opt urk ( xk , uk ) + fk+1(xk+1) k = n,1 61 则 max z=c1x1+c2x2+cnxn . w1x1+w2x2+wnxnw x1,x2,xn为正整数(i=1,2,n) 1 .阶段k：第k次装载第k种物品 （k=1,2,n） 2.状态变量sk+1：在第k次开始时，背 包中允许装入前k种物品的重量； 3.决策变量xk：第k次装载第k种物品 的件数； 采

37、用动态规划顺序解法建模求解 s.t 4. 决策允许集合： dk(xk)=dk|0dksk+1/wk,dk为整数； 5. 状态转移方程：sk=sk+1-wkxk 6. 阶段指标：vk=ckxk 7. 递推方程 fk(sk)=maxckxk+fk-1(sk) =maxckxk+fk-1(sk+1-wkxk) 8. 终端条件：f0(s1)=0 例6:对于一个具体问题c1=4，c2=5， c3=6；w1=3，w2=4，w3=5；以及w=10 用动态规划求解 f0(s1)=0 4max)( 4 30 21 21 xxf sx 对于k=1 33222111000 1212888444000f1(s2) 1

38、09876543210s2 * 1 x )4(5 0 max)( 2312 4/32 32 xsfx sx xf 对于k=2 10210110000 13121098554000f2(s3) 101312109121098985854544000c2+f2 210210210101010100000 x2 109876543210s3 * 2 x 13 012, 56 ,13max 0(5),126),10max 5-106max)10( 222 323 210 3 3 ）（ ）（ ， fff xfxf x对于k=3 , 0 x, 1x, 2x * 3 * 2 * 1 最大值为13 67 库存

39、问题 例8 某工厂生产并销售某种产品，已知 今后四个月市场需求预测如表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个月

40、初（发货以前）的库存量； 第k个月的生产量； sk+1=sk+uk-gk； gk(sk ,dk)=ckuk； f8(s8)=0,x8=0； 最优指标函数 fk(sk) fk(xk)=mingk(sk ,uk)+fk+1(sk+1) =minckuk+fk+1(sk-gk+uk) 12 5 . 58 ; 5u 67 ; 4u 5 . 66 ; 3u 75 ; 2u min )2(0*5 . 0)3(min)0(f 3 3 3 3 343 52 3 ufu s u整数 )()()(min)(f 333433 52 33 gusfseucs s u 整数 递推方程 对于u3 max(0,2-s3)u

41、3min(6,5-s3,6-s3),其中s3的 取值范围为0,1,2,3 当s3=0时 2)0(u * 3 对于k=3 u*3(s3) f3( s3) c+e+f4 u3(s3) 0012 8811.512 1211.5812.51211.581312.51211.513.51312.512 210321043215432 3210 s3 对于k=2 u*2(s2) f2( s2) c+e+f3 u2(s2) 3 4 5 13.5 15 15.5 16 14.51713.5161517.51716.515.51817.5171618.518 210432154326543 3 2 10 s2

42、3 15.5 0 u*1(s1) f1( s1) c+f2 u1(s1) 2 21.52221.521 5432 0 s1 21 对于k=1 得出最佳生产计划为，第一个月生产2单位，第二个月生 产5单位，第三个月不生产，第四个月生产4个单位。 总结此类生产存贮问题的基本方程为： 0)( )()()(min)(f 11 1k nn kkkkkk u k sf gusfseucs k 1,.,1,nnk 若最大库存量为q,每月最大生产能力为p.则状 态集合为： )(,min k s0 1 1 n kj k j jj gpgq 允许决策集合为： ,min k u), 0(max n kj k sq

43、k g k s j gp k s k g 74 采购与销售问题 例9某商店在未来的四个月里，准备利用商店的一个 仓库来专门经销某种商品，仓库最大容量为这种商品 1000单位。假定商店每月只能卖出仓库现有的货物。 当商店在某月购货时，下月初才能到货。预测该商店 未来四个月的买卖价格如 下表，假定商店在1月开始 经销时，仓库贮有该商品500单位，试问，如何制定 这四个月的订购与销售计划，使获利最大（不计库存 费）。 1 10 12 2 8 9 3 11 13 4 15 17 月份 （k） 购买单价 （ck） 销售单价 （pk） 解： k=1，2，3，4 状态变量sk xk第k月卖出的货物数量 yk

44、第k月订购的货物数量 状态转移方程： sk+1 = sk + yk -xk pk xk +fk+1（sk+1） ，求f1（500） -ck yk 0 xk sk 0yk 1000-(sk -xk ) 已知：仓库最大容量为1000单位。商店每月只卖出仓库 现有的货物。当商店在某月购货时，下月初才能到 货。 1月开始经销 时，仓库贮有该商品500单位，如何制定四个月的订 购与销售计划，使获利最大（不计库存费）。 第k月的购买单价ck，销售单价pk， fk（sk）=第k月初库存为时sk ， 从第k月到第4月末所获得的最大利润 =max ,0 xk sk ,0yk 1000-(sk -xk ) （ s

45、k + yk xk） 决策变量： s1=500 ,0sk1000 k=2，3，4 第k个月的库存量（含上月的定货） 基本方程： f5（s5）=0 求f1（500） fk（sk）= max pk xk 0 xk sk -ck yk 0yk 1000-(sk -xk ) +fk+1 （sk+yk-xk) k=4，3，2，1 f4（s4）= maxp4 x4 0 x4 s4 -c4 y4 0y4 1000-(s4 x4 ) =p4 s4=17 s4 x*4= s4 y*4= 0 当k=4时 当k=3时 f3（s3）= maxp3 x3 0 x3 s3 -c3 y3 0y3 1000-(s3 x3 )

46、 +f4 （s3+y3-x3) =max13 x3 0 x3 s3 -11 y3 0y3 1000-(s3 x3 ) +17 （s3+y3-x3) ,0s41000 ,0s31000 当k=3时 f3（s3）=max13 x3 0 x3 s3 -11 y3 0y3 1000-(s3 x3 ) +17 （s3+y3-x3) =max-4 x3 0 x3 s3 +6 y3 0y3 1000-(s3 x3 ) +17 s3 求maxz=-4 x3+6 y3 +17s3 0 x3 s3 0y3 1000-(s3 x3 ) 取z=-4 x3+6 y3 +17s3 x3 s3 - x3 +y3 1000-

47、s3 x3, y30 求maxz=-4 x3+6 y3 +17s3 ,0s31000 x*3= s3 y*3=100 0 =6000+13s3 x3 + x1 =s3 - x3 +y3 + x2= 1000-s3 maxz=-4 x3+6 y3 +17s3 x1,x2,x3, y30 x3 y3 x1 x2 -4 6 0 0 z- 17s3 x1 1 0 1 0s3 x2 -1 1 0 1 1000-s3 x3 y3 x1 x2 2 0 0 -6 z-6000-11s3 x1 1 0 1 0s3 y3 -1 1 0 1 1000-s3 x3 y3 x1 x2 0 0 -2 -6 z-6000-

48、13s3 x3 1 0 1 0s3 y3 0 1 1 11000 x*3= s3 y*3=100 0 最优值 z=6000+13s3 x3 s3 - x3 +y3 1000-s3 x3, y30 求maxz=-4 x3+6 y3 +17s3 标准型： 最优解： fk（sk）= max pk xk 0 xk sk -ck yk 0yk 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 y2 0y2 1000-(s2 x2 ) +f3 （s2+y2

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

50、,s1=500 x*1= 500 =17000 ，y*1=0 f2（s2）=x*2= 011000+8s2，y*2=1000-s2 =max12 x1 0 x1 500 -10y1 0y1 1000-(500 x1 ) +11000+8（500+y1-x1) =max4 x1 0 x1 500 -2y1 0y1+ x1 500 +15000 . . 0 1 y . . . . . . 500 11 yx 1 x . f1（500）=17000 x*1= 500 ，y*1=0 f2（s2）=x*2= 011000+8s2，y*2=1000-s2 f3（s3）=x*3= s3 ，y*3=1000 6000+13s3 f4（s4）= 17 s4x*4= s4，y*4= 0 xk第k月卖出的货物数量 yk第k月订购的货物数量 sk+1 = sk + yk -xk fk（sk）=第k月初库存为时sk ， 从第k月到第4月末所获得的最大利润 结论：当第1个月初库存为时500时， 4个月能获