《运筹学研究生辅导课件》第二章动态规划.ppt

《《运筹学研究生辅导课件》第二章动态规划.ppt》由会员分享，可在线阅读，更多相关《《运筹学研究生辅导课件》第二章动态规划.ppt（109页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 动态规划 动态规划作为运筹学的一个重要分支是解决多阶动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。段决策过程最优化的一种非常有效的方法。1951年，年，美国数学家贝尔曼（美国数学家贝尔曼（R.Bellman）等人，根据一类）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。贝尔曼等人在研究和解决了大量实际问题之以解决。贝尔曼等人在研究和解决了大量实际问题之后，提出了解决这类问题的后，提出了解决这类问

2、题的所谓所谓“最优性原理最优性原理”，通常称为，通常称为“贝尔曼最优化原理贝尔曼最优化原理”，从而创建了解决，从而创建了解决最优化问题的一种新的方法最优化问题的一种新的方法 动态规划动态规划（Dynamic Programming ）。）。2511214106104131112396581052C1C3D1AB1B3B2D2EC2 为了说明动态规划的基本思想方法和特点，以下图所示为例，讨论求最短路问题的方法。求从A到E的最短路径2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C

3、3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214106104131112396581052C1C3D1AB1B3

4、B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212511214106104131112396581052C1

5、C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2

