资源描述：
《任务分配问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、组合问题中的分支限界法任务分配问题主讲人：郭嘉明张旋任务分配问题任务分配问题要求把n项任务分配给n个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如图所示是一个任务分配的成本矩阵。C＝9278643758187694任务1任务2任务3任务4人员a人员b人员c人员d图任务分配问题的成本矩阵求最优分配成本的上界和下界考虑任意一个可行解，例如矩阵中的对角线是一个合法的选择，表示将任务1分配给人员a、任务2分配给人员b、任务3分配给人员c、任务4分配给人员d，其成本是9+4+1+4=18；或者应用贪心法求得一个
2、近似解：将任务2分配给人员a、任务3分配给人员b、任务1分配给人员c、任务4分配给人员d，其成本是2+3+5+4=14。显然，14是一个更好的上界。为了获得下界，考虑人员a执行所有任务的最小代价是2，人员b执行所有任务的最小代价是3，人员c执行所有任务的最小代价是1，人员d执行所有任务的最小代价是4。因此，将每一行的最小元素加起来就得到解的下界，其成本是2+3+1+4=10。需要强调的是，这个解并不是一个合法的选择（3和1来自于矩阵的同一列），它仅仅给出了一个参考下界，这样，最优值一定是[10,14]之间的某个值。设当前已对
3、人员1～i分配了任务，并且获得了成本v，则限界函数可以定义为：（2）在结点2，将任务1分配给人员a，获得的成本为9，目标函数值为9+(3+1+4)=17，超出目标函数的界[10,14]，将结点2丢弃；在结点3，将任务2分配给人员a，获得的成本为2，目标函数值为2+(3+1+4)=10，将结点3加入待处理结点表PT中；在结点4，将任务3分配给人员a，获得的成本为7，目标函数值为7+(3+1+4)=15，超出目标函数的界[10,14]，将结点4丢弃；在结点5，将任务4分配给人员a，获得的成本为8，目标函数值为8+(3+1+4)=
4、16，超出目标函数的界[10,14]，将结点5丢弃；应用分支限界法求解图所示任务分配问题，对解空间树的搜索如图所示，具体的搜索过程如下：（1）在根结点1，没有分配任务，根据限界函数估算目标函数值为2+3+1+4=10；（3）在表PT中选取目标函数值极小的结点3优先进行搜索；（4）在结点6，将任务1分配给人员b，获得的成本为2+6=8，目标函数值为8+(1+4)＝13，将结点6加入表PT中；在结点7，将任务3分配给人员b，获得的成本为2+3=5，目标函数值为5+(1+4)＝10，将结点7加入表PT中；在结点8。将任务4分配给人
5、员b，获得的成本为2+7=9，目标函数值为9+(1+4)＝14，将结点8加入表PT中；（5）在表PT中选取目标函数值极小的结点7优先进行搜索；（6）在结点9，将任务1分配给人员c，获得的成本为5+5=10，目标函数值为10+4=14，将结点9加入表PT中；在结点10，将任务4分配给人员c，获得的成本为5+8=13，目标函数值为13+4=17，超出目标函数的界[10,14]，将结点10丢弃；（7）在表PT中选取目标函数值极小的结点6优先进行搜索；（8）在结点11，将任务3分配给人员c，获得的成本为8+1=9，目标函数值为9+4
6、=13，将结点11加入表PT中；在结点12，将任务4分配给人员c，获得的成本为8+8=16，目标函数值为16+4=20，超出目标函数的界[10,14]，将结点12丢弃；（9）在表PT中选取目标函数值极小的结点11优先进行搜索；（10）在结点13，将任务4分配给人员d，获得的成本为9+4=13，目标函数值为13，由于结点13是叶子结点，同时结点13的目标函数值是表PT中的极小值，所以，结点13对应的解即是问题的最优解，搜索结束。C＝9278643758187694任务1任务2任务3任务4人员a人员b人员c人员d图任务分配问题的
7、成本矩阵4→alb=16104×startlb=101→alb=172→alb=103→alb=151→blb=133→blb=104→blb=141→clb=144→clb=174→clb=173→clb=134→dlb=13图9分支限界法求解任务分配问题示例(×表示该结点被丢弃，结点上方的数组表示搜索顺序)23567891213111××××为了在搜索过程中构建搜索经过的树结构，设一个表ST，在表PT中取出最小值结点进行扩充时，将最小值结点存储到表ST中，表PT和表ST的数据结构为(人员i-1分配的任务,<任务k,人员i
8、>lb)(e)扩展结点11后的状态，最优解为2→a1→b3→c4→d图任务分配问题最优解的确定(0,<2,a>10)(2,<1,b>13)(2,<3,b>10)(2,<4,b>14)(0,<2,a>10)(2,<1,b>13)(2,<4,b>14)(3,<1,c>14)(0,<2,a>10
