规划数学-确定型动态规划

《运筹学》第八、九章动态规划第八章动态规划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讲确定型性动态规划(6.2)最短路问题资源分配问题生产与存储问题动态规划和静态规划的关系自学背包问题、排序问题、货郎担问题•资源分配问题：–把有限的资源(如资金、材料、设备、人力等)分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。–资源可以有一种或若干种，–只有一种资源可供分配的问题称之为一维资源分配问题。资源分配问题(6.2.2)例1：某工业部门按国家计划的安排，拟将某高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如下表所示。问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。工厂盈利设备台数000013542710639111141211125131112甲乙丙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开始到最后阶段采用最优分配策略取得的最大的效益值;–递推方程函数式0)()(),()(4411)(maxsfsfxsPsfkkkkkSXxkkkkk边界条件：基本方程：第三阶段：设将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*012345000014412662311113412124512125逆序求解表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*012345000010＋45＋05120＋65＋410＋010230＋115＋610＋411＋014240＋125＋1110＋611＋411＋0161,250＋125＋1210＋1111＋611＋411＋0212表9－2第一阶段：设将S1台设备（S1＝5）分配给甲厂、乙厂和丙厂时，则最大盈利值为：f1(S1)＝max[P1(X1)+f2(5－X1)]其中，X1＝0,1,2,3,4,5X1S1P1(X1)＋f2(5－X1)f1(5)X1*01234550＋213＋167＋149＋1012＋513＋0210,2按计算表格的顺序反推，可知最优分配方案有两个：1）由X1*＝0，S2＝S1－X1*＝5－0＝5。再由表9－2，可知X2*＝2。S3＝S2－X2*＝5－2＝3，故X3*＝S3＝3。即得甲厂分得0台，乙厂分得2台，丙厂分得3台。2）由X1*＝2，S2＝S1－X1*＝5－2＝3。再由表9－2，可知X2*＝2。S3＝S2－X2*＝3－2＝1，故X3*＝S3＝1。即得甲厂分得2台，乙厂分得2台，丙厂分得1台。以上两种最优方案的总盈利均为21万元。例2机器负荷问题——某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1，其中u1为投入生产的机器数量，年完好率为a=0.7；在低负荷下生产的产量函数为h=5y，其中y为投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好的机器数量S1＝1000台，试问每年如何安排机器在高低负荷下的生产，使在五年内生产的产品总产量最高。2、资源连续分配问题•动态规划的数学模型–每年为一个阶段，即阶段变量k=1,2,3,4,5;–状态变量sk表示第k年初所拥有的完好机器台数，s1=1000;–决策变量uk表示第k年投入高负荷生产的机器数，允许决策集合Uk(sk)={uk︱0≤uk≤sk};sk－uk表示为第k年初分配在低负荷下生产的机器数量。–状态转移方程为sk+1=auk+b(sk–uk)=0.7uk+0.9(sk–uk)–=0.9sk–0.2uk;–阶段指标vk(sk,xk)表示第k年的产量：vk(sk,uk)=8uk+5(sk–uk)=5sk+3uk;–最优指数函数fk(sk)表示第k阶段从sk开始到最后阶段采用最优分配策略实现的最大产量;0)(5,4,3,2,1)2.09.0(35)(),()(661011)(maxmaxsfkusfussfusvsfkkkkkSukkkkkSUukkkkkkk边界条件：基本方程：解：•K=5从第5阶段开始，向前逆推计算55)(),()(35maxmax5555066555055usSuSusfusvsff5(s5)是关于u5的单增函数，故u*5=s5时，f5(s5)最大，f5(s5)=8s5•K=4440444405440554440444.12.12)2.09.0(835835)(),()(maxmaxmaxmax44444444ususussussfusvsfsusususuf4(s4)是关于u4的单增函数，故u*4=s4时，f4(s4)=13.6s4•K=33303333043304433303328.024.17)2.09.0(6.13356.1335)(),()(maxmaxmaxmax33333333ususussussfusvsfsusususuf3(s3)是关于u3的单增函数，故u*3=s3时，f3(s3)=17.52s3•K=222022220322033222022504.08.20)2.09.0(52.173552.1735)(),()(maxmaxmaxmax22222222ususussussfusvsfsusususuf2(s2)是关于u2的单调减函数，故u*2=0时，f2(s2)=20.8s2依次类推，可求得：u1*＝0，f1(s1)＝23.7s1•最优生产策略：u*1=0，u*2=0，u*3=s3，u*4=s4，u*5=s5•各阶段状态：–s1=1000，u*1=0，–s2=0.9s1–0.2u1=0.9s1=900，u*2=0，–s3=0.9s2–0.2u2=0.9s2=810，u*3=s3，–s4=0.9s3–0.2u3=0.7s3=576，u*4=s4–s5=0.9s4–0.2u4=0.7s4=397，u*5=s5–s6=0.9s5–0.2u5=0.7s5=278即前两年应把年初全部完好的机器投入低负荷下生产，后三年应把年初全部完好的机器投入高负荷下生产。这样最高产量为23700台。–企业一年中的产品生产往往是分期分批生产的。–组织每批产品的生产，都要花费一些生产准备费和存贮费用。•若某一时期增大生产批量则可减少生产批次，从而降低生产成本。•与此同时，批量大了，必然增加库存而使存贮费用增加。–在企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题。生产存储问题(6.2.3)1、生产计划问题：例3某工厂要对一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的需求量如下表所示。假定该厂生产每批产品的固定成本为3千元，若不生产就为0，每单位产品成本为1千元，每个时期生产能力所允许的最大生产批量为不超过6个单位，每个时期末未售出的产品，每单位需付存货费0.5千元。还假定在第一个时期的初始库存量为0，第四个时期之末的库存量也为0。试问：该厂应如何安排各个时期的生产与库存，才能在满足市场需求的条件下，总成本最小。时期(k)1234需求量(dk)2324•动态规划的数学模型–该问题分成四个阶段，k表示年度，k＝1，2，3，4;–状态变量sk-1表示为第k年初的库存量，第k－1年末的库存量。–决策变量uk表示为第k年的生产量，dk表示为第k年的需求量。允许决策集合Dk(sk)={uk︱0≤uk≤6}–状态转移方程为sk=sk-1+uk－dk;s0＝0;s4＝0–第k年的生产成本为：66211300)(kkkkkkuuuuuc当，，＝当＝当解：第k期末库存量为sk的存贮费用为:hk(sk)=0.5sk总成本为:ck(uk)＋hk(sk)fk(sk)表示由第1年的初始库存为0到第k年末的库存为Sk的最小总成本。fk(sk)＝min{ck(uk)＋hk(sk)＋fk-1(sk-1)}＝min{ck(uk)＋hk(sk)＋fk-1(sk＋dk－uk)}k=1,2,3,4边界条件f0(s0)＝0写出顺序递推关系式：由于库存量必须非负,sk-1＝sk＋dk－uk,uk≤sk＋dkuk≤6,所以uk≤min{sk＋dk，6}sk≤即使以后各期不再生产，须满足最后的库存为0。在0和min{，6-dk}之间取值nkjjd1nkjjd1f1(s1)＝min{c1(u1)＋h1(s1)＋f0(s0)}s1＝s0+u1－d1d1=2s1＝0，u1＝2，f1(0)＝5s1＝1，u1＝3，f1(1)＝6.5s1＝2，u1＝4，f1(2)＝842jjd对s1≤＝9之间的值分别进行计算。k＝1s1＝3，u1＝5，f1(3)＝9.5s1＝4，u1＝6，f1(4)＝11f2(s2)＝min{c2(u2)＋h2(s2)＋f1(s2＋d2－u2)}k＝2其中，u2≤min{s2＋3，6}s2＝1，f2(1)＝min{c2(u2)＋h2(1)＋f1(4－u2)}5.9565.65845.90min(0)f0(3)C(1)f0(2)C(2)f