AnyMath 文档
Notebook

材料最佳切割问题的算法解决方案

导言

最佳切割问题是一个经典的操作研究问题，当需要将标准尺寸的材料分离成指定参数的空白时就会出现。 目标是以最少的原材料消耗满足生产计划。

本文研究了这个问题的数学公式以及基于线性和整数规划组合的算法解决方案。

此示例演示如何使用线性规划和整数线性规划例程求解切削问题。

我们将连接必要的库。

In [ ]: 
neededLibs = ["LinearAlgebra", "JuMP", "GLPK", "MathOptInterface", "HiGHS"]
for lib in neededLibs
    try
        eval(Meta.parse("using $lib"))
    catch ex
        Pkg.add(lib)
        eval(Meta.parse("using $lib"))
    end
end

const MOI = MathOptInterface

任务说明

该公司以标准长度的管道形式接收坯料。 让我们定义这个长度。

In [ ]: 
длина_заготовки = 40

然后将这些管道切割成适合进一步使用的标准尺寸的坯料。 优化任务是确定一个切割方案，该方案将允许您使用最少数量的源管道来完成一组给定的订单。

有必要为每种尺寸指定所需的钢坯尺寸和订单量。

In [ ]: 
список_длин = [8, 12, 16, 20]
требуемое_количество = [90, 111, 55, 30]
число_типов = length(список_длин)

假设在切割过程中没有材料损失，并且没有考虑切割操作的成本。

解算法

切割模式被定义为一组钢坯长度，当它被切割时，可以从一个单一的管道获得。

образец_раскроя.png

而不是完全搜索可接受的切割模式，使用迭代列生成过程。 该算法实现了两级优化方案:

  1. 主要任务（线性松弛）：最大限度地减少原始空白的数量，同时满足当前模式组合的需求。

  2. 辅助任务（列生成）：搜索通过主任务的双变量计算的具有负现值的新模板。 否定性准则提供了目标函数的改进。

迭代过程继续进行，直到改进模式被用尽，这对应于单纯形方法中的最优性条件。 所得线性松弛溶液作为下界。

最后阶段：为了获得整数解，问题在生成的一组模板上反复求解，并要求整数个变量。 这种方法将线性规划的效率与整数方法的精度相结合。

设置任务

在这个问题陈述中，样本是一个整数的向量，其中的元素表示长度列表中每个标准尺寸的空白数。 要存储模板，将使用名称组织矩阵 образцы，其中每列对应一个图案。

第一个模板（第一列）对应于两个长度为8的空白和一个长度为20的空白。 第二模板为两个长度为12的坯料和一个长度为16的坯料。 这两个模板都是可以接受的，因为每个模板中所有空白的总长度不超过 длина_заготовки = 40.

在这个公式中，如果 x —这是一个整数的列向量，指示每个样本使用多少次，然后是产品 给出每种类型的空白总数的列向量。 需求满足条件写成 образцы*x >= требуемое_количество.

为了形成初始的可接受切割模式集，使用最简单的选项，仅包含一个标准尺寸的空白。 每个这样的样本包括给定大小的最大可能数量的空白。

In [ ]: 
образцы = Diagonal(floor.(Int, длина_заготовки ./ список_длин))
число_образцов = size(образцы, 2)

子问题的目标是最小化仅依赖于拉格朗日乘数的函数。 变量是非负整数（每种类型的空白数）。 唯一的限制是模板中坯料的总长度不得超过原始坯料（管道）的长度。

In [ ]: 
подзадача = Model(GLPK.Optimizer)
@variable(подзадача, разрезы[1:число_типов] >= 0, Int)
@constraint(подзадача, dot(список_длин, разрезы) <= длина_заготовки)

初始化循环的变量。

In [ ]: 
приведённая_стоимость = -Inf
допуск_приведённой_стоимости = -0.0001
статус_выхода = MOI.OPTIMAL

让我们开始循环。

