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

1、基于Matlab解决m个人n项任务的最优分派摘要对图论中二元匹配问题及其不同要求下的最优匹配问题,在线性规划的理论基础上,基于Matlab软件,给出最大效益或最小成本的求解程序及运行命令。具有较广泛和很方便的实际应用价值。 关键词二元匹配 邻接矩阵 最大效益分派 最小成本分派 Matlab程序命令 在现实中有多种多样的分派(匹配)问题,他们的共同特征是:在满足一定的分派条件的前提下,通过制定分派方案以达到总体效益最佳的目的。本文就解决m个人、n项工作的最优分派方案为目的,基于Matlab软件给出的计算程序具有运行速度快、命令简洁,并且对较多类型的分派问题均可求解,在实际应用中具有可操作性。 设

2、二元匹配的邻接矩阵为W,其中:cij表示xi人做yj项工作的效益(或表示yj项由xi人完成所付的成本);再设决策变量xij=1:第i个人做第j项工作(任务);或xij=0:第i个人不做第j项工作(任务)。根据线性规划可建立如下所示的数学模型,其中:k为每个人所承担的任务项数,t为执行每项任务所需要的人数。 一、一人一项任务的分派问题 这种分派(匹配)问题,是指每个人最多只能承担一项任务,并且每项任务最多只能由一个人承担;建立该类问题的数学模型时,只需在上面数学模型中(1)和(2)取等式,且k=t=1即可。为应用方便,先建立三个m文件(源码、程序及命令在Matlab 检验通过),再分别讨论这类问

3、题。 第一个M文件matrixGenerator.m如下: function array = matrixGenerator(len) array = zeros(2 * len, len 2);for row = 1 : len;for ind = 1 : len; array(row, ind + (row - 1) * len) = 1; end, end,for row = len + 1 : len * 2; for ind = 1 : len;array(row, (row - len) + (ind - 1) * len) = 1; end, end 第二个M文件ipslvWra

4、per.m为: function x, how = ipslvWraper(W) W=W' a=W(:);a=a'valueMat=-a;len = length(valueMat);base = sqrt(len); if floor(base) = base;sprintf('价值系数的个数不能开平方而得到整数,参数错误!n'); how = 0; x = ; return; end,A = matrixGenerator(base);intlist = ones(1,len); B = ones(2*base, 1);ctype = zeros(2*bas

5、e, 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);for i = 1 : len;result(i) = x(i);end,result' 第三个M文件ipslv_mex.m在免费工具箱lpsolve文件夹中,可以由MathWorks公司网站下载lpsolve文件夹。 1. 人数与任务的项数相等(m=n) 此时每人必须承担一项任务,且每项

6、任务由且仅由一人承担。 在Matlab运行窗口中输入以下运行命令: clear, W=2 3 5 1 7;2 5 4 6 3;4 2 6 3 8;3 4 2 1 5;6 8 9 4 7; x, how = ipslvWraper(W); (若由邻接矩阵求成本最小的匹配,W = -W即可。)返回的结果为: how = 0z = -30(最优值为-z = 30,若求成本最小的匹配,返回中最优值为z。) 2. 人数多于任务的项数(m > n) 此时每人最多承担一项任务,且每项任务由且仅由一人承担。人数m多于任务数n,增添m-n列,其元素均为0,构成方阵(a);即虚构m-n项任务。执行这些虚构的

7、任务的效率为0,在求出效益最大匹配的输出结果中,划去虚构的这些列,即可得最佳匹配方案。 3. 人数少于任务的项数(m < n) 此时每人必须承担一项任务,且每项任务最多有一人承担。人数m少于任务数n,增添n-m行,其元素均为0,构成方阵(b);即虚构n-m个人。设这些虚构人执行各项任务的效率为0,在求出效益最大匹配的输出结果中,划去虚构的这些行,即可得最佳匹配方案。 二、一人多项任务的分派问题 所谓一人多项任务的分派(匹配),是指每个人可以承担多项任务,并且每项任务最多只能由一个人执行;假设共有m个人和n项任务,也分以下几种不同的形式讨论。 1. 每个人必须承担k项任务 由于每个人必须承

8、担k项任务,且每项任务最多只能由一个人执行,所以有m×kn;建立的模型为:在前面给出的数学模型中(1)取“=k”,(2)取“1”即可。 在Matlab运行窗口中输入以下运行命令: W=6 9 5 6 5 7;8 8 6 7 4 5;7 8 6 6 5 7; 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;0 1,ze,1,ze,. 1 0 0 0 0;0 0 1,ze,

9、1,ze,1,0 0 0;0 0 0 1,ze,1,ze,1 0 0;0 0 0 0 1,ze,1,ze,1 0;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,最优的匹配方案为:x1y2、y5;x2y1、y4;x3y3、y6。 2. 每个人最多可承担k项任务 每个人最多承担

10、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。运行后得最优匹配为:x1y2、y5、y6;x2y1、y3、y4 。 3. 每个人最少执行k项任务 每个人最少承担k项,且每项必须由一个人承担;模型为:在前面的数学模型中(1)取“k”,(2)取“=1”即可。比如把例2改为:有三个人,六项任务,要求每人最少完成两项任务,其他条件和要求不变;只需

11、在运行命令中修改一项:ctype=1;1;1;0;0;0;0;0;0; 运行后得最优匹配为:x1y2、y6;x2y1、y4;x3y3、y54. 第i人承担k i项任务 这种情况更具有一般性,比如把例2改为:第一个人必须完成两项,第二个人最多完成四项,第三个人最少完成一项,其他条件不变。也只需在运行命令中修改两项:B=2;4;1;1;1;1;1;1;1; ctype=0;-1;1;0;0;0;0;0;0 .运行后得最优匹配为:x1y2、y6;x2y1、y3、y4;x3y5。 三、多人合作完成任务的分派问题 所谓多人合作完成任务的分派,是指有些任务可以由一个人单独完成,而有些任务必须由若干个人共同

12、合作才能完成;假设共有m个人和n项任务,分以下几种不同的形式讨论。 1. 所有任务必须由h个人共同合作才能完成 由于每个人可承担多项任务,且每项任务必须由h个人共同合作才能完成;所建立的模型为:在前面给出的数学模型中(1)取“n”,(2)取“=h”。 在Matlab运行窗口中输入以下运行命令: W=6 9 6 6 4;8 7 6 7 5;7 8 5 6 6;W=W'c=-W(:);c=c' ze=zeros(1,4); A=1 1 1 1 1, zeros(1,10); zeros(1,5),1 1 1 1 1, zeros(1,5); zeros(1,10),1 1 1 1

13、1; 1,ze,1,ze,1,ze;0 1,ze,1,ze,1 0 0 0;0 0 1,ze,1,ze,1 0 0;0 0 0 1,ze,1,ze,1 0;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,所得最优匹配为:y1x2、x3;y2x1、x3;y

14、3x1、x2;y4x1、x2;y5x2、x3。即:x1y2、y3、y4;x2y1、y3、y4、y5;x3y1、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项任务必须由h i个人合作才能完成 由于