动态规划第3节课件.ppt

《动态规划第3节课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、建立动态规划模型的一般步骤1划分阶段。即按时间和空间的先后顺序适当地划分为满足递推关系的若干个阶段。2正确选择状态变量。（可知性和无后效性）3根据状态变量和决策变量的含义，正确写出状态转移方程sk+1=Tk(sk,uk)4明确指标函数Vk.n、最优指标函数fk(sk)及k阶段指标Vk(sk,us)的含义。5正确列出最优指标函数的递推关系及边界条件。第3节资源分配问题所谓分配问题，就是将数量一定的一种或若干种资源（例如原材料，资金，机器设备，劳力，食品等等），恰当地分配给若干个使用者，使效益函数为最优。资源分配问题：离散、连续。（1）资源离散分配问题例1某工业部门根据国家计划

2、的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂获得这种设备，可以提供的期望盈利如下表所示。问如何分配这五台设备给各厂，才能使国家得到的期望盈利最大？工厂盈利设备台数甲乙丙012345037912130510111111046111212解：设xj（j=1,2,3）分别表示分配给甲、乙、丙三个厂的设备台数。则此问题可写成以下数学模型：maxz=g1(x1)+g2(x2)+g3(x3)其中g1(x1)，g2(x2)，g3(x3)分别对应表中甲、乙、丙厂的期望盈利数。先考虑构成动态规划模型的条件：1、按工厂将问题划分为三个阶段，并将工厂编号为k=1,2,

3、3。2、设状态变量Sk表示为分配给第k个工厂至第3个工厂的设备台数。（显然S1=5，所以可考虑用逆序法。）3、决策变量Xk，表示为分配给第k个工厂的设备数。0≤Xk≤Sk。4、状态转移方程为Sk+1=Sk-Xk5、阶段指标gk(sk,xk)表示Xk设备分配到第k个工厂所得的期望盈利值。因此基本方程为：下面用逆序法采用表格形式进行求解。k=3，0≤X3≤S3，S4=S3-X3S3X3(S3)g3(S3，X3)+f4(S4)f3(S3)X3*(S3)000+0*00114+0*41226+0*623311+0*1134412+0*1245512+0*125k=2，0≤X2≤S2

4、，S3=S2-X2S2X2(S2)g2(S2,X2)+f3(s3)f2(S2)X2*(S2)000+0001010+45+0*5120120+65+410+0*102301230+115+610+4*11+0142S2X2(S2)g2(S2,X2)+f3(s3)f2(S2)X2*(S2)4012340+125+11*10+6*11+411+0161或250123450+125+1210+11*11+611+411+0212k=1，0≤X1≤S1，S2=S1-X1S1X1(S1)g2(S1X1)+f2(s2)f1(s1)x1*50123450+21*3+167+14*9+10

5、12+513+0210或2按计算表格的顺序反推，得最优分配方案有两个：第一方案：x1*=0x2*=2x3*=3第二方案：x1*=2x2*=2x3*=1它们所得的总盈利都为21（万元）。本例若设Sk表示分配给从第1个工厂到第k个工厂的设备台数，即S3=5，因此，本例还可用顺序法求解，其结果完全一致。思考题：如果原设备台数是4台，求最优分配方案？例1实际上是一个一维资源分配问题。一维资源分配问题总可以写成“静态规划”问题：maxz=g1(x1)+g2(x2)+…+gn(xn)由于这类问题的特殊结构，可以把它看成是一个多阶段决策问题，并利用动态规划的递推关系求解。一般有（1）阶段

6、划分：通常把资源分配给一个或几个使用者的过程作为一个阶段。即把问题中变量的个数作为阶段数，k=1,2,…n。（2）状态变量SK的含义：SK表示分配用于生产第k种产品至第n种产品的资源数。显然S1=a，所以该类问题可用逆序法求解。（也可用顺序法，Sn=a）（3）决策变量dk的选定：dk=xk，含义为分配给生产第k种产品的资源数。允许决策集合为：Dk(Sk)={dk

7、0≤dk=xk≤Sk}。（4）状态转移方程：Sk+1=Sk-dk=Sk-xk(Sk=Sk+1+xk)（5）由于阶段指标vk(Sk,xk)=gk(xk)，所以指标函数：基本方程为（2）资源连续分配问题如此进行n年，如

8、何确定投入A的资源量u1、…、un，使总收入最大？（2）资源连续分配问题此类问题的静态规划模型为：设sk为状态变量，它表示在第k阶段（第k年）可投入A、B两种生产的资源量；uk为决策变量，它表示在第k阶段（第k年）用于A生产的资源量，则sk-uk表示用于B生产的资源量；状态转移方程为：sk+1=auk+b(sk-uk)最优值函数fk(sk)表示有资源量sk从第k阶段至第n阶段采取最优分配方案进行生产后所得到的最大总收入。动态规划的逆推关系方程为：最后求得的f1(s1)即为所求问题的最大收入。例2机器负荷分配问题某种