十动态规划的应用---资源分配问题

1、 设有某种原料，总数量为设有某种原料，总数量为 a，用于生产，用于生产 n 种产种产品。若分配数量品。若分配数量 xi 用于生产第用于生产第 i 种产品，其收益为种产品，其收益为 gi ( xi )，问应如何分配，才能使生产，问应如何分配，才能使生产 n 种产品的总种产品的总收入最大？收入最大？ 资源分配问题资源分配问题1 资源平行分配问题资源平行分配问题Max Z = g1(x1)+g2(x2)+ +gn(xn) s.t. x1+ x2 + + xn = a xi 0 i = 1, 2, , n静态规静态规划模型划模型不考虑回收不考虑回收 例例3 3 某公司拟将某公司拟将5 5台某种设备分配

2、给所属的甲、台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。公司提供的盈利如表。 问：这五台设备如何分配给各工厂，才能使公问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。司得到的盈利最大。 046111212051011111103791213012345丙丙乙乙甲甲工厂工厂 盈利盈利设备台数设备台数 甲甲乙乙丙丙012345037912130510111111046111212如何划分如何划分阶段阶段s1的可达状态集合的可达状态集合s2的可达状态集合的可达状态集合s3的可达状态集合的可达状态集合决

3、策变量决策变量 uk(sk) 0 sk3个阶段个阶段xk状态转移方程？状态转移方程？甲甲乙乙丙丙012345037912130510111111046111212s1s2s3321x1x2x3基本方程基本方程?指标函数指标函数gk(xk)?kkkxss1s4解：将问题按工厂分为三个阶段，甲、乙、丙分解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为别编号为1 1，2 2，3 3。决策变量决策变量xk: 分配给生产第分配给生产第 k 个工厂的设备数量个工厂的设备数量 分配给第分配给第 k 个工厂个工厂至第至第 3 个工厂的设备个工厂的设备数量（第数量（第k阶段开始阶段开始剩余的设备数量）。剩余的

4、设备数量）。状态变量状态变量 sk :甲甲乙乙丙丙012345037912130510111111046111212Dk ( sk )= uk|0 uk= xk sk 0)()(max44110sfsfxgsfkkkksxkkkk基本方程：基本方程：数量为数量为 sk 的设备分的设备分配给第配给第 k 个工厂至个工厂至第第 3 个工厂所得到个工厂所得到的最大总收益的最大总收益状态转移方程状态转移方程:sk+1 = sk - - xkxk的取值的取值范围？范围？甲甲乙乙丙丙0123450379121305101111110461112120) 0()()(max) 0(344330333 gsf

5、xgfsx 11) 3(3 fx3*(0) = 0 x3*(1) = 1x3*(2) = 2x3*(3) = 3k =3，s3=0,1,2,3,4,5，0 x3 s3s3 = 0s3 = 3甲甲乙乙丙丙0123450379121305101111110461112120461112124) 1 ()0(max)()(max) 1 (331 , 0443303333 ggsfxgfxsx 6) 2(3 fs3 = 2s3 = 1甲甲乙乙丙丙01234503791213051011111104611121212)4(3 f 12)5(3 fx3*(5) = 4,5x3*(4) = 40461112

6、12x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5结果可写结果可写成表格的成表格的形式形式:s3 = 4s3 = 5甲甲乙乙丙丙012345037912130510111111046111212 k =2，s3 = s2 - x2，s2=0,1,2,3,4,5，0 x2 s2，有有x2*(0) = 0s2 = 00)0()()(max)0(233220222 gsfxgfsxx3s3g3(x3)f3(s3) x*3012345012345046111212 12046111212012344,5322ssxx2*(1) =

7、1s2 = 1甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3) x*3012345012345046111212 12046111212012344,550540max)0()1()1()0(max)()(max)1(1 ,032321 ,03322022222 xxsxfgfgsfxgfx2*(2) =2s2 = 2甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3) x*3012345012345046111212 12046111212012344,5100104560

8、max)0()2()1()1()2()0(max)()(max)2(2, 1 ,03232322, 1 ,03322022222 xxsxfgfgfgsfxgf1401141065110max)0()3()1()2()2()1()3()0(max)()(max)3(3,2, 1 ,0323232323,2, 1 ,03322022222 xxsxfgfgfgfgsfxgfx2*(3) =2甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3) x*3012345012345046111212 12046111212012344,5s2 =

