动态规划ppt课件

.,1,五.动态规划,.,2,动态规划的基本概念：1阶段：把问题分为互相联系有一定次序的阶段，一般按时间和空间的自然特征划分。2状态：每个阶段开始所处自然状况或客观条件，不可控制。用表示第阶段的状态变量，代表第阶段所有始点的集合，又称该阶段的可达状态集合（状态变量的取值范围）。状态的性质：无后效性（马尔科夫性）3决策：某个阶段的某个状态决定下一个阶段的状态用表示第阶段当状态处于时的决策变量。4策略：是一个按顺序排列的决策组成的集合。用表示由过程的第阶段开始到终止状态为止的过程，即问题的后部子过程，称为子过程策略。当成为全过程的策略，简称策略。所有策略（允许策略集合）中达到最优效果的策略为最优策略,动态规划（1）,.,3,5状态转移方程：确定由一个状态转到另一个状态的演变过程。第阶段到阶段的状态转移方程为6指标函数：衡量过程优劣的数量指标。动态规划模型的指标函数应具有可分离性和满足递推关系。表示从第阶段的状态开始到第阶段的终止的过程。,.,4,7最优值函数：表示从第阶段的状态开始到第阶段的终止的过程，采取最优策略所得到的指标函数值。,.,5,动态规划解法：第一步：划分阶段第二步：选择状态变量第三步：确定决策变量第四步：写状态转移方程第五步：指标函数,动态规划（1）,.,6,动态规划（1）,动态规划的逆序解法和顺序解法：,.,7,顺推法求解非线性规划：maxZ=4x1+9x2+2x32x1+x2+x3=10 xi=0I=1,2,3,动态规划应用之二：资源分配问题,动态规划（1）,引例：某种原料总数为a分配给n种产品，分配数量Xi用于生产第i种产品，效益为gi(xi),.,8,顺推法求解非线性规划：maxZ=4x1+9x2+2x32x1+x2+x3=10 xi=0I=1,2,3分析：理解为第一阶段投资x1，第二阶段投资x2第三阶段投资x3求最大利润maxZ=4x1+9x2+2x32三阶段投资总额共有10亿元非线性规划问题求解第一阶段投资总额S1（状态变量）第一二阶段投资总额S2（状态变量）第一二三阶段投资总额S3（状态变量）,x1,x2,x3,S3,S2,S1,S1=X1S2=X1+X2S3=X1+X2+X3,动态规划应用之二：资源分配问题,动态规划（1）,.,9,解:设状态变量S1=X1,S2=S1+X2,S3=S2+X3.F1(S1)=4X1=4S1(第一阶段投资x1产生的效益4X1）第一二阶段投资总量为S2产生的效益第一阶段投资x1产生的效益第二阶段投资X2产生的效益F2(S2)=9X2+F1(S1)=4S2+5X2X2X3=9/40=X3=10在X3=9/4,F3(S3)有最小值,F3(S3)最大值X310maxF3(S3)=2*102=200即X3=10,则X1,X2为0maxZ=200.,动态规划（1）,.,10,X3,H3(S3,X3),10,9/4,在X3=9/4,F3(S3)有最小值,F3(S3)最大值X310,动态规划（1）,.,11,背包问题用动态规划解下列问题：MaxZ=8X1+7X2S.T.2X1+X285X1+2X215X1,X2为非负整数,经济意义：X1,X2为物品数量，8，7为单位物品的价值，2，1为单位物品的体积，8为背包的最大容积，5，2为单位物品的重量，15为背包的最大承受重量（太重背包带会断）,动态规划（1）,.,12,用动态规划逆序算法解下列问题（二维背包问题）：MaxZ=8X1+7X2（最大效益，重量限制，体积限制）S.T.2X1+X28(重量)5X1+2X215(体积)X1,X2为非负整数解：用逆序算法。设：阶段：分成两个阶段，分别对应第1种物体的数量X1，第2种物体的数量X2第1阶段决定背包中第1种物体的数量决策变量：X1，X2为背包中两种物体的数量状态变量：V1为第1阶段可供分配重量，V18W1为第1阶段可供分配体积，W115，V2，W2对应第2阶段于是，F*2（V2，W2）=Max7X20X2V2(重量)02X2W2(体积),x1,x2,V1，W1,V2，W2,V1=8，W1=15V2=V1-2X1(重量)W2=W1-5X1(体积),动态规划（1）,.,13,X2为整数F*2（V2，W2）=Max7X2=7minV2,W2/2(V是小于等于V的最大整数)F*1（V1，W1）=Max8X1+F*2（V2，W2）=Max8X1+F*2（V1-2X1，W1-5X1）02X1V1(重量)05X1W1(体积)X1为整数而V1=8，W1=15因此F*2（V1-2X1，W1-5X1）=7min8-2X1,(15-5X1)/2F*1（8，15）=Max8X1+7min8-2X1,(15-5X1)/202X1805X115X1为整数由于X1min8/2,(15/5)=3(X1为0，1，2，3，分别代入下式，也可用分析)F*1（V1，W1）=Max8X1+7min8-2X1,(15-5X1)/2,动态规划（1）,.,14,X*1=0X*2=minV2,W2/2V2=V1-2X1=8，W2=W1-5X1=15X*2=7因此,最优解为X*1=0,X*2=7,最优值:Z*=49,动态规划（1）,.,15,动态规划（2）,.,16,动态规划（2）,一个老板要把五台高效率的设备调配给自己的三家分厂，各个工厂得到这些设备所产生的利润如下表，问如何调配可以获得最大利润？,阶段,决策变量与状态变量?,动态规划应用之二：资源分配问题,.,17,阶段,决策变量与状态变量决策变量:分配到k厂的设备台数Xk状态变量:分配到k厂到3厂的设备总台数Sk,X1,X2,X3,S1,S2,S3,S3=X3S2=X2+X3S1=X1+X2+X3,动态规划（2）,.,18,注意：分配到3厂到3厂的设备总台数S3=分配到3厂的设备台数X3,动态规划（2）,.,19,分配到2厂到3厂的设备总台数S2=X2X3,由已知表：第2厂分配3台设备得效益11由上表：第3厂分配2台设备得效益6,动态规划（2）,.,20,分配给1厂到3厂的设备总台数S1=5,由已知表：第1厂分配4台设备得效益12，由上表：第2，3厂分配1台设备得效益5,由第三表知：总利润21万元X10，第1工厂不分配，第2，3工厂分配5台，S2=X2+X35由第二表对应S25知：X22，第2工厂分配2台，于是第3工厂分配3台,最优分配：第1厂分配0台；第2厂分配2台；第3厂分配3台；总利润21万元,动态规划（2）,.,21,另一个结果是，由第三表知：总利润也是21万元X12，第1工厂分配2台，第2，3工厂分配3台，S2=X2+X33由第二表对应S23知：X22，第2工厂分配2台，于是第3工厂分配1台,最优分配：第1厂分配2台；第2厂分配2台；第3厂分配1台；总利润21万元,动态规划（2）,.,22,一个老板要把五台高效率的设备调配给自己的三家分厂，各个工厂得到这些设备所产生的利润如下表，问如何调配可以获得最大利润？,X1,X2,X3,S1,S2,S3,S3=X3S2=X2+X3S1=X1+X2+X3,可以理解为5亿元，投资于三个项目,动态规划（2）,.,23,注意：投资到3项目到3项目的资金总数S3=投资到3项目的资金总数X3,动态规划（2）,.,24,投资到2项目到3项目的资金总数S2=X2X3=5,由已知表：第2项目投资3亿元得效益11由上表：第3项目投资2亿元得效益6,动态规划（2）,.,25,投资给1项目到3项目的资金总数S1=5亿,由已知表：第1项目投资4亿得效益12，由上表：第2，3项目投资1亿得效益5,由第三表知：总利润21万元X10，第1项目不投资，第2，3工厂投资项目5亿，S2=X2+X35由第二表对应S25知：X22，第2项目投资2亿，于是第3项目投资3亿,最优分配：第1项目投资0亿元；第2项目投资2亿元；第3项目投资3亿元；总利润21万元,动态规划（2）,.,26,动态规划应用之二：资源分配问题（续）例1求解非线性规划例2背包问题（整数规划）例3利润函数为表格（非连续函数）例4固定资金分配问题,动态规划（2）,.,27,固定资金分配,一个老板有N个企业，都需要两种资源，对于第K个企业，如果用第1种资源XK，用第2种资源YK,可以得到利润RK(XK,YK),第1种资源的单位价格为A,第2种资源的单位价格为B,现有资金Z,问应该购买第1种资源（设为X）和第2种资源（设为Y）各多少单位分配到N个企业，可以使总利润达到最大？,动态规划应用之二：资源分配问题（续）,动态规划（2）,.,28,该问题的数学模型为：,.,29,思路：把资源分配换算成资金分配，将二元转换为一元,逆序解法：,.,30,动态规划应用举例动态规划求解机器负荷分配问题,某种机器可以在高低两种不同的负荷下生产，高负荷生产产量函数为G=8U1其中U1表示投入生产的机器数量，年完好率A=0.7低负荷生产产量函数为H=5Y,其中Y表示投入生产的机器数量，年完好率B=0.9,如果初始投入生产的机器1000台，问如何安排生产，使在5年内生产的产品总量达到最大？,高负荷生产,低负荷生产,动态规划（2）,.,31,动态规划建模1划分阶段：年度2状态变量：SK为K年度完好的机器数3决策变量：UK为K年度分配高负荷生产的机器数，SKUK为K年度低负荷生产的机器数4状态转移方程：SK10.7UK+0.9(SKUK)5指标函数：VK为K年度产量，VK8UK+5(SKUK)MAXV1+V2+V3+V4+V56递推公式：F6(S6)=0F6(S6)表示当6年度完好的机器数S6时，从6年到5年最大产量FK(SK)=MAX8UK+5(SKUK)+FK+10.7UK+0.9(SKUK),FK(SK)表示当K年度完好的机器数SK时，从k年到5年最大产量,动态规划（2）,.,32,K5F5(S5)=MAX8U5+5(S5U5)+F60.7U5+0.9(S5U5)因为F60.7U5+0.9(S5U5)0F5(S5)=MAX8U5+5(S5U5)MAX3U5+5S5U5=S5,当U5=S5,F5(S5)8S5K4F4(S4)=MAX8U4+5(S4U4)+F50.7U4+0.9(S4U4)=MAX8U4+5(S4U4)+80.7U4+0.9(S4U4)=MAX1.4U4+12.2S4U4=S4,当U4=S4,F4(S4)13.6S4同理，当U3=S3F3(S3)17.5S3当U2=0,F2(S2)20.8S2当U1=0,F1(S1)23.7S1,动态规划（2）,.,33,最优解：前两年完好机器全部低负荷生产，后三年完好机器全部高负荷生产，最优产量23700台,动态规划（2）,.,34,动态规划（3）,.,35,公司要对某种产品制定一个生产计划或者采购计划，已知初始库存为零每阶段生产数量有上限（生产能力限制），每阶段需求已知，在N阶段末库存为零，问如何制定生产或者采购计划，使生产和库存成本最小？,企业,阶段生产计划？阶段采购计划？,已知阶段需求（定单）已知内部库存,动态规划应用之三：生产计划调度问题,动态规划（3）,.,36,动态规划应用举例生产计划（采购计划）与存贮问题：Min生产费用+存贮费用存贮量=生产量-需求量生产量=00=XK6,K=1F1(V1)=MinC1(X1)H1(V1)+F0(V0),动态规划（3）,.,41,边界条件：,当K1时，对在0至之间的值分别进行计算。,.,42,动态规划（3）,.,43,当K=2时，,其中。对在0至之间的值分别进行计算。得,.,44,.,45,动态规划（3）,当K=3时，其中。对在0至min4,6-2=4之间的值分别进行计算，得,.,46,动态规划（3）,当K4时，要使总成本最小，必须第4时期的库存量为0，即，故有,.,47,动态规划（3）,每个时期的最优决策为：其相应的最小总成本为：20.5千元。,.,48,动态规划（3）,若对每个，都有，则称该点的生产决策具有再生产点性质。若，则称阶段为再生产点。如:和，故阶段0和n是再生产点。设为阶段j到阶段i的总成本,给定j-1和i是再生产点,并且阶段j到阶段i期间的产品全部由阶段j供给,则,.,49,动态规划(3),逆序解法:最优值函数表示在阶段i末库存量时,从阶段1到阶段i的最小成本.递推公式为:,.,50,动态规划(3),设j(n)为计算时,使(1)式右边最小的j值,即则从j(n)阶段到阶段n的最优生产决策为:故j(n)-1为再生产点.,.,51,动态规划(3),用再生产点性质解:(C(X)和H(V)都是凹函数)(1)计算C(1,1)=C(2)+H(0)=5C(1,2)=C(5)+H(3)=3+5+0.5*3C(1,3)=C(7)+H(5)+H(2)=+0.5*5+0.5*2=C(1,4)=C(11)+H(9)+H(6)+H(4)=C(2,2)=C(3)+H(0)=6C(2,3)=C(5)+H(2)=9C(2,4)=C(9)+H(6)+H(4)=C(3,3)=C(2)+H(0)=5C(3,4)=C(6)+H(4)=11C(4,4)=C(4)=7,.,52,动态规划(3),(2)计算,.,53,动态规划(3),(3)由j(4)=3,有因m=j(4)-1=3-1=2,所以j(m)=j(2)=1,故从而最优生产决策为:最小总成本为:20.5千元.,.,54,动态规划(3),考虑阶段j(n)-1到阶段1的最优生产决策.记m=j(n)-1,j(m)是在计算时,使(1)式右边最小的值,则从阶段j(m)到阶段j(n)的最优生产决策为:故阶段j(m)-1为再生产点,其余以此类推.,.,55,动态规划应用之四：库存问题，采购问题不确定性采购问题（随机动态规划）：特点价格是随机的，状态以一定的概率出现购买决策特点市场价格低于最优价格时买市场价格高于最优价格时不买最后期限如果还没购买，无论什么价格都要买,答案应该满足：开始几周时间充分，非最低价不买，到中间几周有点着急中等价也买，最后时刻则没有谈判的余地。,1.阶段2.状态3.决策4.策略5.状态转移方程6.指标函数和最优值函数,动态规划（3）,.,56,例：某工厂在最近五周内需要采购一批原料，估计五周内有价格波动如下表，求那一周以什么价格购买最好,YK为状态变量，表示第K周实际价格XK为决策变量，取0或者1，表示第K周购买或者不买,1.阶段2.状态3.决策4.策略5.状态转移方程6.指标函数和最优值函数,动态规划（3）,.,57,分析：采购期5周分成5个阶段：每周价格看成为状态变量YK为状态变量，表示第K周实际价格XK为决策变量，取0或者1，表示第K周购买或者不买YKE表示第K周实际价格为YK时，而在以后采取最优策略时，采购价格的期望值（最可能的值）FK(YK)表示第K周实际价格为YK时,从第K周到第5周采用最优策略时，价格的最小期望值。从最后一周开始计算，对于最后一周如果还没有购买，按市场价格购买，K=5,F5(500)=500,F5(600)=600,F5(700)=700根据YKE和FK(YK)的定义，K=4,期望价格Y4E=0.3F5(500)+0.3F5(600)+0.4F5(700)=610价格为500的概率为0.3,价格为600的概率为0.3,价格为700的概率为0.4,1.阶段2.状态3.决策4.策略5.状态转移方程6.指标函数和最优值函数,动态规划（3）,.,58,500Y4=500F4(Y4)MinY4,Y4E=MinY4,610=600Y4=600610Y4=700,第四周最优策略为X4=,1采购如Y4=500或者Y4=6000等待如Y4=700,同理K=3,期望价格Y3E=0.3F4(500)+0.3F4(600)+0.4F4(700)=0.3500+0.3600+0.4610574,Y3=500574Y3=600或者700,第三周最优策略为X3=,1采购如Y3=5000等待如Y3=600或者Y3=700,F3(Y3)MinY3,Y3E=MinY3,574=,F4(Y4)表示第4周实际价格为Y4时,从第4周到第5周采用最优策略时，价格的最小期望值,实际价格Y4,期望价格Y4E,实际价格Y3,期望价格Y3E,动态规划（3）,.,59,F2(Y2)MinY2,Y2E=MinY2,552=,Y2=500552Y2=600或者700,第二周最优策略为X2=,1采购如Y3=5000等待如Y3=600或者Y3=700,F1(Y1)MinY1,Y1E=MinY1,536=,Y2=500536Y2=600或者700,第一周最优策略为X2=,1采购如Y3=5000等待如Y3=600或者Y3=700,动态规划解：开始一二三周时间充分，非最低价不买，第四周有点着急中等价也买，第五周则没有谈判的余地。,实际价格Y2,期望价格Y2E,实际价格Y1,期望价格Y1E,答案的确满足：开始几周时间充分，非最低价不买，到中间几周有点着急中等价也买，最后时刻则没有谈判的余地。,动态规划（3）,期望价格Y2E=0.3F3(500)+0.3F3(600)+0.4F3(700)=0.3500+0.3574+0.4574552,.,60,期望价格价500概率0.3第1周出现500第2周出现500第3周出现500第4周出现500第5周出现500第2周出现500=（第1周出现600或者700）并且（第2周出现500）（0.3+0.4）0.30.70.3第5周出现500=（第1,2,3周出现600或者700）并且（第4周出现700）并且（第5周出现500）0.70.70.70.40.3期望价格5000.31+0.7+0.70.7+0.70.70.7+0.70.70.70.4+6000.30.70.70.7+0.70.70.70.4+7000.70.70.70.40.4=525,（第5周出现700第1，2，3周出现600和700，第4周出现700，第5周出现7007000.70.70.70.40.4）,动态规划解-决策效果：期望价格525元,动态规划（3）,.,61,动态规划（4）,.,62,动态规划应用之五：设备更新问题举例：,状态变量？决策变量？指标函数？逆推关系？,一台设备，使用到某年，是买新的，还是继续使用？,是买新的（更新费用），继续使用（维护费用）,动态规划（4）,.,63,动态规划应用之五：设备更新问题举例：（P244例10）状态变量机龄t决策变量设备更新，保留设备第i阶段收入Ii(t)(income)第i阶段运行费用Oi(t)(operating)第i阶段到第n阶段收益Gi(t)(gain)第i阶段到第n阶段=第i阶段+第i+1阶段到第n阶段指标函数收益=收入-运行费用-更新费用Ii(t)-Oi(t)-Ci(t)逆推关系：,动态规划（4）,.,64,动态规划应用举例设备更新问题：逆推关系：,Gi(t)=Max,更新收益:Ii(0)-Oi(0)-Ci(t)+aGi+1(1),保留收益:Ii(t)-Oi(t)+aGi+1(t+1),a表示折现因子,机龄为t,保留机器后，下一阶段机龄为t1,更换机器后，下一阶段机龄为1年,第i到n期的利润,动态规划（4）,.,65,O5(3)=9:表示第5年开始机龄为3年的机器，购买年53=2年,运行费用9运行费用Oj(t)表示第j年开始机龄为t年的机器，购买年jt,动态规划（4）,.,66,说明符号对应：,I5(4)16：机器已经使用了4年，购买年为541年，在第5年的收入为16万元,O1(5)10：机器已经使用了5年，购买年为514年前，第1年使用机器运行费为10万元,动态规划（4）,.,67,j=5,从第5年开始计算时，机器使用了t=1，2，3，4，5年G5（t）表示从第5年开始计算时，机器使用了t年最佳总收入：,G5（t）=Max,更新收益：I5（0）-O5（0）-C5（t）+G6（1）保持收益：I5（t）-O5（t）+G6（t+1）,G5（1）=Max,更新：I5（0）-O5（0）-C5（t）+G6（1）=324-33+0=-5保持：I5（1）-O5（1）+G6（1+1）=28-5+0=23,I5（1）=第5年开始，5-1=4年购买，机龄1年,=23,X5（1）=保持,动态规划（4）,.,68,同理，G5（3）=13，X5（3）=保持G5（4）=6，X5（4）=保持G5（5）=4，X5（5）=保持：第5年使用机龄5年，最好不更新，因为更新的当年利润为负，反正最后一年了。,G5（2）=Max,更新：I5（0）-O5（0）-C5（t）+G6（1）=324-33+0=-5保持：I5（2）-O5（2）+G6（2+1）=24-6+0=18,I5（2）=第5年开始，5-2=3年购买，机龄2年,=18,X5（2）=保持,动态规划（4）,.,69,j=4,从第4年开始计算时，机器使用了1，2，3，4年G4（t）表示从第4年开始计算时，机器使用了t年最佳总收入：,G4（t）=Max,更新：I4（0）-O4（0）-C4（t）+G5（1）保持：I4（t）-O4（t）+G5（t+1）,G4（1）=Max,更新：I4（0）-O4（0）-C4（t）+G5（1）=304-32+23=17保持：I4（1）-O4（1）+G5（1+1）=26-5+18=39,I4（1）=第