运筹学动态规划应用

1、1第十章第十章 动态规划应用举例动态规划应用举例2 第一节第一节 一维资源分配问题一维资源分配问题一、一、一维资源分配问题基本模型及求解方法一维资源分配问题基本模型及求解方法1. 1. 模型模型 设有某种原料，总数量为设有某种原料，总数量为a，用于生产，用于生产n中产品。若分配数中产品。若分配数量量xi用于生产第用于生产第i 种产品，其收益为种产品，其收益为gi(xi)。问应如何分配，才能。问应如何分配，才能使生产使生产n种产品的总收入最大？种产品的总收入最大？此问题可写成静态规划问题：此问题可写成静态规划问题：nixaxxxtsxgxgxgMaxZinnn, 2 , 10.)()()(212

2、211 3 在应用动态规划处理这类在应用动态规划处理这类“静态规划静态规划”问题时，通常以把问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把问题中资源分配给一个或几个使用者的过程作为一个阶段，把问题中的变量的变量xi作为决策变量，将累计的量或随递推过程变化的量选作为决策变量，将累计的量或随递推过程变化的量选为状态变量。为状态变量。 当当gi(xi)都是线性函数时，它是一个线性规划问题；当都是线性函数时，它是一个线性规划问题；当gi(xi)不是线性函数时，它是一个非线性规划问题。但当不是线性函数时，它是一个非线性规划问题。但当n较大时，较大时，具体求解是比较麻烦的。然而，由于这类

3、问题的特殊结构，可具体求解是比较麻烦的。然而，由于这类问题的特殊结构，可以将它看成一个多阶段决策问题，并利用动态规划的递推关系以将它看成一个多阶段决策问题，并利用动态规划的递推关系来解。来解。42. 求解方法求解方法 设状态变量设状态变量sk表示分配用于生产第表示分配用于生产第k种产品至第种产品至第n产品的产品的原料数量。则原料数量。则s1 =a，可用逆推法求解。，可用逆推法求解。 设决策变量设决策变量uk表示分配给生产第表示分配给生产第k种产品的原料数量，种产品的原料数量，即即: uk = xk状态转移方程：状态转移方程：kkkkkxsuss 1允许决策集合：允许决策集合：0|)(kkkkk

4、ksxuusD 把该分配问题看成是对资源总量的消耗过程。把该分配问题看成是对资源总量的消耗过程。5 令最优值函数令最优值函数fk(sk)表示以数量为表示以数量为sk的原料分配给第的原料分配给第k种产品种产品至第至第n种产品所得到的最大总收入。递推关系式为：种产品所得到的最大总收入。递推关系式为：0)(1 , 1,)()(max)(1110 nnkkkkksxkksfnnkxsfxgsfkk利用这个递推关系式进行逐段计算，最后求得最大总收入为利用这个递推关系式进行逐段计算，最后求得最大总收入为f1(a)6例例1 某公司有某公司有9个推销员在全国三个不同市场推销货个推销员在全国三个不同市场推销货物

5、，这三个市场里推销人员数与收益的关系如下表，物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案试作出使总收益最大的分配方案。 31,11)(max)(321iixxxxdsf解：设分配人员的顺序为市场解：设分配人员的顺序为市场1, 2, 3，已知已知 s1=9，用逆推法。，用逆推法。 设设 sk 为第为第k阶段尚未分配的人员数，阶段尚未分配的人员数， xk 为第为第k阶段分配的推阶段分配的推销人员数。则销人员数。则状态转移方程为状态转移方程为 sk1=sk xk 目标函数为目标函数为 推推销销员员市市场场012345678912032475766718290100 11

6、02405060718293104 115 125 13535061728497109 120 131 140 150二、离散的二、离散的一维资源分配问题一维资源分配问题7第三阶段：给第三市场分配第三阶段：给第三市场分配 s3 有有09种可能，第三阶段最优决策表如下种可能，第三阶段最优决策表如下： x3 s3 0 1 2 3 4 5 6 7 8 9 x3* f3* 0 50 0 50 1 50 61 1 61 2 50 61 72 2 72 3 50 61 72 84 3 84 4 50 61 72 84 97 4 97 5 50 61 72 84 97 109 5 109 6 50 61 7

7、2 84 97 109 120 6 120 7 50 61 72 84 97 109 120 131 7 131 8 50 61 72 84 97 109 120 131 140 8 140 9 50 61 72 84 97 109 120 131 140 150 9 150 8第二阶段：给第二市场分配第二阶段：给第二市场分配 s2 有有09种可能，第二阶段最优决策表如下种可能，第二阶段最优决策表如下： x2 s2 0 1 2 3 4 5 6 7 8 9 x2* f2* 0 90 0 90 1 101 100 0 101 2 112 111 110 0 112 3 124 122 121 12

8、1 0 124 4 137 134 132 132 132 0 137 5 149 147 144 143 143 143 0 149 6 160 159 157 155 154 154 154 0 160 7 171 170 169 168 166 165 165 165 0 171 8 180 181 180 180 179 177 176 176 175 1 181 9 190 190 191 191 191 190 188 187 186 185 2,3,4 191 s3 9 8 7 6 5 4 3 2 1 0 s3 0 1 2 3 4 5 6 7 8 9 x3* 0 1 2 3 4

9、5 6 7 8 9 f3* 50 61 72 84 97 109 120 131 140 150 状态转移方程：状态转移方程： s3=s2 x29 第一阶段：给第一市场分配第一阶段：给第一市场分配 由边界条件由边界条件 s1=9，第一阶段最优决策表如下，第一阶段最优决策表如下： x1 s1 0 1 2 3 4 5 6 7 8 9 x1* f1* 9 211 213 218 217 215 208 206 202 201 200 2 218 s20123456789x2*0000000012,3,4f2*90 101 112 124 137 149 160 171 181191得决策过程：得决策

10、过程：x1*=2, x2*=0, x3*=7, f1*=218即即 市场市场1 分配分配 2人，市场人，市场2 不分配不分配 ，市场，市场3 分配分配 7人，人，最大收益为最大收益为218万元。万元。状态转移方程：状态转移方程： s2=s1 x110三、连续的三、连续的一维资源分配问题一维资源分配问题1. 问题的提出问题的提出 在资源分配问题中，还有一类要考虑资源回收利用问题，这里在资源分配问题中，还有一类要考虑资源回收利用问题，这里决策变量为连续值，故称为资源连续分配问题。这类问题一般描决策变量为连续值，故称为资源连续分配问题。这类问题一般描述如下：述如下： 设有数量为设有数量为s1的某种资

11、源，可投入的某种资源，可投入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)。 第二年再将资源数量第二年再将资源数量

