运筹学第9章_动态规划应用举例.

清华大学出版社1五、动态规划第8章动态规划的基本方法第9章动态规划应用举例清华大学出版社2第9章动态规划应用举例第1节资源分配问题第2节生产与存储问题第3节*背包问题第4节*复合系统工作可靠性问题第5节排序问题第6节设备更新问题第7节*货郎担问题清华大学出版社3第1节资源分配问题所谓分配问题，就是将数量一定的一种或若干种资源(例如原材料、资金、机器设备、劳力、食品等等)，恰当地分配给若干个使用者，而使目标函数为最优。清华大学出版社41.1资源分配问题()iigx112212max()()()0,1,2,,nnnizgxgxgxxxxaxiniig(x)iig(x)设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为问应如何分配，才能使生产n产品的总收入最大?此问题可写成静态规划问题：当都是线性函数时，它是一个线性规划问题；当是非线性函数时，它是一个非线性规划问题。但当n比较大时，具体求解是比较麻烦的。由于这类问题的特殊结构，可以将它看成一个多阶段决策问题，并利用动态规划的递推关系来求解。清华大学出版社51.1资源分配问题在应用动态规划方法处理这类“静态规划”问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把问题中的变量xi为决策变量，将累计的量或随递推过程变化的量选为状态变量。清华大学出版社61.1资源分配问题1kkkkkssusx()0kkkkkkDsuuxs()kkfs10()max()(),1,,1()max()kknnkkkkkkkxsnnnnxsfsgxfsxknfsgx1()fa设状态变量sk表示分配用于生产第k种产品至第n种产品的原料数量。决策变量uk表示分配给生产第k种产品的原料数，即uk=xk状态转移方程：允许决策集合：令最优值函数表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收入。因而可写出动态规划的逆推关系式为：利用这个递推关系式进行逐段计算，最后求得即为所求问题的最大总收入。清华大学出版社71.1资源分配问题例1某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表9-1所示。问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。工厂盈利/万元备设台数甲乙丙000013542710639111141211125131112清华大学出版社81.1资源分配问题1kkkssx()kkPx()kkfs1044()max()(),3,2,1()0kkkkkkkkkxsfsPxfsxkfs解:将问题按工厂分为三个阶段，甲、乙、丙三个工厂分别编号为1、2、3设sk表示为分配给第k个工厂至第n个工厂的设备台数。xk表示为分配给第k个工厂的设备台数。则为分配给第k+1个工厂至第n个工厂的设备台数。表示为sk台设备分配到第k个工厂所得的盈利值。表示为sk台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值。因而可写出逆推关系式为清华大学出版社91.1资源分配问题33333()max()xfsPx下面从最后一个阶段开始向前逆推计算。第三阶段：设将s3台设备(s3=0,1,2,3,4,5)全部分配给工厂丙时，则最大盈利值为其中x3=s3=0,1,2,3,4,5因为此时只有一个工厂，有多少台设备就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值，如下表。x3s3P3(x3)f3(s3)x3*012345000014412662311113412124512125表中x3*表示使f3(s3)为最大值时的最优决策。清华大学出版社101.1资源分配问题22222322()max()()xfsPxfsx20,1,2,3,4,5x22322()()pxfsx第二阶段：设把s2台设备(s2=0,1,2,3,4,5)分配给工厂乙和工厂丙时，则对每个s2值，有一种最优分配方案，使最大盈利值为其中因为给乙工厂x2台，其盈利为p2(x2)，余下的s2−x2台就给丙工厂，则它的盈利最大值为f3(s2−x2)。现要选择x2的值，使取最大值。其数值计算如表9-3所示。清华大学出版社111.1资源分配问题2x2s22322()()pxfsx)x(f22*2x表9-3012345000010+45+05120+65+410+010230+115+610+411+014240+125+1110+611+411+0161,250+125+1210+1111+611+411+0212清华大学出版社121.1资源分配问题111121(5)max()(5)xfpxfx10,1,2,3,4,5x1121()(5)pxfx1x1s1121()(5)pxfx1(5)f*1x第一阶段：设把s1台(这里只有s1=5的情况)设备分配给甲、乙、丙三个工厂时，则最大盈利值为其中因为给甲工厂x1台，其盈利为p1(x1)，剩下的5−x1台就分给乙和丙两个工厂，则它的盈利最大值为f2(5−x1)。现要选择x1值，使取最大值，它就是所求的总盈利最大值，其数值计算如表9-4所示。01234550+213+167+149+1012+513+0210,2表9-4清华大学出版社131.1资源分配问题*211505ssx*322523ssx*333xs*211523ssx*322321ssx*331xs然后按计算表格的顺序反推算，可知最优分配方案有两个：(1)由于x1*=0，根据查表9-3知x2*=2，由故即得甲工厂分配0台，乙工厂分配2台，丙工厂分配3台。(2)由于x1*=2，根据查表9-3知x2*=2，由故即得甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。以上两个分配方案所得到的总盈利均为21万元。清华大学出版社141.1资源分配问题111()()guhsu2111()saubsu222()()guhsu12,,,nuuu资源连续分配问题设有数量为s1的某种资源，可投入A和B两种生产。第一年若以数量u1投入生产A，剩下的量s1−u1就投入生产B，则可得收入为其中g(u1)和h(u1)为已知函数，且g(0)=h(0)=0。这种资源在投入A、B生产后，年终还可回收再投入生产。设年回收率分别为0a1和0b1，则在第一年生产后，回收的资源量合计为第二年再将资源数量s2中的u2和s2−u2分别再投入A、B两种生产，则第二年又可得到收入为如此继续进行n年，试问：应当如何决定每年投入A生产的资源量才能使总的收入最大?清华大学出版社151.1资源分配问题此问题写成静态规划问题为111222211132221max()()()()()()()()()0,1,2,,nnnnnnniizguhsuguhsuguhsusaubsusaubsusaubsuusin清华大学出版社161.1资源分配问题1()kkkksaubsu010()max()()()max()()()1,,2,1nnkknnnnnuskkkkkkkkkusfsguhsufsguhsufaubsukn下面用动态规划方法来处理。设sk为状态变量，它表示在第k阶段(第k年)可投入A、B两种生产的资源量。uk为决策变量，它表示在第k阶段(第k年)用于A生产的资源量，则sk−uk表示用于B生产的资源量。状态转移方程为最优值函数fk(sk)表示有资源量sk，从第k阶段至第n阶段采取最优分配方案进行生产后所得到的最大总收入。因此可写出动态规划的逆推关系式为最后求出f1(s1)即为所求问题的最大总收入。清华大学出版社171.1资源分配问题例2机器负荷分配问题某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1，其中u1为投入生产的机器数量，年完好率a=0.7；在低负荷下生产的产量函数为h=5y，其中y为投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好的机器数量s1=1000台，试问每年如何安排机器在高、低负荷下的生产，使在五年内生产的产品总产量最高。清华大学出版社181.1资源分配问题构造这个问题的动态规划模型：设阶段序数k表示年度。状态变量sk为第k年度初拥有的完好机器数量，同时也是第k−1年度末时的完好机器数量。决策变量uk为第k年度中分配高负荷下生产的机器数量，于是sk−uk为该年度中分配在低负荷下生产的机器数量。这里sk和uk均取连续变量，它们的非整数值可以这样理解，如sk=0.6，就表示一台机器在k年度中正常工作时间只占6/10；uk=0.3，就表示一台机器在该年度只有3/10的时间能在高负荷下工作。状态转移方程为1()0.70.9(),1,2,,5kkkkkkksaubsuusuk()0kkkkkDsuus(,)kkkvsu85()kkkkvusu151,5(,)kkkkVvsuk段允许决策集合为设为第k年度的产量，则故指标函数为清华大学出版社191.1资源分配问题661()()0()max85()0.70.9()1,2,3,4,5kkkkkkkkkkkkuDsfsfsusufusuk令最优值函数fk(sk)表示由资源量sk出发，从第k年开始到第5年结束时所生产的产品的总产量最大值。因而有逆推关系式：清华大学出版社201.1资源分配问题55555555655505555055505()max85()0.70.9()max85(5)max35usususfsusufusuusuus555()8fss从第5年度开始，向前逆推计算。当k=5时，有因f5是u5的线性单调增函数，故得最大解u5*，相应的有清华大学出版社211.1资源分配问题44444444444445444044444404440440()max85()0.70.9()max85()80.70.9()max13.612.2()max1.412.2ususususfsusufusuusuusuusuus444()13.6fss*33333*2222*1111()17.50()20.80()23.7usfssufssufss,相应的,相应的,相应的11()23700fs当k=4时，有故得最大解，u4*=s4，相应的有依此类推，可求得因s1=1000，故清华大学出版社221.1资源分配问题计算结果表明：最优策略为*****123344550,0,,,uuususus即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负荷生产。这样所得的产量最高，其最高产量为23700台。清华大学出版社231.1资源分配问题**21111**32222**43333**54444**655550.70.9()0.9900()0.70.2()0.9810()0.70.9()0.7567()0.70.9()0.7397()0.70.9()0.7278()susussusussusussusussusus台台台台台在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即从始端向终端递推计算出每年年初完好机器数。已知s1=1000台，于是可得清华大学出版社241.1资源分配问题下面讨论始端固定、终端自由的一般情形。12,gcuhdu1(),1,2,,kkkksaubsukn(),1,2,