规划数学 确定型动态规划.pptx

第八章动态规划1建立动态规划模型的步骤1、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一步,在确定多阶段特性后,按时间或空间先后顺序,将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念,以便划分阶段。2、正确选择状态变量Sk选择变量既要能确切描述过程演变又要满足无后效性,而且各阶段状态变量的取值能够确定。一般地,状态变量的选择是从过程演变的特点中寻找。3、确定决策变量Uk及允许决策集合Dk通常选择所求解问题的关键变量作为决策变量,同时要给出决策变量的取值范围,即确定允许决策集合。第八章动态规划24、确定状态转移方程Sk+1=Tk(Sk,Uk)根据k阶段状态变量和决策变量,写出k+1阶段状态变量,状态转移方程应当具有递推关系。5、正确写出指标函数Vk,n的关系,它应满足下面三个性质:Vk,n是定义在全过程和所有后部子过程上的数量函数具有可分离性,并满足递推关系,即Vk,n(Sk,Uk,Sk+1,……Sn+1)=φk(Sk,Uk,Vk+1,n(Sk+1,Uk+1,Sn+1))函数φk(Sk,Uk,Vk+1,n)对于变量Vk+1,n要严格单调。6、恰当地定义最优指标函数阶段指标函数是指第k阶段的收益,最优指标函数是指从第k阶段状态出发到第n阶段末所获得收益的最优值。第八章动态规划3动态规划模型分类过程变量确定随机离散连续离散确定型离散随机型连续确定型连续随机型7、写出恰当的边界条件,从边界条件开始,逐段递推寻优,在每一个子问题的求解中,均用了它前面的子问题的最优化结果,依次进行,最后一个子问题所得的最优结果,就是这个问题的最优解,并找到相应的最优策略。第6章动态规划动态规划的基本理论(2学时)确定型动态规划(2学时)随机型动态规划(1学时)动态规划的软件计算 (1学时)第14讲确定型性动态规划()最短路问题资源分配问题生产与存储问题动态规划和静态规划的关系 自学背包问题、排序问题、货郎担问题资源分配问题:把有限的资源(如资金、材料、设备、人力等)分配给若干使用者,而使某一指标为最优的问题即为资源分配问题。资源可以有一种或若干种,只有一种资源可供分配的问题称之为一维资源分配问题。资源分配问题()例1:某工业部门按国家计划的安排,拟将某高效率的设备五台,分配给所属的甲、乙、丙三个工厂,各工厂若获得这种设备之后,可以为国家提供的盈利如下表所示。问:这五台设备如何分配给各工厂,才能使国家得到的盈利最大。1、一维资源分配问题动态规划的数学模型将三个分厂看作是三个阶段,即阶段变量k=1,2,3;状态变量sk表示第k阶段初可分配的设备台数,0≤sk≤5;决策变量xk表示第k阶段分配给分厂k的设备台数,允许决策集合Xk(sk)={xk︱0≤xk≤sk};状态转移方程为sk+1=sk-xk;阶段指标Pk(sk,xk)表示第k阶段从sk台设备中分配给k分厂xk台设备的阶段效益;最优指数函数fk(sk)表示第k阶段从sk开始到最后阶段采用最优分配策略取得的最大的效益值;递推方程函数式第三阶段:设将S3台设备(S3=0,1,2,3,4,5)全部分配给丙厂时,最大盈利值为:f3(S3)=max[P3(X3)]其中X3=S3=0,1,2,3,4,5X3*表示使得f3(S3)为最大值时的最优决策。X3S3P3(X3)f3(S3)X3*0123450000144126623111134**********逆序求解表9-1第二阶段:设将S2台设备(S2=0,1,2,3,4,5)分配给乙厂和丙厂时,对每一个S2值,都有一种最优分配方案,使得最大盈利值为:f2(S2)=max[P2(X2)+f3(S2-X2)],X2=0,1,2,3,4,5X2S2P2(X2)+f3(S2-X2)f2(S2)X2*0**********+45+05120+65+410+010230+115+610+411+014240+125+1110+611+411+0161,250+125+1210+1111+611+411+0212表9-2