12、s2按按u2和和s2-u2分别投入分别投入A、B两种生产，如两种生产，如此继续此继续n年，试问：应当如何决定每年投入年，试问：应当如何决定每年投入A生产的资源量生产的资源量u1，u2，un，才能使总收入最大？，才能使总收入最大？ 112. 基本模型基本模型nisuusbaususbaususbausushugushugMaxZiinnnnnnn, 2 , 10)()()()()()()(122231112111 3. 求解方法求解方法设状态变量设状态变量sk表示第表示第k阶段可投入阶段可投入A和和B两种生产的资源量；两种生产的资源量；决策变量决策变量uk表示第表示第k阶段可投入阶段可投入A生产

13、的资源量，则生产的资源量，则sk uk为可投为可投入入B生产的资源量。生产的资源量。已知已知 s1，可用逆推法求解。，可用逆推法求解。 12状态转移方程：状态转移方程：)(1kkkkusbaus 令最优值函数令最优值函数fk(sk)表示以数量为表示以数量为sk的资源量分配给第的资源量分配给第k阶段至第阶段至第n阶段所得到的最大总收入。阶段所得到的最大总收入。递推关系式为：递推关系式为：1 ,2,1,0)()()()(max)(1110 nnksfusbaufushugsfnnkkkkkkksukkkk最后求得最大总收入为最后求得最大总收入为f1(s1)。13例例2 机器负荷分配问题机器负荷分配

14、问题(书书P253)解解：设状态变量设状态变量sk表示第表示第k年度初拥有的完好机器数量，同时表年度初拥有的完好机器数量，同时表示第示第k1年度末拥有的完好机器数量。年度末拥有的完好机器数量。设决策变量设决策变量uk表示第表示第k年度中分配高负荷下生产的机器数年度中分配高负荷下生产的机器数量，则量，则sk uk为该年度中分配低负荷下生产的机器数量。为该年度中分配低负荷下生产的机器数量。状态转移方程：状态转移方程：)( 9 . 07 . 0)(1kkkkkkkusuusbaus 允许决策集合：允许决策集合：0|)(kkkkkksxuusD 141 ,2,50)()(9.07.0)(58max)(

15、661)( ksfusufususfkkkkkkksDukkkkk 515, 1),(kkkkusvV令最优值函数令最优值函数fk(sk)表示以资源量表示以资源量sk出发，从第出发，从第k年开始至第年开始至第5年结年结束时，生产的产品最大值。递推关系式为：束时，生产的产品最大值。递推关系式为：设设vk(sk , uk)为第为第k年度的产量，则年度的产量，则vk 8 uk 5(sk uk)故指标函数为：故指标函数为：15当当k=5时，有时，有53max)(58max)(9.07.0)(58max)(55055505556555055555555suusuusufususfsususu 求得最大解

16、：求得最大解：5555*58)(,ssfsu 相应的，有相应的，有4444*46 .13)(,ssfsu 3333*35 .17)(,ssfsu 222*28 .20)(, 0ssfu 111*17 .23)(, 0ssfu 因因10001 s，故最高产量为，故最高产量为23700)(11 sf（台）（台）补充作业补充作业14 若计划期结束时完好的机器台数为若计划期结束时完好的机器台数为500台，应台，应如何安排生产使产量最大？如何安排生产使产量最大？16 第二节第二节 生产与存贮问题生产与存贮问题一、一、生产计划问题生产计划问题1. 问题的提出问题的提出 设某公司要制定一设某公司要制定一项项

17、n个阶段的生产计划。已知初始库存个阶段的生产计划。已知初始库存为零，每阶段该产品的生产量有上限的限制；每阶段社会对为零，每阶段该产品的生产量有上限的限制；每阶段社会对该产品的需求量是已知的，在该产品的需求量是已知的，在n阶段末库存为零。问该公司阶段末库存为零。问该公司如何制定每个阶段的生产计划，使产品总成本最低。如何制定每个阶段的生产计划，使产品总成本最低。设设dk为第为第k阶段对产品的需求量，阶段对产品的需求量，xk为第为第k阶段该产品的阶段该产品的生产量，生产量，sk1为为k阶段末的产品库存量。则有阶段末的产品库存量。则有 sk1 sk xk dk由此可见，过程演化方向由由此可见，过程演化

18、方向由s1至至 sn1 。2. 基本模型基本模型17 设设ck(xk)表示第表示第k阶段生产量阶段生产量xk的成本费用，它包括生产准备的成本费用，它包括生产准备成本成本K和产品成本和产品成本axk(a是单位产品成本是单位产品成本)两项费用两项费用 ，hk(sk )为第为第k阶段开始时有产品库存量阶段开始时有产品库存量sk 所需的存贮费用。故所需的存贮费用。故k阶段的成本阶段的成本费用为费用为ck(xk) hk(sk)。m表示每阶段最多能生产该产品的上限数表示每阶段最多能生产该产品的上限数量。量。因而，上述问题的模型为因而，上述问题的模型为nkxnkmxnkdxssstsshxcMinGkkkj

19、jjknnkkkkk,2 , 1,2 , 101,2 , 1)(0,0.)()(11111 为为整整数数18nnkdxsskkkk, 1, 2 , 11 根据动态规划求解规则，采用逆推法，递推关系式：根据动态规划求解规则，采用逆推法，递推关系式：1 ,1,)()()(min)(1121 nnksfshxcsfkkkkkkxkkkkk 边界条件为：边界条件为：0)(11 nnsf用动态规划方法求解如下：用动态规划方法求解如下：由于过程演化方向由由于过程演化方向由s1至至 sn1 ，则其状态转移方程：，则其状态转移方程：问题的关键是确定问题的关键是确定 sk 和和 xk 的取值范围。的取值范围。

20、从边界条件出发，利用这个递推关系式进行计算，对每个从边界条件出发，利用这个递推关系式进行计算，对每个k计计算算fk(sk) 的值，最后求得的值，最后求得f1(0)即为所求最小总费用。即为所求最小总费用。19xk 的取值范围的取值范围：sk 的取值范围的取值范围：下限为：下限为0；上限为；上限为)0,min(1 knkjjdmdmdk 1 表示表示k1阶段生产时的最大库存量，如果不生产则阶段生产时的最大库存量，如果不生产则库存量更小。这是由生产与存贮问题的特性决定的，即库存量更小。这是由生产与存贮问题的特性决定的，即k1阶段进行生产的条件是该阶段初的库存一定为零，而一旦进阶段进行生产的条件是该阶

21、段初的库存一定为零，而一旦进行生产则尽可能按最大生产能力生产。行生产则尽可能按最大生产能力生产。:1k 下下限限0)1( kxkkkkkkksdxdxss 0)2(1由由), 0max(1kkksd 20:2k 上上限限mxk )1(kkkkkkkkkkkdssxsdsdxss 111max)2(达达最最大大时时不不变变的的情情况况下下，当当、在在知知：由由)max,min(12kkkkdssm 21例例3 某工厂生产某种产品的月生产能力为某工厂生产某种产品的月生产能力为6件，已知今后四个月的件，已知今后四个月的每批产品的固定成本和单位产品成本分别为每批产品的固定成本和单位产品成本分别为3千元

22、、千元、1千元。如果本千元。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为月存储费为0.5千元，试安排月生产计划并做到：千元，试安排月生产计划并做到： 1、保证满足每月的销售量，并规定计划期初和期末库存为零；、保证满足每月的销售量，并规定计划期初和期末库存为零； 2、在生产能力允许范围内，安排每月生产量计划使产品总成本、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费即生产费用加存储费)最低。最低。3. 实例实例(P263 例例3)月份月份阶段阶段k月销售量月销售量dk月初库存月初库存

