Задача о распределении производства

Поступил заказ: за время произвести единиц продукции номенклатуры на станках . Пусть:

- производительность –го станка по -ой продукции (число единиц продукции , которое можно сделать на станке в единицу времени);

- затраты на производство продукции на станке в единицу времени.

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

Построим экономико-математическую модель задачи. Обозначим - время, в течение которого станок изготавливает продукцию .

Ограничения по времени:

(1.1).

Ограничения в соответствии с заказами:

По смыслу задачи (1.2).

Пусть - общие затраты на производство всей продукции.

 

 

Задача о раскрое

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

Выделяют два этапа решения задачи оптимального раскроя. На первом этапе определяются рациональные способы раскроя мате­риала, на втором — решается задача линейного программирова­ния для определения интенсивности использования рациональных способов раскроя. Определение рациональных способов раскроя материала.

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

Пусть k — индекс вида заготовки, k = 1,.... q; i — индекс спо­соба раскроя единицы материала, i = 1,..., р; а_ik — количество (це­лое число) заготовок вида k, полученных при раскрое единицы материала <-м способом.

Приведенное определение рационального способа раскроя мо­жет быть формализовано следующим образом.

Способ раскроя v называется рациональным (оптимальным по Па­рето), если для любого другого способа раскроя i из соотношений а_ik ³ а_vk, k = 1,..., q, следуют соотношения а_ik = а_vk, k = 1,..., q.

2. Определение интенсивности использования рациональных спо­собов раскроя.

Обозначения:

j —индекс материала, j = 1,..., п;

k —индекс вида заготовки, k = 1,..., q;

i — индекс способа раскроя единицы материала, i = 1,..., р;

а_ijk — количество (целое число) заготовок вида k, полученных при раскрое единицы j -го материала i -м способом;

b_k — число заготовок вида k в комплекте, поставляемом заказ­чику;

d_j — количество материала j -го вида;

x_ji — количество единицу j -го материала, раскраиваемых по i -му способу (интенсивность использования способа раскроя);

c_ji — величина отхода, полученного при раскрое единицы j -го материала по i -му способу;

у — число комплектов заготовок различного вида, поставля­емых заказчику.

 

Модель А раскроя с минимальным расходом материалов:

 

Здесь (1) — целевая функция (минимум количества использу­емых материалов);

(2) — система ограничений, определяющих количество заготовок, необходимое для выполнения заказа;

(3) — условия неотрицательности переменных.

Специфическими для данной области приложения модели ли­нейного программирования являются ограничения (2).

 

Модель В раскроя с минимальными отходами:

 

Здесь (4) — целевая функция (минимум отходов при раскрое ма­териалов);

(5) — система ограничений, определяющих количество заготовок, необходимое для выполнения заказа;

(6) — условия неотрицательности переменных.

 

Модель С раскроя с учетом комплектации:

Здесь (7) — целевая функция (максимум комплектов, включающих заготовки различных видов);

(8) — ограничения по количеству материалов;

(9) — система ограничений, определяющих количество заготовок, необходимое для формирования комплектов;

(10) — условия неотрицательности переменных.

Специфическими для данной области приложения модели ли­нейного программирования являются ограничения (9).

 

Пример 1. Способы раскроя металлического стержня.

Определите все рациональные способы раскроя металлического стержня длиной 100 см на заготовки трех типов: длиной 20, 30 и 50 см. Укажите величину отходов для каждого способа.

Решение. Для данного материала и указанных заготовок су­ществует семь различных рациональных способов раскроя. Все они приведены в следующей таблице:

Пример 2. Способы раскроя куска кожи.

Определите все рациональные способы раскроя прямоугольного куска кожи размером 100 х 60 см на квадратные заготовки со сторо­нами 50,40 и 20 см и укажите величину отходов для каждого способа.

Решение. Для данного материала и указанных заготовок су­ществует шесть различных рациональных способов раскроя:

 

 

Пример 3. Изготовление парников из металлических стержней.

При изготовлении парников используется материал в виде ме­таллических стержней длиной 220 см. Этот материал разрезается на стержни длиной 120, 100 и 70 см. Для выполнения заказа тре­буется изготовить 80 стержней длиной 120 см, 120 стержней дли­ной 100 см и 102 стержня длиной 70 см.

Решение. Определяем все рациональные способы раскроя ма­териала на заготовки. Таких способов оказывается пять:

Используем модель А для одного вида материала. Тогда х_i — количество единиц материала, раскраиваемых по i -му способу.

Для ответа на второй и третий вопросы задачи получаем сле­дующую модель линейного программирования с критерием «ми­нимум общего количества используемого материала»:

Решая задачу, получаем следующий результат:

Ответы: 1. Пять способов. 2. 134 единицы материала. 3. Три из пяти рациональных способов раскроя.