6、(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1251121410610413111239658

7、1052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态

8、 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D1 （D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E 1、阶段（阶段（stage）为为了了便便于于求求解解和和表表示示决决策策过过程程的的发发展展顺顺序序，而而把把所所给给问问题题恰恰当当地地划划分分为为若若干干个个相相互互联联系系又又有有区区别别的的子子问问题题，称称之之为为多多段段决决策策问问题题的的阶阶段段。一一个个阶阶段段，就就是是需需要要作作出出一一个个决决策策的的子子问问题题，通通常常，阶阶段段是是按按决决策策进进行行的的时时间间顺顺序序或或

9、空空间间特特征征上上先先后后顺顺序序划划分分的的。用用以以描描述述阶阶段段的的变变量量叫叫作作阶阶段段变变量量，一一般般以以k表表示示阶阶段段变变量量阶阶段段数数等等于于多多段段决决策策过过程程从从开开始始到到结结束束所所需需作作出出决决策策的的数数目目，例例如如上上面面的的最最短短路路问问题就是一个四阶段决策过程。题就是一个四阶段决策过程。动态规划的基本概念和基本原理动态规划的基本概念和基本原理2、状态（状态（state）每个阶段开始时过程所处的自然状况或客观每个阶段开始时过程所处的自然状况或客观条件。条件。反映状态变化的量叫做状态变量，它可以反映状态变化的量叫做状态变量，它可以用一个数，一

10、组数或一向量来描述，用一个数，一组数或一向量来描述，。状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需必须包含在给定的阶段上确定全部允许决策所需要的信息。要的信息。它应能描述过程的特征并具有它应能描述过程的特征并具有“无后无后效性效性”，即当前阶段状态给定时，这个阶段以后，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。用过程的演变与该阶段以前各阶段的状态无关。用sk表示状态变量表示状态变量（state variable）。）。一一般般状状态态变变量量的的取取值值有有一一定定的的范范围围或或允允许许集集合合，称称为为可可能能状状态态集集（set of ad

11、missible states）。可可能能状状态态集集实实际际上上是是关关于于状状态态的的约约束束条条件件。通通常常可可能能状状态态集集用用相相应应阶阶段段状状态态sk的的大大写写字字母母Sk表表示示，可可能能状状态态集集可可以以是是一一离离散散取取值值的的集集合合，也也可可以以为为一一连连续续的的取取值值区区间间，视视具具体体问问题题而而定定例例如如上上面面的的最最短短路路问问题题中中，第第一一阶阶段段状状态态为为A，状状态态变变量量s1的的状状态态集集合合S1=A；第第二二阶阶段段则则有有三三个个状状态态：B1,B2,B3,状状态态变变量量s2的的状状态态集集合合S2=B1,B2,B3 .

12、3、决策（决策（decision）当一个阶段的状态确定后，可以作出不同的当一个阶段的状态确定后，可以作出不同的决定决定或选择或选择，从而演变到下一阶段的某个状态，这种决定，从而演变到下一阶段的某个状态，这种决定或选择称为决策。或选择称为决策。用以描述决策变化的量称之决策变量用以描述决策变化的量称之决策变量（decision variable）。和状态变量一样，决策变量可以用一个。和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，由于各阶段的决策取决数，一组数或一向量来描述，由于各阶段的决策取决于状态变量于状态变量sk，所以用，所以用 uk(sk)，表示阶段，表示阶段k的状态为的状态为

13、sk时的决策变量。时的决策变量。决策变量的取值往往也有一定的允许范围，称之决策变量的取值往往也有一定的允许范围，称之允许决策集合允许决策集合（set of admissible decision）。）。决决策变量策变量uk(sk)的允许决策集用的允许决策集用Uk(sk)表示表示,允许决策集允许决策集合实际是决策的约束条件。合实际是决策的约束条件。4、策略（策略（policy）一组有序的一组有序的决策序列决策序列构成一个策略，从第构成一个策略，从第k阶阶段至第段至第n阶段的一个策略称为阶段的一个策略称为k部部子策略记为子策略记为 pk,n(sk)=uk，uk+1，un，当当k=1时的时的k部子策

14、部子策略称为全过程策略，简称策略，记为略称为全过程策略，简称策略，记为p1,n(s1)。在实际问题中，由于在各个阶段可供选择的在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列多可供选择的决策序列(策略策略)，由它们组成的集合，由它们组成的集合，称之允许策略集合，记作称之允许策略集合，记作P1,n，从允许策略集中，从允许策略集中，找出具有最优效果的策略称为最优策略。找出具有最优效果的策略称为最优策略。5、状态转移方程（状态转移方程（equation of state transition）反映前后反

15、映前后阶段状态之间关系的方程称为阶段状态之间关系的方程称为状状态转移方程。在确定型多阶段决策过程中，态转移方程。在确定型多阶段决策过程中，一旦某阶段的状态和决策为已知，下一阶段一旦某阶段的状态和决策为已知，下一阶段的的 状态便完全确定，用状态转移方程反映这状态便完全确定，用状态转移方程反映这种状态间的种状态间的演变规律演变规律，记作：，记作：有些问题的状态转移方程不一定存在数学表有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律达式，但是它们的状态转移，还是有一定规律可循的。可循的。6、阶段指标值（阶段指标值（objective value in a stage）阶

16、段指标值是第阶段指标值是第k阶段的状态为阶段的状态为sk和采取决策和采取决策uk时的效益，通常表示为时的效益，通常表示为 dk（sk，uk）。）。对对不不同同问问题题，阶阶段段指指标标值值可可以以是是诸诸如如费费用用、成成本本、产产值值、利利润润、产产量量、耗耗量量、距距离离、时时间间，等等等等。例例如如上上面面的的最最短短路路问问题题中中，如如果果第第二二阶阶段段地地状状态态为为B2,采采取取决决策策是是由由B2到到达达C1,则则阶阶段段指指标标值为值为6。7、指标函数（指标函数（objective function）衡量在选定某策略时，其优劣的数量指标。衡量在选定某策略时，其优劣的数量指标

17、。定义在整个过程（定义在整个过程（1到到n阶段）上的指标函数阶段）上的指标函数记为：记为：V1,n（s1，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

18、,n(sk)的函数，因此它可的函数，因此它可简记简记为：为：Vk,n（sk，pk,n）指指标标函函数数Vk,n（sk，pk,n）通通常常是是描描述述所所实实现现的的全全过过程程或或k后后部部子子过过程程效效果果优优劣劣的的数数量量指指标标，它它是是由由各各阶阶段段的的阶阶段段指指标标函函数数dk（sk，uk）累累积积形形成成的的，适适于于用用动动态态规规划划求求解解的的问问题题的的指指标标函函数数，必必须须具具有有关关于于阶阶段段指指标标的的可可分分离离形形式式对对于于后后部部子过程的指标函数可以表示为：子过程的指标函数可以表示为：式中，式中，表示某种运算，可以是加、乘等。表示某种运算，可以是

19、加、乘等。总总之之，具具体体问问题题的的目目标标函函数数表表达达形形式式需需要要视视具体问题而定。具体问题而定。多阶段决策问题中，常见的目标函数形式之一多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即是取各阶段效应之和的形式，即:有些问题，如系统可靠性问题，其目标函数是有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如：取各阶段效应的连乘积形式，如：8、最优指标函数（最优指标函数（optimal value function）指标函数的最优值称为最优指标函数，记为指标函数的最优值称为最优指标函数，记为fk(sk)，它表示，它表示从第从第k阶段状态阶段状态

20、sk 出发，采用出发，采用最最优策略优策略到终止状态时的后部子过程指标函数值，到终止状态时的后部子过程指标函数值，即即式中式中opt即即optimization，根据具体问题可取，根据具体问题可取max或或min。与它相应的子策略称为在。与它相应的子策略称为在sk状态下状态下的最优子策略，记为的最优子策略，记为pk*(sk)；而构成该子策略；而构成该子策略的各段决策称为该过程上的最优决策，记为的各段决策称为该过程上的最优决策，记为 即即 简记为简记为特别当特别当k=1时，时，f1(s1)就是问题的最优值，而就是问题的最优值，而p1*就是最优策略。例如上面的最短路问题中，就是最优策略。例如上面的

21、最短路问题中，有唯一最优值有唯一最优值f1(s1)=18，而，而就是其最优策略。就是其最优策略。多阶段决策问题的数学模型多阶段决策问题的数学模型 综综上上所所述述，适适于于应应用用动动态态规规划划方方法法求求解解的的一一类类多多阶阶段段决决策策问问题题，亦亦即即具具有有无无后后效效性性的的多多阶阶段段决策问题的数学模型呈以下形式决策问题的数学模型呈以下形式:最优化原理最优化原理 （贝尔曼最优化原理）（贝尔曼最优化原理）作作为为一一个个全全过过程程的的最最优优策策略略具具有有这这样样的的性性质质：对对于于最最优优策策略略过过程程中中的的任任意意状状态态而而言言，无无论论其其过过去去的的状状态态和

22、和决决策策如如何何，余余下下的的诸诸决决策策必必构构成成一一个个最最优优子子策策略略。该该原原理理的的具具体体解解释释是是，若若某某一一全全过过程最优策略为：程最优策略为：则对上述策略中所隐含的任一状态而言，则对上述策略中所隐含的任一状态而言，第第k子过程上对应于该状态的最优策略必然子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略包含在上述全过程最优策略p1*中，即为中，即为 动态规划的动态规划的基本方程基本方程 在在上上面面最最短短路路问问题题的的求求解解过过程程中中，在在求求解解的的各各阶阶段段利利用用了了第第k阶阶段段和和第第k+1阶阶段段的的如如下下递递推推关系关系：其中，

23、其中，表示从状态表示从状态sk到由决策到由决策uk(sk)所决定的状态所决定的状态sk+1之间的距离。之间的距离。一一般般地地，对对于于n n个个阶阶段段的的决决策策过过程程，假假设设只只考考虑虑指指标标函函数数是是“和和”与与“积积”的的形形式式，第第k k阶阶段和第段和第k k+1+1阶段间的递推公式可表示如下：阶段间的递推公式可表示如下：(1)(1)当当指指标标函函数数为为下下列列“和和”的的形形式式时时，其其相应的基本方程为相应的基本方程为是边界条件。是边界条件。(2)当当过过程程指指标标函函数数为为下下列列“积积”的的形形式式时时,其相应的基本方程为其相应的基本方程为 一般来说一般来

24、说,要用函数基本方程逆推求解要用函数基本方程逆推求解,首先要有效地建立动态规划模型首先要有效地建立动态规划模型,然后再递推然后再递推求解求解,最后得出结论最后得出结论.然而然而,要把一个实际问题要把一个实际问题用动态规划方法来求解用动态规划方法来求解,还必须首先根据问题还必须首先根据问题的要求。把它构造成动态规划模型的要求。把它构造成动态规划模型,这是非常这是非常重要的一步。正确地建立一个动态规划模型重要的一步。正确地建立一个动态规划模型,往往问题也就解决了一大半往往问题也就解决了一大半,而一个正确的动而一个正确的动态规划模型态规划模型,应该满足哪些条件呢应该满足哪些条件呢?动态规划求解的一般

25、步骤：-确定过程的分段，构造状态变量；-设置决策变量，写出状态转移；-列出阶段指标和指标函数；-写出基本方程，由此逐段递推求解。机器负荷问题例例1 1 有某种机床有某种机床,可以在高低两种不同的可以在高低两种不同的负荷下进行生产负荷下进行生产,在高负荷下生产时在高负荷下生产时,产产品的年产量为品的年产量为g g,与年初投入生产的机床与年初投入生产的机床数量数量u u1 1的关系为的关系为g g=g g(u u1 1)=8)=8u u1 1,这时这时,年终年终机床完好台数将为机床完好台数将为auau1 1,(,(a a为机床完好率，为机床完好率，00a a1,1,设设a a=0.7).=0.7)

