[原创] Matlab 指派问题模型代码

2019/09/12 11:15
阅读数 120

指派问题的基本内容

一般来说指派问题解决的是如何将任务分配到人,使得任务完成的效益最大化(成本型效益则求最小值,利润型效益则求最大值)。上述问题一个 0 - 1 整数规划问题。

问题围绕着任务和人展开,即存在着 m 个任务,以及 n 个人。每个人处理每个任务都会有对应的效益,将所有人的情况写在一起,就组成了一个 m*n 的效益矩阵。

<br/>

当 m = n 时,即此时,任务数和人数相等,那么每个人都会处理一项任务,存在如下约束:

对于任务来说,每个任务必须分配一个人;

对于人来说,每个人必须分配一个任务。

<br/>

类似的,当 m < n 时,任务数小于人数,则存在如下约束:

对于任务来说,每个任务必须分配一个人;

对于人来说,每个人可能会被分配到一个任务,也可能没有分配到任务。

<br/>

当 m > n 时,任务数大于人数,则存在如下约束:

对于任务来说,每个任务必须分配一个人;

对于人来说,每个人可能会被分配到一个或者多个任务,但最多不超过任务总数。

<br/>

模型调用形式

 [x,min_fval,exitflag] = myTaskArrange2(f)

调用说明:

输入变量为一个 m*n 的效益矩阵,其中 m 行为 m 个任务, n 列为 n 个人。

输出变量 x 为与效益矩阵同型的 0-1 矩阵,1表示被安排,0表示不被安排;min_fval 为最优目标值;exitflag 为退出标识符,一般等于 1 表示解收敛。

<br/>

模型代码

function [x,min_fval,exitflag] = myTaskArrange2(f)
%% 程序功能说明
%求解不平衡任务指派问题
%====输入参数====
%f            m行n列的效益矩阵,m个任务,n个人,
%====输出参数====
%x            目标函数取最小值时的自变量值
%min_fval     目标函数的最小值
% exitflag    退出标识符
%程序编写时间:2019年09月

%% 程序主体
[m,n] = size(f); % 获取效益矩阵中任务的个数和人的个数

% 按行拉成一列向量
f = f';
F = f(:);

% 构造等式约束(每一行加起来等于1,即每个任务必须分配一人)
Aeq = cell(m,m);
Aeq(:) = {zeros(1,n)};
Aeq(eye(m,m)==1) = {ones(1,n)};
Aeq = cell2mat(Aeq);
Beq = ones(m,1);

% 取整变量地址
intcon = 1:m*n;

% 变量取值范围(大于0小于1)
LB = zeros(m*n,1);
UB = ones(m*n,1);

if m == n       % 如果任务数等于人数
    % 构造等式约束(每个人一定会被安排)
    Aeq2 = repmat(eye(n,n),1,m);
    Beq2 = ones(n,1);
    Aeq = [Aeq;Aeq2];
    Beq = [Beq;Beq2];
    
    % 整数规划求解
    [x,min_fval, exitflag] = intlinprog(F,intcon,[],[],Aeq,Beq,LB,UB);
    
elseif m < n     % 如果任务数小于人数
    % 构造不等式约束(每一列加起来大于0小于1,即每个人可能被安排也可能不被安排一个任务)
    A = repmat(eye(n,n),1,m);
    B = ones(n,1);
    % 利用整数规划函数求解
    [x,min_fval, exitflag] = intlinprog(F,intcon,A,B,Aeq,Beq,LB,UB);
    
elseif m > n      % 如果任务数大于人数
    % 构造不等式约束(每一列加起来大于1小于m,即每个人可能被安排一个或者多个任务,最多不超过任务数m)
    A = repmat(eye(n,n),1,m);
    B = ones(n,1)*m;
    % 利用整数规划函数求解
    [x,min_fval, exitflag] = intlinprog(F,intcon,A,B,Aeq,Beq,LB,UB);
end
%% 将结果还原成效益矩阵对应形式
x = reshape(x,n,m)';

<br/>

测试算例

为了验证本模型的效果,提供如下测试算例,进行验证:


% 4项任务,4个人完成 最优解:8
f1 = [6,1,3,8;
    6,3,5,2;
    1,1,1,4;
    7,2,5,2];

% 4项任务,5个人完成  最优解:127.8
f2 = [37.7,32.9,38.8,37,35.4;
    43.4,33.1,42.2,34.7,41.8;
    33.3,28.5,38.9,30.4,33.6;
    29.2,26.4,29.6,28.5,31.1];

% 5项任务,3个人完成 最优解:116
f3 = [25,39,34;
    29,38,27;
    31,26,28;
    4,20,40;
    37,18,32];


[x,min_fval,exitflag] = myTaskArrange2(f1) % 修改输入测试效果
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部