第六章动态规划.ppt

《第六章动态规划.ppt》由会员分享，可在线阅读，更多相关《第六章动态规划.ppt（112页珍藏版）》请在三一文库上搜索。

1、1,第六章 动态规划,动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。1951年，美国数学家贝尔曼（ R . Bellman ）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。贝尔曼等人在研究和解决了大量实际问题之后，提出了解决这类问题的所谓“最优性原理”，通常称为“贝尔曼最优化原理”，从而创建了解决最优化问题的一种新的方法 动态规划 （Dynamic Programming ）。,2,动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用，并且获得了显著的效果。在经济管理方

2、面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，他是现代企业管理中的一种重要的决策方法。 许多实际问题采用动态规划方法去处理，常比线性规划或非线性规划更加有效。特别对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法就成为一种非常有效的工具。,3,应特别指出的是，动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本概

3、念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。正如贝尔曼本人所说：“由于动态规划的最优化原理仅仅是一种基本原理，正是它的某种不确定性为你提供了发挥你创造性思维的巨大空间 !,4,本部分我们主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，在通过一些典型的应用问题来说明它的应用。 动态规划所研究的对象是多阶段决策问题。 所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。 每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶

4、段的效益的总和达到最优。,5,第一节 多阶段决策问题,在生产经营活动中，某些问题决策过程可以划分为若干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题。 动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。,6,动态规划求解的多阶段决策问题的特点 通常多阶段决策过程的发展是

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

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

7、的结果常是错误的,10,第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是， 如果A= S1 S2 Sk Sn E是A到E的最短路，则Sk到E的最短路一定是Sk Sn E。 首先将问题划分为4个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。 为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。,11,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,

8、B1,B3,B2,D2,E,C2,f5(E)=0,12,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,13,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,

9、E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,15,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,16,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,17,2

10、,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,18,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=21,19,2,5,1

11、,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B2)=14,20,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1

12、(A)=19,f2(B2)=14,f2(B1)=21,21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2,22,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1

13、,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1,23,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=

14、19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1,24,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策

15、状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E 从A到E的最短路径为19，路线为AB 2C1 D1 E,25,综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最

16、优的方案组合，从而使计算工作量比穷举法大为减少。,26,第二节 动态规划的基本概念和基本原理 多阶段决策过程： 整个决策过程可按时间或空间顺序分解成若干相互联系的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。 多阶段决策过程最优化的目标： 达到整个活动过程的总体效果最优，而非各单个阶段最优的简单总和。 使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说明和定义：,27,1、阶段（stage） 为了便于求解和表示决策过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，

17、称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间顺序或空间特征上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目，例如上面的最短路问题就是一个四阶段决策过程。,28,2、状态（state） 每个阶段开始时过程所处的自然状况或客观条件。反映状态变化的量叫做状态变量，它可以用一个数，一组数或一向量来描述， 。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。它应能描述过程的特征并具有“无后效性”，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。用

18、sk表示状态变量 （state variable）。,29,一般状态变量的取值有一定的范围或允许集合，称为可能状态集（set of admissible states） 。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定例如上面的最短路问题中，第一阶段状态为A，状态变量s1的状态集合S1=A；第二阶段则有三个状态：B1 ,B2 ,B3 ,状态变量s2的状态集合S2=B1 ,B2 ,B3 .,30,3、决策（decision） 当一个阶段的状态确定后，可以作出不同的决定或选择，从而

19、演变到下一阶段的某个状态，这种决定或选择称为决策。 用以描述决策变化的量称之决策变量（decision variable） 。和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，由于各阶段的决策取决于状态变量sk，所以用 uk(sk)，表示阶段k的状态为sk时的决策变量。 决策变量的取值往往也有一定的允许范围，称之允许决策集合（set of admissible decision）。决策变量uk(sk)的允许决策集用Uk(sk)表示, 允许决策集合实际是决策的约束条件。,31,4、策略（policy） 一组有序的决策序列构成一个策略，从第k阶段至第n阶段的一个策略称为k后部子策略记为

20、pk,n (sk)=uk，uk+1，un，当k=1时的k部子策略称为全过程策略，简称策略，记为p1,n (s1) 。 在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P1,n ，从允许策略集中，找出具有最优效果的策略称为最优策略。,32,5、状态转移方程（equation of state transition） 反映前后阶段状态之间关系的方程称为状态转移方程。在确定型多阶段决策过程中，一旦某阶段的状态和决策为已知，下一阶段的 状态便完全确定，用状态转移方程反映这种状态间的演变规律，记作：,

