任务分配问题

组合问题中的分支限界法任务分配问题主讲人：郭嘉明张旋任务分配问题任务分配问题要求把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分配给人员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]之间的某个值。设当前已对人员1～i分配了任务，并且获得了成本v，则限界函数可以定义为：nikkvlb1行的最小值第（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)=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分配给人员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=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图任务分配问题的成本矩阵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,人员ilb)(e)扩展结点11后的状态，最优解为2→a1→b3→c4→d图任务分配问题最优解的确定(0,2,a10)(2,1,b13)(2,3,b10)(2,4,b14)(0,2,a10)(2,1,b13)(2,4,b14)(3,1,c14)(0,2,a10)(2,3,b10)(2,4,b14)(3,1,c14)(1,3,c13)(0,2,a10)(2,3,b10)(2,1,b13)(0,2,a10)(2,3,b10)(2,1,b13)(1,3,c13)(a)扩展根结点后的状态(b)扩展结点3后的状态PTSTPTSTPT(c)扩展结点7后的状态(d)扩展结点6后的状态(2,4,b14)(3,1,c14)(3,4,d13)PTSTPTSTST回溯过程是：(3,4,d13)→(1,3,c13)→(2,1,b13)→(0,2,a10)。算法——任务分配问题1．根据限界函数计算目标函数的下界down；采用贪心法得到上界up；2．将待处理结点表PT初始化为空；3．for(i=1;i=n;i++)x[i]=0;4．k=1;i=0;//为第k个人分配任务，i为第k-1个人分配的任务5．while(k=1)5.1x[k]=1;5.2while(x[k]=n)5.2.1如果人员k分配任务x[k]不发生冲突，则5.2.1.1根据式9.4计算目标函数值lb;5.2.1.2若lb=up，则将i,x[k],klb存储在表PT中；5.2.2x[k]=x[k]+1;5.3如果k==n且叶子结点的lb值在表PT中最小，则输出该叶子结点对应的最优解；5.4否则，如果k==n且表PT中的叶子结点的lb值不是最小，则5.4.1up=表PT中的叶子结点最小的lb值;5.4.2将表PT中超出目标函数界的结点删除；5.5i=表PT中lb最小的结点的x[k]值；5.6k=表PT中lb最小的结点的k值；k++;•#includeiostream.h•#includestdlib.h•#includestdio.h•intn;//工人和任务的数目•intc[1000][1000];•unsignedintmincost=100000;//设置的初始值,大于可能的费用•inttask[1000],temp[1000],worker[1000];•voidmain()•{•voidPlan(intk,unsignedintcost);•inti,j;•printf(pleaseinputtasksandworkers:);•scanf(%d%d,&n,&n);•printf(输入每个工人完成各个工作的费用:\n);•for(i=0;in;i++)•{//设置每个任务由不同工人承担时的费用及全局数组的初值•/*task[i]:值为0表示任务i未分配,值为j表示任务i分配给工人j;•worker[k]:值为0表示工人k未分配任务,值为1表示工人k已分配任务;*/•worker[i]=0;•task[i]=0;•temp[i]=0;•for(j=0;jn;j++)•scanf(%d,&c[i][j]);•}•Plan(0,0);//从任务0开始分配•printf(最小总费用:%d\n,mincost);•for(i=0;in;i++)•printf(工人:%d执行任务:%d\n,i+1,temp[i]+1);••}•voidPlan(intk,unsignedintcost)•{•inti;•if(k=n&&costmincost)•{•mincost=cost;•for(i=0;in;i++)•temp[i]=task[i];//工人i完成任务temp[i]•}•else•{•for(i=0;in;i++)•{•//分配任务k•if(worker[i]==0)•{worker[i]=1;•task[k]=i;•//第一次for(i=0)时，找出0号工人分别执行0，1，2，3，4号任务时总花费最小•//第二次for(i=1)时，找出1号工人分别执行除0号工人的任务以外任务时总花费最•//小，并与i=0时的总花费最小比较•//...•//第5次for(i=4)时，找出总花费最小，并与上次的总花费最小比较•Plan(k+1,cost+c[k][i]);•worker[i]=0;•task[k]=0;•}•}•}•}