Задача оптимального раскроя задача линейного программирования

Модели линейного программирования для решения задач раскроя

Аннотация
Показаны возможности использования модели линейного программирования для решения задач раскроя. Эта область прило­жения модели линейного программирования хорошо изучена. Благодаря работам в области оптимального раскроя основоположника теории линей­ного программирования лауреата Нобелевской премии академика Л.В. Канторовича задачу оптимального раскроя можно назвать классической прикладной оптимизационной задачей.

Большинство материалов, используемых в промышленности, поступает на производство в виде стандартных форм. Непосредственное использование таких материалов, как правило, невозможно. Предварительно их разделяют на заготовки необходимых размеров. Это можно сделать, используя различные способы раскроя материала.
Задача оптимального раскроя состоит в том, чтобы выбрать один или несколько способов раскроя материала и определить, какое количество материала следует раскраивать, применяя каждый из выбранных способов.
Задачи такого типа возникают в металлургии и машиностроении, лесной, лесообрабатывающей, легкой промышленности.

Выделяют два этапа решения задачи оптимального раскроя.
На первом этапе определяются рациональные способы раскроя материала.
На втором этапе решается задача линейного программирования для определения интенсивности использования рациональных способов рас­кроя.
1. Определение рациональных способов раскроя материала.
В задачах оптимального раскроя рассматриваются так называемые рациональные (оптимальные по Парето) способы раскроя. Предположим, что из единицы материала можно изготовить заготовки нескольких видов.
Способ раскроя единицы материала называется рациональным (оптимальным по Парето), если увеличение числа заготовок одного вида возможно только за счет сокращения числа заготовок другого вида.
Пусть к — индекс вида заготовки, к = 1. q;
i — индекс способа раскроя единицы материала, i= 1. q;
a_ik — количество (целое число) заготовок вида k , полученных при раскрое единицы материала i -м способом.
Приведенное определение рационального способа раскроя может быть формализовано следующим образом.
Способ раскроя v называется рациональным (оптимальным по Парето), если для любого другого способа раскроя i из соотношений a_ik >a_vk , к=1, . q, следуют соотношения a_ik = a_vk, k=1, . q.

2. Определение интенсивности использования рациональных способов раскроя.
Обозначения:
j — индекс материала, j = 1. n;
k — индекс вида заготовки, k = 1, . q;
i — индекс способа раскроя единицы материала, i = 1. р;
a_jik — количество (целое число) заготовок вида к , полученных при раскрое единицы j-го материала i-м способом;
b_к — число заготовок вида k в комплекте, поставляемом заказчику;
d_j — количество материала j-го вида;
x_ji — количество единицу-го материала, раскраиваемых по i-му способу (интенсивность использования способа раскроя);
c_ji — величина отхода, полученного при раскрое единицы j-ro материала по i-му способу;
у — число комплектов заготовок различного вида, поставляемых заказчику.

Модель А раскроя с минимальным расходом материалов:
(1)
, где k = 1,…,q (2)
x_ji ≥ 0, где j=1,…,n; i=1,…,p (3)
Здесь (1) — целевая функция (минимум количества используемых материалов);
(2) — система ограничений, определяющих количество заготовок, необходимое для выполнения заказа;
(3) — условия неотрицательности переменных.
Специфическими для данной области приложения модели линейного программирования являются ограничения (2).

Модель В раскроя с минимальными отходами:
(4)
, где k = 1,…,q (5)
x_ji ≥ 0, где j=1,…,n; i=1,…,p (6)
Здесь (4) — целевая функция (минимум отходов при раскрое материалов);
(5) — система ограничений, определяющих количество заготовок,
необходимое для выполнения заказа;
(6) — условия неотрицательности переменных.

Модель С раскроя с учетом комплектации:
y → max (7)
, где j = 1,…,n (8)
, где k = 1,…,q (9)
y ≥ 0, x_ji ≥ 0, где j=1,…,n; i=1,…,p (10)
Здесь (7) — целевая функция (максимум комплектов, включающих заготовки различных видов);
(8) — ограничения по количеству материалов;
(9) — система ограничений, определяющих количество заготовок, необходимое для формирования комплектов;
(10) — условия неотрицательности переменных.
Специфическими для данной области приложения модели линейно­го программирования являются ограничения (9).

Источник

Задачи раскроя.

Широкое применение рационального раскроя промышленных материалов как важнейшего источника экономики материальных ресурсов составляет одну из наиболее важных задач промышленных предприятий. Опыт показал, что рацион раскрой обеспечивает повышение коэффициента использования длинномерных материалов (прутков, труб, круг леса, досок) на 2-5%, а листовых (фанера, листов стали) на 3-7%.

Сущность рационального раскроя состоит в разработке и внедрении таких технологических дополнений раскройных планов, при которых получается необходимый ассортимент (комплект) заготовок, а отходы по площади или по весу сводятся к min. Разработка планов раскроя особенно важна, когда количество всевозможных вариантов чрезвычайно велико.

Впервые методику рационального раскроя материалов, основанную на применении методов ЛП, предложил академик Канторович. В настоящее время эти задачи исследуются в институте математики сибирского отделения.

Формулировка задачи по рациональному раскрою материалов зависит от формы раскраиваемого материала (длинномерные, листовые, рулонные) и тех условий, которые должны учитываться при раскрое (свойство материала). Также раскрой может быть прямолинейным и фигурным.

Математическая модель прямолинейного раскроя.

i – виды заготовок (i=1 m) – A, B, C.

b_i – необходимое количество i-ых заготовок

a_ij – количество заготовок i-го вида раскрываемых по j-му варианту из единицы исходного материала

x_j – количество исходного материала, раскраиваемых по j-му варианту

c_j – отходы от единицы исходного материала, раскраиваемых по j-му варианту

L – показатель эффективности (суммарные отходы)

Найти min L= при условии , x_j

Листы материала размером нужно раскроить так, чтобы получились заготовки типа А — 40 штук размером , а также В – 400 шт размером .

Возьмем 4 способа раскроя, определим отходы от каждого способа

По результатам анализа вариантов раскроя составим таблицу

Источник

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

Выражение для суммарной величины потерь бумаги (отходы) (в м) имеет вид
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

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

Данная задача состоит в разработке такого плана, который обеспечивает необходимый комплект изделий при минимальных отходах (по длине, площади, массе, стоимости и др.) при раскрое материалов или обеспечивает максимальное число комплектов изделий. Пример №2 . Требуется разработать оптимальный план раскроя стандартных листов стали, обеспечивая выход планового числа заготовок разного вида при минимальных суммарных отходах, если известно, что из партии листовой стали необходимо нарезать четыре вида различных заготовок в количестве b_i (i = 1, 2,…,4) штук. Лист стали стандартных размеров может быть раскроен четырьмя способами. Каждому возможному способу раскроя соответствует карта раскроя. Из карт раскроя известен выход заготовок в штуках разных видов a_ij (i = 1, 2,…4; j = 1,2,…,4), а также площадь отходов c_j (j = 1, 2,…,n) при раскрое одного листа стали по j-му способу раскроя. Какое количество листов стали необходимо раскроить тем или иным способом, чтобы отходы были минимальными?

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),
при ограничениях: по общему количеству материала равного сумме его единиц, раскраиваемых различными способами; по требованию комплектности и не отрицательности переменных.

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

Пример №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 , раскроенных каждым из способов:
x₁ – количество отрезков ткани по 10м 2 , раскроенных первым способом в течении месяца, [отрез./мес.];
x₂ – количество отрезков ткани по 10м 2 , раскроенных первым способом в течении месяца, [отрез./мес.];

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

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

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

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

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

Источник