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

- 日理万妓 2023-08-17 16:12 122阅读 0赞

![o\_%E7%A8%BF%E5%AE%9A%E8%AE%BE%E8%AE%A1%E5%AF%BC%E5%87%BA-20190912-111311.png][o_E7_A8_BF_E5_AE_9A_E8_AE_BE_E8_AE_A1_E5_AF_BC_E5_87_BA-20190912-111311.png]

## 指派问题的基本内容 ##

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

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

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

对于任务来说，每个任务必须分配一个人；

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

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

对于任务来说，每个任务必须分配一个人；

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

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

对于任务来说，每个任务必须分配一个人；

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

## 模型调用形式 ##

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

调用说明：

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

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

## 模型代码 ##

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)';

## 测试算例 ##

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

% 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) % 修改输入测试效果

转载于:https://www.cnblogs.com/gshang/p/11510872.html

[o_E7_A8_BF_E5_AE_9A_E8_AE_BE_E8_AE_A1_E5_AF_BC_E5_87_BA-20190912-111311.png]: /images/20230810/bfef191905964f5e9a7d9ad7264ed900.png