资源描述：
《动态规划教学文案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、动态规划5状态转移方程：确定由一个状态转到另一个状态的演变过程。第阶段到阶段的状态转移方程为6指标函数：衡量过程优劣的数量指标。动态规划模型的指标函数应具有可分离性和满足递推关系。表示从第阶段的状态开始到第阶段的终止的过程。7最优值函数：表示从第阶段的状态开始到第阶段的终止的过程，采取最优策略所得到的指标函数值。动态规划解法：第一步：划分阶段第二步：选择状态变量第三步：确定决策变量第四步：写状态转移方程第五步：指标函数动态规划（1）动态规划（1）动态规划的逆序解法和顺序解法：顺推法求解非线性规划：maxZ=4x1+9x2+2x32x1+x2+x
2、3=10xi>=0I=1,2,3动态规划应用之二：资源分配问题动态规划（1）引例：某种原料总数为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=X
3、1S2=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)=
4、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为非负整数经
5、济意义：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阶段
6、可供分配重量，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≤5
7、X1≤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，
8、W2=W1-5X1=15X*2=7因此,最优解为X*1=0,X*2=7,最优值:Z*=49动态规划（1）动态规划（2）动态规划（2）一个老板要把五台高
