动态规划习题详解.doc

动态规划动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼(RBellman)等人在本世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支动态规划。他的名著动态规划于1957年出版，该书是动态规划的第一本著作。 动态规划是现代公司管理中的一种重要决策方法，在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用，并且获得了显著的效果。动态规划可用于解决最优途径问题、资源分派问题、生产计划与库存问题、投资分派问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。由于它所具有独特的解题思绪，在解决某些优化问题时，经常比线性规划或非线性规划方法更有效。第 一 节 动态规划的基本方法多阶段决策的实际问题很多，下面通过具体例子，说明什么是动态规划模型及其求解方法。例1：最短路线问题某工厂需要把一批货品从城市A运到城市E，中间可通过B1 、B2、B3、C1、C2、C3、D1、D2等城市，各城市之间的交通线和距离如下图所示，问应当选择一条什么路线，使得从A到E的距离最短？C1B1 6 3D1 8 4 5B2A 5 6 4 EC2 9 8 7 2D3 6 3 6 7 1 C3B3 8 3 7下面引进几个动态规划的基本概念和相关符号。(1)阶段(Stage)把所给问题的过程，准时间和空间特性划提成若干个互相联系的阶段，以便按顺序去求每个阶段的解，阶段总数一般用字母n表达，用字母k表达阶段变量。 如例l中 (最短路线问题)可看作是n=4阶段的动态规划问题，k=2表达处在第二阶段。 (2)状态(State)状态表达每个阶段开始时系统所处的自然状况或客观条件，它描述了研究问题过程状况。描述各阶段状态的变量称为状态变量，常用字母sk表达第k阶段的状态变量，状态变量的取值范围称为状态集，用Sk表达。 如例l中，第一阶段的状态为A（即出发位置）。第二阶段有三个状态：B1 、B2、B3，状态变量s2=B2表达第2阶段系统所处的位置是B2。第2阶段的状态集S2= B1 、B2、B3。动态规划中的状态变量应具有如下性质：当某阶段状态给定以后，在这个阶段以后过程的发展不受这个阶段以前各个阶段状态的影响。也就是说，未来系统所处的状态只与系统当前所处的状态有关，而与系统过去所处的状态无关，即过去历史只能通过当前的状态去影响它未来的发展，这种特点称为无后效性（又称马尔可夫性）。假如所选定的状态变量不具有无后效性，就不能作为状态变量来构造动态规划模型。如例1中，当某阶段的初始状态即所在的城市选定以后，从这个状态以后的运货路线只与这个城市有关，不受以前的运货路线影响，所以是满足状态的无后效性的。（3）决策(Decision) 当系统在某阶段处在某种状态，可以采用的行动（或决定、选择），从而拟定下一阶段系统将到达的状态，称这种行动为决策。描述决策的变量，称为决策变量。常用字母u k(sk)表达第k阶段系统处在状态sk时的决策变量。决策变量的取值范围称为决策集，用Dk(sk)表达。 在例l的第二阶段中，若从状态B2出发，可以做出三种不同的决策，其允许的决策集为D2(B2)= C1、C2、C3，决策u 2(B2)= C2表达第二阶段处在状态B2，选择的确行动下一阶段是走到C2。 （4）策略(Policy)系统从第k阶段的状态sk开始由每阶段的决策按顺序组成的决策序列 u k(sk) ，u k+1(sk+1)，u n(sn)称为一个策略（k=1,2, ，n）,记作。在例l中，p2,4(B2)= u 2(B2)= C2，u3(C2)= D1，u 4(D1)=E是一个策略，表达第二阶段从状态B2出发，沿着B2C2D1E的方向走到终点。注意策略必须是一串实际可行的序列行动。（5）状态转移方程系统由这一阶段的个状态进行决策后转变到下阶段的另个状态称为状态转移，状态转移既与状态有关，又与决策有关，描述状态转移关系的方程称为状态转移方程，记为：sk+1=Tk(sk，uk)它的实际意义是当系统第k阶段处在状态sk做决策uk时，第k+1阶段系统转移到状态sk+1。状态转移方程在不同的问题中有不同的具体表现形式，在例l中，状态转移方程表达为：sk+1=uk(sk)。（6）阶段指标阶段效益是衡量系统阶段决策结果的一种数量指标，记为：表达系统在第k阶段处在状态sk做出决策uk时所获得的阶段效益。这里的阶段效益在不同的实际问题中有不同的意义。在例l中它表达两个中转站的距离，如表达从中转站B2走到中转站C2之间的距离为7。更一般地有。（7）指标函数指标函数是用来街量所实现过程的优劣的一种数量指标，它是一个定义在全过程和所有后部子过程上的拟定的数量函数，记为：它应具有可分离性，并满足递推关系式：常见的指标函数的形式是：1）过程和任一子过程的指标是它所包含的各阶段指标的和。既2）过程和任一子过程的指标是它所包含的各阶段指标的积。既（8）最优值函数指标函数的最优值，称为最优值函数，记为。它表达系统在第k阶段处在状态sk时按最优策略行动所获得总的效益。既 其中opt是最优化（optimization）的缩写，根据实际问题可取max(最大值)和min(最小值),表达对所有允许策略使后面算式取最优。下面运用动态规划的逆推归纳法，将例1从最后一个城市E逐步推算到第一个城市A，在此表达第k阶段从城市sk到城市E最短路。1)当k=4时：规定，由于第4阶段只有两个城市D1、D2（即s4的取值为D1、D2），从D1到E只有一条路，故，同理。2)当k=3时：s3的取值为C1、C2、C3，从C1出发到E有两条路，一条是通过D1到E，另一条是通过D2到E ，显然：即从C1出发到E的最短路为7，相应决策为，最短路线是C1D1E。同理 2)当k=2时：s2的取值为B1、B2、B3，从B1出发到E有三条路，分别是通过C1、C2、C3到E，则有：同理 2)当k=1时：s1的只有一个取值为A. 从A出发到E有三条路，分别是通过B1、B2、B3到E，则有：于是得到从A到E的最短距离17，为了找出最短路线，按计算的顺序逆推回去，可得到最优策略为：，最短路线是AB1C2D2E。第 二 节 动态规划的基本原理从上面的计算过程中可以看出，在求解的各个阶段，运用了k阶段与k+1阶段之间的递推关系：这种递推关系称为动态规划的基本方程，其中称为边界条件。这个递推方程，是根据下述动态规划的贝尔曼(RBellman)最优化原理推导得来的。动态规划最优化原理：“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简朴地说就是一个最优策略的子策略也是最优的。一般情况下，作为一个动态规划模型的最优值函数在k阶段与k+1阶段之间必须满足下列递推关系：1） 加法型：若则: 即: (1)边界条件为 2）乘法型： (2)边界条件为 这种递推关系式(1)、(2) 称为动态规划的基本方程。这样的求解方法称为逆推解法（或逆序解法）。同理也可给出顺推解法（或顺序解法），动态规划的顺序解法的基本方程为：1）加法型： (1)边界条件为 2）乘法型： (2)边界条件为 注意：此时状态转移方程变为：sk=Tk(sk1，uk)通过对最短路线问题的求解，我们可以把动态规划方法的基本思想归纳如下：动态规划方法的关键，在于运用最优化原理给出最优值函数的递推关系式和边界条件，为此，必须先将问题的过程划分为几个互相联系的阶段，适当选取状态变量、决策变量, 状态转移方程及定义最优值函数。从而把一个大问题化成一系列同类型的子问题，然后逐个求解。例3：逆推解法求解下面问题:解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。设状态变量为s1，s2，s3，s4。并记s1c；令变量x1，x2，x3为决策变量；各阶段指标按乘积方式结合。即令:令最优值函数f k(sk)表达为第k阶段的初始状态为sk时，从第k阶段到第3阶段所得到的最大值。设: s3= x3, s3+ x2=s2, s2+ x1=s1=c则有：x3=s3, 0x2s2, 0x1s1=c即状态转移方程为： s3=s2x2, s2 =s1x1由逆推解法，即最优解x3=s3,由,得和（舍去）又，而，故为极大值点。所以即最优解。求导并令导数等于0可得：，故由于s1=c，由s2 =s1x1，,由s3 =s2x2，因此最优解为：，最大值为：例3：用顺推解法求解下面问题:解:设s4c，决策变量仍为x1，x2，x3；最优值函数f k(sk+1)表达为第k阶段末的结束状态为sk+1，从第1阶段到第k阶段所得到的最大值。设: s2= x1, s2+ x2=s3, s3+ x3=s4=c则有：x1=s2, 0x2s3, 0x3s4=c即状态转移方程为： s2=s3x2, s3=s4x3由顺推解法，即最优解x1=s2,最优解。最优解由于s4=c，由s3=s4x3，,由s2=s3x2，因此最优解为：，最大值为：例4：用顺推解法求解下面问题:解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。设状态变量为s0，s1，s2，s3。并记s39；令变量x1，x2，x3为决策变量；最优值函数f k(sk)表达为第k阶段末的结束状态为sk，从第1阶段到第k阶段所得到的最大值。设: 3x1=s1, s1+2x2=s2, s2+ x3=s39则有：x1=s13,0x2s22 , 0x3s39即状态转移方程为： s1=s22x2, s2=s3x3由顺推解法，即最优解x1=s13,由,得(它不在决策集内)则最大值在端点上，最大值点为x2=0。故得到及最优解。由,得又，故该点为极小值点。而最大值点为x3=s3。故得到及最优解。由于s3不知道，故须在对s3求一次极值，即反推回去即可得最优解为：，最大值为：作业 P214 1，5（1逆推，2顺推）第 二 节 动态规划应用举例一、资源分派问题假设有某种资源的总数量为a(例如原材料、能源、机器设备、劳力、食品等)，可用于生产n个产品，若生产j种产品的所用资源数为xj时，可获得利润为gj(xj)，问如何分派该种资源，使所获得的总利润达成最大。该问题的数学模型可表达为：当gj(xj)都是线性函数时，它是一个线性规划问题；当gj(xj)是非线性函数时,它是个非线性规划问题。但当n比较大时，求解起来是非常麻烦的。由于该问题的特殊性，可以将它当作一个多阶段决策问题，并运用动态规划的方法来求解。我们将n个产品看作是n个阶段，设状态变量sk表达生产第k个产品至第n个产品的资源数量，。决策变量xj表达生产第k个产品的所用资源数量，。显然状态转移方方程为：第k阶段的阶段指标为：。最优值函数表达生产第k个产品至第n个产品的资源数量为sk时所获得的最大总利润。则由动态规划最优化原理，可得动态规划的基本方程为：下面我们来考虑一种资源可回收运用的资源分派问题，这类分派问题的一般描述如下：设有某种资源，初始的拥有量是s1。计划在A、B两个生产车间连续使用n个阶段。巳知在A车间投入资源x时的阶段收益是g(x)，在B车间投入资源y时的阶段收益是h(y)。投入的资源在生产过程中有部分消耗,已知，每生产一个阶段后，车间A、B的资源回收率分别为a和b，0 a，b 1。回收的资源下一阶段可继续使用，求n阶段间总收益最大的资源分派计划。设sj为第j阶段投入A、B两个车间使用的资源数，j=1、2、n。xj为第j阶段投入A车间使用的资源数，投入B车间使用的资源数为yj=sj-xj，j=1、2、n。此问题的静态规划模型为：该模型可用动态规划的方法来解决。令sk为状态变量，表达在第k阶段投入A、B两个车间使用的资源数，k=1、2、n。xk为决策变量，它表达在第k阶段投入A车间使用的资源数，则yk=skxk表达在第k阶段投入B车间使用的资源数，k=1、2、n。状态转移方程为：sk+1=axk+b(s kxk)最优值函数表达拥有资源数为sk时，从第k阶段至第n阶段采用最优分派方案进行生产时所获得的最大总收益。则动态规划的递推公式 下面我们对一个具体问题，用此方法求解。 例1：机器负荷分派问题某公司新购进1000台机床，每台机床都可在高、低两种不同的负荷下进行生产，设在高负荷下生产的产量函数为g(x)=10x（单位：百件），其中x为投入生产的机床数量，年完好率为a=0.7；在低负荷下生产的产量函数为h(y)=6y（单位：百件），其中y为投人生产的机床数量，年完好率为b=0.9。计划连续使用5年，试问每年如何安排机床在高、低负荷下的生产计划，使在五年内生产的产品总产量达成最高。 解：该问题可看作一个5阶段决策问题，一个年度就是一个阶段。状态变量sk取为第k年度度初具有的完好机床台数。决策变量xk为第k年度中分派在高负荷下生产的机器台数，则yk=skxk为第k年度中分派在低负荷下生产的机器台数（假定xk、sk皆为连续变量）。状态转移方方程为：sk+1=axk+b(sk-xk)=0.7xk+0.9(sk-xk)第k年度的产量为：vk(sk,xk)=10xk+6(sk-xk)最优值函数表达拥有机床数为sk时，从第k年度至第五年度采用最优分派方案进行生产时所获得的最大总产量。则动态规划的基本方程为： 下面第5年度开始，用逆推归纳法进行计算。1）k=5时，有由于是x5的单调增长函数，故的最大解为，相应有=10s5。 2) k=4时，有由于是x4的单调增长函数，故的最大解为，相应有=17s4。3) k=3时，有由于是x3的单调增长函数，故的最大解为，相应有=21.9s3。4) 当k=2时，有 由于是x2的单调减少函数，故的最大解为，相应有=25.71s2。5) 当k=1时，有由于是x1的单调减少函数，故的最大解为，相应有=29.139s1。由于第l阶段的初始状态s1是给定的，即s1=1000，因此最优目的函数值为=29139（百件）。计算结果表白：最优策略为，。即前两年应把年初所有完好机床投入低负荷生产，后三年应把年初所有完好机床投入高负荷生产。这样所得的产量最高，其最高产量为29139百件产品。同时，从求解过程还可反过来拟定每年年初的状态，即每年年初所拥有的完好机器台数。已知s1=1000，于是可得：由此可知最优的决策过程是：第一年将所有1000台机器所有投入到低负荷下进行生产，第一年末机床完好数是900台，次年将900台机器继续投入到低负荷下进行生产，次年末机床完好数成为810台，第三年改变策略将这810台机床所有投入到高负荷下进行生产，第三年末机床完好数为567台，第四年将这567台机床所有投入到高负荷下进行生产，第四年末机床完好数成为397台，第五年将这397台机床投入到高负荷下进行生产，这样第五年末剩下的完好机床数为278台，五年共生产产品29139（百件）。 二、生产与存储问题假设为有一个公司，要制定某种产品n个阶段（例如年、月、周）的生产（或购买）计划，已知初始的存储量为零，第k个阶段市场需求量为dk，每个阶段公司的最大产量为M，单位产品的生产成本为a，每次生产的生产准备成本为K。问该公司如何安排生产和存储，才干即满足市场需求，又使总的费用最少？设xk为第k个阶段该产品的生产量。sk为第k个阶段末该产品的库存量，则有sk=sk-1+xk-dk。表达第k个阶段该产品xk时的成本费用，它涉及生产准备成本K和产品成本axk两项费用，即表达在第k个阶段结束时有库存量sk所需的存储费用。故第k个阶段的总成本费用为。上述问题的数学模型为：现在我们用动态规划的顺推归纳法来求解，把它看作一个n阶段决策问题。令 xk为决策变量，它表达在第k阶段的生产量。sk为状态变量，它表达在第k个阶段末该产品的库存量。则状态转移方程为：sk=sk-1+xk-dk。最优值函数表达从第1阶段初始库存量为0到第k阶段末库存量为sk时的最小总费用。则其顺序递推关系式： 其中，这是由于一方面在每个阶段公司的最大产量为M，另一方面由于满足每个阶段市场的需求量，由于第k-1阶段末库存量为sk-1必须非负，即:sk-1= dk+sk -xk0 , xk dk+sk。边界条件为（或）。从边界条件出发，运用上面顺序递推关系式，最后求出的即为所规定的最小总费用。下面通过一个实际例子计算之。例2：某公司通过市场调查，估计此后四个时期市场对某种产品的需要量如下表：时期(k)1234需要量(dk)2（单位）324假定不管在任何时期，生产每批产品的固定成本费为3(千元)，若不生产，则为零；生产单位产品成本费为1(千元)；每个时期生产能力所允许的最大生产批量为不超过6个单位，则任何时期生产x个单位产品的成本费用为： 若 0x6 ， 则生产总成本3十1x 若 x0 ， 则生产总成本0又设每个时期末未销售出去的产品，在一个时期内单位产品的库存费用为0.5(千元)，同时还假定第1时期开始之初和在第4个时期之末，均无产品库存。现在我们的问题是；在满足上述给定的条件下，该厂如何安排各个时期的生产与库存，使所花的总成本费用最低？解：我们将四个时期分为4个阶段，设k为阶段变量，k1，2，3，4。状态变量为sk，它表达在第k个阶段末该产品的库存量。决策变量为xk，它表达在第k阶段的生产量。则状态转移方程为：sk-1= sk-xk+dk。在第k个阶段生产准备成本为： 第k个阶段结束时有库存量sk所需的存贮费用为：。故第k个阶段的总成本费用为。则其顺序递推关系式：其中 边界条件，。 1）当k=1时，由于 对s1的也许取值在0至的值分别进行计算。 2）当k=2时，由于 对s2的也许取值在0至( s1最大可取到4)的值分别进行计算。3）当k=3时，由于 对s3的也许取值在0至( s2最大可取到6)的值分别进行计算。4）当k=4时，由于规定的第4个阶段结束时的库存量为0，即s4=0，因此只须计算 再按计算的顺序反推回去，可得到每个时期的确最优生产决策为：。其相应的最小总成本为20.5千元。三、设备更新问题 现以一台机器在n年内使用和更新决策为例来说明模型的求解方法，用表达在第k年初机器已使用t年（或称役龄为t年），再使用1年时所获得的收益。 表达在第k年初役龄为t年的机器，再使用1年时所需要的运营费用（或维修保养费用）。 表达在第k年初卖掉一台役龄为t年的机器，再买进一台新机器所需要净成本费用。 规定在n年内机器的更新策略，使得总效益达成最大。下面建立该问题的动态规划模型。 设状态变量sk表达在第k年初机器已使用的年数，即机器的役龄。决策变量xk表达在第k年初是继续使用旧机器还是更换新机器的决策，令。状态转移方程为：第k阶段的效益函数为。最优值函数表达第k年初有一台役龄为sk的机器至第n年按最优方案进行更新决策时所获得的最大总效益。则由动态规划的最优化原理，可得动态规划的基本方程为： 一个具数字例子如下：例3：设某公司在第一年初购买一台新设备，该设备在五年内的年运营收益、年运营费用及更换新设备的净费用如下表：（单位：万元）年份(k)役龄(t)运营收益运营费用更新费用第一年022618次年012321681922第三年0122321185710192328第四年01232422191657101520243038第五年01234252320171446914202024303848试为该公司制定一个五年中的设备更新策略，使得公司在五年内总收益达成最大？解：这是一个n=5阶段且初始状态为s1=0的设备更新问题，有关符号假定如上，目的是规定，下面用逆推归纳法进行计算。 1）当k=5时，有2）当k=4时，有3）当k=3时，有4）当k=2时，有5）当k=1时，有由于=44，由上述计算过程逆推回去可知；。即最优的设备更新策略是K，K，R，K，K，也就是该公司在第一年初购买一台新设备后连续使用两年，第三年初再购买一台新设备一直使用到第五年终，这样可使得公司在五年内的达成最大为方便用44万元。四、背包问题 有一个徒步旅行者带一背包，它可容纳物品重量的限度为a公斤。有n种物品可供他选择装入背包中。这n种物品编号为1，2，n。已知第i种物品每件重量为wi公斤，使用价值是第i种物品携带数量xi的函数ci(xi)。问该旅行者应如何选择携带这些物品的件数,使得总使用价值最大? 设xi为第i种物品的装入件数，则问题的数学模型为：将n种物品划分为n个阶段，状态变量sk表达装入第1种物品至第k种物品的总重量。决策变量xk表达装入第k种物品的件数。则状态转移方程为：sk-1=skwkxk。最优值函数表达当总重量不超过sk公斤，背包中只装前k种物品的最大价值。则动态规划的递归方程为：最后得到的就是所求的最大价值。例4：设有一辆栽重为10吨的卡车，用以装载三种货品，每种货品的单位重量及单件价值如表所示，问各种货品应装多少件，才干既不超过总重量又使总价值最大？货品123单位重量 3 4 5单件价值 4 5 6设xj表达第j种货品的件数（j=1,2,3）,则问题可归结为 s.t解: 用动态规划方法来解，问题变为求。必须先算出，。而必须先算出，。而相应的最优策略为，于是得到从而最后得到：所以最优装入方案为：，最大使用价值为13。作业 求解：