Методы оптимизации раскроя материалов
Цель работы: Закрепление знаний в области экономико-математического моделирования, знакомство с методикой решения задачи рационального раскроя материалов, основанной на решении оптимизационной задачи линейного программирования.
Исходные положения. Изготовление многих видов современной промышленной продукции начинается с раскроя материалов, что является одной из важных производственных задач для заготовительного производства и органов материально-технического снабжения.
Задачи оптимального раскроя материалов - одни из первых задач, к решению которых применялись методы линейного программирования. Они заключаются в определении наилучшего способа раскроя поступающего материала, при котором будет изготовлено наибольшее число готовых изделий в заданном ассортименте или будет получено наименьшее количество отходов.
Первая работа, посвященная решению задач, названных впоследствии задачами линейного программирования, появилась в 1939 г. Это была книга Л.В.Канторовича "Математические методы организации и планирования производства". Толчком для ее появления послужила задача, поставленная перед Институтом математики и механики Ленинградского Государственного университета лабораторией фанерного треста. В других отраслях промышленности также успешно применялись экономико-математические методы оптимизации раскроя материалов. Так, еще в 1948 - 1949 гг. математические методы раскроя были успешно применены на вагоностроительном заводе им. Егорова в Ленинграде, что позволило снизить в несколько раз отходы при раскрое различных материалов.
Математическая модель задачи.
Поступающие на предприятие материалы подлежат раскрою на заготовки. От правильности раскроя зависит себестоимость продукции (используется, например на автозаводах и в др.).
В большинстве случаев раскрой материалов на заготовки производится в определенной пропорции, обеспечивающей получение комплекта заготовок (т.е. кратно комплекту).
Задача оптимизации раскроя материалов заключается в разработке таких вариантов раскроя, при которых получают определенное количество заготовок в данном ассортименте (разных видов) с минимальными отходами.
Для составления математической модели задачи оптимального раскроя введем следующие обозначения:
L - длина материала; S - площадь поверхности листового или рулонного материала; N - количество единиц исходного материала.
Необходимо получить m различных видов заготовок либо длиной Li, либо площадью Si, где i - вид заготовки (i=1, 2, ..., m).
Известно число заготовок i-го вида в изделии, т.е. то число заготовок, которое необходимо для производства одного изделия - bi. Число комплектов изделий, выпускаемых предприятием обозначим через k.
Раскрой материала можно произвести n способами. Известно аij - число заготовок i-го вида, получаемое j-м способом (j =1, 2, …, n).
Количество отходов, получаемое при раскрое единицы исходного материала j-м способом - Сj.
Требуется составить такой план раскроя, чтобы обеспечить получение полных комплектов заготовок с минимальными отходами.
Обозначим через xj количество единиц исходного материала, раскроенных j-м способом. Найти такие xj ³ 0, которые удовлетворяют следующим ограничениям:
(ограничение по количеству исходного материала)
(1)
(ограничение по плану производства)
(2)
- столько получается заготовок i-го вида при всех вариантах раскроя. Исходя из условия комплектности получим следующие ограничения по плану производства:
(3)
Суммарная величина отходов должна быть минимальной, тогда функция цели примет вид:
(4)
Пример расчетов в задаче оптимального раскроя материалов.
Из металлических прутков длиной по 6 м каждый, имеющихся в количестве 100 шт. необходимо изготовить конструкцию, изображенную на рис.1.
 |
