Глава 3. оптимальный раскрой

Глава 3. оптимальный раскрой

Цели

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

После того как вы выполните задания, предлагаемые в этой главе, вы будете уметь формулировать и использовать для экономического анализа следующие понятия:

• материал;

• заготовка;

• отходы;

• способ раскроя (рациональный и оптимальный);

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

Модели

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

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

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

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

Пусть 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-м способом;

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

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

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

cji — величина отхода, полученного при раскрое единицы 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 см.

Вопросы:

1. Сколько существует рациональных способов раскроя?

2. Какое минимальное количество материала следует разрезать, чтобы выполнить заказ?

3. Сколько способов раскроя следует использовать при выполнении заказа?

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

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

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

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

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

Вопросы

Вопрос 1. Способ раскроя называется рациональным, если:

1) он является безотходным;

2) он обеспечивает минимум отходов;

3) отходы меньше любой из заготовок;

4) он позволяет получить наибольшее число заготовок;

5) нет другого способа, дающего не меньше заготовок каждого типа.

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

Варианты ответов:

1) шт.; 2) см; 3) шт./см; 4) см/шт.;

5) безразмерная величина.

Вопрос 3. Рассматривается задача оптимального раскроя кожи для пошива перчаток. В соответствующей модели линейного программирования учитывается ограничение на количество материала. Правая часть ограничения измеряется в штуках кожи. Максимизируется количество пар пошитых перчаток. В каких единицах измеряется двойственная оценка ресурсного ограничения?

Варианты ответов:

1) шт.; 2) пара; 3) пара/шт.; 4) шт./пара; 5) безразмерная величина.

Вопрос 4. Сколько существует рациональных способов раскроя металлического стержня длиной 100 см на стержни длиной 50, 20 и 10 см?

Варианты ответов:

1) более десяти; 2) десять; 3) девять;

4) восемь; 5) менее восьми.

Вопрос 5. Какое из следующих утверждений является верным?

Варианты ответов:

1) безотходный способ раскроя является рациональным;

2) безотходный способ раскроя может быть рациональным;

3) безотходный способ раскроя не является рациональным;

4) рациональный способ раскроя является безотходным;

5) рациональный способ раскроя не является безотходным.

Задачи

Задача 1. Из прямоугольного листа железа размером 100 х 60 см необходимо изготовить квадратные заготовки со сторонами 50,40 и 20 см. Эти заготовки нужны в качестве перегородок при изготовлении пластмассовых коробок для хранения инструментов. Чтобы сделать одну коробку, нужно иметь четыре заготовки со стороной 50 см, шесть заготовок со стороной 40 см и двенадцать — со стороной 20 см. На складе находится 100 листов материала.

Вопросы:

1. Сколько существует рациональных способов раскроя?

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

3. Сколько рациональных способов раскроя следует использовать?

4. Сколько листов материала нужно, чтобы изготовить одну коробку?

Задача 2. Существует три рациональных способа раскроя единицы материала А на заготовки трех типов. Эти же заготовки могут быть получены двумя рациональными способами при раскрое единицы материала В. Количество заготовок, получаемых каждым из этих способов, показано в следующей таблице:

Заготовки используются для производства бытовой техники. В комплект поставки входят четыре заготовки первого типа, три заготовки второго типа и семь — третьего типа. На складе имеется 100 единиц материала А и 300 единиц материала В.

Вопросы:

1. Сколько рациональных способов раскроя следует использовать?

2. Какое максимальное число комплектов заготовок можно изготовить из имеющегося материала в предположении, что оставшиеся заготовки можно использовать при выполнении следующего заказа?

3. Сколько единиц материала А следует раскраивать третьим способом?

4. Какое максимальное число комплектов заготовок можно изготовить из имеющегося материала, если число заготовок второго типа в комплекте увеличится до семи?

Задача 3. При раскрое деталей для производства единственного изделия на швейной фабрике используются два артикула ткани. Ширина ткани 1 м. Изделие собирается из двух деталей, причем каждая из них может быть получена путем раскроя ткани любого типа. Ткани можно раскраивать тремя способами, количество деталей каждого вида, полученных из одного погонного метра ткани, указано в следующей таблице:

