动态规划 本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例.

Presentation on theme: "动态规划 本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例."— Presentation transcript:

1 动态规划 本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例

2 动态规划 动态规划是解决多阶段决策过程最优化的一种数学方法。1951年美国数学家贝尔曼等人根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。贝尔曼的《动态规划》于1957年出版。 动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。

3 动态规划 所谓多阶段决策问题是指这样的决策问题:其过程可分为若干个相互联的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。当每一阶段的决策选定以后，就构成一个决策序列，称为一个策略，它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。 状态 x1 阶段1 T1 决策u1 x2 决策u2 阶段2 T2 x3 ... xk 决策uk 阶段k Tk xk+1 xn 决策un 阶段n Tn xn+1

4 多阶段决策问题 工厂生产过程:由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。 设备更新问题:一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费．因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。

5 多阶段决策问题 连续生产过程的控制问题:一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。 资源分配问题:资源分配问题属于静态问题。如某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题。

6 动态规划求解的特点 通常多阶段决策过程的发展是通过状态的一系列变换来实现的。
一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。 适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。 　 无后效性(又称马尔柯夫性)是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。

7 动态规划问题实例 例6-1 给定一个线路网络，要从A向F铺设一条输油管，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？ C1
8 2 E1 D1 3 B1 3 3 2 C2 5 F1 6 4 5 5 5 1 A E2 D2 G 2 3 C3 2 3 3 8 F2 7 3 6 B2 3 6 8 6 D3 3 E3 4 C4

8 动态规划 C1 E1 D1 B1 C2 F1 A E2 D2 G C3 F2 B2 D3 E3 C4 6 1 8 2 3 3 3 2 5 4
7 3 6 B2 3 6 8 6 D3 3 E3 4 C4

9 动态规划的基本概念 1.阶段与阶段变量 为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称为多段决策问题的阶段。 描述阶段的变量称为阶段变量，常用k表示。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。

10 动态规划的基本概念 2.状态、状态变量与可能状态集
描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量包含在给定的阶段上确定全部允许决策所需要的信息。 每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1。通常定义阶段的状态即指其初始状态。 一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，sk∈Sk，。

11 动态规划问题实例 C1 E1 D1 B1 C2 F1 A E2 D2 G C3 F2 B2 E3 D3 C4 状态1 状态2 状态3 状态4
状态5 状态6 状态7 C1 6 1 8 2 E1 D1 3 B1 3 3 2 C2 5 F1 6 4 5 5 5 1 A E2 D2 G 2 3 C3 2 3 3 8 F2 7 3 6 B2 3 6 8 6 3 E3 D3 4 C4 第1阶段 第2阶段 第3阶段 第4阶段 第5阶段 第6阶段

12 动态规划的基本概念 3.决策 当一阶段的状态确定后，可以作出不同的选择从而演变到下一阶段的某个状态，这种选择手段称为决策。在最优控制问题中也称为控制。 描述决策的变量，称为决策变量。决策变量的允许取值的范围称为允许决策集合。决策变量是状态变量的函数。用uk(sk)表示第K阶段处于状态sk时的决策变量； Dk(sk)表示sk的允许决策集合。

13 动态规划问题实例 u2(B2)=C2 D2(B2)={C2,C3,C4} C1 E1 D1 B1 C2 F1 A E2 D2 G C3 F2
状态1 状态2 状态3 状态4 状态5 状态6 状态7 u2(B2)=C2 D2(B2)={C2,C3,C4} C1 6 1 8 2 E1 D1 3 B1 3 3 2 C2 5 F1 6 4 5 5 5 1 A E2 D2 G 2 3 3 C3 2 3 8 F2 7 3 6 B2 3 6 8 6 D3 3 E3 4 C4 第1阶段 第2阶段 第3阶段 第4阶段 第5阶段 第6阶段