26、.在低负荷下生产时在低负荷下生产时,产产品的年产量为品的年产量为h h,和投入生产的机床数量和投入生产的机床数量u u2 2的关系为的关系为h h=h h(u u2 2)=5)=5u u2 2,相应的机床完好率相应的机床完好率为为b b(0(0b b1,1,设设b b=0,9),=0,9),一般情况下一般情况下a a 0所以 d2(x2)=d2|13-x2d217-x2由此 f2(x2)=5(13-x2)-13x2+377=-18x2+442,d2*=13-x2生生 产产 库库 存存 问问 题题对于k=1f1(x1)=minc1d1+f2(x2)d1D1(x1)=min11d1+442-18x

27、2 d1D1(x1)=min11d1+442-18(x1-r1+d1)d1D1(x1)=min11d1+442-18(x1-0+d1)d1D1(x1)=min-7d1-18x1+442 d1D1(x1)D D1 1(x(x1 1)=d)=d1 1|d|d1 1 0,r0,r2 2 x x1 1-r-r1 1+d+d1 1 HH =d =d1 1|d|d1 1 0,r0,r2 2+r+r1 1-x-x1 1 d d1 1 H+rH+r1 1-x-x1 1 =d =d1 1|d|d1 1 0,8-x0,8-x1 1 d d1 1 9-x9-x1 1 生生 产产 库库 存存 问问 题题根据题意 x1

