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

1、1 1第九章第九章动态规划应用举例动态规划应用举例(Duality Theory)1 一维资源分配问题一维资源分配问题2 生产与存贮问题生产与存贮问题3 背包问题背包问题4 设备更新问题设备更新问题5 货郎担问题货郎担问题2 2 第一节第一节 一维资源分配问题一维资源分配问题一、一、一维资源分配问题基本模型及求解方法一维资源分配问题基本模型及求解方法1. 1. 模型模型 设有某种原料，总数量为设有某种原料，总数量为a，用于生产，用于生产n种产品。若分配数种产品。若分配数量量xi用于生产第用于生产第i 种产品，其收益为种产品，其收益为gi(xi)。问应如何分配，才能。问应如何分配，才能使生产使生

2、产n种产品的总收入最大？种产品的总收入最大？此问题可写成静态规划问题：此问题可写成静态规划问题：nixaxxxtsxgxgxgMaxZinnn, 2 , 10.)()()(212211 3 3 在应用动态规划处理这类在应用动态规划处理这类“静态规划静态规划”问题时，通常以把问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把问题中资源分配给一个或几个使用者的过程作为一个阶段，把问题中的变量的变量xi作为决策变量，将累计的量或随递推过程变化的量选作为决策变量，将累计的量或随递推过程变化的量选为状态变量。为状态变量。 当当gi(xi)都是线性函数时，它是一个线性规划问题；当都是线性函数

3、时，它是一个线性规划问题；当gi(xi)不是线性函数时，它是一个非线性规划问题。但当不是线性函数时，它是一个非线性规划问题。但当n较大时，较大时，具体求解是比较麻烦的。然而，由于这类问题的特殊结构，可具体求解是比较麻烦的。然而，由于这类问题的特殊结构，可以将它看成一个多阶段决策问题，并利用动态规划得递推关系以将它看成一个多阶段决策问题，并利用动态规划得递推关系来解。来解。4 42. 求解方法求解方法 设状态变量设状态变量sk表示分配用于生产第表示分配用于生产第k种产品至第种产品至第n产品的产品的原料数量。则原料数量。则s1 =a，可用逆推法求解。，可用逆推法求解。 设决策变量设决策变量uk表示

4、分配给生产第表示分配给生产第k种产品的原料数量，种产品的原料数量，即即: uk = xk状态转移方程：状态转移方程：kkkkkxsuss 1允许决策集合：允许决策集合：0|)(kkkkkksxuusD 把该分配问题看成是对资源总量的消耗过程。把该分配问题看成是对资源总量的消耗过程。5 5 令最优值函数令最优值函数fk(sk)表示以数量为表示以数量为sk的原料分配给第的原料分配给第k种产品种产品至第至第n种产品所得到的最大总收入。递推关系式为：种产品所得到的最大总收入。递推关系式为：0)(1 , 1,)()(max)(1110 nnkkkkksxkksfnnkxsfxgsfkk利用这个递推关系式

5、进行逐段计算，最后求得最大总收入为利用这个递推关系式进行逐段计算，最后求得最大总收入为f1(a)6 6例例1 1 某公司有某公司有9个推销员在全国三个不同市场推销货个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。试作出使总收益最大的分配方案。 31,11)(max)(321iixxxxdsf解：设分配人员的顺序为市场解：设分配人员的顺序为市场1, 2, 3，已知已知 s1=9，用逆推法。，用逆推法。 设设 sk 为第为第k阶段尚未分配的人员数，阶段尚未分配的人员数， xk 为第为第k阶段分

6、配的推阶段分配的推销人员数。则销人员数。则状态转移方程为状态转移方程为 sk1=sk xk 目标函数为目标函数为 推推销销员员市市场场012345678912032475766718290100 1102405060718293104 115 125 13535061728497109 120 131 140 150二、离散的二、离散的一维资源分配问题一维资源分配问题7 7第三阶段：给第三市场分配第三阶段：给第三市场分配 s3 有有09种可能，第三阶段最优决策表如下：种可能，第三阶段最优决策表如下： x3 s3 0 1 2 3 4 5 6 7 8 9 x3* f3* 0 50 0 50 1 5

7、0 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 72 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 8第二阶段：给第二市场分配第二阶段：给第二市场分配 s2 有有09种可能，第二阶段最优决策表如下：种可能，第二阶

8、段最优决策表如下： 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 121 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

9、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 5 6 7 8 9 f3* 50 61 72 84 97 109 120 131 140 150 状态转移方程：状态转移方程： s3=s2 x29 9 第一阶段：给第一市场分配第一阶段：给第一市场分配 由边界条件由边界条件 s1=9，第一阶段最优决策表如下：，第一阶段最优决策表如下： x1 s1 0 1 2 3 4 5 6 7 8 9 x1* f1* 9 211 213 218 217

10、 215 208 206 202 201 200 2 218 s20123456789x2*0000000012,3,4f2*90 101 112 124 137 149 160 171 181191得决策过程：得决策过程：x1*=2, x2*=0, x3*=7, f1*=218即即 市场市场1 分配分配 2人，市场人，市场2 不分配不分配 ，市场，市场3 分配分配 7人，人，最大收益为最大收益为218万元。万元。状态转移方程：状态转移方程： s2=s1 x11010 在资源分配问题中，还有一类要考虑资源回收利用问题，这里在资源分配问题中，还有一类要考虑资源回收利用问题，这里决策变量为连续值，

11、故称为资源连续分配问题。这类问题一般描决策变量为连续值，故称为资源连续分配问题。这类问题一般描述如下：述如下： 设有数量为设有数量为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，

12、则在第一年生产后，回收的资源，则在第一年生产后，回收的资源量合计为量合计为s2=au1+b(s1-u1)。 第二年再将资源数量第二年再将资源数量s2按按u2和和s2-u2分别投入分别投入A、B两种生产，如两种生产，如此继续此继续n年，试问：应当如何决定每年投入年，试问：应当如何决定每年投入A生产的资源量生产的资源量u1，u2，un，才能使总收入最大？，才能使总收入最大？ 三、连续的三、连续的一维资源分配问题一维资源分配问题1. 问题的提出问题的提出11112. 基本模型基本模型nisuusbaususbaususbausushugushugMaxZiinnnnnnn, 2 , 10)()()(

13、)()()()(122231112111 3. 求解方法求解方法设状态变量设状态变量sk表示第表示第k阶段可投入阶段可投入A和和B两种生产的资源量；两种生产的资源量；决策变量决策变量uk表示第表示第k阶段可投入阶段可投入A生产的资源量，则生产的资源量，则sk uk为可投为可投入入B生产的资源量。生产的资源量。已知已知 s1，可用逆推法求解。，可用逆推法求解。 1212状态转移方程：状态转移方程：)(1kkkkusbaus 令最优值函数令最优值函数fk(sk)表示以数量为表示以数量为sk的资源量分配给第的资源量分配给第k阶段至第阶段至第n阶段所得到的最大总收入。阶段所得到的最大总收入。递推关系式

14、为：递推关系式为：1 ,2,1,0)()()()(max)(1110 nnksfusbaufushugsfnnkkkkkkksukkkk最后求得最大总收入为最后求得最大总收入为f1(s1)。1313例例2 2 机器负荷分配问题机器负荷分配问题解解：设状态变量设状态变量sk表示第表示第k年度初拥有的完好机器数量，同时表年度初拥有的完好机器数量，同时表示第示第k1年度末拥有的完好机器数量。年度末拥有的完好机器数量。设决策变量设决策变量uk表示第表示第k年度中分配高负荷下生产的机器数年度中分配高负荷下生产的机器数量，则量，则sk uk为该年度中分配低负荷下生产的机器数量。为该年度中分配低负荷下生产的

15、机器数量。状态转移方程：状态转移方程：)( 9 . 07 . 0)(1kkkkkkkusuusbaus 允许决策集合：允许决策集合：0|)(kkkkkksxuusD 14141 , 2 , 50)()(9 . 07 . 0)(58max)(661)( ksfusufususfkkkkkkksDukkkkk 515, 1),(kkkkusvV令最优值函数令最优值函数fk(sk)表示以资源量表示以资源量sk出发，从第出发，从第k年开始至第年开始至第5年结年结束时，生产的产品最大值。递推关系式为：束时，生产的产品最大值。递推关系式为：设设vk(sk , uk)为第为第k年度的产量，则年度的产量，则v

16、k 8 uk 5(sk uk)故指标函数为：故指标函数为：1515当当k=5时，有时，有53max)(58max)(9 . 07 . 0)(58max)(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（台）（台）1616 第二节第二节 生产与存贮问题生

17、产与存贮问题 设某公司要制定一项设某公司要制定一项n个阶段的生产计划。已知初始库存个阶段的生产计划。已知初始库存为零，每阶段该产品的生产量有上限的限制；每阶段社会对为零，每阶段该产品的生产量有上限的限制；每阶段社会对该产品的需求量是已知的，在该产品的需求量是已知的，在n阶段末库存为零。问该公司阶段末库存为零。问该公司如何制定每个阶段的生产计划，使产品总成本最低。如何制定每个阶段的生产计划，使产品总成本最低。一、一、生产计划问题生产计划问题1. 问题的提出问题的提出设设dk为第为第k阶段对产品的需求量，阶段对产品的需求量，xk为第为第k阶段该产品的阶段该产品的生产量，生产量，sk1为为k阶段末的

18、产品库存量。则有阶段末的产品库存量。则有 sk1 sk xk dk由此可见，过程演化方向由由此可见，过程演化方向由s1至至 sn1 。2. 基本模型基本模型1717 设设ck(xk)表示第表示第k阶段生产量阶段生产量xk的成本费用，它包括生产准备的成本费用，它包括生产准备成本成本K和产品成本和产品成本axk(a是单位产品成本是单位产品成本)两项费用两项费用 ，hk(sk )为第为第k阶段开始时有产品库存量阶段开始时有产品库存量sk 所需的存贮费用。故所需的存贮费用。故k阶段的成本阶段的成本费用为费用为ck(xk) hk(sk)。m表示每阶段最多能生产该产品的上限数表示每阶段最多能生产该产品的上

19、限数。因而，上述问题的模型为因而，上述问题的模型为nkxnkmxnkdxssstsshxcMinGkkkjjjknnkkkkk,2 , 1,2 , 101,2 , 1)(0,0.)()(11111 为为整整数数1818nnkdxsskkkk, 1, 2 , 11 根据动态规划求解规则，采用逆推法，递推关系式：根据动态规划求解规则，采用逆推法，递推关系式：1 ,1,)()()(min)(1121 nnksfshxcsfkkkkkkxkkkkk 边界条件为：边界条件为：0)(11 nnsf用动态规划方法求解如下：用动态规划方法求解如下：由于过程演化方向由由于过程演化方向由s1至至 sn1 ，则其状

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

21、由生产与存贮问题的特性决定的，即k1阶段进行生产的条件是该阶段初的库存一定为零，而一旦进阶段进行生产的条件是该阶段初的库存一定为零，而一旦进行生产则尽可能按最大生产能力生产。行生产则尽可能按最大生产能力生产。:1k 下下限限0)1( kxkkkkkkksdxdxss 0)2(1由由), 0max(1kkksd 2020:2k 上上限限mxk )1(kkkkkkkkkkkdssxsdsdxss 111max)2(达达最最大大时时不不变变的的情情况况下下，当当、在在知知：由由)max,min(12kkkkdssm 2121例例3 某工厂生产某种产品的月生产能力为某工厂生产某种产品的月生产能力为6件

22、，已知今后四个月的件，已知今后四个月的每批产品的固定成本和单位产品成本分别为每批产品的固定成本和单位产品成本分别为3千元、千元、1千元。如果千元。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为品的月存储费为0.5千元，试安排月生产计划并做到：千元，试安排月生产计划并做到： 1、保证满足每月的销售量，并规定计划期初和期末库存为零；、保证满足每月的销售量，并规定计划期初和期末库存为零； 2、在生产能力允许范围内，安排每月生产量计划使产品总成、在生产能力允许范围内，安排每月生产量计划使产品总成本本(即生产费用加存储费

23、即生产费用加存储费)最低。最低。3. 实例实例月份阶段k月销售量dk月初库存sk月末库存sk+1112s1 0s2223s2s3332s3s4444s4s5 02222设设xk为第为第k阶段生产量，则有阶段生产量，则有k阶段生产成本：阶段生产成本： 6601300)(kkkkkkxxxxxck阶段存贮成本：阶段存贮成本： kkkssh5 . 0)( 则则k阶段总成本：阶段总成本： )()(kkkkshxc 4 , 3 , 2 , 11 kdxsskkkk状态转移方程：状态转移方程：采用逆推法，递推关系式：采用逆推法，递推关系式：1 ,2,3,4)()()(min)(1121 ksfshxcsf

24、kkkkkkxkkkkk 边界条件为：边界条件为：0)(55 sf2323k=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当当2424)4()()(min)(44544444424414 xsfshxcsfx x4s401234x4*f4(s4)07.047.016.536.526.026.0

25、35.515.542.002.02525k=3 3)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当当2626)2()()(min)(33433333323313 xsfshxcsfx x3s30123456x3*f3(s3)012.012.513.013.511.0611.0111.512.012.513.010.551

26、0.528.011.512.012.510.008.038.011.512.09.508.02727k=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当当2828)3()()(min)(22322222222212 xsfshxcsfx x2s20123456x2*f2(s2)017.017.5

27、16.017.0516.0116.517.015.516.5415.5216.016.515.016.0315.5312.516.014.515.5012.5412.514.015.0012.52929k=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

28、* =0 , x3* =6, x4* =03030例例4 某工厂生产上需要在近五周内采购一批原料，而某工厂生产上需要在近五周内采购一批原料，而估计在未来五周内价格有波动，其浮动价格和概率已估计在未来五周内价格有波动，其浮动价格和概率已测得如下表。试求在那一周以什么价格购入，使其价测得如下表。试求在那一周以什么价格购入，使其价格的数学期望值最小，并求出期望值。格的数学期望值最小，并求出期望值。二、二、不确定性采购问题不确定性采购问题单单 价价 概概 率率 500 0.3 600 0.3 700 0.4 解解: 这里价格是一个随机变量，是按某种已知的概率分这里价格是一个随机变量，是按某种已知的概率

29、分布取值的。按采购期限布取值的。按采购期限5周分为周分为5个阶段，将每周的价格个阶段，将每周的价格看作该阶段的状态。看作该阶段的状态。3131yk为状态变量，表示第为状态变量，表示第k周的实际价格。周的实际价格。xk为决策变量，当为决策变量，当xk1表示第表示第k周采购，当周采购，当xk0，不采购。，不采购。ykE表示第表示第k周决定等待，而在以后采取最优决策时采购价格的周决定等待，而在以后采取最优决策时采购价格的期望值。期望值。 fk(yk)表示第表示第k周实际价格为周实际价格为yk时，从第时，从第k周到第周到第5周最优决策的周最优决策的期望值。期望值。 逆序递推关系为：逆序递推关系为：kE

30、kkkkkkkkkkkkkEkkkkkEkkkyyfxyyfxfffyEfykssyyyfsyyyyf )(0)(1)700(4 . 0)600(3 . 0)500(3 . 0)(5 , 2 , 1700,600,500)(,min)(111115555（不采购）（不采购）（采购）（采购）(1)3232从最后一周，向前递推：从最后一周，向前递推：k=5时，因时，因700)700(,600)600(,500)500(,)(55555555 fffsyyyf即在第五周，若所需地原料尚未买入，无论价格多少，都必须采购。即在第五周，若所需地原料尚未买入，无论价格多少，都必须采购。k=4时，由（时，由（

31、1）式可知）式可知6107004 . 06003 . 05003 . 0)700(4 . 0)600(3 . 0)500(3 . 05554 fffyE第第4 4周的最优决策为周的最优决策为700060050014444 yxyx（不采购）（不采购）或或（采购）（采购） 700610600600500500610,min,min)(444444444444yyyyyyyfsyEsy3333 700600574500500574,min,min)(33333333333，yyyyyyfsyEsy700600050013333或或（不不采采购购）（采采购购） yxyxk=3时，由（时，由（1）式可

32、知）式可知5746104 . 06003 . 05003 . 0)700(4 . 0)600(3 . 0)500(3 . 04443 fffyE3434 7006008 .5515005008 .551,min,min)(22222222222，yyyyyyfsyEsy700600050012222或或（不不采采购购）（采采购购） yxyxk=2时，由（时，由（1）式可知）式可知8 .5515744 . 05743 . 05003 . 0)700(4 . 0)600(3 . 0)500(3 . 03332 fffyE3535 70060026.53650050026.536,min,min)(

33、11111111111，yyyyyyfsyEsy700600050011111或或（不不采采购购）（采采购购） yxyx由上可知，最优策略为：在第一、二、三周时，若价格为由上可知，最优策略为：在第一、二、三周时，若价格为500就采购，否则等待；在第四周时，若价格为就采购，否则等待；在第四周时，若价格为500或或600就采就采购，否则等待；在第五周，无论价格多少，都必须采购。购，否则等待；在第五周，无论价格多少，都必须采购。按照该最优策略，价格的数学期望为：按照该最优策略，价格的数学期望为：k=1时，由（时，由（1）式可知）式可知26.5368 .5514 . 08 .5513 . 05003

34、. 0)700(4 . 0)600(3 . 0)500(3 . 02221 fffyE382.52526.5364 . 026.5363 . 05003 . 0 3636 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？起作用（使用价值）最大？物品物品 1 2 j n重量（公斤重量（公斤/ /件）件

35、） a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。货物装载问题、人造卫星内的物品装载问题等。第三节第三节 背包问题背包问题1. 1. 模型模型3737设设xj 为第为第j 种物品的装件数（非负整数）则问题的数学模型如下：种物品的装件数（非负整数）则问题的数学模型如下： ). 2 . 1(0max1njxaxaxcZjnijjjnjjj 且且为为整整数数用动态规划方法求解，令用动态规划方法求解，令 fx(y) = 总重量不超过

36、总重量不超过 y 公斤，包中只装有前公斤，包中只装有前k 种物品时的最大种物品时的最大使用价值。使用价值。 其中其中y 0， k 1,2, , n 。所以问题就是求所以问题就是求 fn(a) 3838其递推关系式为：其递推关系式为： nkxayfxcyfkkkkkayxkkk 2 )(max)(10其其中中当当 k=1 时，有：时，有：的的最最大大整整数数表表示示不不超超过过其其中中1111111 , )(ayayayxaycyf 3939求下面背包问题的最优解求下面背包问题的最优解 且且为为整整数数0,55231258max321321321xxxxxxxxxZ物品物品 1 2 3重量（公斤

37、）重量（公斤） 3 2 5使用价值使用价值 8 5 12解：解：a5 ，问题是求，问题是求 f3(5) )55(12max)5(323503333xfxfxax 整整数数2. 2. 一维背包问题实例一维背包问题实例4040 )1()0(223231032355032350333333333)0(12),5(0max)55(12max)55(12max)55(12max)5(xxxxxxaxffxfxxfxxfxf ，整整数数整整数数4141 5 5 )( 2)1()0(1112122, 10212250212502222222222)1(10),3(5),5(0max)25(max)25(ma

38、x)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整数整数整数整数4242 )0()0(0max)20(max)20(max)20(5max)0(1)0(121202122002120022222222ffxfxxfxxfxfxxxxxax 5 5 整数整数整数整数4343)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111 xxcfxxcfxxcfxxcf ) 1, 1(1310, 85, 8max) 1 (10),3(5),5(0max)5(212)1()0(1112222 xxffffxxx )( 4444

39、)0, 0(0)0()0(0max)0(211)0(122 xxfffx )0,1,1(13012,130max)0(12),5(0max)5(321)1()0(22333 xxxfffxx所以，最优解为所以，最优解为 X（1 . 1 . 0），），最优值为最优值为 Z = 13。4545实例（二维背包）实例（二维背包） 有一辆最大货运量为有一辆最大货运量为13t、最大容量为、最大容量为10件的卡车，用以装载件的卡车，用以装载3种货物，每种货物的单位重量及种货物，每种货物的单位重量及相应单位价值如下表所示。应如何装载可使总价值最大？相应单位价值如下表所示。应如何装载可使总价值最大？货物编号货物

40、编号i i 1 1 2 2 3 3单位重量（单位重量（t t） 1 1 3 3 6 6单位价值单位价值 c ci i 4 4 5 5 8 8解：设装载第解：设装载第i种货物的件数为种货物的件数为 （i=1,2,3），则问题可表述为），则问题可表述为 136310.321321xxxxxxts321854maxxxxz Nxixii 3 , 2 , 1, 0ix3. 3. 二维背包问题实例二维背包问题实例46461231114)(xxg 2225)(xxg 3338)(xxg 36x23x1x121xss 232xss 343xss 104 s关于件数的约束关于件数的约束:kkkxss 1关于重

41、量的约束关于重量的约束:kkkkxauu 13, 2, 1 k3, 2, 1 k134 u3436xsu 2323xuu 121xuu 基本方程式：基本方程式： 0),(3 , 2 , 1),()(max),(110111001111usfkxauxsfxgusfkkkkkkkkuxasxkkkkkkkk11 a32 a63 a4747 0),(3 , 2 , 1),()(max),(110111 ,min01111usfkxauxsfxgusfkkkkkkkkausxkkkkkkk1231114)(xxg 2225)(xxg 3338)(xxg 36x23x1x121xss 232xss 3

42、43xss 104 s134 u3436xsu 2323xuu 121xuu 11 a32 a63 a4848问题就是求：问题就是求：)613,10()(max)13,10(),(332331360100344333xxfxgfusfxx )613,10()(max33233613 ,10min, 1 , 03xxfxgx )613,10(8max33232, 1 , 03xxfxx 1231114)(xxg 2225)(xxg 3338)(xxg 36x23x1x121xss 232xss 343xss 104 s134 u3436xsu 2323xuu 121xuu 11 a32 a63

43、a4949)613,10(8max33232, 1 , 03xxfxx )1 , 8(16),7 , 9(8),13,10(0max222fff ),()(max),(221223003323232usfxgusfuxsx )3,()(max23231223 ,min, 1 , 0332xuxsfxgusx )313,10(5max)13,10(2212313 ,10min, 1 , 022xxfxfx )313,10(5max22124 , 1 , 02xxfxx 5050)1 , 6(20),4 , 7(15),7 , 8(10),10, 9(5),13,10(max11111fffff

44、)37 ,9(5max)7 , 9(221237 , 9min, 1 , 022xxfxfx )37 ,9(5max22122, 1 , 02xxfxx )1 , 7(10),4 , 8(5),7 , 9(max111fff )31 ,8(5max)1 , 8(221231 , 8min, 1 , 022xxfxfx )31 ,8(5max221202xxfxx )1 , 8(0max1f 5151),()(max),(11011,min0221221usfxgusfusx 4max1,min0221xusx ),13,10(1f),10,9(1f),7 ,8(1f),4 ,7(1f),1 ,

