用Octave计算整数规划问题（分支定界法）
广告
{{v.name}}
分支定界法的核心思想：
1. 松弛：去掉整数约束，求解对应的线性规划（称为松弛问题）。
2. 判断：若松弛问题的解是整数 → 即为最优解；若不是 → 选择非整数变量进行分支。
3. 分支：对非整数变量 \(x_k = v\)，构造两个子约束 \(x_k \le \lfloor v \rfloor\) 和 \(x_k \ge \lceil v \rceil\)，形成两个子问题。
4. 定界：计算每个子问题的目标函数值，剪去不可能包含最优解的子问题（如目标值小于当前最优界）。
5. 迭代：重复上述步骤，直到所有子问题被剪枝或找到整数解。
代码如下：
function [x_opt, z_opt] = branch_and_bound(f, A, b, lb, ub, ctype, sense)
    % 初始化最优解和最优界
    x_opt = [];
    z_opt = -inf;  % 最大化问题初始下界为负无穷
    param.lpsolver = 1;
    param.itlim = 100;
    vartype = repmat('C', length(f), 1);

    % 求解松弛问题
    [x_relax, z_relax, status] = glpk(f, A, b, lb, ub, ctype, vartype, sense, param);

    if status ~= 0
        return;  % 松弛问题无可行解
    end

    % 判断是否为整数解
    if all(abs(x_relax - round(x_relax)) < 1e-6)
        x_opt = x_relax;
        z_opt = z_relax;
        return;
    end

    % 选择第一个非整数变量分支
    k = find(abs(x_relax - round(x_relax)) > 1e-6, 1);
    v = x_relax(k);
    floor_v = floor(v);
    ceil_v = ceil(v);

    % 分支1：x_k ≤ floor_v
    A1 = [A; zeros(1, size(A,2))]; A1(end, k) = 1;
    b1 = [b; floor_v];
    ctype1 = [ctype, 'U'];
    [x1, z1] = branch_and_bound(f, A1, b1, lb, ub, ctype1, sense);

    % 分支2：x_k >= ceil_v
    A2 = [A; zeros(1, size(A,2))]; A2(end, k) = 1;
    b2 = [b; ceil_v];
    ctype2 = [ctype, 'D'];
    [x2, z2] = branch_and_bound(f, A2, b2, lb, ub, ctype2, sense);

    % 更新最优解
    if z1 > z_opt
        x_opt = x1;
        z_opt = z1;
    end
    if z2 > z_opt
        x_opt = x2;
        z_opt = z2;
    end
end
例子：
\( \max\ Z = 10x_1 + 6x_2 + 4x_3 \\ \)
\( s.t. \begin{cases} x_1 + x_2 + x_3 \le 100 \\ 10x_1 + 4x_2 + 5x_3 \le 600 \\ 2x_1 + 2x_2 + 6x_3 \le 300 \\ x_1,x_2,x_3 \ge 0且为整数 \end{cases} \)
定义目标函数系数（max Z = 10x1 + 6x2 + 4x3），代码如下：
>> c = [10, 6, 4]';
定义约束系数矩阵 A，代码如下：
>> A = [ 1, 1, 1;
     10, 4, 5;
      2, 2, 6];
定义约束右端项 b，代码如下：
>> b = [100, 600, 300]';
定义变量下界，代码如下：
>> lb = [0, 0, 0]';
变量无上界，代码如下：
>> ub = [];
定义约束类型：3个约束都是 ≤，对应 'UUU'，代码如下：
>> ctype = "UUU";
定义优化方向：最大化模型（-1），代码如下：
>> s = -1;
求解，代码如下：
>> [x_opt, z_opt] = ...
   branch_and_bound (c, A, b, lb, ub, ctype, s)
error: max_recursion_depth exceeded
error: called from
    repmat
    branch_and_bound at line 7 column 5
    branch_and_bound at line 33 column 6
    branch_and_bound at line 39 column 6
友链