In [ ]: 
while приведённая_стоимость < допуск_приведённой_стоимости && статус_выхода == MOI.OPTIMAL
    основная_задача = Model(HiGHS.Optimizer)
    set_silent(основная_задача)
    @variable(основная_задача, x[1:число_образцов] >= 0)
    @objective(основная_задача, Min, sum(x))
    @constraint(основная_задача, Спрос, образцы * x .>= требуемое_количество)
    optimize!(основная_задача)
    статус_выхода = termination_status(основная_задача)
    количество_заготовок = round(objective_value(основная_задача), digits = 2)
    if статус_выхода == MOI.OPTIMAL
        println("被使用 ", количество_заготовок, " 空白")
        двойственные_переменные = dual.(основная_задача[:Спрос])
        @objective(подзадача, Min, 1.0 - dot(двойственные_переменные, разрезы))
        set_silent(подзадача)
        optimize!(подзадача)
        приведённая_стоимость = objective_value(подзадача)
        статус_подзадачи = termination_status(подзадача)
        новый_образец = round.(Int, value.(разрезы))
        if статус_подзадачи == MOI.OPTIMAL && приведённая_стоимость < допуск_приведённой_стоимости
            образцы = [образцы новый_образец]
            число_образцов = число_образцов + 1
        end
    else
        break
    end
end

Используется 97.5 заготовок
Используется 92.0 заготовок
Используется 88.33 заготовок
Используется 88.3 заготовок

在这个阶段，已经获得了线性规划问题的解决方案。 要完成计算，有必要使用最终的一组模板再次解决问题，更改解决方案变量的类型。 到整数。 还需要计算废物量-每个样品和整个任务的未使用材料量。

In [ ]: 
if статус_выхода != MOI.OPTIMAL
    println("列生成阶段的错误")
else
    целочисленная_задача = Model(HiGHS.Optimizer)
    set_silent(целочисленная_задача)
    @variable(целочисленная_задача, x_целое[1:число_образцов] >= 0, Int)
    @objective(целочисленная_задача, Min, sum(x_целое))
    @constraint(целочисленная_задача, Спрос, образцы * x_целое .>= требуемое_количество)
    optimize!(целочисленная_задача)
    статус_целое = termination_status(целочисленная_задача)
    if статус_целое == MOI.OPTIMAL
        значения_x = value.(x_целое)
        использовано_заготовок = sum(значения_x)
        println("\nОптимальное решение использует ", использовано_заготовок, " 空白")
        общие_отходы = sum((образцы * значения_x - требуемое_количество) .* список_длин)
        for j in 1:length(значения_x)
            if значения_x[j] > 0
                println("\nРаскроить ", значения_x[j], " 根据样品空白 ", j)
                for w in 1:size(образцы, 1)
                    if образцы[w, j] > 0
                        println("    ", образцы[w, j], " 长度详情 ", список_длин[w])
                    end
                end
                отходы_образца = длина_заготовки - dot(образцы[:, j], список_длин)
                общие_отходы += отходы_образца
                println("    这个样品的浪费: ", отходы_образца)
            end
        end
        println("一般废物: ", общие_отходы, ".")
    else 
        println("最终优化中的错误")
    end
end

Оптимальное решение использует 89.0 заготовок

Раскроить 15.0 заготовок по образцу 4
    2 деталей длины 20
    Отходы этого образца: 0

Раскроить 18.0 заготовок по образцу 5
    1 деталей длины 8
    2 деталей длины 16
    Отходы этого образца: 0

Раскроить 20.0 заготовок по образцу 6
    2 деталей длины 12
    1 деталей длины 16
    Отходы этого образца: 0

Раскроить 36.0 заготовок по образцу 7
    2 деталей длины 8
    2 деталей длины 12
    Отходы этого образца: 0
Общие отходы в задаче: 28.0.
In [ ]: 
println("\nТаблица результатов:")
println("Длина\tТребуется\tПроизведено")
println("------\t---------\t-----------")
произведено = round.(Int, образцы * значения_x)
for i in 1:length(список_длин)
    println(список_длин[i], "\t", требуемое_количество[i], "\t\t", произведено[i])
end

Таблица результатов:
Длина	Требуется	Произведено
------	---------	-----------
8	90		90
12	111		112
16	55		56
20	30		30

结论

此示例显示了用于求解最优切割问题的完整算法循环。 演示了使用线性松弛来查找改进模式和随后的整数规划以获得最终计划的迭代方法的有效性。

由此产生的解决方案允许您确定所需材料的最小量并分析生产废料的结构。 所提出的方法对优化各行业的工艺流程具有实用价值。