Найти оптимальный план раскроя материала, чтобы количество отходов было минимальным при условии получения полных комплектов заготовок для изготавливаемых конструкций.
Решение.
Имеется N=100 прутков.
Длина прута l=6 м.
Деталей на один комплект требуется:
длиной 1,5 м - 2 шт.,
длиной 2 м - 2 шт.,
длиной 2,5 м - 3 шт.,
длиной 3 м - 2 шт.
Определим возможные варианты раскроя материала (прутков):
3м 3м
1) |-----------------------------|-----------------------------| без отходов
3м 2,5м 0,5м
2) |-----------------------------|--------------------------|---| отходы 0,5 м
3м 2 м 1м
3) |-----------------------------|----------------------|------| отходы 1 м
3м 1,5м 1,5м
4) |-----------------------------|--------------|---------------| без отходов
2,5м 2,5м 1м
5) |--------------------------|-------------------------|-------| отходы 1 м
2,5м 2м 1,5м
6) |--------------------------|----------------------|----------| без отходов
2,5м 1,5м 1,5м 1м
7) |--------------------------|-------------|------------|------| отходы 1 м
2м 2м 2м
8) |--------------------|--------------------|------------------| без отходов
2м 2м 1,5м 0,5м
9) |--------------------|--------------------|---------------|---| отходы 0,5 м
2м 1,5м 1,5м 1м
10)|-------------------|----------------|---------------|--------| отходы 1 м
1,5м 1,5м 1,5м 1,5м
11)|---------------|--------------|---------------|--------------| без отходов
Представим в табличном виде количество различного вида заготовок, получаемых с помощью всех возможных вариантов раскроя и требование по комплектации изделия.
Количество заготовок по вариантам раскроя
| Виды заготовок | Варианты раскроя | Кол-во заготовок на комплект | ||||||||||
| 3 м | - | - | - | - | - | - | - | |||||
| 2,5 м | - | - | - | - | - | - | - | |||||
| 2 м | - | - | - | - | - | |||||||
| 1,5 м | - | - | - | - | - | |||||||
| Отходы | - | 0,5 | - | - | 0,5 | - | 0,5 | - | min отходов |
В соответствии с имеющимися вариантами раскроя и условиями комплектности, получаем общее количество
3-х метровых заготовок 2Х1+Х2+Х3+Х4=2k;
2,5 метровых заготовок Х2+2Х5+Х6+Х7=3k;
2-х метровых заготовок Х6+3Х8+2Х9+Х10=2k;
1,5 метровых заготовок 2Х4+Х6+2Х7+Х9+2Х10+4Х11=2k.
Ограничение по исходным материальным ресурсам:
Х1 + Х2 + Х3 + Х4 + Х5 + Х6 + Х7 + Х8 + Х9 + Х10 + Х11 = 100
Функция цели (при условии минимизации отходов):
f(х) = 0,5Х2 + Х3 + Х5 + 0,5Х7 + 0,5Х9 + Х10 → min.
Приведем задачу к каноническому виду. Обозначим количество комплектов k через переменную Х12, тогда модель примет вид:
Х1+Х2+Х3+Х4+Х5+Х6+Х7+Х8+Х9+Х10+Х11 = 100
2Х1+Х2+Х3+Х4 -2Х12 = 0
Х2+2Х5+Х6+Х7 -3Х12 = 0
Х6+3Х8+2Х9+Х10 -2Х12 = 0
2Х4+2Х6+2Х7+Х9+2Х10+4Х11 -2Х12 = 0
Xj ≥ 0, j = 1, 2, …, 12,
функция цели (на минимум отходов)
f(x)= 0,5Х2+Х3+Х5+0,5Х7+0,5Х9+Х10 → min,
функция цели (на максимум комплектов)
f(x)= Х12 → max.
Решение данной задачи с помощью программы “Симплекс-метод” проводится следующим образом: вводится число переменных N=11 и число ограничений M=4. Для решения модель записывается следующим образом:
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 | X12 | ||
| = | |||||||||||||
| -2 | = | ||||||||||||
| -3 | = | ||||||||||||
| -2 | = | ||||||||||||
| -2 | = | ||||||||||||
| 0,5 | 0,5 | 0,5 | min |
Решение данной задачи с помощью программы “Симплекс-метод”, реализованной на ЭВМ, дает следующие результаты:
Количество выпускаемых комплектов Х12 = 28;
1-м вариантом раскраивается Х1=28 прутков;
5-м вариантом раскраивается Х5=14 прутков;
6-м вариантом раскраивается Х6=57 прутков;
остальные 8 вариантов раскроя оказались невыгодными - Х2,3,4=0, Х7-11=0, отходы составили f(x)=14 метров.
Порядок выполнения работы.
1. Изучение студентами исходных положений и экономико-математической постановки задачи оптимального раскроя материалов.
2. Разбиение студенческой подгруппы на бригады и получение ими исходного задания.
3. Определение возможных вариантов раскроя с помощью графических построений.
4. Построение математической модели оптимального раскроя в общем виде, приведение модели к каноническому виду и составление матрицы исходных данных для расчета задачи на ЭВМ.
5. Расчет производится с помощью программы "Решение задач линейного программирования симплекс-методом", реализованной на ПЭВМ в табличном процессоре “Excel” или комплексе программ для учебного процесса "Prima".
6. Анализ и экономическая интерпретация результатов моделирования на ЭВМ, которые должны быть отражены в выводах по работе.
Отчет по работе должен содержать
1. Цель и экономико-математическую постановку задачи на раскрой материалов, графические построения вариантов раскроя.
2. Экономико-математическую модель в общем и каноническом виде, исходные данные для расчета на ЭВМ.
3. Результаты моделирования на ЭВМ и их экономическую интерпретацию.
4. Выводы по лабораторной работе должны содержать анализ и экономическую интерпретацию результатов моделирования.