Задача о раскрое или минимизации отходов (обрезков)
Пример №1 . Продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины — по 2 метра. По специальным заказам потребителей фирма поставляет рулоны и других размеров, для чего производится разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров приведены в табл.
| Заказ | Ширина рулона (м) | Количество рулонов |
| 1 | 0,5 | 150 |
| 2 | 0,7 | 200 |
| 3 | 0,9 | 300 |
Требуется найти такие сочетания различных вариантов разрезания стандартных рулонов, чтобы поступившие заказы полностью удовлетворить с минимальными потерями (отходами).
Рассмотрим все возможные варианты раскроя стандартного рулона, соответствующие данные приведем в табл.
| Ширина рулона(м) | Варианты раскроя рулона | Минимальное количество рулонов | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| 0,5 | 0 | 2 | 2 | 4 | 1 | 0 | 150 |
| 0,7 | 1 | 1 | 0 | 0 | 2 | 0 | 200 |
| 0,9 | 1 | 0 | 1 | 0 | 0 | 2 | 300 |
| Отходы в м | 0,4 | 0,3 | 0,1 | 0 | 0,1 | 0,2 | — |
Определим переменные:
Xj — количество стандартных рулонов, разрезаемых по варианту j, j =1, 2, 3,4,5, 6.
Ограничения непосредственно связаны с требованием обеспечить изготовление требуемого количества нестандартных рулонов. Используя данные табл., получим:
2Х2 + 2 Х3 + 4 Х4 + Х5= 150 — количество рулонов шириной 0,5 м,
X1 + Х2 + 2 Х5 = 200 — количество рулонов шириной 0,7 м,
X1 + Х3 + 2 Х6 =300 — количество рулонов шириной 0,9 м.
Выражение для суммарной величины потерь бумаги (отходы) (в м) имеет вид
0,4Х1 + 0,3 Х2 + 0,1 Х3 + 0,1 Х5 + 0,2 Х6.
Таким образом, математическая модель в общем виде имеет вид
min f(x) = 0,4 X1 + 0,3Х2 + 0,1Х3 + 0,1Х5 + 0,2Х6.
при ограничениях:
2Х2 + 2 Х3 + 4 Х4 + Х5 = 150
Х 2 + Х2 + 2 Х5 = 200
Х 2 + Х3 + 2 Х6 = 300
Задача о раскрое материалов
Составим экономико-математическую модель задачи. Обозначим через xj – количество исходного материала (листов стали), которые необходимо раскроить по одному из способов j . Ограничения в задаче должны соответствовать плановому выходу заготовок различных видов. Целевая функция сводиться к нахождению минимума отходов при раскрое
Читайте также: Постельное белье из поплина что это за ткань
F=1,4·x1+0,1·x2+2,1·x3+0,1·x4→(min)..
Ограничения по выходу заготовок i-го вида по всем j способам раскроя:
Пример №3 . На раскрой (распил, обработку) поступает материал одного образца в количестве a единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных числам b1, b2,…,bl (условие комплектности). Каждая единица материала может быть раскроена n различными способами, причем использование i -го способа (i = 1, 2,…,n) дает aik единиц k-го изделия (k = 1, 2,…,l). Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.
Составим экономико-математическую модель задачи.
Обозначим через xi – число единиц материала, раскраиваемых i-ым способом, и x – число изготавливаемых комплектов изделий. Тогда целевая функция сводиться к нахождению
F=x→(max),
при ограничениях: по общему количеству материала равного сумме его единиц, раскраиваемых различными способами; по требованию комплектности и не отрицательности переменных.
Пример №4 . На предприятии имеются бревна длиной L м, которые необходимо разрезать на заготовки длиной l1, l2, l3 м в количестве p1, p2, p3 соответственно.
Необходимо составить оптимальный план раскройки материала, который обеспечивает минимальные отходы, при условии выполнения плана по выходу заготовок. Исходные данные приведены в таблице.
Решение: Сначала составим математическую модель нашей задачи. Возможные варианты раскроя и отходы при каждом из них запишем в виде таблицы.
| Длина заготовки | Варианты раскроя | Количество заготовок | ||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| 2,1 | 3 | 2 | 2 | 1 | 1 | 0 | 0 | 600 |
| 2,3 | 0 | 1 | 0 | 1 | 0 | 2 | 1 | 720 |
| 1,4 | 0 | 0 | 1 | 1 | 3 | 1 | 3 | 900 |
| Остаток, м | 0,2 | 0 | 0,9 | 0,7 | 0,2 | 0,5 | 0 | |
Обозначим через xi количество бревен, разрезанных по i-му варианту (i=1..7). Тогда суммарный остаток отходов запишется в виде линейной функции:
Z = 0,2x1 + 0x2 + 0,9x3 + 0,7x4 + 0,2x5 + 0,5x6 + 0x7
При этом должны выполняться условия выполнения плана по количеству заготовок, т.е.
3x1 + 2x2 + 2x3 + x4 + x5 = 600
x2 + x4 + 2x6 + x7 = 720
x3 + x4 + 3x5 + x6 + 3x7 = 900
Таким образом, для решения поставленной задачи необходимо найти minZ при ограничениях. Поскольку minZ = -max(-Z(x)), то вместо задачи минимизации функции будем решать задачу максимизации функции:
Z = -(0,2x1 + 0x2 + 0,9x3 + 0,7x4 + 0,2x5 + 0,5x6 + 0x7)
Пример №5 . Для пошива одного изделия требуется выкроить из ткани 6 деталей. На швейной фабрике были разработаны два варианта раскройки ткани. В таблице (расположенной ниже) приведены характеристики вариантов раскроя 10 м 2 ткани комплектность, т.е. количество деталей определенного вида, которые необходимы для пошива одного изделия. Ежемесячный запас ткани для пошива изделий данного типа составляет 405 м 2 . В ближайший вечер планируется сшить 90 изделий.
Построить математическую модель задачи, позволяющий в ближайший месяц выполнить план по пошиву с минимальным количеством отходов.
Таблица — Характеристики вариантов раскроя отрезков ткани по 10м 2
| Вариант раскроя | Количество деталей, шт./отрез | Отходы, м 2 /отрез | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| 1 | 60 | 0 | 90 | 40 | 70 | 90 | 0,5 |
| 2 | 80 | 35 | 20 | 78 | 15 | 0 | 0,35 |
| Комплектность, шт./изделие | 1 | 2 | 2 | 2 | 2 | 2 | |
Математическая постановка задачи
Переменные задачи
В данной задаче искомые величины явно не указаны, но сказано, что должен быть выполнен ежемесячный план по пошиву 90 изделий. Для пошива 90 изделий в месяц требуется раскроить строго определенное количество деталей. Крой производится из отрезков ткани по 10 м 2 двумя различными способами, которое позволяют получить различное число деталей. Поскольку заранее неизвестно, сколько ткани будет раскраиваться первым способом и сколько – вторым, то в качестве искомых величин можно задать количество отрезков ткани по 10м 2 , раскроенных каждым из способов:
x1 – количество отрезков ткани по 10м 2 , раскроенных первым способом в течении месяца, [отрез./мес.];
x2 – количество отрезков ткани по 10м 2 , раскроенных первым способом в течении месяца, [отрез./мес.];
Целевая функция
Целью решения задачи является выполнение плана при минимальном количестве отходов. Поскольку количество изделий строго запланировано (90 шт./мес.), то этот параметр не описывает ЦФ, а относится к ограничению, невыполнение которого означает, что задача не решена. А критерием эффективности выполнение плана служит параметр «количество отходов», который необходимо свести к минимуму. Поскольку при раскрое одного отреза (10м 2 ) ткани по 1-му варианту получается 0,5м 2 отходов, а по 2-му варианту – 0,35м 2 (см. таблицу 1), то общее количество отходов при крое (ЦФ) имеет вид
L(x) = 0.5x1 + 0.35x2 = min,
Ограничения
Количество раскроев ткани различными способами ограничивается следующими условиями:
- Должен быть выполнен план по пошиву изделий, другими словами, общее количество выкроенных деталей должно быть таким, чтобы из него можно было пошить 90 изделий в месяц, а именно: 1-го вида должно быть как минимум 90 и деталей остальных видов – как минимум по 180 (см. комплектность в таблицу).
- Расход ткани не должен превышать месячного запаса на складе;
- Количество отрезков раскроенной ткани не может быть отрицательным.
Ограничение по плану пошива пальто имеют следующую содержательную форму записи.
(Общее количество деталей №1 выкроенных по всем вариантам)≥ (90 штук);
(Общее количество деталей №2 выкроенных по всем вариантам) ≥ (180 штук);
(Общее количество деталей №6 выкроенных по всем вариантам) ≥ (180 штук);
Ограничение по расходу ткани имеет следующие формы записи:
Содержательную
(общее количество ткани, раскроенной за месяц)≤ (405м 2 )
Математическую
x1+x2≤405/10
Не отрицательность количества раскроенных отрезков задается в виде
x1 ≥ 0, x2 ≥ 0
Пример №6 . Имеется 69 труб для отопительной сети по 1070 см каждая. Их необходимо разрезать на трубы по 130, 150 и 310 см. Найти такой вариант раскроя поступивших труб, при котором отходы были бы минимальными.
Этап 1. Определяем варианты оптимального распила труб.
| Варианты раскроя | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 310 | 3 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 150 | 0 | 3 | 2 | 1 | 0 | 3 | 2 | 1 | 0 | 3 | 2 | 1 | 0 |
| 130 | 1 | 0 | 1 | 2 | 3 | 2 | 3 | 4 | 5 | 4 | 5 | 7 | 8 |
| Остатки | 10 | 0 | 20 | 40 | 60 | 50 | 70 | 90 | 110 | 100 | 120 | 10 | 30 |
Этап 2.
Составим экономико-математическую модель задачи. Обозначим через xj – количество труб, которые необходимо распилить по одному из способов j. Целевая функция сводиться к нахождению минимума отходов при распиле:
10x1 + 20x3 + 40x4 + 60x5 + 50x6 + 70x7 + 90x8 + 110x9 + 100x10 + 120x11 + 10x12 + 30x13 → min
Ответ: необходимо использовать только второй вариант распила (нулевые отходы)
- Свежие записи
- Балкон в многоквартирном доме: является ли он общедомовым имуществом?
- Штраф за остекление балкона в 2022: что это и как избежать наказания
- Штраф за мусор с балкона: сколько заплатить за выбрасывание окурков
- Оформление балконного окна: выбираем шторы из органзы
- Как выбрать идеальные шторы для маленькой кухни с балконом