14 动态规划的基本概念 4.策略 一个按顺序排列的决策组成的集合。由过程的第K阶段开始到终止阶段为止的过程称为问题的后部子过程。由每段的决策按顺序排列组成的决策函数序列{uk(sk),…,un(sn)}称为K子过程策略，简称子策略，记为pk,n(sk)。 当K=1时，此决策函数序列称为全过程的一个策略，简称策略，记为p1,n(s1)，即: p1,n(s1)= {u1(s1), u2(s2),…,un(sn)}

15 动态规划问题实例 p3,6(C2)={u3(C2), u4(D2), u5(E3), u6(F1)}
状态1 状态2 状态3 状态4 状态5 状态6 状态7 C1 6 1 8 2 E1 D1 3 B1 3 3 2 C2 5 F1 6 4 5 5 5 1 A E2 D2 G 2 3 C3 2 3 3 8 F2 7 3 6 B2 3 6 8 6 E3 D3 3 4 C4 p3,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)}

16 动态规划的基本概念 5.状态转移方程 确定过程由一个状态到另一个状态的演变过程。若给定第K阶段的状态变量sk的值，如果该阶段的决策变量uk一经确定，第K+1阶段的状态变量sk+1的值也就完全确定。即sk+1的值随sk和uk的值变化而变化。这种确定的对应关系记为: sk+1=Tk(sk , uk(sk)) 投资x1 投资x2 投资x3 投资x4 s1=600 状态s2 状态s3 状态s4 状态s5 工厂1 工厂2 工厂3 工厂4 s4=s3-x3 s2=s1-x1 s3=s2-x2 状态变量sk :可用于第k, k+1,…n个工厂的投资额。 决策变量xk :第 k 阶段对第 k 个工厂的投资额。 状态转移方程: sk+1 = sk - xk

17 动态规划的基本概念 1)阶段指标函数(阶段效应) 6.指标函数和最优值函数
用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用等等。 1)阶段指标函数(阶段效应) 用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk。

18 动态规划的基本概念 (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) 累积形成的。

19 动态规划的基本概念 适于用动态规划求解的问题的过程指标函数(即目标函数)，必须具有关于阶段指标的可分离形式．对于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) 多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即: å = n k i u s g V ) , ( 有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如: Õ = n k i u s g V ) , (

20 动态规划的基本概念 指标函数的最优值称为最优值函数，记为fk(sk)。它表示从第K阶段的状态开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。 ) , ( 1 } { + = n k u s V opt f L 相应的子策略称为sk状态下的最优子策略，记为pk*(sk) ；而构成该子策赂的各段决策称为该过程上的最优决策，记为: uk*(sk), uk+1*(sk+1),…, un*(sn)。 特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。但若取值不唯一,则问题的最优值记为f0有: ) ( )} { 1 * Î = s f opt S

21 动态规划的基本概念 ï î í ì = Î n k U u S s T st V opt f , 2 1 ) ( L
7. 多阶段决策问题的数学模型 综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式: ï î í ì = Î + n k U u S s T st V opt f , 2 1 ) ( ~ L

22 最短路径问题 C1 E1 D1 B1 C2 F1 A E2 D2 G C3 F2 B2 D3 E3 C4 例6-2:用动态规划求解最短路径。
8 2 E1 D1 3 B1 3 3 2 C2 5 F1 6 4 5 5 5 1 A E2 D2 G 2 3 C3 2 3 3 8 F2 7 3 6 B2 3 6 8 6 D3 3 E3 4 C4

23 最短路径问题 将问题分成五个阶段，第k阶段到达的具体地点用状态变量sk表示，例如:s2=B2表示第二阶段到达位置B2。这里状态变量取字符值而不是数值。 将决策定义为到达下一站所选择的路径，例如目前的状态是s2=B2，这时决策允许集合包含三个决策，它们是D2(s2)=D2(B2)={B2→C2，B2 → C3，B2 →C4}。 最优指标函数 fk(xk) 表示从目前状态到E的最短路径。终端条件为: f7 (s7) = f7(G) = 0 其含义是从G到G的最短路径为0。 递推方程为: )} ( ) , { 1 + Î = k s D u f V Min

24 贝尔曼最优化原理 作为一个全过程的最优策略具有这样的性质:对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。 该原理的具体解释是，若某一全过程最优策略为: p1*(s1) ={ u1*(s1), u2*(s2),…, un*(sn)} 则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1* 中，即为: pk*(sk) ={uk*(sk), uk+1*(sk+1),…, un*(sn)}

25 贝尔曼最优化原理 基于贝尔曼最优化原理，提出了一种逆序递推法；该法的关键在于给出一种递推关系。一般把这种递推关系称为动态规划的函数基本方程。
对于求最小的加法的计算公式为: ï î í ì - = + Î 1 , 2 )}, ( )) { min ) L n k s f u g U