45、6(1f),7 ,9(1f),4 ,8(1f),1 ,7(1f).1 ,8(1f)13,10(1f4max113,10min01xx 4max11001xx ,4040,36,32,28,24,20,16,12, 8 , 4 , 0max .101 x1231114)(xxg 2225)(xxg 3338)(xxg 36x23x1x121xss 232xss 343xss 104 s134 u3436xsu 2323xuu 121xuu 11 a32 a63 a5252同理可求得同理可求得 ,36)10,9(1 f. 91 x,28)7 ,8(1 f. 71 x,16)4 ,7(1 f. 41

46、 x,4)1 ,6(1 f. 11 x,28)7 ,9(1 f. 71 x,16)4 ,8(1 f. 41 x,4)1 ,7(1 f. 11 x,4)1 ,8(1 f. 11 x)1 , 8(16),7 , 9(8),13,10(0max)13,10(2222ffff 40)13,10(2 f,41420,1615,2810,365,40max , 12 x)1 , 7(10),4 , 8(5),7 , 9(max)7 , 9(1112ffff ,2814,21,28max . 02 x. 32 x5353,44max)1 ,8(0max)1 ,8(12 ff. 02 x)1 , 8(16),

47、7 , 9(8),13,10(0max)13,10(2223ffff ,41)13,10(2 f,28)7 ,9(2 f.4)1 ,8(2 f,41416,288,41max . 03 x,10010343 xss130136343 xuu,41)13,10(),(2332 fusf. 12 x, 9110232 xss.103133232 xuu. 32 x, 7310232 xss.49133232 xuu5454, 91 x, 12 x. 03 x所以最优决策方案为所以最优决策方案为 ：最优装载价值为：最优装载价值为：.41max z,36)10,9(),(1221 fusf. 91 x

48、 10922us 4722us,16)4 ,7(),(1221 fusf. 41 x, 41 x, 32 x. 03 x)854(max321xxxz 5555 排序问题指排序问题指n 种零件经过不同设备加工是的顺序问题。其目的是种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。使加工周期为最短。 1、n 1 排序问题排序问题 即即n 种零件经过种零件经过1 种设备进行加工，如何安排？种设备进行加工，如何安排？14682023交货日期（交货日期（d）45173加工时间（加工时间（t）零件代号零件代号2j1j3j4j5j例例1、 第五节第五节 排序问题排序问题5656 （1）平均通过

49、设备的时间最小）平均通过设备的时间最小 按零件加工时间非负次序排列顺序，其时间最小。（即将加工时按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可）间由小到大排列即可）1j2j3j4j5j零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间1481320 交货时间交货时间82314620 平均通过时间平均通过时间2 .9)1481320(51 x5757延迟时间延迟时间 = 13 6 = 7 （2）按时交货排列顺序）按时交货排列顺序1j2j3j4j5j零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间56101720

50、 交货时间交货时间82314620 平均通过时间平均通过时间6 .11)56101720(51 x延迟时间延迟时间 = 05858 （3）既满足交货时间，又使平均通过时间最小）既满足交货时间，又使平均通过时间最小1j2j3j4j5j零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间1691320 交货时间交货时间82314620延迟时间延迟时间 = 0 平均通过时间平均通过时间8 .9)1691320(51 x5959 2、n 2 排序问题排序问题 即即n 种零件经过种零件经过2 种设备进行加工，如何安排？种设备进行加工，如何安排？例例2、49523B53786A

51、零件零件2j1j3j4j5j设备设备ABT6060经变换为经变换为49523B53786A 零件零件2j1j3j4j5j设备设备加工顺序图如下：加工顺序图如下：ABT3j1j2j4j5j3756895432+2+2-5 加工周期加工周期 T = 3+7+5+6+8+2 = 31小小即即BAtti 6161 3、n 3 排序问题排序问题 即即n 种零件经过种零件经过 3 种设备进行加工，如何安排？种设备进行加工，如何安排？例例3、3468564683579310CBA1j2j3j4j5j6262ABCT变换变换4+36+45+86+56+48+65+37+53+910+3B + CA+B1j2j

52、3j4j5j6363排序排序4+36+45+86+56+48+65+37+53+910+3B + CA+B1j2j3j4j5j复原复原3468564683579310CBA1j2j3j4j5j6464计算计算T = 6+10+8+7+6+4+3 = 44计算依据：计算依据：ABcCBABCBAttttttttttiiiiii maxmin maxmin或或即可按下式计算即可按下式计算或或6565 企业中经常会遇到一台设备应该使用多少年更新最合算的问题。企业中经常会遇到一台设备应该使用多少年更新最合算的问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，一般来说，一台设备在比较新时，年运

53、转量大，经济收入高，故障少，维修费用少，但随着使用年限的增加，年运转量减少故障少，维修费用少，但随着使用年限的增加，年运转量减少因而收入减少，故障变多，维修费用增加。如果更新可提高年因而收入减少，故障变多，维修费用增加。如果更新可提高年净收入，但是当年要支出一笔数额较大的购买费。净收入，但是当年要支出一笔数额较大的购买费。设备更新的一般提法为：在已知一台设备的效益函数设备更新的一般提法为：在已知一台设备的效益函数 ，维，维修费用函数修费用函数 及更新费用函数及更新费用函数 条件下，要求在条件下，要求在n年内的年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使每年年初作出决策，是继续使

54、用旧设备还是更换一台新的，使n年总效益最大。年总效益最大。 )(tr)(tu)(tc第六节第六节 设备更新问题设备更新问题6666 例例1、 某台新设备的年效益及年均维修费、更新净费用如下表某台新设备的年效益及年均维修费、更新净费用如下表所示。试确定今后所示。试确定今后5年内的更新策略，使总收益最大。年内的更新策略，使总收益最大。单位：万元单位：万元)(trk)(tuk)(tck 役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.56767解：以年限划分阶段解：以年限划分阶段k：1，2，3，4，5决策变量决策变量 : kx第第k

55、年初保留使用年初保留使用(keep)第第k年初更新年初更新(replacement) RKxk状态变量状态变量 : ks第第k年初，设备已使用过的年数，称役龄。年初，设备已使用过的年数，称役龄。状态转移方程：状态转移方程： RxKxsskkkk111123)(11xg)(22xg)(33xg3x2x1x01 s12 s3s4s454x5x5s)(44xg)(55xg6s6868)(tr在第在第k年设备已使用过年设备已使用过t年（或役龄为年（或役龄为t年），再使用年），再使用1年时的效益。年时的效益。 )(tu在第在第k年设备已使用过年设备已使用过t年（或役龄为年（或役龄为t年），再使用年），再

56、使用1年年时的维修费用。时的维修费用。)(tc在第在第k年卖掉一台役龄为年卖掉一台役龄为t年的设备，买进一台新的设年的设备，买进一台新的设备的更新净费用。备的更新净费用。 )(trk)(tuk)(tck 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.56969)(trk)(tuk)(tck 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5即：即： )(tc“买一部新机器的费用买一部新机器的费用”“卖一部卖一部

57、t年役龄的旧年役龄的旧机器的收益机器的收益”。 阶段指标函数：阶段指标函数： RxscurKxsusrxgkkkkkkkkkkkk)()0()0()()()(7070最优指标函数最优指标函数 ：第：第k年初，使用一台已用了年初，使用一台已用了 年的设年的设备，到第备，到第5年末的最大效益，有年末的最大效益，有)(kksfks RxfscurKxsfsusrsfkkkkkkkkkkkkkkk)1()()0()0()()()(max)(111按逆序建立递推式：按逆序建立递推式： 0)(1 , 2 , 3 , 4 , 5)()(max)(6611sfksfxgsfkkkkRorKxkkk下面用逆序法

58、求解：下面用逆序法求解： 7171K=5时：时：)()(max)(6655555sfxgsfRorKx RxscurKxsusr5555555555)()0()0()()(max此时，此时， 的所有可能取值为：的所有可能取值为：1，2，3，4。下分别求最优指。下分别求最优指标函数值：标函数值：5s RxcurKxurf55555555)1()0()0()1()1(max)1(123)(11xg)(22xg)(33xg3x2x1x01 s12 s3s4s454x5x5s)(44xg)(55xg6s7272)(trk)(tuk)(tck 役龄役龄项目项目012345效益效益54.543.7532.

59、5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 RxcurKxurf55555555)1()0()0()1()1(max)1(, 5 . 35 . 15 . 0515 . 4max 此时，此时， Kx )1(*57373)(trk)(tuk)(tck 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 RxcurKxurf55555555)2()0()0()2()2(max)2(, 5 . 22 . 25 . 055 . 14max 此时，此时， Kx )2(*574

60、74)(trk)(tuk)(tck 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 RxcurKxurf55555555)3()0()0()3()3(max)3(, 25 . 25 . 05275. 3max 此时，此时， Rx )3(*57575)(trk)(tuk)(tck 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 RxcurKxurf55555555)4()0()0()4()4(max)4(,