Задача о раскрое или минимизации отходов (обрезков)

Пример №1. Продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины - по 2 метра. По специальным заказам потребителей фирма поставляет рулоны и других размеров, для чего производится разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров приведены в табл.

Выражение для суммарной величины потерь бумаги (отходы) (в м) имеет вид
0,4Х₁ + 0,3 Х₂ + 0,1 Х₃ + 0,1 Х₅ + 0,2 Х₆.

Таким образом, математическая модель в общем виде имеет вид
min f(x) = 0,4 X₁ + 0,3Х₂ + 0,1Х₃ + 0,1Х₅ + 0,2Х₆.
при ограничениях:
2Х₂ + 2 Х₃ + 4 Х₄ + Х₅ = 150
Х ₂ + Х₂ + 2 Х₅ = 200
Х ₂ + Х₃ + 2 Х₆ = 300

Задача о раскрое материалов

Таблица 3

F=1,4·x₁+0,1·x₂+2,1·x₃+0,1·x₄→(min)..
Ограничения по выходу заготовок i-го вида по всем j способам раскроя:

Пример №3. На раскрой (распил, обработку) поступает материал одного образца в количестве a единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных числам b₁, b₂,…,b_l (условие комплектности). Каждая единица материала может быть раскроена n различными способами, причем использование i-го способа (i = 1, 2,…,n) дает a_ik единиц k-го изделия (k = 1, 2,…,l). Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.
Составим экономико-математическую модель задачи.
Обозначим через x_i – число единиц материала, раскраиваемых i-ым способом, и x – число изготавливаемых комплектов изделий. Тогда целевая функция сводиться к нахождению

F=x→(max),
при ограничениях: по общему количеству материала равного сумме его единиц, раскраиваемых различными способами; по требованию комплектности и не отрицательности переменных.

Пример №4. На предприятии имеются бревна длиной L м, которые необходимо разрезать на заготовки длиной l₁, l₂, l₃ м в количестве p₁, p₂, p₃ соответственно.
Необходимо составить оптимальный план раскройки материала, который обеспечивает минимальные отходы, при условии выполнения плана по выходу заготовок. Исходные данные приведены в таблице.

Таким образом, для решения поставленной задачи необходимо найти minZ при ограничениях. Поскольку minZ = -max(-Z(x)), то вместо задачи минимизации функции будем решать задачу максимизации функции:
Z = -(0,2x₁ + 0x₂ + 0,9x₃ + 0,7x₄ + 0,2x₅ + 0,5x₆ + 0x₇)

Пример №5. Для пошива одного изделия требуется выкроить из ткани 6 деталей. На  швейной фабрике были разработаны два варианта раскройки ткани. В таблице (расположенной ниже) приведены характеристики вариантов раскроя 10 м² ткани комплектность, т.е. количество деталей определенного вида, которые необходимы для пошива одного изделия. Ежемесячный запас ткани для пошива изделий данного типа составляет 405 м². В ближайший вечер планируется сшить 90 изделий.
Построить математическую модель задачи, позволяющий в ближайший месяц выполнить план по пошиву с минимальным количеством отходов.

Таблица - Характеристики вариантов раскроя отрезков ткани по 10м²

Математическая постановка задачи

Переменные задачи
В данной задаче искомые величины явно не указаны, но сказано, что должен быть выполнен ежемесячный план по пошиву 90 изделий. Для пошива 90 изделий в месяц требуется раскроить строго определенное количество деталей. Крой производится из отрезков ткани по 10 м² двумя различными способами, которое позволяют получить различное число деталей. Поскольку заранее неизвестно, сколько ткани будет раскраиваться первым способом и сколько – вторым, то в качестве  искомых величин можно задать количество отрезков ткани по 10м², раскроенных каждым из способов:
x₁ – количество отрезков ткани по 10м², раскроенных первым способом в течении  месяца, [отрез./мес.];
x₂ – количество отрезков ткани по 10м², раскроенных первым способом в течении  месяца, [отрез./мес.];

Целевая функция
Целью решения задачи является выполнение плана при минимальном количестве отходов. Поскольку количество изделий строго запланировано (90 шт./мес.), то этот параметр не описывает ЦФ, а относится к ограничению, невыполнение которого означает, что задача не решена. А критерием эффективности выполнение плана служит параметр «количество отходов», который необходимо свести к минимуму. Поскольку при раскрое одного отреза (10м²) ткани по 1-му варианту получается 0,5м² отходов, а по 2-му варианту – 0,35м² (см. таблицу 1), то общее количество отходов при крое (ЦФ) имеет вид
L(x) = 0.5x₁ + 0.35x₂ = min,

Ограничения
Количество раскроев ткани различными способами ограничивается следующими условиями:

• Должен быть выполнен план по пошиву изделий, другими словами, общее количество выкроенных деталей должно быть таким, чтобы из него можно было пошить 90 изделий в месяц, а именно: 1-го вида должно быть как минимум 90 и деталей остальных видов – как минимум по 180 (см. комплектность в таблицу).
• Расход ткани не должен превышать месячного запаса на складе;
• Количество отрезков раскроенной ткани не может быть отрицательным.

Математически эти ограничения записываются в виде:
60x₁ + 80x₂≥90;
35x₂≥180;
90x₁ + 20x₂≥180;
40x₁ + 78x₂≥180;
70x₁ + 15x₂≥180;
90x₁ ≥180;

Ограничение по расходу ткани имеет следующие формы записи:
Содержательную
(общее количество ткани, раскроенной за месяц)≤ (405м²)
Математическую
x₁+x₂≤405/10

Не отрицательность количества раскроенных отрезков задается в виде
x₁ ≥ 0, x₂ ≥ 0

Таким образом, математическая модель задачи имеет вид
L(x) = 0.5x₁ + 0.35x₂ = min [м²отх./мес.],
60x₁ + 80x₂≥90;
35x₂≥180;
90x₁ + 20x₂≥180;
40x₁ + 78x₂≥180;
70x₁ + 15x₂≥180;
90x₁ ≥180;
x₁+x₂≤40,5
x₁ ≥ 0, x₂ ≥ 0

Пример №6. Имеется 69 труб для отопительной сети по 1070 см каждая. Их необходимо разрезать на трубы по 130, 150 и 310 см. Найти такой вариант раскроя поступивших труб, при котором отходы были бы минимальными.

Решение.

Этап 1. Определяем варианты оптимального распила труб.

Этап 2.
Составим экономико-математическую модель задачи. Обозначим через x_j – количество труб, которые необходимо распилить по одному из способов j. Целевая функция сводиться к нахождению минимума отходов при распиле:
10x₁ + 20x₃ + 40x₄ + 60x₅ + 50x₆ + 70x₇ + 90x₈ + 110x₉ + 100x₁₀ + 120x₁₁ + 10x₁₂ + 30x₁₃ → min

x₁ + x₃ + x₄ + x₅ + x₆ + x₇ + x₈ + x₉ + x₁₀ + x₁₁ + x₁₂ + x₁₃ = 69

Ответ: необходимо использовать только второй вариант распила (нулевые отходы)