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

第二章 动态规划,动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。1951年，美国数学家贝尔曼（R.Bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。贝尔曼等人在研究和解决了大量实际问题之后，提出了解决这类问题的所谓“最优性原理”，通常称为“贝尔曼最优化原理”，从而创建了解决最优化问题的一种新的方法 动态规划（Dynamic Programming）。,为了说明动态规划的基本思想方法和特点，以下图所示为例，讨论求最短路问题的方法。,求从A到E的最短路径,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,f5(E)=0,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,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,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(C1)=8,f4(D1)=5,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,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,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(B1)=20,f3(C2)=7,f3(C1)=8,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,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,f2(B1)=21,f2(B2)=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,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,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,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（B2，C1）C1,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（B2，C1）C1（C1，D1）D1,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（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E,1、阶段（stage）为了便于求解和表示决策过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间顺序或空间特征上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目，例如上面的最短路问题就是一个四阶段决策过程。,动态规划的基本概念和基本原理,2、状态（state）每个阶段开始时过程所处的自然状况或客观条件。反映状态变化的量叫做状态变量，它可以用一个数，一组数或一向量来描述，。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。它应能描述过程的特征并具有“无后效性”，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。用sk表示状态变量（state variable）。,一般状态变量的取值有一定的范围或允许集合，称为可能状态集（set of admissible states）。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定例如上面的最短路问题中，第一阶段状态为A，状态变量s1的状态集合S1=A；第二阶段则有三个状态：B1,B2,B3,状态变量s2的状态集合S2=B1,B2,B3.,3、决策（decision）当一个阶段的状态确定后，可以作出不同的决定或选择，从而演变到下一阶段的某个状态，这种决定或选择称为决策。用以描述决策变化的量称之决策变量（decision variable）。和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，由于各阶段的决策取决于状态变量sk，所以用 uk(sk)，表示阶段k的状态为sk时的决策变量。决策变量的取值往往也有一定的允许范围，称之允许决策集合（set of admissible decision）。决策变量uk(sk)的允许决策集用Uk(sk)表示,允许决策集合实际是决策的约束条件。,4、策略（policy）一组有序的决策序列构成一个策略，从第k阶段至第n阶段的一个策略称为k部子策略记为 pk,n(sk)=uk，uk+1，un，当k=1时的k部子策略称为全过程策略，简称策略，记为p1,n(s1)。在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P1,n，从允许策略集中，找出具有最优效果的策略称为最优策略。,5、状态转移方程（equation of state transition）反映前后阶段状态之间关系的方程称为状态转移方程。在确定型多阶段决策过程中，一旦某阶段的状态和决策为已知，下一阶段的 状态便完全确定，用状态转移方程反映这种状态间的演变规律，记作：,有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。,6、阶段指标值（objective value in a stage）阶段指标值是第k阶段的状态为sk和采取决策uk时的效益，通常表示为 dk（sk，uk）。对不同问题，阶段指标值可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间，等等。例如上面的最短路问题中，如果第二阶段地状态为B2,采取决策是由B2到达C1,则阶段指标值为6。,7、指标函数（objective function）衡量在选定某策略时，其优劣的数量指标。定义在整个过程（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,n(sk)的函数，因此它可简记为：Vk,n（sk，pk,n）,指标函数Vk,n（sk，pk,n）通常是描述所实现的全过程或k后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数dk（sk，uk）累积形成的，适于用动态规划求解的问题的指标函数，必须具有关于阶段指标的可分离形式对于后部子过程的指标函数可以表示为：,式中，表示某种运算，可以是加、乘等。,总之，具体问题的目标函数表达形式需要视具体问题而定。,多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:,有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如：,8、最优指标函数（optimal value function）指标函数的最优值称为最优指标函数，记为fk(sk)，它表示从第k阶段状态 sk 出发，采用最优策略到终止状态时的后部子过程指标函数值，即,式中opt即optimization，根据具体问题可取max或min。与它相应的子策略称为在sk状态下的最优子策略，记为pk*(sk)；而构成该子策略的各段决策称为该过程上的最优决策，记为,即,简记为,特别当k=1时，f1(s1)就是问题的最优值，而p1*就是最优策略。例如上面的最短路问题中，有唯一最优值f1(s1)=18，而,就是其最优策略。,多阶段决策问题的数学模型 综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:,最优化原理（贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：,则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为,动态规划的基本方程 在上面最短路问题的求解过程中，在求解的各阶段利用了第k阶段和第k+1阶段的如下递推关系：,其中，,表示从状态sk到由决策uk(sk)所决定的状态sk+1之间的距离。,一般地，对于n个阶段的决策过程，假设只考虑指标函数是“和”与“积”的形式，第k阶段和第k+1阶段间的递推公式可表示如下：(1)当指标函数为下列“和”的形式时，其相应的基本方程为,是边界条件。,(2)当过程指标函数为下列“积”的形式时,其相应的基本方程为,一般来说,要用函数基本方程逆推求解,首先要有效地建立动态规划模型,然后再递推求解,最后得出结论.然而,要把一个实际问题用动态规划方法来求解,还必须首先根据问题的要求。把它构造成动态规划模型,这是非常重要的一步。正确地建立一个动态规划模型,往往问题也就解决了一大半,而一个正确的动态规划模型,应该满足哪些条件呢?,动态规划求解的一般步骤：-确定过程的分段，构造状态变量；-设置决策变量，写出状态转移；-列出阶段指标和指标函数；-写出基本方程，由此逐段递推求解。,机器负荷问题例1 有某种机床,可以在高低两种不同的负荷下进行生产,在高负荷下生产时,产品的年产量为g,与年初投入生产的机床数量u1的关系为g=g(u1)=8u1,这时,年终机床完好台数将为au1,(a为机床完好率，0a1,设a=0.7).在低负荷下生产时,产品的年产量为h,和投入生产的机床数量u2的关系为h=h(u2)=5u2,相应的机床完好率为b(0b1,设b=0,9),一般情况下ab。,假设某厂开始有x=1000台完好的机床，现要制定一个五年生产计划，问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为最高。解：首先构造这个问题的动态规划模型。1变量设置(1)设阶段变量k表示年度，因此，阶段总数n=5。(2)状态变量sk表示第k年度初拥有的完好机床台数，同时也是第k-1年度末时的完好机床数量。,(3)决策变量uk，表示第k年度中分配于高负荷下生产的机床台数。于是sk-uk便为该年度中分配于低负荷下生产的机床台数 这里sk与uk均取连续变量，当它们有非整数数值时可以这样理解：如sk0.6，就表示一台机器在k年度中正常工作时间只占6/10；uk=0.4时，就表示一台机床在 k年度只有4/10的时间于高负荷下工作 2状态转移方程为 k=1，2，,6,5最优目标函数递推方程。令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第5年度结束这段时间的产品产量，根据最优化原理有以下递推关系：k=1,2,3,4,5,3允许决策集合,在第k段为,4目标函数。设vk(sk,uk)为第k年度的产量，则vk(sk,uk)=8uk+5(sk-uk),因此，目标函数为,k1,2,5,6.边界条件为 下面采用逆序递推计算法,从第5年度开始递推计算。k=5时有 显然，当u5*=s5时，f5(s5)有最大值，相应的有f5(s5)=8s5 k=4时有,=,因此，当u4*=s4时，有最大值f4(s4)=13.6s4,k=3 时有 可见，当u3*=s3时，f3(s3)有最大值f3(s3)=17.55s3.k=2 时有=+=此时，当取u2*=0时有最大值，即f2(s2)=20.8s2，其中s2=0.7u1+0.9(s1-u1),=,k=1时有+=当取u1*=0时,f1(s1)有最大值，即f1(s1)=23.7s1,因为s1=1000,故f1(s1)=23700个产品 按照上述计算顺序寻踪得到下述计算结果：,上面所讨论的最优决策过程是所谓始端状态s1固定，终端状态s6自由如果终端也附加上一定的约束条件，那么计算结果将会与之有所差别例如，若规定在第五个年度结束时，完好的机床数量为500台(上面只有278台)，问应该如何安排五年的生产，使之在满足这一终端要求的情况下产量最高？,解：由状态转移方程 有得 显而易见，由于固定了终端的状态s6，第五年的决策变量U5的允许决策集合U5(s5)也有了约束，上式说明U5(s5)已退化为一个点，即第五年投入高负荷下生产的机床数只能由式U5=4.5s5-2500作出一种决策，故,500,当k=5时有 当k=4时有 显然，只有取u4*=0，f4(s4)有最大值，即f4(s4)=21.7s4-7500。同理类推,=,=,=,=,k=3时有 可知,当u3*=0时,f3(s3)有最大值f4(s4)=24.5s3-7500.k=2时有 此时,当u2*=0时有最大值,即f2(s2)=27.1s2-7500,=,=,=,=,+,k=1时有 只有取u1*=0时,f1(s1)有最大值，即 f1(s1)=29.4s1-7500。由此可见，为了使下一个五年计划开始的一年有完好的机床500台，其最优策略应该为：在前4年中，都应该把全部机床投人低负荷下生产，在第5年，只能把部分完好机投入高负荷下生产。根据最优策赂，从始端向终端递推计算出各年的状态，即算出每年年初的完好机床台数，因为s11000台，于是有,=,=,因此，u5*=4.5s5-2500=452(台)，这就是说第5年里还有204台投入低负荷下生产，否则不能保证s6=0.7u5+0.9(u5-s5)=500(台)。在上述最优决策下，5年里所得最高产量为：f1(s1)29.4s1-7500=29400-750021900(个)。可见，附加了终端约束条件以后，其最高产量f1(s1)比终端自由时要低一些。,（台）,（台）,（台）,（台）,（台）,（台）,资源分配问题,1.问题的一般提法 设有某种资源，总数量为a，用于生产n种产品；若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，可使总收益最大？,2.数学规划模型,模型的特点变量分离。,如何分配设备，可使获利最大？,各分厂在不同设备台数下所获利润,动态规划的数学模型将三个分厂看作是三个阶段，即阶段变量 k=1,2,3;状态变量sk 表示第k 阶段初可分配的设备台数,0 sk 6;决策变量xk 表示第k 阶段分配给分厂k 的设备台数，允许决策集合Xk(sk)=xk 0 xk sk;状态转移方程为 sk+1=sk-xk;阶段指标vk(sk,xk)表示第k 阶段从sk台设备中分配给k 分厂xk 台设备的阶段效益;最优指数函数fk(sk)表示第k阶段从sk 开始到最后阶段采用最优分配策略取得的最大的效益值;递推方程函数式,逆序求解K=3,第III分厂在不同设备台数下所获利润,k=2,第II分厂在不同设备台数下所获利润,第III分厂在设备台数为s3下所获得的最大利润,k=1,第I分厂在不同设备台数下所获利润,第II分厂在设备台数为s2下所获得的最大利润,6,18,1,2,顺序递推，得出结论,第I 分厂1套或2套第II 分厂2套或1套第III 分厂3套,背 包 问 题,则 Max z=c1x1+c2x2+cnxn s.t.w1x1+w2x2+wnxnW x1,x2,xn为正整数,阶段k：第k次装载第k种物品（k=1,2,n）状态变量xk：第k次装载时背包还可以装载的重量；决策变量dk：第k次装载第k种物品的件数；,4.决策允许集合：Dk(xk)=dk|0 dkxk/wk，dk为整数；5.状态转移方程：xk+1=xk-wkdk6.阶段指标：vk=ckdk7.递推方程 fk(xk)=maxckdk+fk+1(xk+1)=maxckdk+fk+1(xk-wkdk)8.终端条件：fn+1(xn+1)=0,背 包 问 题,例3 对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及W=5用动态规划求解 f4(x4)=0 对于k=3,K=3,对于k=2,列出f2(x2)的数值表,K=2,对于k=1,列出f1(x1)的数值,K=1,例 今有1000台机床，要投放到A、B两个生产部门，计划连续使用3年。已知对A部门投入uA台机器时的年收益是g(uA)=4(uA)2(元)，机器完好率a=0.5，相应的B部门的年收益是h(uB)=2(uB)2(元)，完好率b=0.9。试求使3年间总收益最大的年度机器分配方案。解 以每年作为一个阶段，设状态变量和决策变量都是连续取值的。K阶段状态变量xk取为该年度初完好的设备数，决策变量取为该年度投入A活动的设备数，则有 0 xk1000，0ukxk状态转移方程为：xk+1=0.5uk+0.9(xk-uk),解 以每年作为一个阶段，设状态变量和决策变量都是连续取值的。K阶段状态变量xk取为该年度初完好的设备数，决策变量取为该年度投入A活动的设备数，则有 0 xk1000，0ukxk状态转移方程为：xk+1=0.5uk+0.9(xk-uk)动态规划基本方程,逆序求条件最优目标函数值fk(xk)和条件最优决策k=3时，0u3x3，注意到f4(x4)=0，有,k=2时，0u2x2，有,逆序求条件最优目标函数值fk(xk)和条件最优决策k=1时，0u1x1，x2=0.5u1+0.9(x1-u1)，f2(x2),二、复合系统工作可靠性问题,1.问题的一般提法 设某工作系统由n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。已知部件i上装有xi个备用件时，其正常工作的概率为pi(xi)；每个部件i的备用件重量为wi，系统要求总重量不超过W。问应如何安排备用件可使系统可靠性最高？,串接:,2.数学规划模型,模型的特点变量分离。,3.用动态规划方法求解,阶段k状态sk决策xk,=1,n表示安排第k个部件备用件的过程；表示在给第k个部件安排之前还剩有的容许重量；表示第k个部件上安排的备用件数量；,状态转移sk+1,=sk-wkxk；,阶段指标vk指标函数vkn,例 某厂设计的一种电子设备由三种元件A、B、C串联而成，已知三种元件的价格及可靠性如表6.28所示，要求设计中使用元件的总费用不超过10万元，问如何设计使设备的可靠性达到最大（不考虑重量限制）。下表为 价格及可靠性,解 如前所述建立动态规划数学模型；按元件种类划分为3个阶段，k=1，2，3；决策变量xk表示第k个部件配备的元件数；状态变量sk表示从第k阶段到第3阶段配备元件 的总费用；状态转移方程为：sk+1=skckxk其中ck表示第k种部件的元件单价；允许决策集合为：,；,以pk表示第k个部件中的1个元件的正常工作概率，假定部件k的xk个元件是并联的，则,为xk个元件均不正常工作的概率，fk（sk）表示由 状态sk开始从第k个到第3个部件的设备最大可靠性。k=3时，,由于A、B至少要购置1件，用于购置C的最高金额为s3=1023=5万元，计算结果如表6.29所示。,表6.29 k=3时计算结果,k=2时，,下表为 k=2时计算结果,k=1时，,下表为 k=1时计算结果,逆向追踪得：x1*=2，s2=6，x2*=1，s3=3，x3*=3，即A元件用2个，B元件用1个，C元件用3个，最高可靠性为0.682.。,生 产 库 存 问 题,例5.9：一个工厂生产某种产品,1-7月份生产成本和产品需求量的变化情 况如下表：,阶段k：月份，k=1,2,7,8；状态变量xk：第k个月初（发货以前）的库存量；决策变量dk：第k个月的生产量；状态转移方程：xk+1=xk-rk+dk；决策允许集合：Dk(xk)=dk|dk0,rk+1xk+1H=dk|dk0,rk+1xk-rk+dkH；阶段指标：vk(xk,dk)=ckdk；终端条件：f8(x8)=0,x8=0；,递推方程：fk(xk)=minvk(xk,dk)+fk+1(xk+1)dkDk(xk)=minckdk+fk+1(xk-rk+dk)dkDk(xk),对于k=7因为 x8=0有 d7=0递推方程为f7(x7)=minc7d7+f8(x8)=0 d7=0,生 产 库 存 问 题,对于k=6因为d7=0，所以x7=r7=4而x6-r6+d6=x7=4因此有d6=x7+r6-x6=4+7-x6=11-x6也是唯一的决策。因此递推方程为：f6(x6)=minc6d6+f7(x7)d6=11-x6=10d6=10(11-x6)=110-10 x6,生 产 库 存 问 题,对于k=5f5(x5)=minc5d5+f6(x6)d5D5(x5)=min20d5+110-10 x6 d5D5(x5)=min20d5+110-10(x5-r5+d5)d5D5(x5)=min20d5+110-10(x5-2+d5)d5D5(x5)=min10d5-10 x5+130 d5D5(x5)D5(x5)=d5|d50,r6x5-r5+d5H=d5|d50,r6+r5-x5d5H+r5-x5=d5|d50,9-x5d511-x5,生 产 库 存 问 题,因为x5H=9，因此9-x50，决策允许集合可以简化为 D5(x5)=d5|9-x5d511-x5递推方程成为f5(x5)=min10d5-10 x5+130 9-x5d511-x5=10(9-x5)-10 x5+130=220-20 x5 d5*=9-x5,生 产 库 存 问 题,对于k=4f4(x4)=minc4d4+f5(x5)d4D4(x4)=min17d4+220-20 x5 d4D4(x4)=min17d4+220-20(x4-r4+d4)d4D4(x4)=min17d4+220-20(x4-3+d4)d4D4(x4)=min-3d4-20 x4+280 d4D4(x4),生 产 库 存 问 题,D4(x4)=d4|d40,r5x4-r4+d4H=d4|d40,r5+r4-x4d4H+r4-x4=d4|d40,5-x4d412-x4=d4|max0,5-x4d412-x4,由于 在f4(x4)的表达式中d4的系数是-3，因此d4在决策允许集合中应取集合中的最大值，即d4=12-x4由此 f4(x4)=-3(12-x4)-20 x4+280=-17x4+244,生 产 库 存 问 题,对于k=3f3(x3)=min c3d3+f4(x4)d3D3(x3)=min 13d3+244-17x4 d3D3(x3)=min 13d3+244-17(x3-r3+d3)d3D3(x3)=min-4d3-17x3+329 d3D3(x3)D3(x3)=d3|d30,r4x3-r3+d3H=d3|d30,r4+r3-x3d3H+r3-x3=d3|d30,8-x3d314-x3=d3|max0,8-x3d314-x3由此 f3(x3)=-4(14-x3)-17x3+329=-13x3+273,d3*=14-x3,生 产 库 存 问 题,对于k=2f2(x2)=minc2d2+f3(x3)d2D2(x2)=min18d2+273-13x3 d2D2(x2)=min18d2+273-13(x2-r2+d2)d2D2(x2)=min18d2+273-13(x2-8+d2)d2D2(x2)=min5d2-13x2+377 d2D2(x2)D2(x2)=d2|d20,r3x2-r2+d2H=d2|d20,r3+r2-x2d2H+r2-x2=d2|d20,13-x2d217-x2,生 产 库 存 问 题,因为 13-x20所以 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-18x2 d1D1(x1)=min11d1+442-18(x1-r1+d1)d1D1(x1)=min11d1+442-18(x1-0+d1)d1D1(x1)=min-7d1-18x1+442 d1D1(x1),D1(x1)=d1|d10,r2x1-r1+d1H=d1|d10,r2+r1-x1d1H+r1-x1=d1|d10,8-x1d19-x1,生 产 库 存 问 题,根据题意 x1=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年的总收入最大。,问题：状态和决策怎样设置？,决策是更新与否，可用0-1变量表示；状态可设为车龄。,阶段k状态sk决策xk,=1,10表示第k年的决策过程；=tk表示第k年的车龄；,状态转移tk+1,=tk+1,(1-xk),阶段指标vk指标函数vkn,=rktk-uktk-ck(tk),xk,例9（生产库存问题）某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。,解:以每个时期作为一个阶段，该问题分为4个阶段，k=1，2，3，4；决策变量xk表示第k阶段生产的产品数；状态变量sk表示第k阶段初的库存量；,以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期需求之和减去本期的库存量，,所以xk的上限为min（,，6），故有：Dk（sk）=xk|max（0，dksk）xkmin（,，6）,阶段指标函数rk（sk，xk）表示第k期的生产费用与存贮费用之和：,最优指标函数fk（sk）表示第k期库存为sk到第4期末的生产与存贮最低费用，动态规划基本方程为：,例10（库存销售问题）设某公司计划在1至4月份从事某种商品经营。已知仓库最多可存储600件这种商品，已知1月初存货200件，根据预测知1至4月份各月的单位购货成本及销售价格如表6.13所示，每月只能销售本月初的库存，当月进货供以后各月销售，问如何安排进货量和销售量，使该公司四个月获得利润最大（假设四月底库存为零）。表6.13 单位购货成本及销售价格,解:按月份划分阶段，k=1，2，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）表示第k月初库存为sk时从第k月至第4月末的最大利润，则动态规划基本方程为：,k=4时，,x4*=s4y4*=0k=3时，,为求出使44s35x3+4y3最大的x3，y3，须求解线性规划问题：,只有两个变量x3，y3，可用图解法也可用单纯形法求解，取得最优解，x3*=0，y3*=600s3，f3（s3）=40s3+2400,100,例 某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该种原料今后五周内取不同单价的概率如下表所示。试确定该部门在五周内购进这批原料的最优策略，使采购价格的期望值最小。,101,解 这里价格是一个随机变量，是按某种已知的概率分布取值的。用动态规划方法处理，按采购期限5周分5个阶段，将每周的价格看作该阶段的状态，设sk为状态变量，表示第k周的实际价格xk为决策变量，当xk=1，表示第k周决定采购；当xk=0，表示第k周决定等待。SkE表示第k周决定等待，而在以后采用最优决策时采购价格的期望值。,fk(sk)表示第k周实际价格为sk时，从第k周至第五周采用最优决策所得的最小期望值。因而可写出逆序递推关系式为fk(sk)=minsk,SkE skSk(1)f5(s5)=s5 s5S5,其中Sk=500,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，即在第五周时，若所需的原料尚未买入，则无论市场价格如何，都必须采购，不能再等。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元。试用动态规划方法确定一种生产方案（即每炉该装几个瓷瓶），使总的期望成本为最小。,