文档介绍：:1阶段:把问题分为互相联系有一定次序的阶段,一般按时间和空间的自然特征划分。2状态:每个阶段开始所处自然状况或客观条件,不可控制。用表示第阶段的状态变量,代表第阶段所有始点的集合,又称该阶段的可达状态集合(状态变量的取值范围)。状态的性质:无后效性(马尔科夫性)3决策:某个阶段的某个状态决定下一个阶段的状态用表示第阶段当状态处于时的决策变量。4策略:是一个按顺序排列的决策组成的集合。用表示由过程的第阶段开始到终止状态为止的过程,即问题的后部子过程,称为子过程策略。当成为全过程的策略,简称策略。所有策略(允许策略集合)中达到最优效果的策略为最优策略动态规划(1)25状态转移方程:确定由一个状态转到另一个状态的演变过程。第阶段到阶段的状态转移方程为6指标函数:衡量过程优劣的数量指标。动态规划模型的指标函数应具有可分离性和满足递推关系。表示从第阶段的状态开始到第阶段的终止的过程。37最优值函数:表示从第阶段的状态开始到第阶段的终止的过程,采取最优策略所得到的指标函数值。4动态规划解法:第一步:划分阶段第二步:选择状态变量第三步:确定决策变量第四步:写状态转移方程第五步:指标函数动态规划(1)5动态规划(1)动态规划的逆序解法和顺序解法:6顺推法求解非线性规划:maxZ=4x1+9x2+2x32x1+x2+x3=10xi>=0I=1,2,3动态规划应用之二:资源分配问题动态规划(1)引例:某种原料总数为a分配给n种产品,分配数量Xi用于生产第i种产品,效益为gi(xi)7顺推法求解非线性规划: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)8解:设状态变量S1=X1,S2=S1+X2,S3=S2+(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=(1)9X3H3(S3,X3)109/4在X3=9/4,F3(S3)有最小值,F3(S3)最大值X3=10动态规划(1)10