动态规划84111

1、精品文档你我共享 动态规划 规划问题的最终目的就是确定各决策变量的取值， 以使目标函数 达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合 的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、 分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动 过程：它可以分解为若干个互相联系的阶段， 在每一阶段分别对应着 一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决 策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为 一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以 有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一 个确定的效果，

2、采取不同的策略，就会得到不同的效果。多阶段的决 策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便 得到最佳的效果。动态规划(dynamic programming)同前面介绍过的 各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动 态规划是一种求解多阶段决策问题的系统技术， 可以说它横跨整个规 划领域(线性规划和非线性规划)。当然，由于动态规划不是一种特 定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确 定义的一组规则，动态规划必须对具体问题进行具体的分析处理。 在 多阶段决策问题中，有些问题对阶段的划分具有明显的时序性， 动态 规划的“动态”二字也由此而得名

3、。动态规划的主要创始人是美国数 学家贝尔曼(Bellman)。20世纪40年代末50年代初，当时在兰德公 司(Rand Corporation )从事研究工作的贝尔曼首先提出了动态规划 AAAAAA 的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部 著作动态规划。该著作成为了当时唯一的进一步研究和应用动态 规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962 年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手 们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的 发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特 顿（Mitt

4、en ）。爱尔思先后于1961年和1964年出版了两部关于动态规 划的著作，并于1964年同尼母霍思尔（Nemhause）、威尔德 (Wild) 一道创建了处理分枝、循环性多阶段决策系统的一般性理论。 梅特顿 提出了许多对动态规划后来发展有着重要意义的基础性观点, 并且对 明晰动态规划路径的数学性质做出了巨大的贡献。 动态规划在工程技术、经济管理等社会各个领域都有着广泛的应 用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解 决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排 序问题、设备更新问题以及生产过程最优控制问题等， 是经济管理中 一种重要的决策技术。许多规划问题用

5、动态规划的方法来处理， 常比 线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数 学无法发挥作用，动态规划便成为了一种非常有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规 划和随机性动态规划；也可以按照决策变量的取值是否连续分为 连续 性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概 念、理论和方法，并通过典型的案例说明这些理论和方法的应用。 7.1动态规划的基本理论 1.1多阶段决策过程的数学描述 有这样一类活动过程，其整个过程可分为若干相互联系的阶段, 每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。 任何一个阶段（stage，即决策点）

6、都是由输入（input ）、决策 (decision )、状态转移律( transformation function)和输出 （output）构成的，如图7-1 （a）所示。其中输入和输出也称为状 态（state），输入称为输入状态，输出称为输出状态。 dn S1 Stage n Sn+1 状态转移 （a） gn = r(Sn,dn) (b) 图7-1 由于每一阶段都有一个决策，所以每一阶段都应存在一个衡量决 策效益大小的指标函数，这一指标函数称为 阶段指标函数，用g表示。 显然g是状态变量Sn和决策变量dn的函数，即gn = r （S, dn）,如图 7-1 (b)所示。显然，输出是输入和

7、决策的函数，即: Sn* = f(Sn,dn) (7-1 ) 式(7-1 )即为状态转移律。在由N个阶段构成的过程里，前一个阶 段的输出即为后一个阶段的输入。 1.2 动态规划的基本概念 动态规划的数学描述离不开它的一些基本概念与符号，因此有必 要在介绍多阶段决策过程的数学描述的基础上，系统地介绍动态规划 的一些基本概念。 1. 阶段(stage) 阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段 变量，常用k来表示。阶段的划分一般是根据时间和空间的自然特 征来进行的，但要便于将问题的过程转化为多阶段决策的过程。对 于具有N个阶段的决策过程，其阶段变量 k= 1, 2,，N。 2. 状

