用Octave计算指派问题（利润矩阵转成本矩阵）
广告
{{v.name}}
关键补充1：最大化利润问题的转化
若目标为总利润最大，需将利润矩阵\(P\)转化为等价的成本矩阵\(C\)，转化方法为：
\(C = M - P\)
其中\(M\)为利润矩阵中的最大元素，转化后对\(C\)用匈牙利法求解最小成本，对应的指派方案即为原利润矩阵的最大利润方案。
关键补充2：非平衡指派问题的转化
若执行者数m≠任务数n（非平衡），需通过补0行/补0列将矩阵转化为max(m,n)阶方阵，补0的含义为：
- 若\(m< n\)（执行者少，任务多）：补\(n-m\)行0元素，代表虚拟执行者，完成任务的成本为0（实际为未分配的任务，需根据场景调整）；
- 若\(m>n\)（执行者多，任务少）：补\(m-n\)列0元素，代表虚拟任务，执行者完成虚拟任务的成本为0（实际为闲置的执行者）。
关键补充3：退化问题
若行/列消去后，某行/列出现多个0元素，但无法选出n个独立0元素，属于退化问题，按步骤3-4正常调整矩阵即可，无需额外处理。
例子：
3个销售员（\(A_1,A_2,A_3\)）分配3个区域（\(B_1,B_2,B_3\)），单位利润矩阵如下（单位：千元），求总利润最大的指派方案。
\( P = \begin{bmatrix} 5 & 3 & 4 \\ 4 & 6 & 2 \\ 3 & 5 & 7 \end{bmatrix} \)
步骤1：利润矩阵转成本矩阵
利润矩阵中最大元素\(M=7\)，成本矩阵\(C=7-P\)：
\(C = \begin{bmatrix}2&4&3\\3&1&5\\4&2&0\end{bmatrix}\)
步骤2：对成本矩阵执行匈牙利法
1. 行消去：每行减该行最小值
- 行1：2→[0,2,1]
- 行2：1→[2,0,4]
- 行3：0→[4,2,0]
行消去后矩阵：\(\begin{bmatrix}0&2&1\\2&0&4\\4&2&0\end{bmatrix}\)
2. 列消去：每列最小值均为0，无需消去，矩阵不变。
步骤2：寻找独立0元素
圈出3个独立0（\(A_1→B_1\)、\(A_2→B_2\)、\(A_3→B_3\)），为最优解。
步骤3：还原最大利润方案
对应原利润矩阵的指派方案：
- \(A_1→B_1\)（5）、\(A_2→B_2\)（6）、\(A_3→B_3\)（7）；
总最大利润：\(5+6+7=18\)千元。
代码如下：
function [assign, opt_val] = hungarian_assign(C, type)
    % 匈牙利法求解指派问题（n阶方阵）
    % 输入：
    %   C: n×n矩阵，成本矩阵（type='min'）或利润矩阵（type='max'）
    %   type: 求解类型，'min'=最小化成本，'max'=最大化利润
    % 输出：
    %   assign: 1×n向量，assign(i)=j表示将第i个执行者指派给第j个任务
    %   opt_val: 最优值（最小成本/最大利润）
    
    % 输入校验
    [n, m] = size(C);
    if n ~= m
        error('成本/利润矩阵必须为n阶方阵！');
    end
    if ~ismember(type, {'min', 'max'})
        error('type必须为''min''或''max''！');
    end
    
    % 保存原始矩阵，用于最终计算最优值
    origC = C;
    % 最大化利润转化为最小化成本（用cost变量，不覆盖origC）
    if strcmp(type, 'max')
        M = max(origC(:));
        cost = M - origC;
    else
        cost = origC;
    end
    
    % 匈牙利法核心步骤（行消去+列消去+找独立0+调整矩阵）
    row_mask = false(1, n);
    col_mask = false(1, n);
    assign = zeros(1, n);
    row_assign = zeros(1, n); % row_assign(j)=i 列j指派给行i
    
    % 行消去
    for i = 1:n
        cost(i,:) = cost(i,:) - min(cost(i,:));
    end
    
    % 列消去
    for j = 1:n
        cost(:,j) = cost(:,j) - min(cost(:,j));
    end
    
    % 寻找独立0元素并重复调整（核心循环）
    while true
        % 标记独立0并获得列->行的指派（row_assign）
        [row_mask, col_mask, row_assign] = mark_zero(cost, n);
        % 画盖0线：线穿过所有未标记的行和所有已标记的列
        line_num = (n - sum(row_mask)) + sum(col_mask);
        if line_num == n
            break;
        end
        % 调整矩阵：找到未被任何线覆盖的最小值并调整
        % 未被覆盖的元素位于被标记的行且列未被标记
        uncovered = row_mask' & ~col_mask;
        vals = cost(uncovered);
        if isempty(vals)
            break;
        end
        theta = min(vals);
        cost(uncovered) = cost(uncovered) - theta;
        % 将theta加到被两条线覆盖的元素（即未被标记的行与已标记的列的交点）
        cost(~row_mask', col_mask) = cost(~row_mask', col_mask) + theta;
    end
    
    % 确定指派方案
    for j = 1:n
        assign(row_assign(j)) = j;
    end
    
    % 计算最优值（直接使用原始矩阵origC）
    opt_val = sum(origC(sub2ind([n,n], 1:n, assign)));
end

% 辅助函数：标记独立0元素
function [row_mask, col_mask, row_assign] = mark_zero(cost, n)
    % 使用标准匈牙利流程：先贪婪找独立0（starred zeros），然后标记行/列
    row_star = zeros(1, n); % row_star(i) = j 表示行i的star列
    col_star = zeros(1, n); % col_star(j) = i 表示列j的star行
    for i = 1:n
        for j = 1:n
            if cost(i,j) == 0 && row_star(i) == 0 && col_star(j) == 0
                row_star(i) = j;
                col_star(j) = i;
            end
        end
    end
    row_assign = col_star; % 返回列->行的指派（col j 指派给 row col_star(j)）

    % 标记：先标记所有没有star的行
    row_mask = false(1, n);
    col_mask = false(1, n);
    for i = 1:n
        if row_star(i) == 0
            row_mask(i) = true;
        end
    end

    % 反复：在被标记的行中标记含0的列；在被标记的列中标记含star的行，直到不再改变
    while true
        changed = false;
        for i = 1:n
            if row_mask(i)
                for j = 1:n
                    if cost(i,j) == 0 && ~col_mask(j)
                        col_mask(j) = true;
                        changed = true;
                    end
                end
            end
        end
        for j = 1:n
            if col_mask(j)
                if col_star(j) ~= 0 && ~row_mask(col_star(j))
                    row_mask(col_star(j)) = true;
                    changed = true;
                end
            end
        end
        if ~changed
            break;
        end
    end
end
结果如下：
>> [assign1, val1] = hungarian_assign([5 3 4;4 6 2;3 5 7], 'max')
assign1 =

   1   2   3

val1 = 18
友链