Задача раскроя
artpgchАлгоритмическое решение задачи оптимального раскроя материалов
Введение
Задача оптимального раскроя является классической проблемой операционных исследований, возникающей при необходимости разделения материалов стандартных размеров на заготовки заданных параметров. Цель заключается в удовлетворении производственного плана при минимальном расходе сырья.
Данная работа рассматривает математическую постановку данной задачи и алгоритмический подход к её решению на основе комбинации линейного и целочисленного программирования.
В этом примере демонстрируется, как решить задачу раскроя с использованием линейного программирования с подпрограммой целочисленного линейного программирования.
Подключим необходимые библиотеки.
#import Pkg
#Pkg.add(["LinearAlgebra", "JuMP", "GLPK", "MathOptInterface", "HiGHS"])
using LinearAlgebra, JuMP, GLPK, MathOptInterface, HiGHS
const MOI = MathOptInterface
Описание задачи
На предприятие поступают заготовки в виде труб стандартной длины. Определим эту длину.
длина_заготовки = 40
Затем производится распил этих труб на заготовки стандартных размеров, пригодных для дальнейшего использования. Задача оптимизации заключается в том, чтобы определить такую схему раскроя, которая позволит выполнить заданный набор заказов, используя минимальное количество исходных труб.
Необходимо задать требуемые размеры заготовок и объёмы заказов для каждого из этих размеров.
список_длин = [8, 12, 16, 20]
требуемое_количество = [90, 111, 55, 30]
число_типов = length(список_длин)
Допустим, что потери материала в процессе распила отсутствуют, а стоимость операции раскроя не учитывается.
Алгоритм решения
Под раскройным шаблоном понимается набор длин заготовок, которые могут быть получены из одной трубы при её распиле.
Вместо полного перебора допустимых раскройных шаблонов применяется итеративная процедура генерации столбцов. Алгоритм реализует двухуровневую оптимизационную схему:
-
Основная задача (линейная релаксация): Минимизация количества исходных заготовок при удовлетворении спроса комбинацией текущих шаблонов.
-
Вспомогательная задача (генерация столбцов): Поиск нового шаблона с отрицательной приведённой стоимостью, вычисляемой через двойственные переменные основной задачи. Критерий отрицательности обеспечивает улучшение целевой функции.
Итерационный процесс продолжается до исчерпания улучшающих шаблонов, что соответствует условию оптимальности в симплекс-методе. Полученное решение линейной релаксации служит нижней оценкой.
Финальная стадия: Для получения целочисленного решения задача решается повторно над сгенерированным множеством шаблонов с требованием целочисленности переменных. Этот подход сочетает эффективность линейного программирования с точностью целочисленных методов.
Постановка задачи
В данной постановке задачи образец представляет собой вектор целых чисел, элементы которого указывают количество заготовок каждого типоразмера из списка длин. Для хранения шаблонов организуется матрица с именем образцы, где каждый столбец соответствует одному шаблону.
Первый шаблон (первый столбец) соответствует двум заготовкам длиной 8 и одной заготовке длиной 20. Второй шаблон — двум заготовкам длиной 12 и одной заготовке длиной 16. Оба шаблона являются допустимыми, поскольку суммарная длина всех заготовок в каждом из них не превышает длина_заготовки = 40.
В данной формулировке, если x — это вектор-столбец целых чисел, указывающий, сколько раз используется каждый образец, то произведение даёт вектор-столбец с общим количеством заготовок каждого типа. Условие удовлетворения спроса записывается как образцы*x >= требуемое_количество.
Для формирования начального набора допустимых раскройных образцов используются простейшие варианты, содержащие заготовки только одного типоразмера. В каждый такой образец включается максимально возможное количество заготовок данного размера.
образцы = Diagonal(floor.(Int, длина_заготовки ./ список_длин))
число_образцов = size(образцы, 2)
Цель подзадачи — минимизировать функцию, которая зависит только от множителей Лагранжа. Переменные — это целые неотрицательные числа (количество заготовок каждого типа). Единственное ограничение: общая длина заготовок в шаблоне не должна превышать длину исходной заготовки (трубы).
подзадача = Model(GLPK.Optimizer)
@variable(подзадача, разрезы[1:число_типов] >= 0, Int)
@constraint(подзадача, dot(список_длин, разрезы) <= длина_заготовки)
Инициализируем переменные для цикла.
приведённая_стоимость = -Inf
допуск_приведённой_стоимости = -0.0001
статус_выхода = MOI.OPTIMAL
Запустим цикл.
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
На данном этапе получено решение задачи линейного программирования. Для завершения расчётов необходимо решить задачу повторно с окончательным набором шаблонов, изменив тип переменной решения на целочисленный. Также требуется вычислить объём отходов — количество неиспользованного материала для каждого образца и для всей задачи в целом.
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
println("\nТаблица результатов:")
println("Длина\tТребуется\tПроизведено")
println("------\t---------\t-----------")
произведено = round.(Int, образцы * значения_x)
for i in 1:length(список_длин)
println(список_длин[i], "\t", требуемое_количество[i], "\t\t", произведено[i])
end
Заключение
В данном примере представлен полный алгоритмический цикл решения задачи оптимального раскроя. Продемонстрирована эффективность итеративного подхода, использующего линейную релаксацию для поиска улучшающих шаблонов и последующего целочисленного программирования для получения итогового плана.
Полученное решение позволяет определить минимальное количество требуемого материала и провести анализ структуры отходов производства. Представленный метод обладает практической ценностью для оптимизации технологических процессов в различных отраслях промышленности.