资源分配模型精.ppt

资源分配模型第1页，本讲稿共11页 例例1 1 某公司有某公司有9 9个推销员在全国三个不同市场推销货物，这个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。益最大的分配方案。解：设分配人员的顺序为市场解：设分配人员的顺序为市场1,2,31,2,3，采用反向阶段编号。，采用反向阶段编号。设设 s sk k 为第为第k k阶段尚未分配的人员数，边界条件为阶段尚未分配的人员数，边界条件为 s s3 3=9=9，设，设 x xk k 为第为第k k阶段分配的推销人员数；仍采用反向递推，状态转阶段分配的推销人员数；仍采用反向递推，状态转移方程为移方程为 s sk k11=s sk k x xk k 目标函数为目标函数为第2页，本讲稿共11页 例例1 1 第一阶段：给第三市场分配第一阶段：给第三市场分配 s s1 1 有有0909种可能，第一阶段最优决策表如下种可能，第一阶段最优决策表如下：为什么与例为什么与例1 1 的第一阶段的表有差别？的第一阶段的表有差别？因为不存在边界条件因为不存在边界条件 s s0 0=0=0第3页，本讲稿共11页 例例1 1 第二阶段：给第二市场分配第二阶段：给第二市场分配 s s2 2 有有0909种可能，第二阶段最优决策表如下：种可能，第二阶段最优决策表如下：第4页，本讲稿共11页 例例1 1 第三阶段：给第一市场分配第三阶段：给第一市场分配 由边界条件由边界条件 s s3 3=9=9，第三阶段最优决策表如下：，第三阶段最优决策表如下：得决策过程：得决策过程：x x3 3*=2,*=2,x x2 2*=0,*=0,x x1 1*=7,*=7,f f3 3*=218*=218即即 市场市场1 1 分配分配 2 2人，市场人，市场2 2 不分配不分配 ，市场，市场3 3 分配分配 7 7人人第5页，本讲稿共11页例例2 2 项目选择问题项目选择问题 某工厂预计明年有某工厂预计明年有A,B,C,DA,B,C,D四个新建四个新建项目，每个项目的投资额项目，每个项目的投资额 w wk k及其投资后及其投资后的收益的收益 v vk k如右表所示。投资总额为如右表所示。投资总额为3030万元，问如何选择项目才能使总收万元，问如何选择项目才能使总收益最大。益最大。n上述问题的静态规划模型如下：上述问题的静态规划模型如下：这是一类这是一类0-10-1规划问题规划问题该问题是经典的旅行背包问题该问题是经典的旅行背包问题 (Knapsack)(Knapsack)该问题是该问题是 NP-completeNP-complete第6页，本讲稿共11页解：设项目选择的顺序为解：设项目选择的顺序为A,B,C,D;A,B,C,D;1 1、阶段、阶段 k k=1,2,3,4=1,2,3,4 分别对应分别对应 D,C,B,A D,C,B,A项目的选择过程项目的选择过程2 2、第、第 k k 阶段的状态阶段的状态 s sk k，代表第，代表第 k k 阶段初尚未分配的投资额阶段初尚未分配的投资额3 3、第、第 k k 阶段的决策变量阶段的决策变量 x xk,k,，代表第，代表第 k k 阶段分配的投资额阶段分配的投资额4 4、状态转移方程为、状态转移方程为 s sk k11=s sk k w wk k x xk k5 5、直接效益、直接效益 d dk k(s sk k,x,xk k)=)=v vk k 或或 0 06 6、总效益递推公式、总效益递推公式 该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。数增长。下面利用决策树来确定各阶段的可能状态。第7页，本讲稿共11页第8页，本讲稿共11页 例例2 2第一阶段第一阶段(项目项目D)D)的选择过程的选择过程ns s1 18 8 时，时，x x1 1只能取只能取0 0；w w1 1=8,=8,v v1 1=5=5第9页，本讲稿共11页例例2 2 第二阶段第二阶段(项目项目C)C)的选择过程的选择过程第10页，本讲稿共11页 例例2 2 第三阶段第三阶段(项目项目B)B)的选择过程的选择过程第四阶段第四阶段(项目项目A)A)的选择过程的选择过程第11页，本讲稿共11页