Методы оптимизации раскроя материалов

Цель работы: Закрепление знаний в области экономико-математического моделирования, знакомство с методикой решения задачи рационального раскроя материалов, основанной на решении оптимизационной задачи линейного программирования.

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

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

Первая работа, посвященная решению задач, названных впоследствии задачами линейного программирования, появилась в 1939 г. Это была книга Л.В.Канторовича "Математические методы организации и планирования производства". Толчком для ее появления послужила задача, поставленная перед Институтом математики и механики Ленинградского Государственного университета лабораторией фанерного треста. В других отраслях промышленности также успешно применялись экономико-математические методы оптимизации раскроя материалов. Так, еще в 1948 - 1949 гг. математические методы раскроя были успешно применены на вагоностроительном заводе им. Егорова в Ленинграде, что позволило снизить в несколько раз отходы при раскрое различных материалов.

Математическая модель задачи.

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

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

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

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

L - длина материала; S - площадь поверхности листового или рулонного материала; N - количество единиц исходного материала.

Необходимо получить m различных видов заготовок либо длиной L_i, либо площадью S_i, где i - вид заготовки (i=1, 2,..., m).

Известно число заготовок i -го вида в изделии, т.е. то число заготовок, которое необходимо для производства одного изделия - b_i. Число комплектов изделий, выпускаемых предприятием обозначим через k.

Раскрой материала можно произвести n способами. Известно а_ij - число заготовок i -го вида, получаемое j -м способом (j =1, 2, …, n).

Количество отходов, получаемое при раскрое единицы исходного материала j -м способом - С_j.

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

Обозначим через x_j количество единиц исходного материала, раскроенных j -м способом. Найти такие x_j ³ 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Х₁+Х₂+Х₃+Х₄=2k;

2,5 метровых заготовок Х₂+2Х₅+Х₆+Х₇=3k;

2-х метровых заготовок Х₆+3Х₈+2Х₉+Х₁₀=2k;

1,5 метровых заготовок 2Х₄+Х₆+2Х₇+Х₉+2Х₁₀+4Х₁₁=2k.

Ограничение по исходным материальным ресурсам:

Х₁ + Х₂ + Х₃ + Х₄ + Х₅ + Х₆ + Х₇ + Х₈ + Х₉ + Х₁₀ + Х₁₁ = 100

Функция цели (при условии минимизации отходов):

f(х) = 0,5Х₂ + Х₃ + Х₅ + 0,5Х₇ + 0,5Х₉ + Х₁₀ → min.

Приведем задачу к каноническому виду. Обозначим количество комплектов k через переменную Х₁₂, тогда модель примет вид:

Х₁+Х₂+Х₃+Х₄+Х₅+Х₆+Х₇+Х₈+Х₉+Х₁₀+Х₁₁ = 100

2Х₁+Х₂+Х₃+Х₄ -2Х₁₂ = 0

Х₂+2Х₅+Х₆+Х₇ -3Х₁₂ = 0

Х₆+3Х₈+2Х₉+Х₁₀ -2Х₁₂ = 0

2Х₄+2Х₆+2Х₇+Х₉+2Х₁₀+4Х₁₁ -2Х₁₂ = 0

X_j ≥ 0, j = 1, 2, …, 12,

функция цели (на минимум отходов)

f(x)= 0,5Х₂+Х₃+Х₅+0,5Х₇+0,5Х₉+Х₁₀ → min,

функция цели (на максимум комплектов)

f(x)= Х₁₂ → 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

Решение данной задачи с помощью программы “Симплекс-метод”, реализованной на ЭВМ, дает следующие результаты:

Количество выпускаемых комплектов Х₁₂ = 28;

1-м вариантом раскраивается Х₁=28 прутков;

5-м вариантом раскраивается Х₅=14 прутков;

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. Выводы по лабораторной работе должны содержать анализ и экономическую интерпретацию результатов моделирования.