23、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

24、=4 4)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=3 3)36 , 6min(),min(

25、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

26、.027k=2 4)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.0

27、16.0315.5312.516.014.515.5012.5412.514.015.0012.529k=1 s10 x1的取值范围：的取值范围： )2 , 0max(), 0max(11111ssd )6 , 6min()max,min(111221sdssm 62021 xs)2()()(min)(11211111121111 xsfshxcsfx x1s123456x1*f1(s1)021.021.522.020.521.5520.5逆计算过程反推得：逆计算过程反推得：x1* =5, x2* =0 , x3* =6, x4* =0这类库存问题的特征：这类库存问题的特征：si xi =03

28、0二、二、不确定性采购问题不确定性采购问题例例4 (P269 例例6) 某工厂生产上需要在近五周内采购一批原料，某工厂生产上需要在近五周内采购一批原料，而估计在未来五周内价格有波动，其浮动价格和概率已测得如而估计在未来五周内价格有波动，其浮动价格和概率已测得如下表。试求在哪一周以什么价格购入，使其价格的数学期望值下表。试求在哪一周以什么价格购入，使其价格的数学期望值最小，并求出期望值。最小，并求出期望值。解解: 这里价格是一个随机变量，是按某种已知的概率分这里价格是一个随机变量，是按某种已知的概率分布取值的。按采购期限布取值的。按采购期限5周分为周分为5个阶段，将每周的价格个阶段，将每周的价格

29、看作该阶段的状态。看作该阶段的状态。31yk为状态变量，表示第为状态变量，表示第k周的实际价格。周的实际价格。xk为决策变量，当为决策变量，当xk1表示表示第第k周采购，当周采购，当xk0，不采购。，不采购。ykE表示第表示第k周决定等待，而在以后采取最优决策时采购价格的周决定等待，而在以后采取最优决策时采购价格的期望值。期望值。 fk(yk)表示第表示第k周实际价格为周实际价格为yk时，从第时，从第k周到第周到第5周最优决策的周最优决策的期望值。期望值。 逆序递推关系为：逆序递推关系为：kEkkkkkkkkkkkkkEkkkkEkkkyyfxyyfxfffyEfykSSyyyfSyyyyf )(0)(1)700(4 . 0)600(3 . 0)500(3 . 0)(5 , 2 , 1700,600,500)(,min)(1111155555（不采购）（不采购）（采购）（采购）(1)32从最后一周，向前递推：从最后一周，向前递推：k=5时，因时，因700)700(,600)600(,500)500(,)(55555555 fffSyyyf即在第五周，若所需的原料尚未买入，无论价格多少，都必须采购。即在第五周，若所需的原料尚未买入，无论价格多少