用Octave计算运输问题（整数规划法）
广告
{{v.name}}
运输问题通常可以看作整数规划问题。
运输问题是最小化线性规划问题。
运输问题的约束是等式约束。
代码如下：
function [opt_x, min_cost, status, extra] = transport_lp(a, b, c)
    % 运输问题线性规划求解
    % 输入：
    %   a: m×1数组，产地产量（m个产地）
    %   b: n×1数组，销地销量（n个销地）
    %   c: m×n矩阵，单位运费矩阵（c(i,j)=A_i→B_j的单位运费）
    % 输出：
    %   min_cost: 最小总运费
    %   opt_x: m×n矩阵，最优调运量矩阵
    
    m = length(a); n = length(b);
    total_a = sum(a); total_b = sum(b);
    c_vec = reshape(c', [], 1); % 将单位运费矩阵转为列向量（决策变量顺序：x11,x12,...,xmn）
    
    % 1. 构建约束矩阵A_eq和约束值b_eq（平衡/不平衡统一处理）
    % 产量约束：每行调运量和=产量，共m行
    A1 = kron(eye(m), ones(1,n));
    b1 = a;
    % 销量约束：每列调运量和=销量，共n行
    A2 = kron(ones(1,m), eye(n));
    b2 = b;
    % 合并约束
    A_eq = [A1; A2];
    b_eq = [b1; b2];
    
    % 2. 非负约束
    lb = zeros(m*n, 1); % 调运量≥0
    ub = [];
    
    % 3. 调用线性规划求解（最小化）
    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);
    opt_x = (reshape(xmin, n, m))'; % 转为调运量矩阵
end
结果如下：
>> [opt_x, min_cost, status, extra] = transport_lp([30;50;20], [60;40], [2 3;1 4;5 2])
opt_x =

   10   20
   50    0
    0   20

min_cost = 170
status = 0
extra =

  scalar structure containing the fields:

    time = 0
    status = 5
友链