《运筹学大学课件10-2动态规划的应用文档.pptx》由会员分享，可在线阅读，更多相关《运筹学大学课件10-2动态规划的应用文档.pptx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、资源分配问题资源分配问题 所谓资源分配问题，是指将供应量有限的一种或若干种资源（如原材料、资金、机器设备、劳力、食品等），分配给若干用户，而使目标函数最优。资源分配问题资源分配问题 设有某种原料，总量为设有某种原料，总量为MM，拟用来进行，拟用来进行n n种生产活动。种生产活动。若分配数量为若分配数量为 的原料用于第的原料用于第i i种生产活动，其收种生产活动，其收益为益为 ，问应如何分配，才使，问应如何分配，才使n n种生产活动总收益种生产活动总收益最大？最大？动态规划模型的求解动态规划模型的求解n n阶段阶段k k：按资源分配给使用者的过程分为按资源分配给使用者的过程分为n n个阶段，个阶
2、段，k=1k=1，2 2，,n,n。n n状态变量状态变量 ：状态变量要按照资源的分配来确定。：状态变量要按照资源的分配来确定。故把故把第第k k阶段的状态变量阶段的状态变量 定义为第定义为第k k阶段初所拥有阶段初所拥有的资源量，即将要在第的资源量，即将要在第k k种活动到第种活动到第n n种活动间分配的种活动间分配的资源量资源量 状态变量的约束条件：状态变量的约束条件：n n决策变量决策变量 ：对第对第k k种活动的资源投放量，即对第种活动的资源投放量，即对第k k种活动的资源分配量。种活动的资源分配量。决策变量的约束条件：决策变量的约束条件：n n状态转移方程：状态转移方程：即第即第k+
3、1k+1阶段初的资源拥有量等于第阶段初的资源拥有量等于第k k阶段的资源拥阶段的资源拥有量与投放量之差。有量与投放量之差。动态规划模型的求解动态规划模型的求解n n若用若用f fk(s(sk k)表示在第表示在第k k阶段拥有资源阶段拥有资源s sk k时，按最优分时，按最优分配方案获得的总收益，则动态基本方程是：配方案获得的总收益，则动态基本方程是：n n指标函数：对第指标函数：对第k k种活动投放资源种活动投放资源x xk k时的收益时的收益。例例例例 船舶总公司拟将船舶总公司拟将船舶总公司拟将船舶总公司拟将5 5 5 5万元资金投放到下属万元资金投放到下属万元资金投放到下属万元资金投放到
4、下属A A A A、B B B B、C C C C 三个船厂，各船厂在获得资金后的收益如下表所示。三个船厂，各船厂在获得资金后的收益如下表所示。三个船厂，各船厂在获得资金后的收益如下表所示。三个船厂，各船厂在获得资金后的收益如下表所示。试用动态规划方法求使总收益最大的投资分配方案试用动态规划方法求使总收益最大的投资分配方案试用动态规划方法求使总收益最大的投资分配方案试用动态规划方法求使总收益最大的投资分配方案？收益收益船厂船厂0 01 12 23 34 45 5A A0 03 35 57 78 89 9B B0 04 46 68 89 99 9C C0 01 13 37 79 91010投资额
5、 解解 第一步，划分阶段。第一步，划分阶段。A A、B B、C C三个船厂分别编号为三个船厂分别编号为1 1，2 2，3 3，对，对A A、B B、C C三个船厂分配资金分别形成三个船厂分配资金分别形成1 1，2 2，3 3三个阶段，即该三个阶段，即该问题可作为三段决策过程。问题可作为三段决策过程。k=1k=1，2 2，3 3。k=1k=1时，将时，将资金分给资金分给1 1，2 2，3 3三个工厂；三个工厂；k=2k=2时，将资金分给时，将资金分给2 2，3 3两个工厂；两个工厂；k=3k=3时，将资金分给时，将资金分给3 3一个工厂。一个工厂。第二步，确定状态变量。第二步，确定状态变量。状态
6、变量状态变量s sk k为第为第k k阶段初拥有的资金数。显然阶段初拥有的资金数。显然第三步，确定决策变量。第三步，确定决策变量。决策变量决策变量x xk k为第为第k k阶段分配给第阶段分配给第k k个船厂的资金数。显个船厂的资金数。显然然第四步，状态转移方程第五步，指标函数。阶段指标函数gk（sk）如上表所示。第六步，函数基本方程：下面求解，从最后一个阶段开始向前逆推计算。下面求解，从最后一个阶段开始向前逆推计算。k=3k=3时，考虑将资金分给船厂时，考虑将资金分给船厂C C，这时，这时这表明，当资金只分配到船厂C时，最好的分配方案是把全部资金都放到船厂C去。因此，可得到的最大收益如表10
7、-2所示。阶段阶段s s3 3f f3 3（s s3 3）x x3 3k=3k=30 01 12 23 34 45 50 01 13 37 79 910100 01 12 23 34 45 5k=2k=2时，时，考虑将资金分给船厂考虑将资金分给船厂B B、C C，这时，这时s s3 3=s=s2 2-x-x2 2,k=2时，汇总于表10-3k=1时，汇总于表10-4由上述计算结果可知：最大收益是：f1(5)=14（万元）最优策略（对船厂A、B、C的资金分配序列）是：x1*(5)=1,x2*(4)=1,x3*(3)=3即最优分配方案是：分给船厂A 1万元，分给船厂B 1万元，分给船厂C 3万元，可得收益最大。最大收益是14万元。作业作业 某公司有五台设备，将有选择地分配给三个工厂，所得收益某公司有五台设备，将有选择地分配给三个工厂，所得收益如表如表10-510-5所示，问公司应如何分配可使总收益最大？所示，问公司应如何分配可使总收益最大？设备设备工厂工厂0 01 12 23 34 45 51 10 03 37 79 9121213132 20 05 510101111111111113 30 04 46 6111112121212