21、有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。,33,6、阶段指标值（objective value in a stage） 阶段指标值是第k阶段的状态为sk和采取决策uk时的效益，通常表示为 dk(sk，uk)。 对不同问题，阶段指标值可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间，等等。例如上面的最短路问题中，如果第二阶段地状态为B2,采取决策是由B2到达C1,则阶段指标值为6。,34,7、指标函数（objective function） 衡量在选定某策略时，其优劣的数量指标。 定义在整个过程（1到n阶段）上的指标函数记为：V1,n（s1，

22、u1，s2，sn，un）， 定义在后部子过程（k到n阶段）上的指标函数记为： Vk,n（sk，uk，sn，un）。 Vk,n（sk，uk，sn，un） 表示第k阶段处于sk状态且所作决策为uk, uk+1, , un时的决策效果。 由此可见， Vk,n（sk，uk，sn，un）不仅跟当前状态sk有关，还跟该子过程策略pk,n(sk)有关，因此它是sk和pk,n(sk)的函数，因此它可简记为：Vk,n（sk， pk,n ）,35,指标函数Vk,n(sk, pk,n )通常是描述所实现的全过程或k后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数dk(sk,uk)累积形成的，适于用动态规划求

23、解的问题的指标函数，必须具有关于阶段指标的可分离形式对于后部子过程的指标函数可以表示为：,式中，表示某种运算，可以是加、减、乘、除、开方等。,36,总之，具体问题的目标函数表达形式需要视具体问题而定。,多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:,有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如：,37,8、最优指标函数（optimal value function） 指标函数的最优值称为最优指标函数，记为fk(sk)，它表示从第k阶段状态 sk 出发，采用最优策略到终止状态时的后部子过程指标函数值，即,式中opt即optimization，根据具

24、体问题可取max或min。与它相应的子策略称为在sk状态下的最优子策略，记为pk*(sk) ；而构成该子策略的各段决策称为该过程上的最优决策，记为,38,即,简记为,特别当k=1时，f1(s1)就是问题的最优值，而p1*就是最优策略。例如上面的最短路问题中，有唯一最优值f1(s1)=18，而,就是其最优策略。,39,多阶段决策问题的数学模型 综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:,40,则对上述策略中所隐含的任一状态而言， 第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为,最优化原理 （贝尔曼

25、最优化原理） 作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：,41,其中，,表示从状态sk到由决策uk(sk)所决定的状态sk+1之间的距离。,动态规划的基本方程 在上面最短路问题的求解过程中，在求解的各阶段利用了第k阶段和第k+1阶段的如下递推关系：,第三节 动态规划模型的建立与求解,42,一般地，对于n个阶段的决策过程，假设只考虑指标函数是“和”与“积”的形式，第k阶段和第k+1阶段间的递推公式可表示如下： (1)当指标函数为下列“和”的形式时，其相应的基本

26、方程为,是边界条件。,43,(2) 当过程指标函数为下列“积”的形式时,其相应的基本方程为,一般来说,要用函数基本方程逆推求解,首先要有效地建立动态规划模型,然后再递推求解,最后得出结论.然而,要把一个实际问题用动态规划方法来求解,还必须首先根据问题的要求。把它构造成动态规划模型,这是非常重要的一步。正确地建立一个动态规划模型,往往问题也就解决了一大半,而一个正确的动态规划模型,应该满足哪些条件呢?,44,建立动态规划数学模型的步骤 1应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k

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

28、，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数而前者约束条件所表示的内容，常就是状态变量sk所代表的内容。,46,3正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。 4. 能够正确地写出状态转移方程，至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk ,uk),47,5根据题意,正确地构造

29、出目标与变量的函数关系目标函数，目标函数应满足下列性质： (1)可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策 uk ,uk+1,un,就是说它是定义在全过程和所有后部子过程上的数量函数。 (2)要满足递推关系，即 (3)函数 对其变元Vk+1,n来说要严格单调。,48,6写出动态规划函数基本方程 例如常见的指标函数是取各段指标和的形式 其中 表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成 ：,49,第五节 动态规划在经济管理中的应用,一、 资源分配问题,假设有一种资源，数量为a，将其分配给n个使用者，分配给第i个使用者数量xi时，相应的收益为gi（

