用Octave计算指派问题（0-1整数规划法）
广告
{{v.name}}
当\(n>10\)时，手工计算效率低且易出错，可通过0-1线性规划编程求解
代码如下：
function [assign, opt_val] = lp_assign(C, type)
    % 输入：
    %   C: m×n矩阵，成本/利润矩阵（m=执行者数，n=任务数）
    %   type: 'min'=最小成本，'max'=最大利润
    % 输出：
    %   assign: 1×m向量，assign(i)=j表示第i个执行者指派给第j个任务（0表示闲置）
    %   opt_val: 最优值
    
    [m, n] = size(C);
    len = m*n;
    c_vec = C(:);
    
    % 最大化利润转化为最小化
    if strcmp(type, 'max')
        c_vec = -c_vec;
    end
    
    % 约束1：每个执行者仅做1个任务（m行）
    A1 = kron(eye(m), ones(1, n));
    b1 = ones(m, 1);
    
    % 约束2：每个任务仅被1个执行者完成（n行）
    A2 = kron(ones(1, m), eye(n));
    b2 = ones(n, 1);
    
    % 合并约束
    A_eq = [A1; A2];
    b_eq = [b1; b2];
    lb = zeros(len, 1);
    ub = ones(len, 1); % 0-1约束
    
    % 求解0-1线性规划
    ctype = repmat('S', m+n, 1); % 等式约束
    vartype = repmat('I', m*n, 1); % 整数变量
    s = 1; % 最小化模型
    param.lpsolver = 1;
    param.itlim = 100;
    [xmin, min_cost, status, extra] = ...
        glpk (c_vec, A_eq, b_eq, lb, ub, ctype, vartype, s, param);
    x_mat = reshape(xmin, m, n);
    
    % 确定指派方案
    assign = zeros(1, m);
    for i = 1:m
        idx = find(x_mat(i,:) == 1);
        if ~isempty(idx)
            assign(i) = idx(1);
        end
    end
    
    % 计算最优值
    opt_val = c_vec' * xmin;
    if strcmp(type, 'max')
        opt_val = -opt_val;
    end
    opt_val = round(opt_val);
end
结果如下：
>> [assign, opt_val] = lp_assign([8 5 9 7;6 7 8 9;5 8 4 6;7 6 8 5], 'min')
assign =

   2   1   3   4

opt_val = 20
>> [assign, opt_val] = lp_assign([5 3 4;4 6 2;3 5 7], 'max')
assign =

   1   2   3

opt_val = 18
>> [assign, opt_val] = lp_assign([8 5 9 7 6 7 8 9 5 8 4 6 7 6 8 5; 6 7 8 9 5 8 4 6 7 6 8 5 8 5 9 7; 5 8 4 6 7 6 8 5 8 5 9 7 6 7 8 9; 7 6 8 5 8 5 9 7 6 7 8 9 5 8 4 6; 5 9 7 6 7 8 9 5 8 4 6 7 6 8 5 8; 7 6 7 8 9 5 8 4 6 7 6 8 5 8 5 9; 8 9 5 8 4 6 7 6 8 5 8 5 9 7 6 7; 8 4 6 7 6 8 5 8 5 9 7 6 7 8 9 5; 7 6 8 5 8 5 9 7 6 7 8 9 5 8 4 6; 5 8 5 9 7 6 7 8 9 5 8 4 6 7 6 8; 5 9 7 6 7 8 9 5 8 4 6 7 6 8 5 8; 9 7 6 7 8 9 5 8 4 6 7 6 8 5 8 5; 6 7 8 9 5 8 4 6 7 6 8 5 8 5 9 7; 8 5 8 5 9 7 6 7 8 9 5 8 4 6 7 6; 4 6 7 6 8 5 8 5 9 7 6 7 8 9 5 8; 7 8 9 5 8 4 6 7 6 8 5 8 5 9 7 6], 'min')
assign =

   11    7    3    4   15    8    5    2   16   12   10    9   14   13    1    6

opt_val = 69
友链