动态规划

五.动态规划动态规划的基本概念：1阶段：把问题分为互相联系有一定次序的阶段，一般按时间和空间的自然特征划分。2状态：每个阶段开始所处自然状况或客观条件，不可控制。用表示第阶段的状态变量，代表第阶段所有始点的集合，又称该阶段的可达状态集合（状态变量的取值范围）。状态的性质：无后效性（马尔科夫性）3决策：某个阶段的某个状态决定下一个阶段的状态用表示第阶段当状态处于时的决策变量。4策略：是一个按顺序排列的决策组成的集合。用表示由过程的第阶段开始到终止状态为止的过程，即问题的后部子过程，称为子过程策略。当成为全过程的策略，简称策略。所有策略（允许策略集合）中达到最优效果的策略为最优策略动态规划（1）1,2,3,4kkSkk()kkuskks,11()(),(),,()knkkkkknnpsusususkk1kk5状态转移方程：确定由一个状态转到另一个状态的演变过程。第阶段到阶段的状态转移方程为6指标函数：衡量过程优劣的数量指标。动态规划模型的指标函数应具有可分离性和满足递推关系。表示从第阶段的状态开始到第阶段的终止的过程。1()kkksusk1k,,11(,,,,)1,2,,knknkkknVVsussknkksn7最优值函数：表示从第阶段的状态开始到第阶段的终止的过程，采取最优策略所得到的指标函数值。kksn,11,,()(,,,,)1,2,,knkkknkkknuufsoptVsusskn动态规划解法：第一步：划分阶段第二步：选择状态变量第三步：确定决策变量第四步：写状态转移方程第五步：指标函数动态规划（1）动态规划（1）动态规划的逆序解法和顺序解法：0)(1,,1,)](),([)(1111)(nnkkkkkSDukksfnnksfusvoptsfkkk0)(,,2,1)](),([)(1011)(11sfnksfusvoptsfkkkkkSDukkkkk顺推法求解非线性规划：maxZ=4x1+9x2+2x32x1+x2+x3=10xi=0I=1,2,3动态规划应用之二：资源分配问题动态规划（1）0...)(...)()(212211innnxaxxxxgxgxgMaxZ引例：某种原料总数为a分配给n种产品，分配数量Xi用于生产第i种产品，效益为gi(xi)顺推法求解非线性规划：maxZ=4x1+9x2+2x32x1+x2+x3=10xi=0I=1,2,3分析：理解为第一阶段投资x1，第二阶段投资x2第三阶段投资x3求最大利润maxZ=4x1+9x2+2x32三阶段投资总额共有10亿元非线性规划问题求解第一阶段投资总额S1（状态变量）第一二阶段投资总额S2（状态变量）第一二三阶段投资总额S3（状态变量）x1x2x3S3S2S1S1=X1S2=X1+X2S3=X1+X2+X3动态规划应用之二：资源分配问题动态规划（1）解:设状态变量S1=X1,S2=S1+X2,S3=S2+X3.F1(S1)=4X1=4S1(第一阶段投资x1产生的效益4X1）第一二阶段投资总量为S2产生的效益＝第一阶段投资x1产生的效益＋第二阶段投资X2产生的效益F2(S2)=9X2+F1(S1)=4S2+5X2X2＝S2当X2=S2时maxF2(S2)=9S2第一二三阶段投资总量为S3产生的效益＝第一二阶段投资S2产生的效益＋第三阶段投资X3产生的效益S2=S3-X3F3(S3)=2X32+F2(S2)=2X32+9(S3-X3)=2X32-9X3+9S3=h3(S3,X3)dh3(S3,X3)/dX3=4X3-9=0=X3=9/40=X3=10在X3=9/4,F3(S3)有最小值,F3(S3)最大值X3＝10maxF3(S3)=2*102=200即X3=10,则X1,X2为0maxZ=200.动态规划（1）X3H3(S3,X3)109/4在X3=9/4,F3(S3)有最小值,F3(S3)最大值X3＝10动态规划（1）背包问题用动态规划解下列问题：MaxZ=8X1+7X2S.T.2X1+X2≤85X1+2X2≤15X1,X2为非负整数经济意义：X1,X2为物品数量，8，7为单位物品的价值，2，1为单位物品的体积，8为背包的最大容积，5，2为单位物品的重量，15为背包的最大承受重量（太重背包带会断）动态规划（1）用动态规划逆序算法解下列问题（二维背包问题）：MaxZ=8X1+7X2（最大效益，重量限制，体积限制）S.T.2X1+X2≤8(重量)5X1+2X2≤15(体积)X1,X2为非负整数解：用逆序算法。设：阶段：分成两个阶段，分别对应第1种物体的数量X1，第2种物体的数量X2第1阶段决定背包中第1种物体的数量决策变量：X1，X2为背包中两种物体的数量状态变量：V1为第1阶段可供分配重量，V1＝8W1为第1阶段可供分配体积，W1＝15，V2，W2对应第2阶段于是，F*2（V2，W2）=Max{7X2}0≤X2≤V2(重量)0≤2X2≤W2(体积)x1x2V1，W1V2，W2V1=8，W1=15V2=V1-2X1(重量)W2=W1-5X1(体积)动态规划（1）X2为整数F*2（V2，W2）=Max{7X2}=7min{[V2],[W2/2]}([V]是小于等于V的最大整数)F*1（V1，W1）=Max{8X1+F*2（V2，W2）}=Max{8X1+F*2（V1-2X1，W1-5X1）}0≤2X1≤V1(重量)0≤5X1≤W1(体积)X1为整数而V1=8，W1=15因此F*2（V1-2X1，W1-5X1）=7min{[8-2X1],[(15-5X1)/2]F*1（8，15）=Max{8X1+7min{[8-2X1],[(15-5X1)/2]}0≤2X1≤80≤5X1≤15X1为整数由于X1≤min{[8/2],[(15/5)]=3(X1为0，1，2，3，分别代入下式，也可用分析)F*1（V1，W1）=Max{8X1+7min{[8-2X1],[(15-5X1)/2]}}动态规划（1）X*1=0X*2=min{[V2],[W2/2]}V2=V1-2X1=8，W2=W1-5X1=15X*2=7因此,最优解为X*1=0,X*2=7,最优值:Z*=49动态规划（1）动态规划（2）动态规划（2）一个老板要把五台高效率的设备调配给自己的三家分厂，各个工厂得到这些设备所产生的利润如下表，问如何调配可以获得最大利润？产生利润工厂1工厂2工厂30台0001台3542台71063台911114台1211125台131112阶段,决策变量与状态变量???动态规划应用之二：资源分配问题阶段,决策变量与状态变量决策变量:分配到k厂的设备台数Xk状态变量:分配到k厂到3厂的设备总台数Sk,产生利润工厂1工厂2工厂30台0001台3542台71063台911114台1211125台131112X1X2X3S1S2S3S3=X3S2=X2+X3S1=X1+X2+X3动态规划（2）P3(X3)F3(S3)X*3X3=0X3=1X3=2X3=3X3=4X3=5S3=0000S3=1441S3=2662S3=311113S3=412124S3=512125注意：分配到3厂到3厂的设备总台数S3=分配到3厂的设备台数X3动态规划（2）分配到2厂的设备台数X2P2(X2)＋F3(S2–X2)F2(S2)X*2X2=0X2=1X2=2X2=3X2=4X2=5S2=0000S2=10＋45＋051S2=20＋65＋410＋0102S2=30＋115＋610＋411＋0142S2=40＋125＋1110＋611＋411＋0161，2S2=50＋125＋1210＋1111＋611＋411＋0212分配到2厂到3厂的设备总台数S2=X2＋X3由已知表：第2厂分配3台设备得效益11由上表：第3厂分配2台设备得效益6动态规划（2）分配到1厂的设备台数X1P1(X1)＋F2(5-X1)F1(5)X*1X1=0X1=1X1=2X1=3X1=4X1=5S1=50＋21=213＋16=197＋14=219＋10=1912＋513＋0=13210，2分配给1厂到3厂的设备总台数S1=5由已知表：第1厂分配4台设备得效益12，由上表：第2，3厂分配1台设备得效益5由第三表知：总利润21万元X1＝0，第1工厂不分配，第2，3工厂分配5台，S2=X2+X3＝5由第二表对应S2＝5知：X2＝2，第2工厂分配2台，于是第3工厂分配3台最优分配：第1厂分配0台；第2厂分配2台；第3厂分配3台；总利润21万元动态规划（2）另一个结果是，由第三表知：总利润也是21万元X1＝2，第1工厂分配2台，第2，3工厂分配3台，S2=X2+X3＝3由第二表对应S2＝3知：X2＝2，第2工厂分配2台，于是第3工厂分配1台最优分配：第1厂分配2台；第2厂分配2台；第3厂分配1台；总利润21万元动态规划（2）一个老板要把五台高效率的设备调配给自己的三家分厂，各个工厂得到这些设备所产生的利润如下表，问如何调配可以获得最大利润？产生利润工厂1项目1工厂2项目2工厂3项目30台0亿0001台1亿3542台2亿71063台3亿911114台4亿1211125台5亿131112X1X2X3S1S2S3S3=X3S2=X2+X3S1=X1+X2+X3可以理解为5亿元，投资于三个项目动态规划（2）P3(X3)F3(S3)X*3X3=0X3=1X3=2X3=3X3=4X3=5S3=0000S3=1441S3=2662S3=311113S3=412124S3=512125注意：投资到3项目到3项目的资金总数S3=投资到3项目的资金总数X3动态规划（2）投资到2项目的资金总数X2P2(X2)＋F3(S2–X2)F2(S2)X*2X2=0X2=1X2=2X2=3X2=4X2=5S2=0000S2=10＋45＋051S2=20＋65＋410＋0102S2=30＋115＋610＋411＋0142S2=40＋125＋1110＋611＋411＋0161，2S2=50＋125＋1210＋1111＋611＋411＋0212投资到2项目到3项目的资金总数S2=X2＋X3=5由已知表：第2项目投资3亿元得效益11由上表：第3项目投资2亿元得效益6动态规划（2）投资到1项目的资金数X1P1(X1)＋F2(5-X1)F1(5)X*1X1=0X1=1X1=2X1=3X1=4X1=5S1=50＋21=213＋16=197＋14=219＋10=1912＋513＋0=13210，2投资给1项目到3项目的资金总数S1=5亿由已知表：第1项目投资4亿得效益12，由上表：第2，3项目投资1亿得效益5由第三表知：总利润21万元X1＝0，第1项目不投资，第2，3工厂投资项目5亿，S2=X2+X3＝5由第二表对应S2＝5知：X2＝2，第2项目投资2亿，于是第3项目投资3亿最优分配：第1项目投资0亿元；第2项目投资2亿元；第3项目投资3亿元；总利润21万元动态规划（2）动态规划应用之二：资源分配问题（续）例1求解非线性规划例2背包问题（整数规划）例3利润函数为表格（非连续函数）例4固定资金分配问题动态规划（2）固定资金分配一个老板有N个企业，都需要两种资源，对于第K个企业，如果用第1种资源XK，用第2种资源YK,可以得到利润RK(XK,YK),第1种资源的单位价格为A,第2种资源的单位价格为B,现有资金Z,问应该购买第1种资源（设为X）和第2种资源（设为Y）各多少单位分配到N个企业，可以使总利润达到最大？动态规划应用之二：资源分配问题（续）动态规划（2）该问题的数学模型为：为非负整数kknkknkknkkkyxZbYaXYyXxyxR,),(max111思路：把资源分配换算成资金分配，将二元转换为一元逆序解法：)()()]()([max)()],([max)(1,,1,0]/[,,1,0zRzfzzfzRzfy