《十动态规划的应用-资源分配问题》由会员分享，可在线阅读，更多相关《十动态规划的应用-资源分配问题（30页珍藏版）》请在金锄头文库上搜索。
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的可达状态集合的可达状态集合决策变量决策变量 uk(s
3、k) 0 sk3个阶段个阶段xk状态转移方程？状态转移方程？甲甲乙乙丙丙012345037912130510111111046111212s1s2s3321x1x2x3基本方程基本方程?指标函数指标函数gk(xk)?s4解解：将将问问题题按按工工厂厂分分为为三三个个阶阶段段，甲甲、乙乙、丙丙分分别编号为别编号为1 1，2 2，3 3。决策变量决策变量xk: 分配给生产第分配给生产第 k 个工厂的设备数量个工厂的设备数量 分配给第分配给第 k 个工厂个工厂至第至第 3 个工厂的设备个工厂的设备数量（第数量（第k阶段开始阶段开始剩余的设备数量）。剩余的设备数量）。状态变量状态变量 sk :甲甲乙乙
4、丙丙012345037912130510111111046111212Dk ( sk )= uk|0 uk= xk sk 基本方程：基本方程：数量为数量为 sk 的设备分的设备分配给第配给第 k 个工厂至个工厂至第第 3 个工厂所得到个工厂所得到的最大总收益的最大总收益状态转移方程状态转移方程:sk+1 = sk - - xkxk的取值的取值范围？范围？甲甲乙乙丙丙012345037912130510111111046111212x3*(0) = 0x3*(1) = 1x3*(2) = 2x3*(3) = 3k =3，s3=0,1,2,3,4,5，0 x3 s3s3 = 0s3 = 3甲甲乙乙
5、丙丙012345037912130510111111046111212046111212s3 = 2s3 = 1甲甲乙乙丙丙012345037912130510111111046111212x3*(5) = 4,5x3*(4) = 4046111212x3s3g3(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，有
6、有x2*(0) = 0s2 = 0x3s3g3(x3)f3(s3)x*3012345012345046111212 12046111212012344,5x2*(1) =1s2 = 1甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*3012345012345046111212 12046111212012344,5x2*(2) =2s2 = 2甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*3012345012345046111212 12046111212012
7、344,5x2*(3) =2甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*3012345012345046111212 12046111212012344,5s2 = 3甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*3012345012345046111212 12046111212012344,5x2*(4) =1,2s2 = 4s2 = 5甲甲乙乙丙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*30
8、12345012345046111212 12046111212012344,5x2*(5) =2结果列于下表：结果列于下表：x2s2g2(x2)+f3(s2-x2)f2(s2)x*20123450123450+00+40+60+110+120+125+05+45+65+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,22x1*(5) =0,2甲甲乙乙丙丙0123
9、45037912130510111111046111212结果可写成表格的形式结果可写成表格的形式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台。台。最优分配方案？最优分配方案？ 最优分配
10、方案二：由最优分配方案二：由 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台，求最优分配方案？台，求最优分配方案？设备台数是设备台数
11、是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* = 2，根据，根据 s2 = s1 - x
12、1* = 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，查表知，查表知 x2*= 2，由，由 s3 =
13、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(u2);年终资源回收率年终资源回收率aB种
14、生产种生产数量数量s2-u2;收益收益h(s2-u2);年终资源回收率年终资源回收率b到到n年年 如此进行如此进行 n 年，如何确定投入年，如何确定投入 A 的资源量的资源量 u1、un，使总收入最大？，使总收入最大？此问题的静态规划问题模型为：此问题的静态规划问题模型为：高负荷高负荷: 产量函数产量函数 g = 8x， 年完好率为年完好率为 a=0.7，机机器器 例例4 4 机器负荷分配问题机器负荷分配问题假假定定开开始始生生产产时时完完好好机机器器的的数数量量为为 1 10 00 00 0台台 。 低负荷低负荷: 产量函数产量函数 h = 5y， 年完好率为年完好率为 b=0.9。 试问每
15、年如何安排机器在高低两种负荷下的生产，试问每年如何安排机器在高低两种负荷下的生产，可使可使5 5年内生产的产品总产量最高年内生产的产品总产量最高? ?投入生产的机投入生产的机器数量器数量 状态变量状态变量 sk状态转移方程状态转移方程决策决策(变量变量) uk第第 k 年初拥有的完年初拥有的完好机器台数好机器台数第第 k 年高负荷下投年高负荷下投入的机器数入的机器数sk+1 = auk+ b(sk - - uk) = 0.7uk+ 0.9 (sk - - uk)0 uk sk分析：分析：第第 k 年低负荷下投年低负荷下投入的机器数入的机器数sk uk阶段？阶段？动态规划基本（递推）方程？动态规
16、划基本（递推）方程？指标函数指标函数第第k年度产量为年度产量为 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 = 0.7uk+ 0.9 (sk - - uk) k = 1, 2, , 5解：设阶段序数解：设阶段序数 k 表示年度，表示年度，sk为第为第 k 年初拥有的完年初拥有的完好机器台数，第好机器台数，第 k 年度高负荷下投入的机器数为年度高负荷下投入的机器数为uk台。台。 fk(sk) =max 8uk+5(
17、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) = 8s50依此类推可得，依此类推可得，因此因此最优策略最优策略为为最高产量为最高产量为23700。问题：问题：1. 每年年初的完好机器数。每年年初的完好机器数。 2. 如规定在第五年结束时完好机器数为如规定在第五年结束时完好机器数为500台，台，该如何安排生产？该如何安排生产？问题：问题：1. 求每年年初的完好机器数求每年年初的完好机器数始端固定终端自由的最优策略始端固定终端自由的最优策略k = 4k = 52. 如规定在第五年结束时完好机器数为如规定在第五年结束时完好机器数为500台，该如何安排生产？台，该如何安排生产？