30、xi），问如何分配使得总收入最大？这就是一维资源分配问题，该问题的数学模型为：,（6.23）,50,式（6.23）是一个静态规划问题，应用动态规划方法求解时人为赋予时间概念，将其看作是一个多阶段决策问题。 按变量个数划分阶段，k=1，2，n； 设决策变量uk=xk，表示分配给第k个使用者的资源数量； 设状态变量为sk，表示分配给第k个至第n个使用者的总资源数量； 状态转移方程：sk+1=skxk，其中s1=a； 允许决策集合：Dk(sk)=xk|0xksk 阶段指标函数：vk(sk，uk)=gk(xk)表示分配给第k个使用者数量xk时的收益；,51,最优指标函数fk(sk)表示以数量sk的资源

31、分配给第k个至第n个使用者所得到的最大收益，则动态规划基本方程为：,由后向前逐段递推，f1(a)即为所求问题的最大收益。,52,例7 某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表6.4所示。试问在各地区如何设置销售点可使每月总利润最大。 表6.4 利润值,53,解： 如前所述，建立动态规划数学模型： 将问题分为3个阶段，k=1，2，3； 决策变量xk表示分配给第k个地区的销售点数； 状态变量为sk表示分配给第k个至第3个地区的销售点总数； 状态转移方程：sk+1=skxk，其中s1=4； 允许决策集合：Dk（sk）=xk|0xk

32、sk 阶段指标函数：gk（xk）表示xk个销售点分配给第k个地区所获得的利润； 最优指标函数fk（sk）表示将数量为sk的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：,54,数值计算如表所示。 表6.5 k=3时计算结果,55,表6.6 k=2时计算结果,表6.7 k=1时计算结果,56,所以最优解为：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。 这个例子是决策变量取离散值的一类分配问题，在实际问题中，相类似的问题还有设备或人力资源的分配问题等。在资源分配问题中

33、，还有一种决策变量为连续变量的资源分配问题，见下面例子。,57,例8 机器负荷问题 某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量（件）函数为g1=8x，其中x为投入高负荷生产的机器数量，年度完好率=0.7（年底的完好设备数等于年初完好设备数的70%）；在低负荷下生产的产量（件）函数为g2=5y，其中y为投入低负荷生产的机器数量，年度完好率=0.9。假定开始生产时完好的机器数量为1000台，试问每年应如何安排机器在高、低负荷下的生产，才能使5年生产的产品总量最多？,58,解：设阶段k表示年度（k=1,2,3,4,5）；状态变量Sk为第k年度初拥有的完好机器数量（同时也是第

34、k-1年度末时的完好机器数量）。决策变量xk为第k年度分配高负荷下生产的机器数量，于是Sk-xk为该年度分配在低负荷下生产的机器数量。这里的Sk和xk均为连续变量，它们的非整数值可以这样理解：如Sk=0.6就表示一台机器在第k年度中正常工作时间只占全部时间的60%；xk=0.3就表示一台机器在第k年度中只有30%的工作时间在高负荷下运转。状态转移方程为：,59,允许决策集合：,设阶段指标Qk(Sk, xk)为第k年度的产量，则：,过程指标是阶段指标的和，即：,令最优值函数fk(Sk)表示从资源量Sk出发，采取最优子策略所生产的产品总量，因而有逆推关系式：,边界条件f6(S6)=0。,60,当k

35、=5时：,因f5(S5)是关于x5的单调递增函数，故取x5*= S5，相应有f5(S5)=8 S5。 当k=4时：,61,因f4(S4)是关于x4的单调递增函数，故取x4*= S4，相应有f4(S4)=13.6 S4；依次类推，可求得： 当k=3时：x3*= S3，f3(S3)=17.5 S3 当k=2时：x2*=0，f2(S2)=20.8 S2 当k=1时：x1*=0，f1(S1=1000)=23.7 S1=23700,计算结果表明最优策略为：x1*=0，x2*=0，x3*= S3，x4*= S4，x5*= S5；即前两年将全部设备都投入低负荷生产，后三年将全部设备都投入高负荷生产，这样可以

36、使5年的总产量最大，最大产量是23700件。 有了上述最优策略，各阶段的状态也就随之确定了，即按阶段顺序计算出各年年初的完好设备数量。,62,上面所讨论的过程始端状态S1是固定的，而终端状态S6是自由的，实现的目标函数是5年的总产量最高。,63,二、 生产与存贮问题 在生产和经营管理中，经常遇到要合理地安排生产（或购买）与库存问题，达到既要满足社会的需要，又要尽量降低成本费用，因此，正确制定生产（后采购）策略，确定不同时期的生产量（或采购量）和库存量，以使总的生产成本费和库存费用之和最小，这就是生产与存贮问题的最有目标,64,1. 生产计划问题 例9 （生产库存问题） 某工厂要对一种产品制定今

