第14讲确定型动态规划.

第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)f0(1)C(3)f0(0)Cmin121212125.1155.075.65.0685.055.95.04115.00min(0)f5.0(4)C(1)f5.0(3)C(2)f5.0(2)C(3)f5.0(1)C(4)f5.0(0)Cmin121212121243jjd对s2≤＝6之间的值分别进行计算。s2＝0，f2(0)＝min{c2(u2)＋h2(0)＋f1(3－u2)}u2=0f2(0)＝9.5u2=0u2=0f2(1)＝11.5，u2=0s2＝2，f2(2)＝min{c2(u2)＋h2(2)＋f1(5－u2)}＝14，u2=5s2＝3，f2(3)＝min{c2(u2)＋h2(3)＋f1(6－u2)}＝15.5，u2=6s2＝4，f2(4)＝min{c2(u2)＋h2(4)＋f1(7－u2)}＝17.5，u2=6s2＝5，f2(5)＝min{c2(u2)＋h2(5)＋f1(8－u2)}＝19.5，u2=6s2＝6，f2(6)＝min{c2(u2)＋h2(6)＋f1(9－u2)}＝21.5，u2=6145.955.114140min(0)f0(2)C(1)f0(1)C(2)f0(0)Cmin232323f3(s3)＝min{c3(u3)＋h3(s3)＋f2(s3＋d3－u3)}其中，u3≤min{s3＋2，6}s3在0至d4＝4之间k＝3s3＝0，f3(0)＝min{c3(u3)＋h3(0)＋f2(2－u3