26 贝尔曼最优化原理 (1)当过程指标函数为“和”的形式时，相应的函数基本方程为: (2)当过程指标函数为“和”的形式时，相应的函数基本方程为:
ï î í ì - = + Î 1 , 2 )}, ( )) { ) L n k s f u g opt U (2)当过程指标函数为“和”的形式时，相应的函数基本方程为: ï î í ì - = + Î 1 2 , n k )} s ( f )) u g { opt ) U L

27 动态规划方法的基本步骤 用函数基本方程逆推求解是常用的方法:首先要有效地建立动态规划模型,然后再递推求解,最后得出结论。
正确地建立一个动态规划模型,是解决问题的关键。 正确的动态规划模型,应该满足下列条件: 1.应将实际问题恰当地分割成n个子问题(n个阶段) 通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n。

28 动态规划方法的基本步骤 2.正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性。 要能够正确地描述受控过程的变化特征。
要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。 要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。 在解静态规划模型时，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数．约束条件所表示的内容，就是状态变量sk 所代表的内容。

29 动态规划方法的基本步骤 3.正确地定义决策变量及各阶段的允许决策集合Uk(sk)
一般将问题中待求的量，选作动态规划模型中的决策变量，或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常常取前者的变量xj为后者的决策变量 uk。 4.正确地写出状态转移方程 要能正确反映状态转移规律。如果给定第k阶段状态变量 sk 的值，则该段的决策变量 uk 一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有: sk+1=Tk(sk ,uk)

30 动态规划方法的基本步骤 5.正确地写出目标函数。
要满足可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策:uk ,uk+1 , … ,un。即它是定义在全过程和所有后部子过程上的数量函数。 要满足递推关系。即: Vk,n (sk,uk,sk+1,uk+1 ,… ,sn+1)=ψk[sk , uk , Vk+1 (sk+1,… ,sn+1)] 函数严格单调。即: ψk[sk,uk,Vk+1 (sk+1 ,… ,sn+1)]对变元Rk+1来说要严格单调。

31 动态规划方法的基本步骤 动态规划的四大要素 状态变量及其可能集合sk∈Sk 决策变量及其允许集合 uk ∈Uk
状态转移方程 sk+1= Tk (sk ,uk ) 阶段效应 Vk ( sk , uk ) 动态规划基本方程 ï î í ì - = + Î 1 , 2 )}, ( )) { ) L n k s f u g opt U