37、后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。,65,解: 以每个时期作为一个阶段，该问题分为4个阶 段，k=1，2，3，4； 决策变量xk表示第k阶段生产的产品数； 状态变量sk表示第k阶段初的库存量； 以dk表示第k阶段的需求，则状态转移方程：sk+1=sk+xkdk；k=4，3，2，1 由于期初及

38、期末库存为0，所以s1=0，s5=0； 允许决策集合Dk（sk）的确定：当skdk时，xk可以为0，当skdk时，至少应生产dksk，故xk的下限为max（0，dksk）每期最大生产能力为6，xk最大不超过6，由于期末库存为0，xk还应小于本期至4期 需求之和减去本期的库存量，,66,所以xk的上限为,故有：,阶段指标函数rk（sk，xk）表示第k期的生产费用 与存贮费用之和：,最优指标函数fk（sk）表示第k期库存为sk到第4期末的生产与存贮最低费用，动态规划基本方程为：,67,先求出各状态允许状态集合及允许决策集合，如表6.8所示。 表6.8 状态允许状态集合及允许决策集合,68,由基本方

39、程计算各阶段策略，结果如下表所示。 表6.9 k=4时计算结果,69,表6.10 k=3时计算结果,70,表6.11 k=2时计算结果,71,表6.12 k=1时计算结果,逆向追踪可得：x1*=5，s2=3，x2*=0，s3=0，x3*=6，s4=4，x4*=0，即第1时期生产5个单位，第3时期生产6个单位，第2，4时期不生产，可使总费用最小，最小费用为20.5千元。,72,例11某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季节是从10月1日至3月31日。下个销售季节各月的需求预测值如表6.14所示。 表6.14 需求预测值 (单位：双),该鞋店的此种鞋完全从外部生产商进货，进货

40、价每双4美元。进货批量的基本单位是箱，每箱10双。由于存贮空间的限制，每次进货不超过5箱。对应不同的订货批量，进价享受一定的数量折扣，具体数值如表6.15所示。,73,表6.15 数量折扣数值表,假设需求是按一定速度均匀发生的，订货不需时间，但订货只能在月初办理一次，每次订货的采购费（与采购数量无关）为10美元。月存贮费按每月月底鞋的存量计，每双0.2美元。由于订货不需时间，所以销售季节外的其他月份的存贮量为“0”。试确定最佳的进货方案，以使总的销售费用最小。,74,解：阶段：将销售季节6个月中的每一个月作为一个阶段，即k=1,2,6； 状态变量：第k阶段的状态变量Sk代表第k个月初鞋的存量；

41、 决策变量：决策变量xk代表第k个月的采购批量； 状态转移律：sk+1=sk+xkdk（dk是第k个月的需求量）； 边界条件：s1=s7=0，f7(s7)=0； 阶段指标函数：rk(sk,xk)代表第k个月所发生的全部费用，即与采购数量无关的采购费Ck、与采购数量成正比的购置费Gk和存贮费Zk.其中：,75,最优指标函数：最优指标函数具有如下递推形式,当k=6时（3月）： 表6.16 k=6时计算结果,76,当k=5时（2月）： 表6.17 k=5时计算结果,77,当k=4时（1月）： 表6.18 k=4 时计算结果,78,当k=3时（12月）： 表6.19 k=3时计算结果,79,当k=2时

42、（11月）：表6.20 k=2时计算结果,当k=1时（10月）：表6.21 k=1时计算结果,80,利用状态转移律，按上述计算的逆序可推算出最优策略：10月份采购4箱（40双），11月份采购5箱（50双），12月份不采购，1月份采购4箱（40双），2月份采购5箱（50双），3月份不采购；最小的销售费用为606美元。,81,三、 背包问题 有人携带背包上山，其可携带物品的重量限度为a公斤，现有n种物品可供选择，设第i种物品的单件重量为ai公斤，其在上山过程中的价值是携带数量xi的函数ci（xi），问应如何安排携带各种物品的数量，使总价值最大。这就是背包问题，类似的货物装载问题，下料问题都等同于背

