基于Matlab解决m个人n项任务的最优分派

基于Matlab解决m个人\n项任务的最优分派[摘要]对图论中二元匹配问题及其不同要求下的最优匹配问题,在线性规划的理论基础上,基于Matlab软件,给出最大效益或最小成本的求解程序及运行命令。具有较广泛和很方便的实际应用价值。[关键词]二元匹配邻接矩阵最大效益分派最小成本分派Matlab程序命令在现实中有多种多样的分派(匹配)问题,他们的共同特征是:在满足一定的分派条件的前提下,通过制定分派方案以达到总体效益最佳的目的。本文就解决m个人、n项工作的最优分派方案为目的,基于Matlab软件给出的计算程序具有运行速度快、命令简洁,并且对较多类型的分派问题均可求解,在实际应用中具有可操作性。设二元匹配的邻接矩阵为W,其中:cij表示xi人做yj项工作的效益(或表示yj项由xi人完成所付的成本);再设决策变量xij=1:第i个人做第j项工作(任务);或xij=0:第i个人不做第j项工作(任务)。根据线性规划可建立如下所示的数学模型,其中:k为每个人所承担的任务项数,t为执行每项任务所需要的人数。一、一人一项任务的分派问题这种分派(匹配)问题,是指每个人最多只能承担一项任务,并且每项任务最多只能由一个人承担;建立该类问题的数学模型时,只需在上面数学模型中(1)和(2)取等式,且k=t=1即可。为应用方便,先建立三个m—文件(源码、程序及命令在Matlab6.5.1检验通过),再分别讨论这类问题。第一个M—文件matrixGenerator.m如下:functionarray=matrixGenerator(len)array=zeros(2*len,len^2);forrow=1:len;forind=1:len;array(row,ind+(row-1)*len)=1;end,end,forrow=len+1:len*2;forind=1:len;array(row,(row-len)+(ind-1)*len)=1;end,end第二个M—文件ipslvWraper.m为:function[x,how]=ipslvWraper(W)W=W';a=W(:);a=a';valueMat=-a;len=length(valueMat);base=sqrt(len);iffloor(base)~=base;sprintf('价值系数的个数不能开平方而得到整数,参数错误!\n');how=0;x=[];return;end,A=matrixGenerator(base);intlist=ones(1,len);B=ones(2*base,1);ctype=zeros(2*base,1);xm=zeros(len,1);xM=ones(len,1);[x,how]=ipslv_mex(valueMat,A,B,intlist,xM,xm,ctype);how,z=valueMat*x,x=x';result=zeros(base,base);fori=1:len;result(i)=x(i);end,result'第三个M—文件ipslv_mex.m在免费工具箱lpsolve文件夹中,可以由MathWorks公司网站下载lpsolve文件夹。1.人数与任务的项数相等(m=n)此时每人必须承担一项任务,且每项任务由且仅由一人承担。在Matlab运行窗口中输入以下运行命令:clear,W=[23517;25463;42638;34215;68947];[x,how]=ipslvWraper(W);(若由邻接矩阵求成本最小的匹配,W=-W即可。)返回的结果为:how=0z=-30(最优值为-z=30,若求成本最小的匹配,返回中最优值为z。)2.人数多于任务的项数(mn)此时每人最多承担一项任务,且每项任务由且仅由一人承担。人数m多于任务数n,增添m-n列,其元素均为0,构成方阵(a);即虚构m-n项任务。执行这些虚构的任务的效率为0,在求出效益最大匹配的输出结果中,划去虚构的这些列,即可得最佳匹配方案。3.人数少于任务的项数(mn)此时每人必须承担一项任务,且每项任务最多有一人承担。人数m少于任务数n,增添n-m行,其元素均为0,构成方阵(b);即虚构n-m个人。设这些虚构人执行各项任务的效率为0,在求出效益最大匹配的输出结果中,划去虚构的这些行,即可得最佳匹配方案。二、一人多项任务的分派问题所谓一人多项任务的分派(匹配),是指每个人可以承担多项任务,并且每项任务最多只能由一个人执行;假设共有m个人和n项任务,也分以下几种不同的形式讨论。1.每个人必须承担k项任务由于每个人必须承担k项任务,且每项任务最多只能由一个人执行,所以有m×k≤n;建立的模型为:在前面给出的数学模型中(1)取“=k”,(2)取“≤1”即可。在Matlab运行窗口中输入以下运行命令:W=[695657;886745;786657];W=W';c=-W(:);c=c';ze=zeros(1,5);zr=zeros(1,6);A=[ones(1,6),zeros(1,12);zr,ones(1,6),zr;zeros(1,12),ones(1,6);1,ze,1,ze,1,ze;01,ze,1,ze,...10000;001,ze,1,ze,1,000;0001,ze,1,ze,100;00001,ze,1,ze,10;ze,1,ze,1,ze,1];intlist=ones(1,18);B=[2;2;2;ones(6,1)];ctype=-[ones(9,1)];xm=zeros(18,1);xM=ones(18,1);[x,how]=ipslv_mex(c,A,B,intlist,xM,xm,ctype);how,z=-c*x,x=x'返回的结果为:how=0,z=42,最优的匹配方案为:x1—y2、y5;x2—y1、y4;x3—y3、y6。2.每个人最多可承担k项任务每个人最多承担k项,且每项最多由一个人承担;模型为:在前面的数学模型中(1)取“≤k”,(2)取“≤1”。比如把例2改为:有三个人,六项任务,要求每人最多完成三项任务,其他条件和要求不变;只需在运行命令中修改以下两项:B=[3;3;3;1;1;1;1;1;1];ctype=[-1;-1;-1;-1;-1;-1;-1;-1;-1]。运行后得最优匹配为:x1—y2、y5、y6;x2—y1、y3、y4。3.每个人最少执行k项任务每个人最少承担k项,且每项必须由一个人承担;模型为:在前面的数学模型中(1)取“≥k”,(2)取“=1”即可。比如把例2改为:有三个人,六项任务,要求每人最少完成两项任务,其他条件和要求不变;只需在运行命令中修改一项:ctype=[1;1;1;0;0;0;0;0;0];运行后得最优匹配为:x1—y2、y6;x2—y1、y4;x3—y3、y54.第i人承担ki项任务这种情况更具有一般性,比如把例2改为:第一个人必须完成两项,第二个人最多完成四项,第三个人最少完成一项,其他条件不变。也只需在运行命令中修改两项:B=[2;4;1;1;1;1;1;1;1];ctype=[0;-1;1;0;0;0;0;0;0].运行后得最优匹配为:x1—y2、y6;x2—y1、y3、y4;x3—y5。三、多人合作完成任务的分派问题所谓多人合作完成任务的分派,是指有些任务可以由一个人单独完成,而有些任务必须由若干个人共同合作才能完成;假设共有m个人和n项任务,分以下几种不同的形式讨论。1.所有任务必须由h个人共同合作才能完成由于每个人可承担多项任务,且每项任务必须由h个人共同合作才能完成;所建立的模型为:在前面给出的数学模型中(1)取“≤n”,(2)取“=h”。在Matlab运行窗口中输入以下运行命令:W=[69664;87675;78566];W=W';c=-W(:);c=c';ze=zeros(1,4);A=[11111,zeros(1,10);zeros(1,5),11111,zeros(1,5);zeros(1,10),11111;1,ze,1,ze,1,ze;01,ze,1,ze,1000;001,ze,1,ze,100;0001,ze,1,ze,10;ze,1,ze,1,ze,1];intlist=ones(1,15);B=[5;5;5;2;2;2;2;2];ctype=[-1;-1;-1;0;0;0;0;0];xm=zeros(15,1);xM=ones(15,1);[x,how]=ipslv_mex(c,A,B,intlist,xM,xm,ctype);how,z=-c*x,x=x'由返回的结果可得:how=0,z=68,所得最优匹配为:y1—x2、x3;y2—x1、x3;y3—x1、x2;y4—x1、x2;y5—x2、x3。即:x1—y2、y3、y4;x2—y1、y3、y4、y5;x3—y1、y2、y5。2.所有任务最多由h个人共同合作才能完成每个人可承担多项任务,且每项任务最多由h个人共同合作完成;模型为:在前面数学模型中(1)取“≤n”,(2)取“≤h”。在运行命令中修改B:前m行的元素为n,后n行的元素为h;修改ctype:共有m+n行,所有元素都取-1。3.所有任务最少由h个人共同合作才能完成每个人可承担多项任务,且每项任务最少由h个人共同合作完成;建立的模型为:在前面给出的数学模型中(1)取“≤n”,(2)取“≥h”。在运行命令中修改B:前m行的元素为n,后n行的元素为h;修改ctype:前m行元素取-1,后n行元素取1。4.第i项任务必须由hi个人合作才能完成由于每个人可承担多项任务,且第i项任务必须由hi个人共同合作完成;建立的模型为:在前面给出的数学模型中(1)取“≤n”,(2)取“=hi”。比如将例3改为:有三个人,五项任务,第一项、第三项任务必须由一人单独完成;第二项、第四项、第五项任务必须由两人合作完成;效益矩阵W如例3所给;求总效益最大的匹配方案。只需在例3的运行命令中修改一项:B=[3;3;3;1;2;1;2;2];运行后得最优匹配为:y1—x2;y2—x1、x3;y3—x1;y4—x1、x2;y5—x2、x3。小结:在线性规划数学模型的理论基础上,基于Matlab软件。对诸类不同的分派问题,模型的修改和命令的变化并不大,这就使模型和程序在实际中的应用较为方便。程序运行的不足之处是仅给出一个最优方案;如果问题存在多种最优方案、如果需要得到,可以在邻接矩阵中交换某些行,即可解决该问题。比如对例3中的W=[69664;87675;78566];变换为w=[78566;87675;69664];可得到不同的最优方案。参考文献:[1]薛定宇等著:高等应用数学问题的MATLAB求解(第2版)[M].北京:清华大学出版社.2008.10[2]赵静等编:数学建模与数学实验(第2版)[M].北京:高等教育出版社,2003.6[3]楼顺天等著:MATLAB7.X程序设计语言[M].西安:西安电子科技大学出版社,2007.8