32 逆推解法 ) , ( max v f = )] ( ) , [ max f v * = )] ( ) , [ max * = f v )]
设已知初始状态为s1,并假定最优值函数fk(sk)表示第k阶段的初始状态为sk，从k阶段到n阶段所得到的最大效益。 从第n阶段开始，则有: ) , ( max n s D x v f Î = 解该问题，得到最优解xn= xn (sn)和最优值fn (sn) 。 在第n阶段，有 )] ( ) , [ max 1 n s D x f v * = - Î 在第k阶段，有 )] ( ) , [ max 1 + Î * = k s D x f v 如此类推，直到第一阶段有 )] ( ) , [ max 2 1 s f x v D * = Î 由于初始状态s1已知,故x1= x1(s1)和f1 (s1)是确定的，从而s2= T1(s1, x1)也就可以确定，于是x2= x2(s2)和f2(s2) 也可确定。按照上述递推过程相反的顺序推算，就可逐步确定每阶段的决策和效益。

33 逆推解法 , max ³ = + x c z 例6-3:用逆推法求解下面问题。 按照变量个数划分阶段，该问题是一个三阶段决策问题。
, max 3 2 1 = + x c z 按照变量个数划分阶段，该问题是一个三阶段决策问题。 状态变量为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

34 顺推解法 ) , ( max v f = )] ( ) , [ max f v * =
设已知终止状态为sn+1,并假定最优值函数fk(sk)表示第k阶段末的结束状态为sk，从1阶段到k n阶段所得到的最大效益。 从第1阶段开始，则有: ) , ( max 1 s D x v f Î = 解该问题，得到最优解x1= x1 (s2)和最优值f1 (s2) 。 在第n阶段，有 )] ( ) , [ max 1 n n-1 s D x f v * = Î + 得到最优解xn= xn (sn+1)和最优值fn (sn+1) 。 由于终止状态sn+1已知,故xn= xn (sn+1)和最优值fn (sn+1)是确定的，按照上述递推过程相反的顺序推算，就可逐步确定每阶段的决策和效益。

35 顺推解法 , max ³ = + x c z 例6-4:用顺推法求解下面问题。
, max 3 2 1 = + x c z 最优值函数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

36 资源分配问题(离散型) 例6-5:设有6万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？ 表1 利润增长额gi(xj) 单位:百元 投资额 (j) 工厂(i) 1 2 3 4

37 资源分配问题(离散型) 解:把对四个工厂的投资依次看成4个阶段的决策过程，确定对第k个工厂的投资额看成第k个阶段的决策，k=1,2,3,4。
投资x1 投资x2 投资x3 投资x4 s1=600 状态s2 状态s3 状态s4 状态s5 工厂1 工厂2 工厂3 工厂4 s4=s3-x3 s2=s1-x1 s3=s2-x2 状态变量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 个工厂以及以后的最大总利润。 î í ì = + ) ( { max 5 1 s f g k x

38 资源分配问题(离散型) 投资额 (j) 工厂(i) 3 k=4时，第4个工厂投资时，还有资金s4，若投资于第4个工厂的资金为x4，则最大利润为: )} ( { max ) 4 5 x g s f = + x4 g4(x4) s4 f4(s4) x4* 100 200 300 400 500 600 100 28 28 100 200 28 47 47 200 300 28 47 65 65 300 400 28 47 65 74 74 400 500 28 47 65 74 80 80 500 600 28 47 65 74 80 85 85 600

39 资源分配问题(离散型) 投资额 (j) 工厂(i) 3 k=3时，第3个工厂投资时，还有资金s3，若投资于第3个工厂的资金为x3，则最大利润为: )} ( ) { max 3 4 x s f g - + = x3 g3+f4 s3 f3(s3) x3* 100 200 300 400 500 600 0+0 100 0+28 18+0 28 200 0+47 18+28 39+0 47 300 0+65 18+47 39+28 61+0 65 200 400 0+74 18+65 39+47 61+28 78+0 89 300 500 0+80 18+74 39+65 61+47 78+28 90+0 108 300 600 0+85 18+80 39+74 61+65 78+47 90+28 95+0 126 300

40 资源分配问题(离散型) 0 100 200 300 400 500 600 )} ( ) { max x s f g - + = 2
投资额 (j) 工厂(i) 2 f3(s3) k=2时，第2个工厂投资时，还有资金s2，若投资于第2个工厂的资金为x2，则最大利润为: )} ( ) { max 2 3 x s f g - + = x2 g2+f3 s2 f2(s2) x2* 100 200 300 400 500 600 0+0 100 0+28 25+0 28 200 0+47 25+28 45+0 53 100 300 0+67 25+47 45+28 57+0 73 200 400 0+89 25+67 45+47 57+28 65+0 92 100,200 500 0+108 25+89 45+67 57+47 65+28 70+0 114 100 600 0+126 25+108 45+89 57+67 65+47 70+28 73+0 134 200

41 资源分配问题(离散型) 0 100 200 300 400 500 600 )} ( ) { max 600 x s f g - + = 1
投资额 (j) 工厂(i) 1 f2(s2) k=1时，s1=600，若投资于第1个工厂的资金为x1，则最大利润为: )} ( ) { max 600 1 2 x s f g - + = x1 g1+f2 s1 f3(s3) x1* 100 200 300 400 500 600 600 0+134 20+114 42+92 60+73 75+53 85+28 90+0 134 0,100,200 此时对应最大值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

42 背包问题 设有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为正整数

43 背包问题 阶段k:第k次装载第k种物品(k=1,2,…,n) 状态变量sk:第k次装载时背包还可以装载的重量
决策变量xk:第k次装载第k种物品的件数 决策允许集合: Dk(sk)={xk|0≤xk ≤ sk/wk，xk为整数}； 状态转移方程:sk+1=sk-wkxk 阶段指标:vk=ckxk 递推方程 fk(sk)=max{ckxk+fk+1(sk+1)} =max{ckxk+fk+1(sk-wkxk)} 终端条件:fn+1(sn+1)=0

44 背包问题 例6-6:已知c1=65,c2=80,c3=30,w1=2,w2=3,w3=1,W=5,f4(x4)=0 k=3时: )} 30
{ max ( ) 3 / 4 x s f c w = + k=2时: )} 3 ( 80 { max ) 2 / x s f c w - + = k=2时: )} 2 ( 65 { max ) 1 / x s f c w - + = 应取第一种物品2件,第三种物品1件,最高价值为160元,背包没有余量。由f1(x1)得列表可以看出，如果背包得容量为W=4，W=3，W=2和W=1时，相应的最优解立即可以得到。

45 资源分配问题(连续型) 设有某种资源总数量为s1,可投入用于生产A、B产品。第一年若以数量u1投入生产A，剩下的s1-u1就投入生产B，则可得到收入为g(u1)+h(s1-u1),其中g(u1)和h(u1) 为已知函数，且g(0)+h(0)=0,这种资源在投入A、B产品生产后，年终还可回收再投入生产。设年回收率分别为0<a<1和0<b<1，则在第一年生产后，回收的资源量合计为s2=au1+bh(s1-u1)。第二年再将资源数量s2中的u2和s2-u2分别投入A、B产品生产，则又可得到收入为g(u2)+h(s2-u2)。如此进行n年，试问应当如何决定每年投入A生产的资源量u1, u2,…, un,才能使总的收入最大？

46 资源分配问题(连续型) 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) 0≤ui≤si+1，i=1，2，…，n 状态变量sk:第k阶段可投入A、B两种生产的资源量 决策变量uk:第k阶段可投入A生产的资源量，则sk-uk投入B生产的资源量 状态转移方程: sk+1=auk+b(sk-uk) ï î í ì - + = )} ( ) { max )]} [ 1 n s u k h g f b au

47 设备负荷分配问题 例6-7:某公司有500辆运输卡车，在超负荷运输(即每天满载行驶500km以上)情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输(即每天行驶300km以下)情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配在两种不同的负荷下完好车辆运输的卡车数量，使5年内的总利润最大？ 状态变量sk:第k年初完好卡车数量，其中s1=500 决策变量xk:第k年初分配给超负荷运输的卡车数量，则分配给低负荷的卡车数为 sk-uk 状态转移方程:sk+1=(1-0.3)xk +(1-0.1)(sk-xk)=0.9sk -0.2xk 阶段指标函数 gk(xk):表示第 k 年度利润,即 gk(xk)=25xk+16(sk-xk)= 16sk + 9xk

48 设备负荷分配问题 { } 最优指标函数fk(sk):第k年度初完好车辆数为sk时，采用最优策略到第 5 年末所产生的最大利润。
î í ì = + ) ( 1 , 2 3 4 5 max 6 s f k x g 第一年初:500辆车全部用于低负荷运输。 第二年初:还有450辆完好的车，也全部用于低负荷运输。 第三年初:还有405辆完好的车，全部用于超负荷运输。 第四年初:还有238.5辆完好的车，全部用于超负荷运输。 第五年初:还有198.45辆完好的车，全部用于超负荷运输。 到第五年末，即第六年初，还剩余138.15辆完好的车。 实现最大利润约3.74亿元。

49 设备负荷分配问题 课堂思考:某公司有1000辆运输卡车，在超负荷运输(即每天满载行驶500km以上)情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输(即每天行驶300km以下)情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配在两种不同的负荷下完好车辆运输的卡车数量，使在第5年年末剩余的完好卡车数量为500台，并且使在5年内的总利润最大？

50 生产计划问题 例6-8:某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的数量如下表所示。该厂生产每批产品的固定成本为3千元，若不生产为0；每单位产品成本为1千元；每个时期生产能力所允许的最大生产批量为不超过6个单位；每个时期末未售出的产品，每单位需支付存储费用0.5千元。假定在第一个时期的库存为0，第四个时期库存量为0。该厂应如何安排各个时期的生产与库存，才能在满足市场需要的条件下，成本最小？ 时期 1 2 3 4 需求量

51 生产计划问题 状态变量sk :第k阶段结束时的产品库存量。 决策变量xk : xk为第k阶段该产品的生产量。
状态转移方程:设dk为第k阶段对产品的需求量，则 sk = sk-1 + xk - dk ck(xk)表示第k阶段生产产品xk时的成本费用。 hk(sk)表示第k阶段结束时有库存量sk所需的存储费用 顺序递推关系为: ï î í ì = + - ) ( , min( )], [ max 1 s f m d h x c k

52 设备更新问题 企业中经常会遇到一台设备应该使用多少年更新最合算的问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费用少，但随着使用年限的增加，年运转量减少因而收入减少，故障变多，维修费用增加。如果更新可提高年净收入，但是当年要支出一笔数额较大的购买费。 设备更新的一般提法为：在已知一台设备的效益函数r(t)，维修费用函数u(t)及更新费用函数c(t)条件下，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使使n年总效益最大。

53 设备更新问题 例6-9:某台新设备的年效益及年均维修费、更新净费用如表所示。试确定今后5年内的更新策略，使总收益最大。 役龄 项目 1 2
1 2 3 4 5 效益r(t) 4.5 3.75 2.5 维修费u(t) 0.5 1.5 更新费c(t) 2.2 3.5

54 设备更新问题 阶段k：运行年份； 状态变量sk：第k年初，设备已使用过的年数，称役龄 决策变量xk： 状态转移方程： î í ì = - R
年初继续使用 第 年初更新 k K R x î í ì = + K x s R k 1 状态转移方程： î í ì = - R x s c u r K g k ) ( 阶段指标函数： 最优指标函数fk(sk)：第k年初，使用一台已用了sk年的设备，到第5年末的最大效益，有： î í ì = + - R x f s c u r K k ) 1 ( max

55 设备更新问题 阶段k：运行年份； 状态变量sk：第k年初，设备已使用过的年数，称役龄 决策变量xk： 状态转移方程： î í ì = - R
年初继续使用 第 年初更新 k K R x î í ì = + K x s R k 1 状态转移方程： î í ì = - R x s c u r K g k ) ( 阶段指标函数： 最优指标函数fk(sk)：第k年初，使用一台已用了sk年的设备，到第5年末的最大效益，有： î í ì = + - R x f s c u r K k ) 1 ( max

56 设备更新问题 役龄 项目 1 2 3 4 5 r(t) 4.5 3.75 2.5 (t) 0.5 1.5 c(t) 2.2 3.5 x5 s5 g5(x5) f5 x*5 K R 1 3.5 3 2 2.5 2.3 1.75 4 0.5 1.5 x3 s3 g3+ f4 f3 x*3 K R 1 9.3 9.5 2 9 8.8 x4 s4 g4+ f5 f4 x*4 K R 1 6 6.5 2 4.5 5.8 3 3.25 5.5 x2 s2 g2+ f3 f2 x*2 K R 1 12.3 12.5