практика. ЗАДАЧИ ОПТИМАЛЬНОГО РАСКРОЯ. Задачи оптимального раскроя
 Скачать 238.12 Kb.
|
|
ЗАДАЧИ ОПТИМАЛЬНОГО РАСКРОЯ Показаны возможности использования модели линейного программирования для решения задач раскроя. Благодаря работам основоположника теории линейного программирования лауреата Нобелевской премии академика Л.В. Канторовича задачу оптимального раскроя можно назвать классической прикладной оптимизационной задачей. После выполнения заданий, вы будете уметь формулировать и использовать для экономического анализа следующие понятия: • материал; • заготовка; • отходы; • способ раскроя (рациональный и оптимальный); • интенсивность использования рациональных способов раскроя. МОДЕЛИ Большинство материалов, используемых в промышленности, поступает на производство в виде стандартных форм. Непосредственное использование таких материалов, как правило, невозможно. Предварительно их разделяют на заготовки необходимых размеров. Это можно сделать, используя различные способы раскроя материала. Задача оптимального раскроя состоит в том, чтобы выбрать один или несколько способов раскроя материала и определить, какое количество материала следует раскраивать, применяя каждый из выбранных способов. Задачи такого типа возникают в металлургии и машиностроении, лесной, лесообрабатывающей, легкой промышленности. Выделяют два этапа решения задачи оптимального раскроя. На первом этапе определяются рациональные способы раскроя материала, на втором – решается задача линейного программирования для определения интенсивности использования рациональных способов раскроя. 1. Определение рациональных способов раскроя материала В задачах оптимального раскроя рассматриваются так называемые рациональные (оптимальные по Парето) способы раскроя. Предположим, что из единицы материала можно изготовить заготовки нескольких видов. Способ раскроя единицы материала называется рациональным (оптимальным по Парето), если увеличение числа заготовок одного вида возможно только за счет сокращения числа заготовок другого вида. Пусть k – индекс вида заготовки, 1,..., k q = ; i – индекс способа раскроя единицы материала, 1, ..., i p = ; aik –количество (целое число) заготовок вида k , полученных при раскрое единицы материала i -м способом. Приведенное определение рационального способа раскроя может быть формализовано следующим образом. Определение. Способ раскроя v называется рациональным (оптимальным по Парето), если для любого другого способа раскроя i из соотношений a a ik vk ≥ , 1,..., k q = , следуют соотношения a a ik vk = , 1,..., k q = . 2. Определение интенсивности использования рациональных способов раскроя Обозначения: j – индекс материала, 1,..., j n = ; k – индекс вида заготовки, 1,..., k q = ; i – индекс способа раскроя единицы материала, 1, ..., i p = ; aijk –количество (целое число) заготовок вида k , полученных при раскрое единицы j -го материала i -м способом; bk –число заготовок вида k в комплекте, поставляемом заказчику; d j –количество материала j-го вида; x ji –количество единицу j -го материала, раскраиваемых по i -му способу ( интенсивность использования способа раскроя); c ji – величина отхода, полученного при раскрое единицы j -го материала по i -му способу; y – число комплектов заготовок различного вида, поставляемых заказчику. 2 Модель А раскроя с минимальным расходом материалов min 1 1 p n x ji j i → = = ∑ ∑ , (1) , 1,..., 1 1 p n a x b k q jik ji k j i ≥ = = = ∑ ∑ , (2) 0, 1,.., ; 1,..., x j n i p ji ≥ = = (3) Здесь (1) – целевая функция (минимум количества используемых материалов); (2) – система ограничений, определяющих количество заготовок, необходимое для выполнения заказа; (3) – условия неотрицательности переменных. Специфическими для данной области приложения модели линейного программирования являются ограничения (2). Модель В раскроя с минимальными отходами min 1 1 p n c x ji ji j i → = = ∑ ∑ , (4) , 1,..., 1 1 p n a x b k q jik ji k j i = = = = ∑ ∑ , (5) 0, 1,.., ; 1,..., x j n i p ji ≥ = = (6) Здесь (4) – целевая функция (минимум отходов при раскрое материалов); (5) – система ограничений, определяющих количество заготовок, необходимое для выполнения заказа; (6) – условия неотрицательности переменных. Модель С раскроя с учетом комплектации max y → , (7) , 1,..., 1 n x d j n ji j j ≤ = = ∑ , (8) , 1,..., 1 1 p n a x b y k q jik ji k j i ≥ = = = ∑ ∑ , (9) 3 0, 0, 1,.., ; 1,..., y x j n i p ji ≥ ≥ = = (10) Здесь (7) – целевая функция (максимум комплектов, включающих заготовки различных видов); (8) – ограничения по количеству материалов; (9) – система ограничений, определяющих количество заготовок, необходимое для формирования комплектов; (10) – условия неотрицательности переменных. Специфическими для данной области приложения модели линейного программирования являются ограничения (9). Пример 1. Способы раскроя металлического стержня. Определите все рациональные способы раскроя металлического стержня длиной 100 см на заготовки трех типов: длиной 20, 30 и 50 см. Укажите величину отходов для каждого способа. Решение.Для данного материала и указанных заготовок существует семь различных рациональных способов раскроя. Все они приведены в следующей таблице: Способ раскроя Количество заготовок длиной Величина отходов, см. 50 см 30 см 20 см 1 2 0 0 0 2 1 1 1 0 3 1 0 2 10 4 0 3 0 10 5 0 2 2 0 6 0 1 3 10 7 0 0 5 0 Пример 2. Способы раскроя кожи. Определите все рациональные способы раскроя прямоугольного куска кожи размером 100 60 ∗ см на квадратные заготовки со сторонами 50, 40 и 20 см и укажите величину отходов для каждого способа. 4 Решение.Для данного материала и указанных заготовок существует шесть различных рациональных способов раскроя. Все они приведены в следующей таблице: Способ раскроя Количество заготовок длиной Величина отходов, см. 50 см 40 см 20 см 1 2 0 0 1000 2 1 1 2 1100 3 1 0 6 1100 4 0 2 7 0 5 0 1 11 0 6 0 0 15 0 Пример 3. Изготовление парников из металлических стержней. При изготовлении парников используется материал в виде металлических стержней длиной 220 см. Этот материал разрезается на стержни длиной 120, 100 и 70 см. Для выполнения заказа требуется изготовить 80 стержней длиной 120 см, 120 стержней длиной 100 см и 102 стержня длиной 70 см. Ответьте на следующие вопросы: 1. Сколько существует рациональных способов раскроя? 2. Какое минимальное количество материала следует разрезать, чтобы выполнить заказ? 3. Сколько способов раскроя следует использовать при выполнении заказа? Решение.Для данного материала и указанных заготовок существует пять различных рациональных способов раскроя. Все они приведены в следующей таблице: Способ раскроя Количество заготовок длиной Величина отходов, см. 120 см 100 см 70 см 1 1 1 0 0 2 1 0 1 30 3 0 2 0 20 4 0 1 1 50 5 0 0 3 10 5 Используем модель A для одного вида материала. Тогда xi – количество единиц материала, раскраиваемых по i -му способу. Для ответа на второй и третий вопросы задачи получаем следующую модель линейного программирования с критерием «минимум общего количества используемого материала»: 1 x 2 x 3 x 4 x 5 x Min 1 1 1 1 1 Заготовка 120 см 1 1 0 0 0 ≥ 80 Заготовка 100 см 1 0 2 1 0 ≥ 120 Заготовка 70 см 0 1 0 1 3 ≥ 102 ( ) * 80, 0, 20, 0,34 X = – оптимальный план исходной задачи. ( ) 134 F x = – значение функционала. Таким образом, требуется разрезать 134 единиц материала, чтобы выполнить заказ. При выполнении заказа следует использовать три из пяти рациональных способов раскроя. Задача 1. Из прямоугольного листа железа размером 100 60 ∗ см необходимо изготовить квадратные заготовки со сторонами 50, 40 и 20 см. Эти заготовки нужны в качестве перегородок при изготовлении пластмассовых коробок для хранения инструментов. Чтобы сделать одну коробку, нужно иметь четыре заготовки со стороной 50 см, шесть заготовок со стороной 40 см и двенадцать – со стороной 20 см. На складе находится 100 листов материала. Ответьте на следующие вопросы: 1. Сколько существует рациональных способов раскроя? 2. Какое максимальное количество коробок можно изготовить при условии, что оставшиеся заготовки можно использовать для следующей партии коробок? 3. Сколько рациональных способов раскроя следует использовать? 4. Сколько листов материала нужно, чтобы изготовить одну коробку? 6 Решение.Для данного материала и указанных заготовок существует шесть различных рациональных способов раскроя. Все они приведены в следующей таблице: Способ раскроя Количество заготовок длиной Величина отходов, см. 50 см 40 см 20 см 1 2 0 0 1000 2 1 1 2 1100 3 1 0 6 1100 4 0 2 7 0 5 0 1 11 0 6 0 0 15 0 Используем модель A для одного вида материала. Тогда 1 6 x x − – количество единиц материала, раскраиваемых по способам 1 - 6, 7 x – количество изготовленных коробок. Используя пакет MathCad 14, исходную информацию для решения этой задачи можно представить в виде следующей таблицы: 1 x 2 x 3 x 4 x 5 x 6 x 7 x Max 0 0 0 0 0 0 1 Заготовка 50 см 2 1 1 0 0 0 -4 ≥ 0 Заготовка 40 см 0 1 0 2 1 0 -6 ≥ 0 Заготовка 20 см 0 2 6 7 11 15 -12 ≥ 0 Материал 1 1 1 1 1 1 0 ≤ 100 ( ) * 0,80, 0, 20, 0, 0, 20 X = – оптимальный план исходной задачи. ( ) 20 F x = – значение функционала. Можно максимально изготовить 20 коробок при условии, что оставшиеся заготовки можно использовать для следующей партии коробок. При этом можно использовать два способа рационального раскроя. Задача 2. Существует три рациональных способа раскроя единицы материала А на заготовки трех типов. Эти же заготовки могут быть получены двумя рациональными способами при раскрое единицы материала В. Количество 7 заготовок, получаемых каждым из этих способов, показано в следующей таблице: Заготовка Материал А Материал В Способ 1 Способ 2 Способ 3 Способ 4 Способ 5 1 0 2 9 1 5 2 4 3 2 5 4 3 10 6 0 8 0 Заготовки используются для производства бытовой техники. В комплект поставки входят четыре заготовки первого типа, три заготовки второго типа и семь — третьего типа. На складе имеется 100 единиц материала А и 300 единиц материала В. Ответьте на следующие вопросы: 1. Сколько рациональных способов раскроя следует использовать? 2. Какое максимальное число комплектов заготовок можно изготовить из имеющегося материала в предположении, что оставшиеся заготовки можно использовать при выполнении следующего заказа? 3. Сколько единиц материала А следует раскраивать третьим способом? 4. Какое максимальное число комплектов заготовок можно изготовить из имеющегося материала, если число заготовок второго типа в комплекте увеличится до семи? Решение.Для данного материала и указанных заготовок существует пять различных рациональных способов раскроя. Используем модель A для одного вида материала. Тогда 1 5 x x − – количество единиц материала, раскраиваемых по способам 1 - 5, 6 x – количество изготовленных комплектов. Используя пакет MathCad 14, исходную информацию для решения этой задачи можно представить в виде следующей таблицы: 8 1 x 2 x 3 x 4 x 5 x 6 x Max 0 0 0 0 0 1 Заготовка 1 0 2 9 1 5 -4 ≥ 0 Заготовка 2 4 3 2 5 4 -3 ≥ 0 Заготовка 3 10 6 0 8 0 -7 ≥ 0 Материал А 1 1 1 0 0 0 ≤ 100 Материал В 0 0 0 1 1 0 ≤ 300 ( ) * 0, 0,100, 280, 20,320 X = – оптимальный план исходной задачи. ( ) 320 F x = – значение функционала. Используется три рациональных способа раскроя из пяти. Из имеющегося материала можно изготовить 320 комплектов заготовок. Третьим способом следует раскраивать все 100 единиц материала А. Для ответа на последний вопрос задачи увеличим количество заготовок в комплекте с 3 до 7. 1 x 2 x 3 x 4 x 5 x 6 x Max 0 0 0 0 0 1 Заготовка 1 0 2 9 1 5 -4 ≥ 0 Заготовка 2 4 3 2 5 4 -7 ≥ 0 Заготовка 3 10 6 0 8 0 -7 ≥ 0 Материал А 1 1 1 0 0 0 ≤ 100 Материал В 0 0 0 1 1 0 ≤ 300 ( ) * 22.5, 0, 77.5,300, 0, 249.3 X = – оптимальный план исходной задачи. ( ) 249 F x = – значение функционала. Задача 3. При раскрое деталей для производства единственного изделия на швейной фабрике используются два артикула ткани. Ширина ткани 1 м. Изделие собирается из двух деталей, причем каждая из них может быть получена путем раскроя ткани любого типа. Ткани можно раскраивать тремя способами, количество деталей каждого вида, полученных из одного погонного метра ткани, указано в следующей таблице: 9 Деталь Ткань 1 Ткань 2 Способ 1 Способ 2 Способ 3 Способ 4 Способ 5 Способ 6 1 8 0 4 12 0 6 2 0 3 1 0 5 2 Ткани 1 поступает на фабрику в 2 раза больше (по длине), чем ткани 2. Количество готовых изделий должно быть максимальным. Ответьте на следующие вопросы: 1. Сколько способов раскроя ткани 1 следует использовать? 2. Какая часть (в %) ткани 1 должна быть раскроена способом 1? 3. На сколько (в %) изменится выход готовых изделий по сравнению с первоначальным, если на фабрику будет поступать равное количество обеих тканей? Решение.Для данного материала и указанных заготовок существует шесть различных рациональных способов раскроя. Предположим, что на фабрику поступает 100 м ткани 2. Тогда ткани 1 поступает 200 м. Используем модель A для одного вида материала. Тогда 1 6 x x − – количество единиц материала, раскраиваемых по способам 1 - 6, 7 x – количество изготовленных комплектов. Используя пакет MathCad 14, исходную информацию для решения этой задачи можно представить в виде следующей таблицы: 1 x 2 x 3 x 4 x 5 x 6 x 7 x Max 0 0 0 0 0 0 1 Деталь 1 8 0 4 12 0 6 -1 ≥ 0 Деталь 2 0 3 1 0 5 2 -1 ≥ 0 Ткань 1 1 1 1 0 0 0 0 ≤ 200 Ткань 2 0 0 0 1 1 1 0 ≤ 100 ( ) * 100,100, 0, 0,100, 0,800 X = – оптимальный план исходной задачи. ( ) 800 F x = – значение функционала. Предположим, что на фабрику оба вида ткани поступают в равных количествах. Тогда при условии, что общее количество ткани остается 10 неизменным и используя пакет MathCad 14, исходную информацию для решения этой задачи можно представить в виде следующей таблицы: 1 x 2 x 3 x 4 x 5 x 6 x 7 x Max 0 0 0 0 0 0 1 Деталь 1 8 0 4 12 0 6 -1 ≥ 0 Деталь 2 0 3 1 0 5 2 -1 ≥ 0 Ткань 1 1 1 1 0 0 0 0 ≤ 150 Ткань 2 0 0 0 1 1 1 0 ≤ 150 ( ) * 109.1, 40.9, 0, 0,150, 0,872.7 X = – оптимальный план исходной задачи. ( ) 872 F x = – значение функционала. Таким образом, следует использовать 2 способа раскроя ткани 1. Способом 1 должна быть раскроена 100 / 200 = 0,5 (50%) часть ткани 1. На (872 – 800) / 800 = 0,09 (9%) по сравнению с первоначальным изменится выход готовых изделий, если на фабрику будет поступать равное количество обеих тканей. Задача 4. На производство поступила партия стержней длиной 250 и 190 см. Необходимо получить 470 заготовок длиной 120 см и 450 заготовок длиной 80 см. Отходы должны быть минимальны. Ответьте на следующие вопросы: 1. Какое количество стержней длиной 250 см надо разрезать? 2. Какое количество стержней длиной 190 см надо разрезать? 3. Какова величина отходов (в см)? 4. Оказалось, что количество стержней длиной 250 см ограничено и равно 200 шт. Какое количество стержней длиной 190 см надо разрезать в этом случае? 5. На сколько при этом увеличатся отходы (в см)? Решение.Для данного материала и указанных заготовок существует пять различных рациональных способов раскроя материала, показанных в таблице: Заготовка Стержень 250 см Стержень 190 см 120 см 2 1 0 1 0 80 см 0 1 3 0 2 Отходы 10 50 10 70 30 11 Задача минимизации отходов при условии выполнения задания по изготовлению заготовок описывается следующей моделью: 1 x 2 x 3 x 4 x 5 x Min 10 50 10 70 30 Заготовка 120 см 2 1 0 1 0 = 470 Заготовка 80 см 0 1 3 1 2 = 450 ( ) * 235, 0,150, 0, 0 X = – оптимальный план исходной задачи. ( ) 3850 F x = – значение функционала. При условии, что количество материала длиной 250 см ограничено, получаем модифицированную модель: 1 x 2 x 3 x 4 x 5 x Min 10 50 10 70 30 Заготовка 120 см 2 1 0 1 0 = 470 Заготовка 80 см 0 1 3 1 2 = 450 Стержень 250 см 1 1 1 0 0 ≤ 200 ( ) * 200, 0, 0, 70, 225 X = – оптимальный план исходной задачи. ( ) 13650 F x = – значение функционала. Таким образом, 235 + 0 + 150 = 385 стержней длиной 250 см нужно разрезать. Стержней, длиной 190 см разрезать не нужно. Величина отходов равна 3850 см. Если количество стержней длиной 250 см ограничено и равно 200 шт., то нужно разрезать 70 + 225 = 295 стержней длиной 190 см. Отходы при этом увеличатся на 13650 – 3850 = 9800 см. Задача 5. Завод заключил договор на поставку комплектов стержней длиной 18, 23 и 32 см. Причем количество стержней разной длины в комплекте должно быть в соотношении 1:5:3. На сегодняшний день имеется 80 стержней длиной по 89 см. Как их следует разрезать, чтобы количество комплектов было максимальным? Ответьте на следующие вопросы: 1. Сколько существует рациональных способов раскроя? 12 2. Сколько комплектов стержней будет выпущено? 3. Какова при этом величина отходов (в см)? Решение.Определяем рациональные способы раскроя материала каждого вида на заготовки. Получаем девять способов, показанных в следующей таблице: Задача максимизации количества комплектов при ограничении на количество используемого материала описывается следующей моделью: 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x Max 0 0 0 0 0 0 0 0 0 1 Стержень 32 см 2 2 1 1 1 0 0 0 0 -3 ≥ 0 Стержень 23 см 1 0 2 1 0 3 2 1 0 -5 ≥ 0 Стержень 18 см 0 1 0 1 3 1 2 3 4 -1 ≥ 0 Материал 1 1 1 1 1 1 1 1 1 0 ≤ 80 ( ) * 40, 0,10, 0, 0,30, 0, 0, 0,30 X = – оптимальный план исходной задачи. ( ) 30 F x = – значение функционала. Существует девять рациональных способов раскроя. Будет выпущено 30 комплектов стержней. При этом величина отходов равна 40 * 2 + 10 * 11 + 30 * 2 = 250 см. Способ раскроя Стержень 1 2 3 4 5 6 7 8 9 32 см 2 2 1 1 1 0 0 0 0 23 см 1 0 2 1 0 3 2 1 0 18 см 0 1 0 1 3 1 2 3 4 Отходы 2 7 11 16 3 2 7 12 17 13 |