43、包问题。 背包问题的数学模型为：,82,下面用动态规划方法求解： 按照装入物品的种类划分阶段，k=1，2，n； 状态变量sk表示装入第k种至第n种物品的总重量； 决策变量xk表示装入第k种物品的件数； 状态转移方程为：sk+1=skakxk 允许决策集合为：,其中,阶段指标函数ck（xk）表示第k阶段装入第k种商品xk件时的价值；,表示不超过,的最大整数；,83,最优指标函数fk（sk）表示第k阶段装入物品总重量为sk时的最大价值，动态规划基本方程为：,例13 某工厂生产三种产品，各产品重量与利润关系如表6.24所示，现将此三种产品运往市场销售，运输能力总重量不超过6吨，问如何安排运输使总利润

44、最大？ 表6.24重量与利润关系表,84,解： 设xi为装载第i种货物的件数，i=1,2,3，该问题数学模型为：,按照装入物品的种类划分阶段，k=1，2，3； 状态变量sk表示装入第k种至第n种物品的总重量； 决策变量xk表示装入第k种物品的件数； 状态转移方程为：sk+1=skakxk,85,表6.25 k=3时计算结果,计算结果如表6.25所示。,k=3时，,86,表6.26 k=2时计算结果,计算结果如表6.26所示。,k=2时，,87,反向追踪得最优方案：x1*=0，x2*=2，x3*=0；最优方案：x1*=1，x2*=0，x3*=1最大总利润为260元。,表6.27 k=1时计算结果

45、,k=1时，,计算结果如表6.27所示。,88,四、 复合系统工作可靠性问题 某个机器工作系统由n个部件串联而成，其中只要有一个部件失效，则整个系统不能正常工作，因此为了提高系统工作的可靠性，在设计时，每个主要部件上都装有备用元件，一旦某个主要部件失效，备用元件会自动投入系统工作，显然备用元件越多，系统工作可靠性越大，但是备用元件越多，系统的成本、重量、体积相应增大，工作精度降低，因此在上述限制条件下，应选择合理的备用元件数，使整个系统的工作可靠性最大。,89,设第i（i=1，2，n）个部件上装有ui个备 用元件，正常工作的概率为pi（ui），则整个 系统正常工作的可靠性为,装第i个部件的费用

46、为ci，重量为wi，要求总费用不超过c，总重量不超过w，则静态规划数学模型为：,90,按部件个数划分阶段，k=1，2，n； 决策变量uk表示部件k上的备用元件数； 状态变量xk表示从第k个到第n个部件的总费用， yk表示从第k个到第n个部件的总重量； 状态转移方程为： xk+1=xkckuk yk+1=ykwkuk 允许决策集合为：,阶段指标函数为pk（uk），表示第k个部件的正常工作概率；,91,最优指标函数fk（xk，yk）表示由状态xk，yk出发，从部件k到部件n的系统工作最大可靠性，则动态规划基本方程为：,f1（c，w）即为整个系统工作的最大可靠性。,92,例14 某厂设计的一种电子设

47、备由三种元件A、B、C串联而成，已知三种元件的价格及可靠性如表6.28所示，要求设计中使用元件的总费用不超过10万元，问如何设计使设备的可靠性达到最大（不考虑重量限制）。 表6.28 价格及可靠性,93,解 如前所述建立动态规划数学模型； 按元件种类划分为3个阶段，k=1，2，3； 决策变量xk表示第k个部件配备的元件数； 状态变量sk表示从第k阶段到第3阶段配备元件 的总费用； 状态转移方程为： sk+1=skckxk 其中ck表示第k种部件的元件单价； 允许决策集合为：,；,94,以pk表示第k个部件中的1个元件的正常工作概率，假定部件k的xk个元件是并联的，则,为xk个元件均不正常工作的

48、概率，fk（sk）表示由状态sk开始从第k个到第3个部件的设备最大可靠性。 k=3时，,由于A、B至少要购置1件，用于购置C的最高金额为s3=1023=5万元，计算结果如表6.29所示。,95,表6.29 k=3时计算结果,96,k=2时，,计算结果如表6.30所示。 表6.30 k=2时计算结果,97,k=1时，,计算结果如表6.31所示。 表6.31 k=1时计算结果,逆向追踪得：x1*=2，s2=6，x2*=1，s3=3，x3*=3，即A元件用2个，B元件用1个，C元件用3个，最高可靠性为0.682.。,98,五、设备更新问题,设备更新问题的一般提法 随着使用年限的增加，设备性能会变差，故障会增加，需要维修或更新。设备使用时间愈长，积累效益愈高，但