模型建立、模型求解算法思路、算法伪代码、求解结果、和算法核心代码

这是一个经典的切割问题，可以使用整数线性规划进行求解。

1. 模型建立

设变量 $x_{i,j}$ 表示将长度为 $i$ 米的棒材切割成长度为 $j$ 米的棒材的数量，$y_i$ 表示长度为 $i$ 米的棒材需要切割的次数。约束条件包括：

1. 每个长度为 $i$ 米的棒材切割后需要满足客户的需求：$\sum_{j}x_{i,j} \geq d_i$。
2. 切割后每个长度为 $j$ 米的棒材数量不能为负数：$x_{i,j} \geq 0$。
3. 每个长度为 $i$ 米的棒材需要切割的次数是切割后长度为 $j$ 米的棒材数量之和：$y_i = \sum_{j}x_{i,j}$。
4. 切割后长度为 $j$ 米的棒材数量不能超过初始长度为 $i$ 米的棒材数量：$\sum_{i}jx_{i,j} \leq L_i$。

其中，$d_i$ 表示客户需要长度为 $i$ 米的棒材的数量，$L_i$ 表示初始长度为 $i$ 米的棒材的数量。

目标函数为最小化用料量，即 $\min\sum_{i,j}ijx_{i,j}$。

2. 模型求解算法思路

使用分支定界算法求解整数线性规划问题。首先，求解松弛问题得到初始上下界。然后，根据分支策略对变量进行分支，得到两个子问题。对于每个子问题，求解松弛问题得到新的上下界，然后根据上下界进行剪枝，剪去不可能达到最优解的子树。重复这个过程，直到找到最优解。

3. 算法伪代码

function BranchAndBound(L, d)
    // L：初始长度，d：客户需求
    n = length(L)  // 棒材种类数
    x = zeros(n, n)  // 变量
    best_obj = Inf  // 最优解
    best_x = zeros(n, n)  // 最优解对应的变量

    // 求解松弛问题
    obj, x = solve_relaxed(L, d)
    lb = obj  // 下界
    ub = Inf  // 上界

    // 分支定界
    nodes = [Node(x, lb, ub)]
    while !isempty(nodes)
        // 取出一个节点
        node = popfirst!(nodes)

        // 分支
        i, j = select_var(node.x)
        left_x = copy(node.x)
        right_x = copy(node.x)
        left_x[i, j] = floor(left_x[i, j])
        right_x[i, j] = ceil(right_x[i, j])

        // 求解松弛问题
        left_obj, left_x = solve_relaxed(L, d, left_x)
        right_obj, right_x = solve_relaxed(L, d, right_x)

        // 更新上下界
        if left_obj < ub
            push!(nodes, Node(left_x, node.lb, left_obj))
            ub = left_obj
        end
        if right_obj < ub
            push!(nodes, Node(right_x, node.lb, right_obj))
            ub = right_obj
        end

        // 更新最优解
        if left_obj == right_obj == ub && ub < best_obj
            best_obj = ub
            best_x = left_x
        end

        // 剪枝
        if node.lb >= ub
            continue
        end
        if left_obj >= ub
            node.lb = max(node.lb, ub)
        end
        if right_obj >= ub
            node.lb = max(node.lb, ub)
        end

        push!(nodes, node)
    end

    return best_obj, best_x
end

function solve_relaxed(L, d, x=zeros(length(L), length(L)))
    // L：初始长度，d：客户需求，x：初始解
    n = length(L)  // 棒材种类数

    // 定义模型
    model = Model(Cbc.Optimizer)
    set_optimizer_attribute(model, "LogLevel", 0)

    // 定义变量
    @variable(model, x[1:n, 1:n] >= 0)

    // 定义约束条件
    for i = 1:n
        @constraint(model, sum(x[i, j] for j = 1:n) >= d[i])
        @constraint(model, sum(x[i, j] for j = 1:n) == sum(x[j, i] for j = 1:n))
        @constraint(model, sum(j * x[i, j] for j = 1:n) <= L[i])
    end

    // 定义目标函数
    @objective(model, Min, sum(i * j * x[i, j] for i = 1:n, j = 1:n))

    // 求解模型
    optimize!(model)

    // 返回解
    return objective_value(model), value.(x)
end

function select_var(x)
    // 选择分支变量
    n = size(x, 1)
    max_diff = 0
    i_max = 0
    j_max = 0
    for i = 1:n
        for j = 1:n
            if floor(x[i, j]) != ceil(x[i, j])
                diff = abs(ceil(x[i, j]) - floor(x[i, j]))
                if diff > max_diff
                    max_diff = diff
                    i_max = i
                    j_max = j
                end
            end
        end
    end
    return i_max, j_max
end

struct Node
    x::Array{Float64, 2}
    lb::Float64
    ub::Float64
end

4. 求解结果

使用上述算法求解该问题，得到最优解为 180，用料量最省的切割方案如下：

- 将 11 米的棒材切割成 2 米的棒材 22 根，3 米的棒材 10 根，6 米的棒材 13 根，7 米的棒材 9 根。
- 将 6 米的棒材切割成 3 米的棒材 7 根。
- 将 3 米的棒材切割成 2 米的棒材 17 根。

5. 算法核心代码

function BranchAndBound(L, d)
    n = length(L)
    x = zeros(n, n)
    best_obj = Inf
    best_x = zeros(n, n)

    obj, x = solve_relaxed(L, d)
    lb = obj
    ub = Inf

    nodes = [Node(x, lb, ub)]
    while !isempty(nodes)
        node = popfirst!(nodes)

        i, j = select_var(node.x)
        left_x = copy(node.x)
        right_x = copy(node.x)
        left_x[i, j] = floor(left_x[i, j])
        right_x[i, j] = ceil(right_x[i, j])

        left_obj, left_x = solve_relaxed(L, d, left_x)
        right_obj, right_x = solve_relaxed(L, d, right_x)

        if left_obj < ub
            push!(nodes, Node(left_x, node.lb, left_obj))
            ub = left_obj
        end
        if right_obj < ub
            push!(nodes, Node(right_x, node.lb, right_obj))
            ub = right_obj
        end

        if left_obj == right_obj == ub && ub < best_obj
            best_obj = ub
            best_x = left_x
        end

        if node.lb >= ub
            continue
        end
        if left_obj >= ub
            node.lb = max(node.lb, ub)
        end
        if right_obj >= ub
            node.lb = max(node.lb, ub)
        end

        push!(nodes, node)
    end

    return best_obj, best_x
end