动态规划应用举例.ppt

第6章 动态规划应用举例,第1节 资源分配问题,1.1 一维资源分配问题,资源分配问题可描述如下：设有某种原料，总数量为a，分配给n个使用者。已知第i个使用者得到数量xi的该种资源，可创造的收益为gi(xi)。问应如何分配该资源，才能使总收益最大。,用动态规划法处理这种问题时，通常把给各个使用者分配资源的过程分别看成一个阶段，按使用者分成先后的n个阶段。即先给第1个使用者分配资源，为第一阶段；再给第2个使用者分配，为第二阶段；依此类推，最后给第n个使用者分配，为第n阶段。,按使用者划分为n个阶段，k=1,2,n； 取第k阶段初（给第k个使用者分配资源时）资源的剩余量sk为状态变量，s1=a； 取分配给第k个使用者的资源数量xk为决策变量，0xksk (k=1,2,n-1)， xn= sn； 状态转移方程为sk+1=sk-xk； 指标函数为Vk,n=gj(xj)； 基本方程为：,由于资源数量常常要求取整数，则状态变量和决策变量也就取整数，所以求解时常采用列表的形式。,例2 某工业部门根据国家计划安排，拟将五台某种高效率的机器分配给所属的甲、乙、丙三个工厂，各工厂得到不同数量的机器可获得的收益如下表。问应如何分配机器，才能使各厂的总效益最大。,解：,分成3个阶段，k=1,2,3；,sk为状态变量，s1=5；,xk为决策变量，0xksk，x3=s3；,状态转移方程sk+1= sk-xk ；,当k=3时：,当k=2时：,当k=1时：,总效益最大为21万元，分配方案为：,(1)甲0台, 乙2台, 丙3台；(2)甲2台, 乙2台, 丙1台。,1.2 二维资源分配问题,二维资源分配问题可描述如下：设有两种原料，数量各为a和b，分配给n个使用者。已知第i个使用者得到两种资源的数量各为xi和yi时，可创造的收益为gi(xi, yi)。问应如何分配该资源，才能使总收益最大。,与一维资源分配问题类似，把给各个使用者分配资源的过程分别看成一个阶段，按使用者分成先后的n个阶段。由于要分配两种资源，所以状态变量要有两个，决策变量也要有两个。,按使用者划分为n个阶段，k=1,2,n； 取第k阶段初（给第k个使用者分配资源时）两种资源各自的剩余量sk和tk为状态变量, s1=a, t1=b； 取分配给第k个使用者两种资源的数量xk和yk为决策变量，0xksk, 0xksk (k=1,n-1), xn= sn, yn= tn； 状态转移方程为：sk+1=sk-xk，tk+1=tk-yk； 指标函数为Vk,n=gj(xj,yj) ； 基本方程为：,虽然建模过程和一维资源分配问题没多大区别，但求解模型却极为困难。为此，需进行简化处理。,1. 拉格朗日乘数法,引入拉格朗日乘数，将二维问题化为,这是一个一维分配问题。取定为某一值，求解得 xi*=xi() ， yi*=yi(xi(), )=yi(),可证，若yi()=b，则对应的xi*, yi*就是原问题的最优解。否则，就用插值法调整的值，渐进地使yi()=b得到满足。,2. 逐次逼近法,逐次逼近法的做法是，先保持一个变量不变，对另一个变量求最优，然后交替地固定，以迭代的形式反复进行，直到满足某种要求为止。,先设x(0)=x1(0), x2(0), xn(0)为满足xi(0)=a的一个可行解，固定x在x(0)，对y求解，则变为一维问题,用一维方法解得y(0)=y1(0), y2(0), yn(0)，再固定y在y(0)，对x求解一维问题,解得x(1)=x1(1), x2(1), xn(1)，再固定x在x(1)，对y求解一维问题。依次轮换下去，得解序列x(k)、 y(k)。,由于gi(xi(0),yi(0)gi(xi(1),yi(0)gi(xi(1),yi(1)，故函数值序列gi(xi(k),yi(k)是单调上升的，但不一定收敛到整体的最优解，一般只能收敛到某一局部最优解。因此，在实际计算时，可选择几个初始点xi(0)进行计算，然后从几个局部最优解中选出一个最好的。,3. 粗格子点法 （疏密法）,先将0xa, 0yb分成网格，然后在格子点上进行计算。为了使计算可行，可先用少数格子点进行粗糙计算，在求出相应最优解后，再在最优解附近的小范围内进一步细分，求出在细分格子点上的最优解。继续细分下去，直至满足要求为止。,第2节 生产与存储问题,2.1 生产计划问题,设某公司对某种产品要制定n个阶段的生产计划。已知它的初始库存为0，每阶段生产产品数量的上限为m；第k阶段，对该产品的需求量为dk，生产产品量为xk时的生产费用为ck(xk)，开始时有库存量vk需要支付的存储费用为hk(vk)；n阶段末的终了库存为0。问该公司应如何制定生产计划，从而使总成本最小。,用动态规划的方法：,状态转移方程为： vk+1= vk+xk-dk,k阶段的产品生产量xk为决策变量，则,k阶段开始时的库存量vk为状态变量， v1=0；,划分为n个决策阶段，k=1,2,.,n；,在求解生产计划问题时，常常需要先给出状态变量vk的取值范围，即确定可达状态集。易推出：,例 某工厂要对一种产品制定今后四个时期的生产计划，据估计四个时期的需求量依次为2、3、2和4。假定该厂生产每批产品的固定成本为3万元，每单位产品的成本为1万元，若不生产就为0；每个时期生产能力的上限为6个单位，每单位产品存放每期的存储费用为0.5万元。还假定第一期开始时和第四期结束时的库存量都为0。试问该厂应如何安排各期的生产与库存，才能在满足需求的条件下，使总成本最小。,状态变量vk的可达状态集：,则有，v1=0，0v24，0v36，0v44。,k=4时：,k=3时：,k=2时：,k=2时：（续）,k=1时：,于是得，总成本最小为20.5万元。,x1*=5， x2*=0， x3*=6， x4*=0,再顺序递推出最优计划为：,即：第一个时期生产产品5个单位，第二个时期不安排生产，第三个时期生产产品6个单位，第四个时期不安排生产。,2.2 不确定性采购问题,某单位准备在以后的n个时期内采购一批物资。各时期的价格不是确定的，而是按照某种已知的概率分布取值。试制定采购策略，确定在哪一时期以什么价格采购，能使采购价的数学期望值最低。,这类问题也适合用动态规划法进行处理,下面通过实例加以说明。,例 某厂生产上须在近五周内采购一批原料，而估计在未来五周的价格有波动，其浮动价格和概率策得如下表。试确定该厂应在哪一周以什么价格购入，能使其采购价的数学期望值最小，并求出期望值。,解：,（1）按采购周数分成5个阶段，k=1,2,5；,（2）取第k阶段(第k周)的实际价格yk为状态变量；,（4）用fk(yk)表示：前k-1周未采购，第k周状态为yk时，从第k周到第5周按最优策略所得到的采购价的期望值。即fk(yk)为最优值函数；,（5）用ykE表示：前k-1周未采购，从第k周到第5周按最优策略所得到的总的采购价的期望值。,显然，ykE=Efk (yk)=0.3fk(500)+0.3fk(600)+0.4fk(700),k=5时：,f5(500)=500, f5(600)=600, f5(700)=700 (x5*=1) y5E=0.3*500+0.3*600+0.4*700=610,k=4时：,f4(500)=min500,610=500, (x4*=1), f4(600)=min600,610=600, (x4*=1), f4(700)=min700,610=610, (x4*=0), y4E=0.3*500+0.3*600+0.4*610=574,k=3时：,f3(500)=min500,574=500, (x3*=1), f3(600)=min600,574=574, (x3*=0), f3(700)=min700,574=574, (x3*=0), y3E=0.3*500+0.3*574+0.4*574=551.8,k=2时：,f2(500)=min500,551.8=500, (x2*=1), f2(600)=min600,551.8=551.8, (x2*=0), f2(700)=min700,551.8=551.8, (x2*=0), y2E=0.3*500+0.3*551.8+0.4*551.8=536.26,k=1时：,f1(500)=min500,536.26=500 (x1*=1), f1(600)=min600,536.26=536.26 (x1*=0), f1(700)=min700,536.26=536.26 (x1*=0), y1E=0.3*500+0.3*536.26+0.4*536.26=525.382,最优的采购策略为：在一、二、三周时，价格为500时采购，否则就等待；在第四周时，价格为500和600都要采购，价格为700就等待；第五周时，无论什么价都要采购。,由此可知，采购价的期望值最小为525.382。,对于不确定性采购问题，还可考虑每期价格的概率分布不同、价格的概率分布为连续分布等情况，都可用与上例类似的方法进行求解。,第3节 背包问题,一个人带一个背包上山，其可携带物品重量的限度为a公斤。设有n种物品可供他选择装入背包，已知第i种物品每件重量为wi公斤，上山过程中的效用是携带数量xi的函数ci(xi)。问此人应如何携带各种物品，才能使总效用最大。,用动态规划法处理这种问题时，通常把一种物品决定带多少件的过程看成一个阶段，按物品种类分成先后的n个阶段。即先决定第1种物品带多少件，为第一阶段；再决定第2种物品，为第二阶段；依此类推，最后决定第n种物品，为第n阶段。,按物品种类划分为n个阶段，k=1,2,n； 取第k阶段初（决定第k种物品带多少件时）可携带重量的剩余量sk为状态变量，s1=a； 取第k种物品携带的数量xk为决策变量，则有0xksk /wk (k=1,2,n-1) ； 状态转移方程为sk+1=sk-wkxk； 指标函数为Vk,n=cj(xj)；,对背包问题求解的难点在于，除第一阶段外，其它阶段的可达状态集不容易给出，下面通过实例说明给出可达状态集的方法。,解：,按变量划分为3个阶段，k=1,2,3,取k阶段时常数项(资源)的余量sk为状态变量，s1=10,取xk为决策变量，0xksk/wk,状态转移方程为 sk+1=sk-wkxk （w1=3, w2=4, w3=5）,指标函数为 Vk,3=cjxj（c1=4, c2=5, c3=6）,由于s1=10，因而求解此问题就是计算f1(10)。而,可见，要先计算f2(10), f2(7), f2(4), f2(1)。,于是，需计算f3(10), f3(7), f3(6), f3(4), f3(3), f3(2), f3(1), f3(0) 。,f3(4)= f3(3)= f3(2)= f3(1)= f3(0)=0 (x3*=0),从而，有,最后，有,所以，最优解为x1*=2, x2*=1, x3*=0，z*=13,二维背包问题：一个人带一个背包上山，其可携带物品重量的限度为a公斤，体积的限度为b立方米。设有n种物品可供他选择装入背包，已知第i种物品每件重量为wi公斤，每件体积为vi立方米，上山过程中的效用是携带数量xi的函数ci(xi)。问此人应如何携带各种物品，才能使总效用最大。,基本方程为：,二维背包问题，其第k阶段有两个状态变量，但决策变量仍只有一个，所以求解难度并没有实质性增加。二维背包问题的求解方法与一维背包问题基本相同。,第4节 复合系统可靠性问题,某种机器的工作系统由n个部件串联组成，只要一个部件失灵，整个系统就不能工作。为提高系统可靠性，每个部件都装备了备用件，并设计了备用件自动投入装置。已知，部件i装备ui个配件时的可靠性为pi(ui)，一个备用件的费用为ci，重量为wi；整个系统备用件的总费用不超过c，总重量不超过w。问应如何选择各部件的备用件数，使整个系统的可靠性最大。,按部件划分为n个阶段；取第k阶段初费用剩余量sk和重量剩余量tk为状态变量，s1=c, t1=w； 取给部件k安装的备用件数uk为决策变量，则有1ukminsk /ck, tk /wk ； 状态转移方程为sk+1=sk-ckuk, tk+1=tk-wkuk 指标函数为Vk,n=pj(uj)；,基本方程为：,该问题的特点是，指标函数为连乘形式，边界条件当然为1。另外，和背包问题一样，求解时要先顺推出各阶段的可达状态集。,例 某厂设计的电子设备由三种元件D1、D2、D3组成。已知三种元件的价格和可靠性如下表所示，要求设计中使用元件的费用不超过105元。问应如何设计，使设备的可靠性达到最大（不考虑重量限制）。,解：,按变量划分为3个阶段，k=1,2,3； sk为状态变量，s1=105； uk为决策变量，1uksk/ck；状态转移方程sk+1=sk-ckuk (c1=30, c2=15, c3=20)；指标函数Vk,3= pj(uj) ( p1(u1) =1-0.1u1, p2(u2) =1-0.2u2, p3(u3) =1-0.5u3 )。,由于s1=105，而,则要先计算f2(75), f2(45), f2(15),于是计算f3(60), f3(45), f3(30), f3(15), f3(0) 。,从而得：,第5节 排序问题,设有n个工件需要在机床A、B上加工，每个工件都必须先经过A而后B两道加工工序。以ai、bi分别表示工件i(1in)在机床A、B上的加工时间。问应如何在两机床上安排各工件的加工顺序，使在机床A上加工第一个工件开始到在机床B上加工完最后一个工件为止，所用的加工总时间最少？,加工工件在机床A上有加工顺序问题，在机床B上也有加工顺序问题。可以证明：最优加工顺序在两台机床上可同时实现。因此，最优排序方案可以只在机床A、B上加工顺序相同的排序中寻找即可。 即使如此，所有可能的方案仍有n!个，这是一个不小的数，用穷举法是不现实的。下面用动态规划法对排序问题进行研究。,当加工顺序排定之后，工件在A上没有等待时间，而在B上则常常需要等待。因此，只有尽量减少在B上等待加工的时间，才能使总加工时间最短。,现以在机床A上更换工件的时刻作为阶段的分界点，分成n个阶段。第k阶段时，Xk表示尚未在A上加工的工件集合，tk表示已在A上加工完的工件还需要在B上的加工时间，(Xk, tk)作为状态。,令fk(Xk, tk)为从状态(Xk, tk)出发，对还未在A上加工的剩余工件按最优排序，完成全部加工任务还需要的时间，即为k-子过程最优值函数。,fk(Xk, tk, i)为从状态(Xk,