8、态(state ) 状态表示每个阶段开始所处的自然状况或客观条件，它描述了研 究问题过程的状况。状态既反映前面各阶段系列决策的结局，又是本 阶段决策的一个出发点和依据；它是各阶段信息的传递点和结合点。 各阶段的状态通常用状态变量 S来加以描述。作为状态应具有这样的 性质：如果某阶段状态给定后，则该阶段以后过程的发展不受此阶段 以前各阶段状态的影响。换句话说，过程的历史只能通过当前的状态 来影响未来，当前的状态是以往历史的一个总结。 这个性质称为无后 ）或健忘性（the 效性 (the future is independent of the past p rocess is forgetful

9、 3. 决策(decision ) 决策是指决策者在所面临的若干个方案中做出的选择。决策变量 dk表示第k阶段的决策。决策变量dk的取值会受到状态S的某种限制, 用D （S）表示第k阶段状态为S时决策变量允许的取值范围，称为 允许决策集合，因而有dk（ S） - D（ S）。 4. 状态转移律(transformation function) 状态转移律是确定由一个状态到另一状态演变过程的方程，这种 演变的对应关系记为 S+1 = Tk（ S , dk）。 5. 策略(policy )与子策略(sub-policy ) 由所有阶段决策所组成的一个决策序列称为一个策略，具有 阶段的动态规划问题的

10、策略可表示为: di(Si),d2(S2),，dN(SN) 从某一阶段开始到过程终点为止的一个决策子序列，称为过程子 策略或子策略。从第k个阶段起的一个子策略可表示为: dk(Sk ),dk十(Sk+),dN (SN) 6.指标函数 指标函数有阶段指标函数和过程指标函数 之分。阶段指标函数是 对应某一阶段决策的效率度量，用 gk= r（S, dk）来表示；过程指 标函数是用来衡量所实现过程优劣的数量指标，是定义在全过程（策 略）或后续子过程（子策略）上的一个数量函数，从第 k个阶段起的 一个子策略所对应的过程指标函数常用 Gn来表示，即: Gk,N = R（Sk dk , Sk 出，dk 卅，

11、,SN , d N ） 构成动态规划的过程指标函数，应具有可分性并满足递推关系; 即: Gk,N = gk Gk十N 这里的表示某种运算，最常见的运算关系有如下二种: ，即: ，即: （1）过程指标函数是其所包含的各阶段指标函数的“和” N Gk,Ng j j土 于是 Gk,N = gk + Gk4t,N （2）过程指标函数是其所包含的各阶段指标函数的“积” N Gk,N =n g j j土 于是 Gk,N = gk X Gk+,N 7.最优指标函数 从第k个阶段起的最优子策略所对应的过程指标函数称为最优 指标函数，可以用式（7-2）加以表示: fk (Sk) = optgk gk卡 gN d

12、kN (7-2) 其中“ opt ”是最优化“ optimization ”的缩写，可根据题意取最大 max或最小“ min”。在不同的问题中，指标函数的含义可能是不 同的，它可能是距离、利润、成本、产量或资源量等。 1.3动态规划的数学模型 动态规划的数学模型除包括式（ 7-2 ）外，还包括阶段的划分、 各阶段的状态变量和决策变量的选取、 允许决策集合和状态转移律的 如何获得最优指标函数呢？ 一个 些特性： （1） （2） N阶段的决策过程，具有如下一 确定等。 刚好有N个决策点； 对阶段k而言，除了其所处的状态Sk和所选择的决策dk外， 再没有任何其它因素影响决策的最优性了； 阶段k仅影响

13、阶段k+1的决策，这一影响是通过 Sk十来实现 的； 贝尔曼（Bellman）最优化原理：在最优策略的任意一阶段 上，无论过去的状态和决策如何，对过去决策所形成的当前 状态而言，余下的诸决策必须构成最优子策略。 根据贝尔曼（Bellman）最优化原理，可以将式（7-2 ）表示为递 精品文档你我共享 (7-3) (7-4) （第 N个阶段, 推最优指标函数关系式（7-3）或式（7-4 ）: fk(Sk) =0pt gy g” =0pt + f叶(SkG dkNdk fk(Sk) =0ptgk gk卡 g” =0ptgkX fk卡(SkHi) dkNdk 利用式（7-3 ）和式（7-4）可表示出最

14、后一个阶段 即k=N的最优指标函数: f N (SN 0PtgN 中 fN H1 (SN -1) dN (7-5) f N (SN ) = optgN X fiN 出(Sn41) dN （7-6） 其中fN+（SN +）称为边界条件。一般情况下，第N阶段的输出状态Sn书已 经不再影响本过程的策略，即式（7-5 ）中的边界条件fN卅（SnG = O, 式（7-6 ）中的边界条件fN卅（SnG=1 ;但当问题第N阶段的输出状态 Sn十对本过程的策略产生某种影响时，边界条件 fN氣Sn S就要根据问 题的具体情况取适当的值，这一情况将在后续例题中加以反映。 已知边界条件fN讥SnG，利用式（7-3）

15、或式（7-4 ）即可求得最 后一个阶段的最优指标函数fN（SN）；有了 fN（SN），继续利用式（7-3 ） 或式（7-4 ）即可求得最后两个阶段的最优指标函数fN（SNj ；有了 fN4（SN4）,进一步又可以求得最后三个阶段的最优指标函数 fN小Snj）；反复递推下去，最终即可求得全过程N个阶段的最优指标 函数fi（Si），从而使问题得到解决。由于上述最优指标函数的构建是 按阶段的逆序从后向前进行的，所以也称为动态规划的逆序算法。 通过上述分析可以看出，任何一个多阶段决策过程的最优化问 题，都可以用非线性规划（特殊的可以用线性规划）模型来描述；因 此，从原则上讲，一般也可以用非线性规划（或

16、线性规划）的方法来 求解。那么利用动态规划求解多阶段决策过程有什么优越性、又有什 么局限性呢? 动态规划的优点：第一，求解更容易、效率更高。动态规划方法 AAAAAA 精品文档你我共享 是一种逐步改善法，它把原问题化成一系列结构相似的最优化子问 题，而每个子问题的变量个数比原问题少得多，约束集合也简单得多, 故较易于确定最优解。第二，解的信息更丰富。非线性规划(或线性 规划)的方法是对问题的整体进行一次性求解的，因此只能得到全过 程的解；而动态规划方法是将过程分解成多个阶段进行求解的，因此 不仅可以得到全过程的解，同时还可以得到所有子过程的解。 动态规划的缺点：第一，没有一个统一的标准模型。由

17、于实际问 题不同，其动态规划模型也就各有差异，模型构建存在一定困难。第 二，应用条件苛刻。由于构造动态规划模型状态变量必须满足“无后 效性”条件，这一条件不仅依赖于状态转移律，还依赖于允许决策集 合和指标函数的结构，不少实际问题在取其自然特征作为状态变量时 并不满足这一条件，这就降低了动态规划的通用性。第三，状态变量 存在“维数障碍”。最优指标函数fk(Sk)是状态变量的函数，当状态 变量的维数增加时，最优指标函数的计算量将成指数倍增长；因此， 无论是手工计算还是电算“维数障碍”都是无法完全克服的。 7.2确定性动态规划问题 确定性动态规划问题即阶段的输出状态完全由其输入状态和决 策所决定的动

18、态规划问题。确定性动态规划解决的问题可能包含经济 管理的方方面面，可以是最短路线问题，可以是资源配置问题，也可 以是其他的规划优化问题。最短路线问题直观、具体地演示了动态规 划的基本概念和基本步骤；因此，让我们首先来分析一下最短路线问 题。 2-1最短路线问题 例7-1美国黑金石油公司（The Black Gold Petroleum AAAAAA 精品文档你我共享 Com pan）最近在阿拉斯加（Alaska）的北斯洛波（North Slope ）发 现了大的石油储量。为了大规模开发这一油田，首先必须建立相应的 输运网络，使北斯洛波生产的原油能运至美国的 3个装运港之一。在 油田的集输站（结

19、点C）与装运港（结点Pi、P2、R）之间需要若干 个中间站，中间站之间的联通情况如图7-2所示，图中线段上的数字 代表两站之间的距离（单位：10千米）。试确定一最佳的输运线路， 使原油的输送距离最短。 解：最短路线有一个重要性质，即如果由起点A经过B点和C点 到达终点D是一条最短路线，则由B点经C点到达终点D定是B到 D的最短路（贝尔曼最优化原理）。此性质用反证法很容易证明，因 为如果不是这样，则从B点到D点有另一条距离更短的路线存在，不 妨假设为B-P-D;从而可知路线 A B-P-D比原路线A-B-C-D 距离短，这与原路线A-B-C-D是最短路线相矛盾，性质得证。 根据最短路线的这一性质

20、，寻找最短路线的方法就是从最后阶段 开始，由后向前逐步递推求出各点到终点的最短路线，最后求得由始 点到终点的最短路；即动态规划的方法是从终点逐段向始点方向寻找 最短路线的一种方法。按照动态规划的方法，将此过程划分为4个阶 段，即阶段变量k =1,234 ；取过程在各阶段所处的位置为状态变量 Sk , 按逆序算法求解。 M 31 P1 M21 6 P2 P3 M 23 33 11 5 4 精品文档你我共享 当k = 4时: 由结点 Mi到达目的地有两条路线可以选择，即选择 R 或 P2； 故: 8 f4(S4 =M3i) =mi nj =6 选择P2 由结点 M2到达目的地有三条路线可以选择，即

21、选择 Pi、 P2 或 R;故: f4(S4 = M 32) = min3 = 3 k 选择P2 由结点 M3到达目的地也有三条路线可以选择，即选择 Pi、P2 或P3;故: 7 4(64 =M33)=min6 = 5 选择 |P 15. 由结点 M34到达目的地有两条路线可以选择，即选择 P2 或 P3； 故: =3 选择P? .3 f4 (S4 M 34)= min 彳 14 J 当k =3时: 由结点 Mi到达下一阶段有三条路线可以选择，即选择 或M3；故: io+6 f3（S3 =M 21） =min 7 +3 j = 1O 选择皿2 l6+5 J Mi、 由结点 M2到达下一阶段也有

22、三条路线可以选择，即选择 M2或M3；故: AAAAAA f32M22）=min9：6L10 选择M2或M3 5+5J 由结点M3到达下一阶段也有三条路线可以选择，即选择 M2、Mb 或M4;故: ii +3 f3（S3 = M 23）= min * 4 + 5 = 9 选择M3或M4 故: 故: 故: 当k=2时: 由结点 Mi到达下一阶段有两条路线可以选择，即选择Mi或M2； 8+10 f2（S2 =M11）=mi n（6 +10j =16 选择M2 由结点M2到达下一阶段也有两条路线可以选择，即选择M2或M3； .9 + 10 f2 （S2 =皿12）= min5 21（11 + 9 =

23、19 选择M2 当k =1时: 由结点C到达下一阶段有两条路线可以选择，即选择 Mi或M2； 精品文档你我共享 f1（S1 =C） = mi np 16 10+19 =28 选择M1 从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条 最佳的输运线路：C Mi M22 M32 P2； C M1iM22 Mb R。最短的 输送距离是280千米。 2-2资源分配问题 所谓资源分配问题，就是将一定数量的一种或若干种资源 （如原 材料、机器设备、资金、劳动力等）恰当地分配给若干个使用者，以 使资源得到最有效地利用。设有m种资源，总量分别为bi （i二 1,2，m，用于生产n种产品，若用Xj代表用

24、于生产第j种产品的 第i种资源的数量（j = 1,2,，n），则生产第j种产品的收益是其 所获得的各种资源数量的函数，即gj = f（ X1j,X2j,，Xmj）。由于总 收益是n种产品收益的和，此问题可用如下静态模型加以描述: n Z Xij = b （i =1,2，,m） j# （i =1,2，m;j =1,2，n） 若Xij是连续变量，当 gj = f（ X1j,X2j,，Xmj）是线性函数时，该 模型是线性规划模型；当 gj = f （ X1j,X2j,，Xmj）是非线性函数时, 该模型是非线性规划模型。 若Xij是离散变量或（和）gj = f（X1j, X2j,， AAAAAA 精品

25、文档你我共享 Xmj）是离散函数时，此模型用线性规划或非线性规划来求解都将是非 常麻烦的。然而在此情况下，由于这类问题的特殊结构，可以将它看 成为一个多阶段决策问题，并利用动态规划的递推关系来求解。 本教材只考虑一维资源的分配问题，设状态变量S表示分配于从 第k个阶段至过程最终（第N个阶段）的资源数量，即第k个阶段初 资源的拥有量；决策变量Xk表示第k个阶段资源的分配量。于是有状 态转移律: 允许决策集合: Dk (Sk) = Xk I 0 兰 Xk 兰 Sk 最优指标函数（动态规划的逆序递推关系式） 存6）迪強（2 + 3（盼）你対-仆-2，1） f N-H(SN 十)=0 利用这一递推关系

26、式，最后求得的f1（S1）即为所求问题的最大总收 益，下面来看一个具体的例子。 例7-2某公司拟将500万元的资本投入所属的甲、乙、丙三 个工厂进行技术改造，各工厂获得投资后年利润将有相应的增长， 增 长额如表7-1所示。试确定500万元资本的分配方案，以使公司总的 年利润增长额最大。 表7-1 投资额 100万元 200万元 300万元 400万元 500万元 甲 30 70 90 120 130 乙 50 100 110 110 110 丙 40 60 110 120 120 解:将问题按工厂分为 三个阶段k = 1,2,3，设状态变量Sk（ k = 1,2,3） 代表从第k个工厂到第3个

27、工厂的投资额，决策变量Xk代表第k个工 厂的投资额。于是有状态转移率Skh =Sk-xk、允许决策集合 Dk（Sk）二Xk |0Xk Sk和递推关系式： fkekXomaXJgkg + fWSkXk）（k2,1） f4（S4）=0 当k =3时: f3（s3）=omaxsg3（x3）+o Mjmasjgsas） 于是有表7-2，表中x3表示第三个阶段的最优决策。 S3 0 1 2 3 4 5 * X3 0 1 2 3 4 5 f3（S3） 0 0.4 0.6 1.1 1.2 1.2 （单位：百万元） 表7-2 f2（S2H0mXa,g2（X2）中 f3（S2 -X2） 于是有表7-3。 f2（

28、S2） 表7-3（单位：百万元） g2（ X2）+f3（ S2 - X 2） 2 0 1 2 3 4 5 0 0+0 0 0 i 0+0. 0.5+0 0.5 1 4 2 0+0. 0.5+0. 1.0+0 1.0 2 6 4 3 0+i. 0.5+0. 1.0+0. 1.1+0 1.4 2 1 6 4 4 0+1. 0.5+1. 1.0+0. 1.1+0. 1.1+0 1.6 1, 2 1 6 4 2 5 0+1. 0.5+1. 1.0+1. 1.1+0. 1.1+0. 1.1 + 2.1 2 2 2 1 6 4 0 当k =1时: fi(Si) =0maxsgi(Xi) + f2(Si -

29、Xi) 于是有表7-4。 表7-4 gi (Xi) +f2 (si - X 1) 0 1 2 3 4 5 fi(Si) Xi 5 0+2. 0.3+1. 0.7+1. 0.9+1. 1.2+0. 1.3+ 2.1 0， 1 6 4 0 5 0 2 然后按计算表格的顺序反推算，可知最优分配方案有两个：（1） 甲工厂投资200万元，乙工厂投资200万元，丙工厂投资100万元; （2）甲工厂没有投资，乙工厂投资200万元，丙工厂投资300万元。 按最优分配方案分配投资（资源），年利润将增长210万元。 这个例于是决策变量取离散值的一类分配问题，在实际问题中, 相类似的问题还有销售店的布局（分配）问题

30、、设备或人力资源的分 配问题等。在资源分配问题中，还有一种决策变量为连续变量的资源 分配问题，请见例7-3。 例7-3机器负荷分配问题。某种机器可在高低两种不同的负 荷下进行生产，设机器在高负荷下生产的产量（件）函数为gi =8x， 其中x为投入高负荷生产的机器数量，年度完好率 a =0.7 （年底的完 好设备数等于年初完好设备数的70% ；在低负荷下生产的产量（件） 函数为g5y，其中y为投入低负荷生产的机器数量，年度完好率 P =0.9。假定开始生产时完好的机器数量为1000台，试问每年应如 何安排机器在高、低负荷下的生产，才能使 5年生产的产品总量最 多？ 解：设阶段k表示年度（k= 1

31、23,4,5）；状态变量Sk为第k年度初 拥有的完好机器数量（同时也是第 k-1年度末时的完好机器数量）。 决策变量Xk为第k年度分配高负荷下生产的机器数量，于是 Sk -Xk为该年度分配在低负荷下生产的机器数量。这里的 Sk和Xk均为连续变 量，它们的非整数值可以这样理解：如Sk =0.6就表示一台机器在第k 年度中正常工作时间只占全部时间的 60% Xk=0.3就表示一台机器在 第k年度中只有30%勺工作时间在高负荷下运转。 状态转移方程为： Sk+ =口兀 + 0（氏xk） =0.7xk +0.9（81, xk） =0.9Sk 0.2xk 允许决策集合： Dk （Sk） = Xk I 0

32、 350 0.9S5 -0.2X5 350 允许决策集合: X5 4.5S5 -1750 Dk(Sk) =Xk |0兰Xk兰Sk “加”第k阶段的终端递推条 对于k =5, 考虑终端递推条件有: D5(S5)=X5 |0X5 4.5S5 -1750 389 同理其他各阶段的允许决策集合可在过程指标函数的递推中产 生。 设阶段指标: Qk(Sk,Xk) =8Xk +5(Sk Xk) =5Sk +3Xk 过程指标: 最优值函数： 5 Qk5 =2 Qj j 土 fk（Sk） =xk骡k）5Sk +3Xk 十 fy（0.9Sk -azxk） 边界条件f6（S6）=0。 当k = 5时: f5（S5）

33、jmaxU5S5 +3x5 + f6（S6）=码愆炉5 +3旳 因f5（S5）是关于X5的单调递增函数，故取x5 = 4.5S5 -1750 ,相应有: 即: O4.5S5 -175OS5 389 Ss 500 x5 =4.5S5 -1750， f5（S5）=18.5S5 -5250 当k = 4时: f4（S4mDax）5S3x f5（0.9S0.2x4） =max 21.65S4 -0-7x4 -5250 X4 0 （S4 ） 由 S5 =O.9S4 -0.2x4 4.5S4 -2500,又因 是关于 X4 的单调递减函数，故取X： =4.5S4 -2500，相应有: 0 4.5S4 -2

34、5OOS4 556S4 714 x4 =4.5S4 -2500， f4（S4）=18.5S4 -3500 当k = 3时: f3（S3） =X3聽）5S3 十陕 + f4（0.9S3 。.“3） =max 21.65s3 0.7x3 -3500 X3S3 （Os） 由 S4 =O.9S3 -0.2x3 4.5S3 -3570，又因 f3（S3）是关于怡 的单调递减函数，故取x3 =4.5S3 - 3570，相应有: O4.5S3 -357OS3 793 S3 1020 由于5=1000，所以S3 0 最优指标函数：最优指标函数具有如下递推形式 fk(Sk) =mi nCk +Gk + Z k

35、+ fk41(Sk 卅) Xk =mi nCk +Gk +0.2(Sk +Xk -dk)+ fk41(Sk +Xk-dk) xk 当k=6时(3月)： 表7-7 S6 0 10 20 X6 20 10 0 f6 (S6) 86 48 0 当k = 5时（2月）： 表7-8 X5 0 10 20 30 40 50 X f5（S5） 0 204 188 164 50 164 10 172 168 142 40 142 20 134 136 122 30 122 30 86 98 90 0 86 40 50 52 0 50 50 4 0 4 当k = 4时（1月）: 表7-9 X4 S 0 10 2

36、0 30 40 50 * X4 f4（S4） 0 302 304 40 302 10 282 282 286 30、 282 40 20 250 262 264 252 20 250 30 212 230 244 230 218 10 212 40 164 192 212 210 196 170 0 164 50 144 174 178 176 152 0 144 60 126 140 144 132 0 126 当k=3时（12月）: 表 7-10 、X3 S 0 10 20 30 40 50 x3 f 3(S3 ) 0 420 422 414 50 414 10 388 402 392 3

37、84 50 384 20 350 370 372 362 332 50 332 30 302 332 340 342 310 314 0 302 40 284 302 310 290 292 298 0 284 当k=2时（11月）: 表 7-11 0 10 20 30 40 50 * X2 f2（S2） 0 500 504 474 468 50 468 10 462 472 454 446 452 40 446 当k =1时（10月）: 表 7-12 0 10 20 30 40 50 X1 f1(S) 0 606 608 40 606 10月份 利用状态转移律，按上述计算的逆序可推算出最优策略: 采购4箱（40双），11月份采购5箱（50双），12月份不采购，1月 份采购4箱（40双），2月份采购5箱（50双），3月份不采购；最小 的销售费用为606美元。 2-4用动态规划求解非线性规划问题 非线性规划问题的求解（在第六章中已讨论）是非常困难的；然 而，对于有些非线性规划问题，如果转化为用动态规划来求解将是十 分方便的。 例7-5用动态规划求解 2 max Z =片 X X2 X X3 Xj +X2 + X3 =36 X1,X2,X3 0 解：阶段：将问题的变量数作为阶段，即k =1,2,3 ； 决策变量：决策变量Xk ； 状态变量：状态变量Sk代表第k阶段的约束右