Модели линейного программирования для решения задач раскроя
Аннотация
Показаны возможности использования модели линейного программирования для решения задач раскроя. Эта область приложения модели линейного программирования хорошо изучена. Благодаря работам в области оптимального раскроя основоположника теории линейного программирования лауреата Нобелевской премии академика Л.В. Канторовича задачу оптимального раскроя можно назвать классической прикладной оптимизационной задачей.
Модели
Большинство материалов, используемых в промышленности, поступает на производство в виде стандартных форм. Непосредственное использование таких материалов, как правило, невозможно. Предварительно их разделяют на заготовки необходимых размеров. Это можно сделать, используя различные способы раскроя материала.Задача оптимального раскроя состоит в том, чтобы выбрать один или несколько способов раскроя материала и определить, какое количество материала следует раскраивать, применяя каждый из выбранных способов.
Задачи такого типа возникают в металлургии и машиностроении, лесной, лесообрабатывающей, легкой промышленности.
Выделяют два этапа решения задачи оптимального раскроя.
На первом этапе определяются рациональные способы раскроя материала.
На втором этапе решается задача линейного программирования для определения интенсивности использования рациональных способов раскроя.
1. Определение рациональных способов раскроя материала.
В задачах оптимального раскроя рассматриваются так называемые рациональные (оптимальные по Парето) способы раскроя. Предположим, что из единицы материала можно изготовить заготовки нескольких видов.
Способ раскроя единицы материала называется рациональным (оптимальным по Парето), если увеличение числа заготовок одного вида возможно только за счет сокращения числа заготовок другого вида.
Пусть к — индекс вида заготовки, к = 1,..., q;
i - индекс способа раскроя единицы материала, i= 1,..., q;
aik — количество (целое число) заготовок вида k, полученных при раскрое единицы материала i-м способом.
Приведенное определение рационального способа раскроя может быть формализовано следующим образом.
Способ раскроя v называется рациональным (оптимальным по Парето), если для любого другого способа раскроя i из соотношений aik >avk , к=1, ..., q, следуют соотношения aik = avk, k=1, ..., q.
2. Определение интенсивности использования рациональных способов раскроя.
Обозначения:
j - индекс материала, j = 1,..., n;
k - индекс вида заготовки, k = 1, ..., q;
i - индекс способа раскроя единицы материала, i = 1,..., р;
ajik — количество (целое число) заготовок вида к, полученных при раскрое единицы j-го материала i-м способом;
bк — число заготовок вида k в комплекте, поставляемом заказчику;
dj - количество материала j-го вида;
xji - количество единицу-го материала, раскраиваемых по i-му способу (интенсивность использования способа раскроя);
cji— величина отхода, полученного при раскрое единицы j-ro материала по i-му способу;
у— число комплектов заготовок различного вида, поставляемых заказчику.
Модель А раскроя с минимальным расходом материалов:
(1)
, где k = 1,…,q (2)
xji ≥ 0, где j=1,…,n; i=1,…,p (3)
Здесь (1) - целевая функция (минимум количества используемых материалов);
(2) - система ограничений, определяющих количество заготовок, необходимое для выполнения заказа;
(3) - условия неотрицательности переменных.
Специфическими для данной области приложения модели линейного программирования являются ограничения (2).
Модель В раскроя с минимальными отходами:
(4)
, где k = 1,…,q (5)
xji ≥ 0, где j=1,…,n; i=1,…,p (6)
Здесь (4) - целевая функция (минимум отходов при раскрое материалов);
(5) - система ограничений, определяющих количество заготовок,
необходимое для выполнения заказа;
(6) - условия неотрицательности переменных.
см. пример задачи о раскрое или минимизации отходов
Модель С раскроя с учетом комплектации:
y → max (7)
, где j = 1,…,n (8)
, где k = 1,…,q (9)
y ≥ 0, xji ≥ 0, где j=1,…,n; i=1,…,p (10)
Здесь (7) - целевая функция (максимум комплектов, включающих заготовки различных видов);
(8) - ограничения по количеству материалов;
(9) - система ограничений, определяющих количество заготовок, необходимое для формирования комплектов;
(10) - условия неотрицательности переменных.
Специфическими для данной области приложения модели линейного программирования являются ограничения (9).