运筹学第九章动态规划应用举例

1第九章动态规划应用举例(DualityTheory)1一维资源分配问题2生产与存贮问题3背包问题4设备更新问题5货郎担问题2第一节一维资源分配问题一、一维资源分配问题基本模型及求解方法1.模型设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，才能使生产n种产品的总收入最大？此问题可写成静态规划问题：nixaxxxtsxgxgxgMaxZinnn,,2,10..)()()(2122113在应用动态规划处理这类“静态规划”问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把问题中的变量xi作为决策变量，将累计的量或随递推过程变化的量选为状态变量。当gi(xi)都是线性函数时，它是一个线性规划问题；当gi(xi)不是线性函数时，它是一个非线性规划问题。但当n较大时，具体求解是比较麻烦的。然而，由于这类问题的特殊结构，可以将它看成一个多阶段决策问题，并利用动态规划得递推关系来解。42.求解方法设状态变量sk表示分配用于生产第k种产品至第n产品的原料数量。则s1=a，可用逆推法求解。设决策变量uk表示分配给生产第k种产品的原料数量，即:uk=xk状态转移方程：kkkkkxsuss1允许决策集合：}0|{)(kkkkkksxuusD把该分配问题看成是对资源总量的消耗过程。5令最优值函数fk(sk)表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收入。递推关系式为：0)(1,,1,)}()({max)(1110nnkkkkksxkksfnnkxsfxgsfkk利用这个递推关系式进行逐段计算，最后求得最大总收入为f1(a)6例1某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。31,,11)(max)(321iixxxxdsf解：设分配人员的顺序为市场1,2,3，已知s1=9，用逆推法。设sk为第k阶段尚未分配的人员数，xk为第k阶段分配的推销人员数。则状态转移方程为sk＋1=sk–xk目标函数为二、离散的一维资源分配问题7第三阶段：给第三市场分配s3有0－9种可能，第三阶段最优决策表如下：8第二阶段：给第二市场分配s2有0~9种可能，第二阶段最优决策表如下：状态转移方程：s3=s2–x29第一阶段：给第一市场分配由边界条件s1=9，第一阶段最优决策表如下：x1s10123456789x1*f1*92112132182172152082062022012002218得决策过程：x1*=2,x2*=0,x3*=7,f1*=218即市场1分配2人，市场2不分配，市场3分配7人，最大收益为218万元。状态转移方程：s2=s1–x110在资源分配问题中，还有一类要考虑资源回收利用问题，这里决策变量为连续值，故称为资源连续分配问题。这类问题一般描述如下：设有数量为s1的某种资源，可投入A和B两种生产。第一年若以数量u1投入生产A，剩下的量s1-u1就投入生产B，则可得收入为g(u1)+h(s1-u1)，其中g(u1)和h(u1)为已知函数，且g(0)=h(0)=0。这种资源在投入生产A、B后，年终还可回收再投入生产。设年回收率分别为0a1和0b1，则在第一年生产后，回收的资源量合计为s2=au1+b(s1-u1)。第二年再将资源数量s2按u2和s2-u2分别投入A、B两种生产，如此继续n年，试问：应当如何决定每年投入A生产的资源量u1，u2，…，un，才能使总收入最大？三、连续的一维资源分配问题1.问题的提出112.基本模型nisuusbaususbaususbausushugushugMaxZiinnnnnnn,,2,10)()()()}()()()({1222311121113.求解方法设状态变量sk表示第k阶段可投入A和B两种生产的资源量；决策变量uk表示第k阶段可投入A生产的资源量，则sk－uk为可投入B生产的资源量。已知s1，可用逆推法求解。12状态转移方程：)(1kkkkusbaus令最优值函数fk(sk)表示以数量为sk的资源量分配给第k阶段至第n阶段所得到的最大总收入。递推关系式为：1,2,,1,0)()]}([)()({max)(1110nnksfusbaufushugsfnnkkkkkkksukkkk最后求得最大总收入为f1(s1)。13例2机器负荷分配问题解：设状态变量sk表示第k年度初拥有的完好机器数量，同时表示第k－1年度末拥有的完好机器数量。设决策变量uk表示第k年度中分配高负荷下生产的机器数量，则sk－uk为该年度中分配低负荷下生产的机器数量。状态转移方程：)(9.07.0)(1kkkkkkkusuusbaus允许决策集合：}0|{)(kkkkkksxuusD141,2,,50)()]}(9.07.0[)(58{max)(661)(ksfusufususfkkkkkkksDukkkkk515,1),(kkkkusvV令最优值函数fk(sk)表示以资源量sk出发，从第k年开始至第5年结束时，生产的产品最大值。递推关系式为：设vk(sk,uk)为第k年度的产量，则vk＝8uk＋5(sk－uk)故指标函数为：15当k=5时，有}53{max)}(58{max)]}(9.07.0[)(58{max)(55055505556555055555555suusuusufususfsususu求得最大解：5555*58)(,ssfsu相应的，有4444*46.13)(,ssfsu3333*35.17)(,ssfsu222*28.20)(,0ssfu111*17.23)(,0ssfu因10001s，故最高产量为23700)(11sf（台）16第二节生产与存贮问题设某公司要制定一项n个阶段的生产计划。已知初始库存为零，每阶段该产品的生产量有上限的限制；每阶段社会对该产品的需求量是已知的，在n阶段末库存为零。问该公司如何制定每个阶段的生产计划，使产品总成本最低。一、生产计划问题1.问题的提出设dk为第k阶段对产品的需求量，xk为第k阶段该产品的生产量，sk＋1为k阶段末的产品库存量。则有sk＋1＝sk＋xk－dk由此可见，过程演化方向由s1至sn＋1。2.基本模型17设ck(xk)表示第k阶段生产量xk的成本费用，它包括生产准备成本K和产品成本a·xk(a是单位产品成本)两项费用，hk(sk)为第k阶段开始时有产品库存量sk所需的存贮费用。故k阶段的成本费用为ck(xk)＋hk(sk)。m表示每阶段最多能生产该产品的上限数。因而，上述问题的模型为nkxnkmxnkdxssstsshxcMinGkkkjjjknnkkkkk,,2,1,,2,101,,2,1)(0,0..)]()([11111为整数18nnkdxsskkkk,1,,2,11根据动态规划求解规则，采用逆推法，递推关系式：1,,1,)]()()([min)(1121nnksfshxcsfkkkkkkxkkkkk边界条件为：0)(11nnsf用动态规划方法求解如下：由于过程演化方向由s1至sn＋1，则其状态转移方程：问题的关键是确定sk和xk的取值范围。从边界条件出发，利用这个递推关系式进行计算，对每个k计算fk(sk)的值，最后求得f1(0)即为所求最小总费用。19xk的取值范围：sk的取值范围：下限为0；上限为)0,min(1knkjjdmdm－dk－1表示k－1阶段生产时的最大库存量，如果不生产则库存量更小。这是由生产与存贮问题的特性决定的，即k－1阶段进行生产的条件是该阶段初的库存一定为零，而一旦进行生产则尽可能按最大生产能力生产。:1k下限0)1(kxkkkkkkksdxdxss0)2(1由),0max(1kkksd20:2k上限mxk)1(kkkkkkkkkkkdssxsdsdxss111max)2(达最大时不变的情况下，当、在知：由＋)max,min(12kkkkdssm21例3某工厂生产某种产品的月生产能力为6件，已知今后四个月的每批产品的固定成本和单位产品成本分别为3千元、1千元。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为0.5千元，试安排月生产计划并做到：1、保证满足每月的销售量，并规定计划期初和期末库存为零；2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。3.实例月份阶段k月销售量dk月初库存sk月末库存sk+1112s1＝0s2223s2s3332s3s4444s4s5＝022设xk为第k阶段生产量，则有k阶段生产成本：6601300)(kkkkkkxxxxxck阶段存贮成本：kkkssh5.0)(则k阶段总成本：)()(kkkkshxc4,3,2,11kdxsskkkk状态转移方程：采用逆推法，递推关系式：1,2,3,4)]()()([min)(1121ksfshxcsfkkkkkkxkkkkk边界条件为：0)(55sf23k=44)26,4min(),min(344dmdjjs4的上限：所以，s4[0,4]。x4的取值范围：)4,0max(),0max(44414ssd)4,6min()max,min(444524sdssm44044xs当33144xs当22244xs当11344xs当00444xs当24)]4()()([min)(44544444424414xsfshxcsfxx4s401234x4*f4(s4)07.047.016.536.526.026.035.515.542.002.025k=33)36,6min(),min(243dmdjjs3的上限：所以，s3[0,3]。x3的取值范围：)2,0max(),0max(33313ssd)6,6min()max,min(333423sdssm62033xs当51133xs当40233xs当30333xs当26)]2()()([min)(33433333323313xsfshxcsfxx3s30123456x3*f3(s3)012.012.513.013.511.0611.0111.512.012.513.010.5510.528.011.512.012.510.008.038.011.512.09.508.027k=24)26,9min(),min(142dmdjjs2的上限：所以，s2[0,4]。x2的取值范围：)3,0max(),0max(22212ssd)6,6min()max,min(222322sdssm63022xs当52122xs当41222xs当30322xs当20422xs当28)]3()()([min)(22322222222212xsfshxcsfxx2s20123456x2*f2(s2)017.017.516.017.0516.0116.517.015.516.5415.5216.016.515.016.0315.5312.516.014.515.5012.5412.514.015.0012.529k=1s1＝0x1的取值范围：)2,0max(),0max(11111ssd)6,6min()max,min