28、=2所以 D1(x1)=d1|6d17由此 d1=7f1(x1)=-7d1-18x1+442=-77182442=357将以上结果总结成下表：生生 产产 库库 存存 问问 题题三、设备更新问题例4 某运输公司购进一批卡车投入运营，公司每年初需对卡车作出更新或继续使用的决定。假设第k年中，rk(tk)表示车龄为tk的车使用一年的收入，uk(tk)表示车龄为tk的车使用一年的维修费用，ck(tk)表示车龄为tk的车更新成新车的费用。现公司需制定一个10年计划，以决定如何安排使10年的总收入最大。12S1=？x1x2 10 x10s10v1v2v10s2问题：状态和决策怎样设置？决策是更新与否，可用

29、0-1变量表示；状态可设为车龄。阶段k状态sk决策xk=1,10表示第k年的决策过程；=tk表示第k年的车龄；状态转移tk+1=tk +1(1-xk)阶段指标vk指标函数vkn=rktk -uktk -ck(tk)(1-xk)(1-xk)xk例例9 （生产（生产库存问题）库存问题）某工厂要对一种产品制定今后四个时期的某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为产品的需求量分别为2，3，2，4单位，假设每单位，假设每批产品固定成本为批产品固定成本为3千元，若不生产为千元，若不生产为0，每单位，每单位产品

