《基于Matlab解决m个人n项任务的最优分派》由会员分享，可在线阅读，更多相关《基于Matlab解决m个人n项任务的最优分派（3页珍藏版）》请在金锄头文库上搜索。
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 即可。
3、 为应用方便,先建立三个 m文件(源码、程序及命令在 Matlab 6.5.1 检验通过),再分别讨论 这类问题。 第一个 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, (
4、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); if floor(base) = base;sprintf(价值系数的个数不能开平方而得到整数,参数错误!n); how = 0; x = ; return; end,A = matrixGenerator(base);intlist = ones(1,le
5、n); 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);for i = 1 : len;result(i) = x(i);end,result 第三个 M文件 ipslv_mex.m 在免费工具箱 lpsolve 文件夹中,可以由 MathWorks 公司 网站下载 lpso
6、lve 文件夹。 1. 人数与任务的项数相等(m=n) 此时每人必须承担一项任务,且每项任务由且仅由一人承担。 在 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 多
7、于任务数 n,增添 m-n 列,其元素均为 0,构成方阵(a);即虚构 m-n 项任务。执行这些虚构的任务的效率为 0,在求出效益最大匹配的输出结果中,划去虚构的这些列,即可得最佳匹配方案。 3. 人数少于任务的项数(m n) 此时每人必须承担一项任务,且每项任务最多有一人承担。人数 m 少于任务数 n,增添 n-m 行,其元素均为 0,构成方阵(b);即虚构 n-m 个人。设这些虚构人执行各项任务的效率为 0,在 求出效益最大匹配的输出结果中,划去虚构的这些行,即可得最佳匹配方案。 二、一人多项任务的分派问题 所谓一人多项任务的分派(匹配),是指每个人可以承担多项任务,并且每项任务最多只能
8、由一个人执行;假设共有 m 个人和 n 项任务,也分以下几种不同的形式讨论。 1. 每个人必须承担 k 项任务 由于每个人必须承担 k 项任务,且每项任务最多只能由一个人执行,所以有 mkn;建 立的模型为:在前面给出的数学模型中(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),on
9、es(1,6);1,ze,1,ze,1,ze;0 1,ze,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 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,最优的匹配方
10、案为:x1y2、y5;x2y1、y4;x3y3、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。运行后得最优匹配为:x1y2、y5、y6;x2y1、y3、y4 。 3. 每个人最少执行 k 项任务 每个人最少承担 k 项,且每项必须由一个人承担;模型为:在前面的数学模
11、型中(1)取“k”,(2)取“=1”即可。比如把例 2 改为:有三个人,六项任务,要求每人最少完成两项任 务,其他条件和要求不变;只需在运行命令中修改一项:ctype=1;1;1;0;0;0;0;0;0; 运行后得最 优匹配为:x1y2、y6;x2y1、y4;x3y3、y5 4. 第 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;x
12、2 y1、y3、y4;x3y5。 三、多人合作完成任务的分派问题 所谓多人合作完成任务的分派,是指有些任务可以由一个人单独完成,而有些任务必须由 若干个人共同合作才能完成;假设共有 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
13、); 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 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,x
14、M,xm,ctype);how,z=-c*x,x=x 由返回的结果可得: how = 0 ,z = 68,所得最优匹配为:y1x2、x3;y2x1、x3;y3 x1、x2;y4x1、x2;y5x2、x3。即:x1y2、y3、y4;x2y1、y3、y4、y5;x3 y1、y2、y5。 2. 所有任务最多由 h 个人共同合作才能完成 每个人可承担多项任务,且每项任务最多由 h 个人共同合作完成;模型为:在前面数学模 型中(1)取“n”,(2)取“h” 。在运行命令中修改 B:前 m 行的元素为 n,后 n 行的元素为 h;修 改 ctype:共有 m+n 行,所有元素都取-1。 3. 所有任务最少
15、由 h 个人共同合作才能完成 每个人可承担多项任务,且每项任务最少由 h 个人共同合作完成;建立的模型为:在前面 给出的数学模型中(1)取“n”,(2)取“h” 。在运行命令中修改 B:前 m 行的元素为 n,后 n 行的元素为 h;修改 ctype:前 m 行元素取-1,后 n 行元素取 1。 4. 第 i 项任务必须由 h i 个人合作才能完成 由于每个人可承担多项任务,且第 i 项任务必须由 hi 个人共同合作完成;建立的模型为: 在前面给出的数学模型中(1)取“n”,(2)取“=hi” 。 比如将例 3 改为:有三个人,五项任务,第一项、第三项任务必须由一人单独完成;第二项、 第四项、
16、第五项任务必须由两人合作完成;效益矩阵 W 如例 3 所给;求总效益最大的匹配方 案。只需在例 3 的运行命令中修改一项:B=3;3;3;1;2;1;2;2; 运行后得最优匹配为:y1x2;y2x1、x3;y3x1;y4x1、x2;y5x2、x3。 小结:在线性规划数学模型的理论基础上,基于 Matlab 软件。对诸类不同的分派问题,模 型的修改和命令的变化并不大,这就使模型和程序在实际中的应用较为方便。程序运行的不 足之处是仅给出一个最优方案;如果问题存在多种最优方案、如果需要得到,可以在邻接矩阵 中交换某些行,即可解决该问题。比如对例 3 中的 W=6 9 6 6 4;8 7 6 7 5;7 8 5 6 6;变换为 w=7 8 5 6 6;8 7 6 7 5;6 9 6 6 4; 可得到不同的最优方案。 参考文献: 1 薛定宇等著:高等应用数学问题的 MA
