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

第二章动态规划,动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。1951年，美国数学家贝尔曼（R.Bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。贝尔曼等人在研究和解决了大量实际问题之后，提出了解决这类问题的所谓“最优性原理”，通常称为“贝尔曼最优化原理”，从而创建了解决最优化问题的一种新的方法动态规划（DynamicProgramming）。,为了说明动态规划的基本思想方法和特点，以下图所示为例，讨论求最短路问题的方法。,求从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，路线为AB2C1D1E,1、阶段（stage）为了便于求解和表示决策过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间顺序或空间特征上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目，例如上面的最短路问题就是一个四阶段决策过程。,动态规划的基本概念和基本原理,2、状态（state）每个阶段开始时过程所处的自然状况或客观条件。反映状态变化的量叫做状态变量，它可以用一个数，一组数或一向量来描述，。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。它应能描述过程的特征并具有“无后效性”，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。用sk表示状态变量（statevariable）。,一般状态变量的取值有一定的范围或允许集合，称为可能状态集（setofadmissiblestates）。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定例如上面的最短路问题中，第一阶段状态为A，状态变量s1的状态集合S1=A；第二阶段则有三个状态：B1,B2,B3,状态变量s2的状态集合S2=B1,B2,B3.,3、决策（decision）当一个阶段的状态确定后，可以作出不同的决定或选择，从而演变到下一阶段的某个状态，这种决定或选择称为决策。用以描述决策变化的量称之决策变量（decisionvariable）。和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，由于各阶段的决策取决于状态变量sk，所以用uk(sk)，表示阶段k的状态为sk时的决策变量。决策变量的取值往往也有一定的允许范围，称之允许决策集合（setofadmissibledecision）。决策变量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、状态转移方程（equationofstatetransition）反映前后阶段状态之间关系的方程称为状态转移方程。在确定型多阶段决策过程中，一旦某阶段的状态和决策为已知，下一阶段的状态便完全确定，用状态转移方程反映这种状态间的演变规律，记作：,有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。,6、阶段指标值（objectivevalueinastage）阶段指标值是第k阶段的状态为sk和采取决策uk时的效益，通常表示为dk（sk，uk）。对不同问题，阶段指标值可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间，等等。例如上面的最短路问题中，如果第二阶段地状态为B2,采取决策是由B2到达C1,则阶段指标值为6。,7、指标函数（objectivefunction）衡量在选定某策略时，其优劣的数量指标。定义在整个过程（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、最优指标函数（optimalvaluefunction）指标函数的最优值称为最优指标函数，记为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),一般情况下a0所以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-18x2d1D1(x1)=min11d1+442-18(x1-r1+d1)d1D1(x1)=min11d1+442-18(x1-0+d1)d1D1(x1)=min-7d1-18x1+442d1D1(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；允许决策集合：0xksk，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,解这里价格是一个随机变量，是按某种已知的概率分布取值的。用动态规划方法处理，按