Ткани 1 поступает на фабрику в 2 раза больше (по длине), чем ткани 2. Количество готовых изделий должно быть максимальным.

Вопросы:

1. Сколько способов раскроя ткани 1 следует использовать?

2. Какая часть (в \%) ткани 1 должна быть раскроена способом 1?

3. На сколько (в \%) изменится выход готовых изделий по сравнению с первоначальным, если на фабрику будет поступать равное количество обеих тканей?

Задача 4. На производство поступила партия стержней длиной 250 и 190 см. Необходимо получить 470 заготовок длиной 120 см и 450 заготовок длиной 80 см. Отходы должны быть минимальны.

Вопросы:

1. Какое количество стержней длиной 250 см надо разрезать?

2. Какое количество стержней длиной 190 см надо разрезать?

3. Какова величина отходов (в см)?

4. Оказалось, что количество стержней длиной 250 см ограничено и равно 200 шт. Какое количество стержней длиной 190 см надо разрезать в этом случае?

5. На сколько при этом увеличатся отходы (в см)?

Задача 5. Завод заключил договор на поставку комплектов стержней длиной 18, 23 и 32 см. Причем количество стержней разной длины в комплекте должно быть в соотношении 1:5:3. На сегодняшний день имеется 80 стержней длиной по 89 см. Как их следует разрезать, чтобы количество комплектов было максимальным?

Вопросы:

1. Сколько существует рациональных способов раскроя?

2. Сколько комплектов стержней будет выпущено?

3. Какова при этом величина отходов (в см)?

Ответы и решения

Ответы на вопросы: 1—5, 2 — 4, 3—3, 4—2, 5 — 1.

Задача 1. Решение.

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

Получаем шесть рациональных способов раскроя:

Пусть х1, ..., х6 — количество единиц материала, раскроенных соответствующим способом, х7 — количество изготовленных коробок. Тогда ответ на второй вопрос можно получить, используя следующую модель:

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

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

Значение двойственной оценки показывает, что при увеличении количества материала на один лист можно дополнительно изготовить 0,2 коробки.

В следующей таблице приведены границы устойчивости:

Учитывая границы устойчивости по ограничению «материал», можно сделать вывод, что для изготовления одной коробки требуется пять листов железа.

Ответы: I. Шесть способов. 2. 20 коробок. 3. Два способа. 4. Пять листов.

Задача 2. Решение.

Заметим, что всего существует пять рациональных способов раскроя.

Пусть х1, ..., х5 — количество единиц материала, раскроенных соответствующим способом, х6 — количество комплектов. Тогда используем следующую модель:

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

Используется три рациональных способа раскроя из пяти. Из имеющегося материала можно изготовить 320 комплектов заготовок. Третьим способом следует раскраивать все 100 единиц материала А. Для ответа на последний вопрос задачи увеличим количество заготовок в комплекте с 3 до 7. Получим следующий результат:

Ответы: 1. Три способа. 2. 320 комплектов. 3. 100 единиц. 4. 249 комплектов.

Задача 3. Решение.

Предположим, что на фабрику поступает 100 м ткани 2. Тогда ткани 1 поступает 200 м. Модель оптимального раскроя будет иметь следующий вид:

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

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

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

Ответы: 1. Два способа. 2.50\%. 3. На 9\%.

Задача 4. Решение.

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

Задача минимизации отходов при условии выполнения задания по изготовлению заготовок описывается следующей моделью:

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

При условии, что количество материала длиной 250 см ограничено, получаем модифицированную модель:

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

Ответы: 1. 385 стержней. 2. 0. 3. 3850см. 4. 295 стержней. 5. На 9800 см.

Задача 5. Решение.

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

Задача максимизации количества комплектов при ограничении на количество используемого материала описывается следующей моделью:

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

Ответы: 1. Девять способов. 2. 30 комплектов. 3. 250см.