资源分配模型

资源分配模型例1某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。31,,3)(max)(321iixxxxdxf解：设分配人员的顺序为市场1,2,3，采用反向阶段编号。设sk为第k阶段尚未分配的人员数，边界条件为s3=9，设xk为第k阶段分配的推销人员数；仍采用反向递推，状态转移方程为sk–1=sk–xk目标函数为例1第一阶段：给第三市场分配s1有0~9种可能，第一阶段最优决策表如下：为什么与例1的第一阶段的表有差别？因为不存在边界条件s0=0例1第二阶段：给第二市场分配s2有0~9种可能，第二阶段最优决策表如下：例1第三阶段：给第一市场分配由边界条件s3=9，第三阶段最优决策表如下：x3s30123456789x3*f3*92112132182172152082062022012002218得决策过程：x3*=2,x2*=0,x1*=7,f3*=218即市场1分配2人，市场2不分配，市场3分配7人例2项目选择问题某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额wk及其投资后的收益vk如右表所示。投资总额为30万元，问如何选择项目才能使总收益最大。上述问题的静态规划模型如下：•这是一类0-1规划问题•该问题是经典的旅行背包问题(Knapsack)•该问题是NP-complete项入选项未入选1030)(maxkkxxwxvxfkkkkkkk解：设项目选择的顺序为A,B,C,D;1、阶段k=1,2,3,4分别对应D,C,B,A项目的选择过程2、第k阶段的状态sk，代表第k阶段初尚未分配的投资额3、第k阶段的决策变量xk,，代表第k阶段分配的投资额4、状态转移方程为sk–1=sk–wkxk5、直接效益dk(sk,xk)=vk或06、总效益递推公式该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。例2第一阶段(项目D)的选择过程s18时，x1只能取0；w1=8,v1=5s1x1d1(s1,x1)s0=s1-w1x1f0(s0,x0*)f1(s1,x1*)条件003003x4=x2=1x3=0005005x4=x3=1x2=00080815005x3=x2=1x4=0001501515705x3=x2=0x4=10018018151005x4=x3=0x2=10020020151205x4=x2=0x3=10030030152205x4=x3=x2=0例2第二阶段(项目C)的选择过程w3=10v3=8s3x3d3(s3,x3)s2=s3-w3x3f2(s2,x2*)f3(s3,x3*)条件001599*1518508x4=1003014143018201422*x4=0项目决策投资额直接收益vkAx4=000Bx3=1108Cx2=1129Dx1=185总额3022例2第三阶段(项目B)的选择过程w4=15v4=12s4x4d4(s4,x4)s3=s4-w4x4f3(s3,x3*)f4(s4,x4*)条件00302222*3011215921第四阶段(项目A)的选择过程