30、成本为产品成本为1千元，每个时期最大生产能力不超千元，每个时期最大生产能力不超过过6个单位，每期期末未出售产品，每单位需付个单位，每期期末未出售产品，每单位需付存贮费存贮费0.5千元，假定第千元，假定第1期初和第期初和第4期末库存量期末库存量均为均为0，问该厂如何安排生产与库存，可在满足，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。市场需求的前提下总成本最小。解解:以每个时期作为一个阶段，该问题分为以每个时期作为一个阶段，该问题分为4个个阶段，阶段，k=1，2，3，4；决策变量决策变量xk表示第表示第k阶段生产的产品数；阶段生产的产品数；状态变量状态变量sk表示第表示第k阶段

31、初的库存量；阶段初的库存量；以以dk表示第表示第k阶阶段的需求，段的需求，则则状状态转态转移方程：移方程：sk+1=sk+xkdk；k=4，3，2，1由于期初及期末由于期初及期末库库存存为为0，所以，所以s1=0，s5=0；允允许许决策集合决策集合Dk（sk）的确定：当）的确定：当skdk时时，xk可可以以为为0，当，当skdk时时，至少，至少应应生生产产dksk，故，故xk的下的下限限为为max（0，dksk）每期最大生）每期最大生产产能力能力为为6，xk最大不超最大不超过过6，由于期末，由于期末库库存存为为0，xk还应还应小于本期小于本期至至4期需求之和减去本期的期需求之和减去本期的库库存

32、量，存量，所以所以xk的上限的上限为为min（，6），故有：），故有：Dk（sk）=xk|max（0，dksk）xkmin（，6）阶阶段指段指标标函数函数rk（sk，xk）表示第）表示第k期的生期的生产费产费用用与存与存贮费贮费用之和：用之和：最最优优指指标标函数函数fk（sk）表示第）表示第k期期库库存存为为sk到第到第4期期末的生末的生产产与存与存贮贮最低最低费费用，用，动态规动态规划基本方程划基本方程为为：例例10 （库库存存销销售售问题问题）设设某公司某公司计计划在划在1至至4月份从事某种商品月份从事某种商品经营经营。已知已知仓库仓库最多可存最多可存储储600件件这这种商品，已知种商品

33、，已知1月初月初存存货货200件，根据件，根据预测预测知知1至至4月份各月的月份各月的单单位位购货购货成本及成本及销销售价格如表售价格如表6.13所示，每月只能所示，每月只能销销售本月售本月初的初的库库存，当月存，当月进货进货供以后各月供以后各月销销售，售，问问如何安如何安排排进货进货量和量和销销售量，使售量，使该该公司四个月公司四个月获获得利得利润润最最大（假大（假设设四月底四月底库库存存为为零）。零）。表表6.13 单单位位购货购货成本及成本及销销售价格售价格月份月份购货购货成本成本C销销售价格售价格P12344038404245423944解解:按月份划分阶段，按月份划分阶段，k=1，2

34、，3，4；状态变量状态变量sk表示第表示第k月初的库存量，月初的库存量，s1=200，s5=0；决策变量：决策变量：xk表示第表示第k月售出的货物数量，月售出的货物数量，yk表示表示第第k月购进的货物数量；月购进的货物数量；状态转移方程：状态转移方程：sk+1=sk+yk-xk；允许决策集合：允许决策集合：0 xksk，0yk600-（sk-xk）；）；阶段指标函数为：阶段指标函数为：pkxkckyk表示表示k月份的利润，其月份的利润，其中中pk为第为第k月份的单位销售价格，月份的单位销售价格，ck为第为第k月份的单月份的单位购货成本；位购货成本；最优指标函数最优指标函数fk（sk）表示第）表

