应用
摘 要：非标准指派问题是生产管理者在日常工作中经常会遇到的一类问题，它的数学模型是讨论指派个人需要完成项任务的目标最优化（
）。
为了更好地将数学与计算机结合，本文针对“人少任务多型”及“人多任务少型”两类非标准指派问题，基于数学理论方法：“加边补零法”和“加边补最小值法”，利用计算机软件Matlab与Lingo求解，高效解决问题。
关键词：非标准指派；加边补零法；加边补最小值法；Matlab；Lingo 在日常生活安排和企业生产管理工作中，经常会遇到给人分派工作，如：某单位有个人需要完成项任务，根据每个人完成每项任务的工作效率来研究如何分配任务，使完成任务所消耗的总资源最少或总收益最大。形如这样的问题称之为指派问题，指派问题是0-1型整数规划问题中比较常见的一种，它的特点是决策变量只有0和1两种取值，在问题讨论时，通常把某个人是否执行某项任务取值为1和0，建立一般指派问题与0-1规划对应关系。目前，一般指派问题根据人数和任务数的数量关系大致有以下三种情况：（1）人数和任务数相等，即每个人必须只完成一项任务；（2）人数小于任务数，一个人可以完成几项任务；（3）人数大于任务数，一项任务可由几个人来完成。其中，第一种指派为标准指派，它是一种最基础的指派，人与任务一对应；第二、第三种指派属于非标准指派。对于比较复杂的非标准指派问题的模型，求解也更加困难。因此，本文通过具体的案例采用计算机软件[1,2]Matlab和Lingo求解非标准型问题。
1 预备知识 1.1 标准指派问题
标准指派问题是经济计划工作中经常遇到的一个问题。当指派个人去完成项任务时，要求满足以下3个前提假设：人数等于任务数；每个人必须且只需
完成一项任务；每项任务必须且只需一人去完成。如果用表示第个人完成第项任务时的效率（或时间、成本等），
，而变量
则相应的极小化数学模型如下：
由该数学模型不难看出其代数性质：每一次指派对应于一个阶排列。如果将视为一个
指派方阵，则由上述约束条件可得到：每次指派对应于个位于
不同行不同列上1的定位。故，所有可能方法数为。由此可见，指派问题一定有最优解。但是，用穷举法来决定最优解其工作量是巨大的。对于上述最佳指派问题的线性规划问题，可用单纯形法或表上作业法求解。然而，由于指派问题的特殊性，用这两种方法求解要比匈牙利法复杂得多。匈牙利法是目前求解标准指派问题行之有效且比较简单的解法。标准指派问题的匈牙利算法大致为4个步骤：变换价值系数矩阵，使各行各列都出现0元素；进行试指派，以寻求最优解；做最少的直线覆盖当前所有0元素；对上述所得矩阵进行变换，以增加其 0元素。
1.2 非标准指派问题
对于前述标准指派问题要求满足3个前提假设，但在实际应用中，大多的指派问题并不具备第一个假设，在生活实际和生产安排中，经常会遇到“人少任务多”型；“人多任务少”型的非标准指派问题。在解决非标准指派问题时，常采用的方法是“加边补零法”、“加边补最小值法”。要注意的是，几个人完成同一件事的时间并不是他们独立完成这件事时间的简单叠加，所以应根据实际情况对计算结果进行一定分析和处理。本文通过具体的案例，给出这两种种情况的 Lingo和Matlab解法。
2 “人少任务多”型指派问题
例 1 分配甲、乙、丙三人去完成4项任务，每人完成各项任务的时间为如下表所示，规定一个人最多完成两项任务，而一项任务只能由一个人完成，问：应如何分配任务，可以使得总花费的时间最少？
任务 人 任务1 任务2 任务3 任务4 甲 10 5 15 20 乙 2 10 5 15 丙 3 15 14 13 2.1加边补零法
由于人少任务多，且一个人最多完成两项任务，因此，可以把每个人化作两个相同的人，然后再添加两列虚拟的任务，完成各项任务的时间的时间均为0，用系数矩阵来表示出这种变化：
2.1.1 Matalb求解
clear all；
C=[10 5 15 20 0 0;10 5 15 20 0 0;2 10 5 15 0 0;2 10 5 15 0 0;3 15 14 13 0 0;3 15 14 13 0 0];
n=size(C,1); C=C(:); A=[];B=[]; Ae=zeros(2*n,n^2); for i=1:n
for j=(i-1)*n+1:n*i Ae(i,j)=1; end
for k=i:n:n^2 Ae(n+i,k)=1; end end
Be=ones(2*n,1); Xm=zeros(n^2,1); XM=ones(n^2,1);
[x,z]=linprog(C,A,B,Ae,Be,Xm,XM); x=reshape(x,n,n); disp('最优解矩阵为:'); Assignment=round(x) disp('最优解为:'); z
结果如下：
最优解矩阵为:
Assignment =
0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 最优解为： z =25
由结果可得甲完成任务2，乙完成任务25。
2.1.2 Lingo求解
sets: task/1..6/; people/1..6/;
Assign(task,people):c,x; endsets data:
c=10,5,15,20,0,0, 10,5,15,20,0,0, 2,10,5,15,0,0,
0 0 0 0 0 1 0 0 0 0 1 0 1和3，丙完成任务4，可以使得总花费的时间最少为2,10,5,15,0,0, 3,15,14,13,0,0, 3,15,14,13,0,0; enddata
min = @sum (Assign:c*x);
@for(task(j):@sum(people(i):x(i,j))=1); @for(people(i):@sum(task(j):x(i,j))=1); @for(Assign:@bin(x));
结果如下：
Global optimal solution found. Objective
value: Objective
bound: Infeasibilities: 000000
Extended solver
steps: Total solver
iterations: Value Reduced Cost
X( 1, 1) 0.000000 10.00000 25.00000 25.00000 0
0
0. Variable
X( 1, 2) 1.000000 5.000000
X( 1, 3) 0.000000 15.00000
X( 1, 4) 0.000000 20.00000
5) 6) 1) 2) 3) 4) 5) 6) 1) 2) 3) 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 1.000000 0.000000 0.000000 X( 1,
X( 1,
X( 2,
X( 2,
X( 2,
X( 2,
X( 2,
X( 2,
X( 3,
X( 3,
X( 3,
0.000000 0.000000 10.00000 5.000000 15.00000 20.00000 0.000000 0.000000 2.000000 10.00000 5.000000 X( 3, 4) 0.000000 15.00000
X( 3, 5) 0.000000 0.000000
X( 3, 6) 0.000000 0.000000
1) 2) 3) 4) 5) 6) 1) 2) 3) 4) 5) 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 X( 4,
X( 4,
X( 4,
X( 4,
X( 4,
X( 4,
X( 5,
X( 5,
X( 5,
X( 5,
X( 5,
2.000000 10.00000 5.000000 15.00000 0.000000 0.000000 3.000000 15.00000 14.00000 13.00000 0.000000 X( 5, 6) 0.000000 0.000000
X( 6, 1) 0.000000 3.000000
X( 6, 2) 0.000000 15.00000
X( 6, 3) 0.000000 14.00000
X( 6, 4) 0.000000 13.00000
X( 6, 5) 0.000000 0.000000
X( 6, 6) 1.000000 0.000000
由结果可得甲完成任务2，乙完成任务1和3，丙完成任务4，可以使得总花费的时间最少为25。
2.2 加边补最小值法
由于人少任务多，因此，可以加一行所加元素相应列的最小值，使效率矩阵为方阵， 用系数矩阵来表示出这种变化：
2.2.1 Matlab求解
clear all；
C=[10 5 15 20;2 10 5 15;3 15 14 13;2 5 5 13];
n=size(C,1); C=C(:); A=[];B=[];
Ae=zeros(2*n,n^2); for i=1:n
for j=(i-1)*n+1:n*i Ae(i,j)=1; end
for k=i:n:n^2 Ae(n+i,k)=1; end end
Be=ones(2*n,1); Xm=zeros(n^2,1); XM=ones(n^2,1);
[x,z]=linprog(C,A,B,Ae,Be,Xm,XM); x=reshape(x,n,n); disp('最优解矩阵为:'); Assignment=round(x) disp('最优解为:');
z
结果如下： 最优解矩阵为:
Assignment =
0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
最优解为：z =25
结果仍然显示甲完成任务2，乙完成任务1和3，丙完成任务4，可以使得总花费的时间最少为25。
2.2.2 Lingo求解
sets: task/1..4/; people/1..4/;
Assign(people,task):c,x; endsets data:
c=10,5,15,20, 2,10,5,15, 3,15,14,13,
2,5,5,13; enddata
min = @sum (Assign:c*x);
@for(task(j):@sum(people(i):x(i,j))=1); @for(people(i):@sum(task(j):x(i,j))=1); @for(Assign:@bin(x));
结果如下：
Global optimal solution found. Objective
value: 000
Extended solver
steps: Total solver
iterations: Variable Value Reduced Cost
C( 4, 4) 13.00000 0.000000
X( 1, 1) 0.000000 10.00000
X( 1, 2) 1.000000 5.000000
0
0
25.00 X( 1, 3) 0.000000 15.00000
X( 1, 4) 0.000000 20.00000
X( 2, 1) 2) 3) 4) 1) 2) 3) 4) 1) 2)
X( 2,
X( 2,
X( 2,
X( 3,
X( 3,
X( 3,
X( 3,
X( 4,
X( 4,
1.000000 2.000000 0.000000 10.00000 0.000000 5.000000 0.000000 15.00000 0.000000 3.000000 0.000000 15.00000 0.000000 14.00000 1.000000 13.00000 0.000000 2.000000 0.000000 5.000000 X( 4, 3) 1.000000 5.000000
X( 4, 4) 0.000000 13.00000
结果仍然显示甲完成任务2，乙完成任务1和3，丙完成任务4，可以使得总花费的时间最少为25。
3 “人多任务少”型指派问题
例2 有6个人甲、乙、丙、丁、戊、戌要翻译日文、韩文、英文和俄文4本书，他们每个人都精通这4种语言，各自翻译1本书所需的时间如下矩阵所示，每个人只能翻译1本书，1本书可以由 1个人或 2个人来翻译，问如何分配任务，可以使他们总共花的时间最少?
3.1 加边补零法
由于人多任务少，且1本语言书可以由2个人翻译，可以把每1本书变成2本相同的书，问题可看成6个人翻译8本语言书，缺少的2个人数用虚拟的2个人补足，虚拟的2个人翻译每本书所用的时间为0，用系数矩阵表示出这种变化：
3.1.1 Matlab求解
clear all；
C=[5 5 8 8 6 6 10 10;6 6 12 12 4 4 5 5;3 3 6 6 3 3 8 8;9 9 5 5 11 11 4 4;4 4 3 3 5 5 7 7;8 8 7 7 5 5 9 9;0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0];
n=size(C,1); C=C(:); A=[];B=[];
Ae=zeros(2*n,n^2); for i=1:n
for j=(i-1)*n+1:n*i Ae(i,j)=1; end
for k=i:n:n^2 Ae(n+i,k)=1; end end
Be=ones(2*n,1); Xm=zeros(n^2,1); XM=ones(n^2,1);
[x,z]=linprog(C,A,B,Ae,Be,Xm,XM); x=reshape(x,n,n);
disp('最优解矩阵为:'); Assignment=round(x) disp('最优解为:'); z
最优解矩阵为： Assignment =
1 0
0 0
0 0
0 1
0 0
0 0
0 0
0 0
最优解为：z =24 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
由结果可得甲和丙翻译日文书，乙和戌翻译英文书，丁翻译俄文书，戊翻译韩文书，6个人翻译8本书的总共时间最少为24小时，由于8本书是原来4本书的叠加，所以6个人翻译8本书所花的时间应该是6个人翻译4本书的两倍，故实际最少时间应该是12小时。
3.1.2 Lingo求解
sets: task/1..8/; people/1..8/;
Assign(task,people):c,x; endsets data:
c=5,5,8,8,6,6,10,10 6,6,12,12,4,4,5,5, 3,3,6,6,3,3,8,8, 9,9,5,5,11,11,4,4, 4,4,3,3,5,5,7,7, 8,8,7,7,5,5,9,9, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0; enddata
min = @sum (Assign:c*x);
@for(task(j):@sum(people(i):x(i,j))=1); @for(people(i):@sum(task(j):x(i,j))=1); @for(Assign:@bin(x));
结果显示甲和丙翻译日文书，乙和戌翻译英文书，丁翻译俄文书，戊翻译韩文书，6个人翻译8本书的总共时间最少为24小时。由2.1.1的分析从而实际最少时间应该是12小时。
3.2 加边补最小值法
由于人少任务多，因此，可以加两列所加元素相应行的最小值，次小值，使效率矩阵为方阵， 用系数矩阵来表示出这种变化：
3.2.1 Matlab求解
clear all；
C=[5 8 6 10 5 6;6 12 4 5 4 5;3 6 3 8 3 3;9 5 11 4 4 5;4 3 5 7 3 4;8 7 5 9 5 7]; n=size(C,1);
C=C(:); A=[];B=[];
Ae=zeros(2*n,n^2); for i=1:n
for j=(i-1)*n+1:n*i
Ae(i,j)=1; end
for k=i:n:n^2 Ae(n+i,k)=1; end end
Be=ones(2*n,1); Xm=zeros(n^2,1); XM=ones(n^2,1);
[x,z]=linprog(C,A,B,Ae,Be,Xm,XM);x=reshape(x,n,n); disp('最优解矩阵为:'); Assignment=round(x) disp('最优解为:');
z
最优解矩阵为： Assignment =
1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1
0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 最优解为：z =24
由结果可得甲和丙翻译日文书，乙和戌翻译英文书，丁翻译俄文书，戊翻译韩文书，与采用加边补零法求得的结果一致。
3.2.2 Lingo求解
sets: task/1..6/; people/1..6/;
Assign(people,task):c,x; endsets data:
c=5,8,6,10,5,6 6,12,4,5,4,5 3,6,3,8,3,3 9,5,11,4,4,5 4,3,5,7,3,4 8,7,5,9,5,7; enddata
min = @sum (Assign:c*x);
@for(task(j):@sum(people(i):x(i,j))=1); @for(people(i):@sum(task(j):x(i,j))=1); @for(Assign:@bin(x));
结果显示甲和丙翻译日文书，乙和戌翻译英文书，丁翻译俄文书，戊翻译韩文书，与采用加边补零法求得的结果一致。
4 总结
本文利用Matlab和Lingo求解非标准型指派问题。对于指派问题而言，Lingo所写模型可以看作对数学模型的翻译，简单直白并能够做到高效的表达目标函数和约束条件。而Matlab能从直观的角度分析函数所给的关系，理解更为深刻。值得注意的是，几个人完成同一件事的时间并不是他们独立完成这件事时间的简单叠加，所以应根据实际情况对计算结果进行一定分析和处理。
参研 2021年重庆市高等教育教学改革研究项目：《面向新时代“四有”好老师的数学卓越教师培养模式创新与实践研究》，213419；
参考文献
[1]许洪睿. 数学分析及数学软件在数学建模当中的应用探究[J]. 电子测试,2015(3):156
-158.
[2]王建江,杜振国,刘进. 优化建模软件在运筹学(整数规划)教学中的应用[J]. 科技视界，2020(9):29-32.
[3]钱丽丽.一般指派问题的LINGO解法讨论[J]. 林区教学,2020(4):97-100. [4]王增富. \"人少任务多\"最小分派问题的一种解法[J]. 燕山大学学报,2004,28(5):467-
[5]李林汉,张文良.基于Matlab编程的一类指派问题解法[J].廊坊师范学院学报(自然科学版),2015,15(01):11-14.
[6]朱德通．最优化模型与实验[M]．上海：同济大学出版社，2003.
[7]张世勇．一种新的混合粒子群优化算法[J]．重庆工商大学学报：自然科学版，2007，24(3)：241-245
因篇幅问题不能全部显示，请点此查看更多更全内容