9、 3甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3) x*3012345012345046111212 12046111212012344,516011411610115120max)0()4()1()3()2()2()3()1()4()0(max)()(max)4(4 , 3, 2, 1 , 032323232324 , 3, 2, 1 , 03322022222 xxsxfgfgfgfgfgsfxgfx2*(4) =1,2s2 = 4210114116111110125120max)0()5() 1 ()4()2()3()3()

10、2()4() 1 ()5()0(max)()(max)5(5,4, 3,2, 1 ,03232323232325,4, 3,2, 1 ,03322022222xxsxfgfgfgfgfgfgsfxgfs2 = 5甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3) x*3012345012345046111212 12046111212012344,5x2*(5) =2结果列于下表：结果列于下表：x2s2g2(x2)+f3(s2-x2)f2(s2)x*20123450123450+00+40+60+110+120+125+05+45+6

11、5+115+1210+010+410+610+1111+011+411+611+011+411+0051014162101221,22k =1时，时， s2 = s1 - x1， s1 = 5， 0 x1 s1，有有x2s2f2(s2)x*2012345051014162101221,2221013512109147163210max) 0() 5() 1 () 4() 2() 3() 3() 2() 4() 1 () 5() 0(max)()(max)(2121212121215 , 4 , 3 , 2 , 1 , 0 ,2211011111 fgfgfgfgfgfgsfxgsfxsxx1*

12、(5) =0,2甲甲乙乙丙丙012345037912130510111111046111212结果可写成表格的形式结果可写成表格的形式x1s1g1(x1)+f2(s1-x1)f1(s1)x*101234550+213+167+149+1012+513+0210,2最优分配方案一：由最优分配方案一：由 x1* = 0，根据，根据 s2 = s1- x1* = 5- 0 = 5，查表知，查表知 x2* = 2，由，由s3 = s2- x2* = 5 - 2 = 3，故，故 x3* = s3 =3。即得甲工厂分配。即得甲工厂分配0台，乙工厂分配台，乙工厂分配2台，丙台，丙工厂分配工厂分配3台。台。最

13、优分配方案？最优分配方案？ 最优分配方案二：由最优分配方案二：由 x1* = 2，根据，根据 s2 = s1 - x1* = 5- 2 = 3，查表知，查表知 x2*= 2，由，由 s3 = s2 - x2*= 3 - 2 =1，故，故 x3* = s3 =1。即得甲工厂分配。即得甲工厂分配2台，乙工厂分配台，乙工厂分配2台，台，丙工厂分配丙工厂分配1台。台。 以上两个分配方案所得到的总盈利均为以上两个分配方案所得到的总盈利均为21万元。万元。问题：问题： 如果原设备台数是如果原设备台数是4 4台，求最优分配方案？台，求最优分配方案？ 如果原设备台数是如果原设备台数是3 3台，求最优分配方案？

14、台，求最优分配方案？设备台数是设备台数是4 4台，台，x1s1g1(x1)+f2(s1-x1)f1(s1)x*101234540+163+147+109+512+013+0171,2 最优分配方案一：由最优分配方案一：由 x1* = 1，根据，根据 s2 = s1 - x1* = 4- 1 = 3，查表知，查表知 x2*= 2，由，由 s3 = s2 - x2*= 3 - 2 =1，故，故 x3* = s3 =1。即得甲工厂分配。即得甲工厂分配1台，乙工厂分配台，乙工厂分配2台，台，丙工厂分配丙工厂分配1台，总盈利为台，总盈利为17万元。万元。 最优分配方案二：由最优分配方案二：由 x1* =

15、 2，根据，根据 s2 = s1 - x1* = 4- 2 = 2，查表知，查表知 x2*= 2，由，由 s3 = s2 - x2*= 2 - 2 =0，故，故 x3* = s3 =0。即得甲工厂分配。即得甲工厂分配2台，乙工厂分配台，乙工厂分配2台，台，丙工厂分配丙工厂分配0台，总盈利为台，总盈利为17万元。万元。 设备台数是设备台数是3 3台，台，x1s1g1(x1)+f2(s1-x1)f1(s1)x*101234530+143+107+59+012+013+0140 最优分配方案一：由最优分配方案一：由 x1* = 0，根据，根据 s2 = s1 - x1* = 3- 0 = 3，查表知

16、，查表知 x2*= 2，由，由 s3 = s2 - x2*= 3 - 2 =1，故，故 x3* = s3 =1。即得甲工厂分配。即得甲工厂分配0台，乙工厂分配台，乙工厂分配2台，台，丙工厂分配丙工厂分配1台，总盈利为台，总盈利为14万元。万元。 2 资源连续分配问题资源连续分配问题A种生产种生产数量数量u1投入投入 收益收益g (u1) 年终资源回收率年终资源回收率a B种生产种生产数量数量s1-u1 收益收益h (s1-u1)年终资源回收率年终资源回收率b资源数量资源数量s1第一年第一年资源数量资源数量s2=au1+b(s1-u1)第二年第二年 A种生产种生产数量数量u2投入投入;收益收益g

17、(u2);年终资源回收率年终资源回收率aB种生产种生产数量数量s2-u2;收益收益h(s2-u2);年终资源回收率年终资源回收率b到到n年年 如此进行如此进行 n 年，如何确定投入年，如何确定投入 A 的资源量的资源量 u1、un，使总收入最大？，使总收入最大？此问题的静态规划问题模型为：此问题的静态规划问题模型为： nisuusbaususbaususbaustsushugZiinnnnniiii, 2 , 1,0)()()(.)()(max1222311121 1s（拥拥有有的的总总资资源源数数 已已知知）高负荷高负荷: 产量函数产量函数 g = 8x， 年完好率为年完好率为 a=0.7，

18、机器机器 例例4 4 机器负荷分配问题机器负荷分配问题假定开始生产时完好机器的数量为假定开始生产时完好机器的数量为10001000台。台。 低负荷低负荷: 产量函数产量函数 h = 5y， 年完好率为年完好率为 b=0.9。 试问每年如何安排机器在高低两种负荷下的生试问每年如何安排机器在高低两种负荷下的生产，可使产，可使5 5年内生产的产品总产量最高年内生产的产品总产量最高? ?投入生产的机投入生产的机器数量器数量 状态变量状态变量 sk状态转移方程状态转移方程决策决策(变量变量) uk第第 k 年初拥有的完年初拥有的完好机器台数好机器台数第第 k 年高负荷下投年高负荷下投入的机器数入的机器数

19、sk+1 = auk+ b(sk - - uk) = 0.7uk+ 0.9 (sk - - uk)0 uk sk分析：分析：第第 k 年低负荷下投年低负荷下投入的机器数入的机器数sk uk阶段？阶段？动态规划基本（递推）方程？动态规划基本（递推）方程？ 515, 1),(kkkkusvV指标函数指标函数第第k年度产量为年度产量为)( 58),(kkkkkkusuusv fk(sk) =max 8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk)0 uk skk = 5, 4, 3, 2, 1sk+1阶段指标阶段指标f6(s6) = 0 则状态转移方程为则状态转移方程为sk+1

20、= 0.7uk+ 0.9 (sk - - uk) k = 1, 2, , 5解：设阶段序数解：设阶段序数 k 表示年度，表示年度，sk为第为第 k 年初拥有的年初拥有的完好机器台数，第完好机器台数，第 k 年度高负荷下投入的机器数为年度高负荷下投入的机器数为uk台。台。 fk(sk) =max 8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk)0 uk skk = 5, 4, 3, 2, 1f6(s6) = 0 基本方程为基本方程为f4(s4) = 13.6s4u*4 = s4k = 4u*5 = s5k = 5f5(s5) = 8s553max)()(58max)(550665550555555susfususfsusu2 .124 . 1max)(2 .126 .13max)(9 . 07 . 0()(58max)(44044404445444044444444suusuusufususfsususu0依此类推可得，依此类推可得，111*1222*23333*37 .23)(08 .20)(05 .17)(ssfussfussfsu 因此因此最优策略最优策略为为5*54*43*3*2*1, 0, 0sususuuu 最高产量为最高产量为23700。问题：问题：