35、示第k月初库存为月初库存为sk时从第时从第k月至第月至第4月末的最大利润，则动态规划基本方程为：月末的最大利润，则动态规划基本方程为：k=4时时，x4*=s4y4*=0k=3时时，为为求出使求出使44s35x3+4y3最大的最大的x3，y3，须须求解求解线线性性规规划划问题问题：只有两个只有两个变变量量x3，y3，可用，可用图图解法也可用解法也可用单纯单纯形形法求解，取得最法求解，取得最优优解，解，x3*=0，y3*=600s3，f3（s3）=40s3+2400例例 某部门欲采购一批原料，原料价格在五周内可能某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该种原料今后五周内取不同单

36、价有所变动，已预测得该种原料今后五周内取不同单价的概率如下表所示。试确定该部门在五周内购进这批的概率如下表所示。试确定该部门在五周内购进这批原料的最优策略，使采购价格的期望值最小。原料的最优策略，使采购价格的期望值最小。原料价格（元）原料价格（元）概率概率5006007000.30.30.4100解解 这里价格是一个随机变量，是按某种已知的概这里价格是一个随机变量，是按某种已知的概率分布取值的。用动态规划方法处理，按采购期限率分布取值的。用动态规划方法处理，按采购期限5周分周分5个阶段，将每周的价格看作该阶段的状态，设个阶段，将每周的价格看作该阶段的状态，设sk为状态变量，表示第为状态变量，表

37、示第k周的实际价格周的实际价格xk为决策变量，当为决策变量，当xk=1，表示第，表示第k周决定采购；当周决定采购；当xk=0，表示第，表示第k周决定等待。周决定等待。SkE表示第表示第k周决定等待，而在以后采用最优决策周决定等待，而在以后采用最优决策时采购价格的期望值。时采购价格的期望值。101fk(sk)表示第表示第k周周实际实际价格价格为为sk时时，从第，从第k周至第周至第五周采用最五周采用最优优决策所得的最小期望决策所得的最小期望值值。因而可写。因而可写出逆序出逆序递递推关系式推关系式为为fk(sk)=minsk,SkE skSk (1)f5(s5)=s5 s5S5,其中其中Sk=500

38、,600,700,k=1,2,3,4,5.由由SkE和和fk(sk)的定的定义义可知可知SkE=Efk+1(sk+1)=0.3fk+1(500)+0.3fk+1(600)+0.4fk+1(700),(2)并且得出最并且得出最优优决策决策为为(3)从最后一周开始；逐步向前递推计算，具体计从最后一周开始；逐步向前递推计算，具体计算过程如下：算过程如下：k=5时，因时，因f5(s5)=s5,s5S5,故有故有 f5(500)=500；f5(600)=600；f5(700)=700，即在第五周时，若所需的原料尚未买入，则即在第五周时，若所需的原料尚未买入，则无论市场价格如何，都必须采购，不能再等。无论

39、市场价格如何，都必须采购，不能再等。k=4时，由时，由SkE=0.3 fk+1(500)+0.3 fk+1(600)+0.4 fk+1(700)可知可知 S4E=0.3500+0.3600+0.3700=610，由（由（3）式可知，第四周的最）式可知，第四周的最优优决策决策为为于是，由（于是，由（1）式，得）式，得 同理求得 S3E=0.3f4E(500)+0.3f4E(600)+0.3f4E(700)四、其他随机型问题举例例5 某瓷厂接受订制一个瓷瓶的任务。瓷瓶用电炉烧制。据技术分析估计，每个瓷瓶出炉后的合格率为0.5，各瓶合格与否相互独立（即一炉如装有n个瓷瓶，那么出炉后都不合的概率为0.5n）。制造一个瓷瓶的原料费为100元，烧一炉的费用为300元。现因厂中条件限制最多只能烧3炉，每炉最多装4个瓷瓶。若3炉的瓷瓶无1个合格，则因不能履行合同而被罚款1600元。试用动态规划方法确定一种生产方案（即每炉该装几个瓷瓶），使总的期望成本为最小。