Задачи оптимизации раскроя

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

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

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

Знакомство с задачами раскроя начнем с линейного раскроя.

Пример 10.1. Из 50 шт. брусьев длиной 6,5 м необходимо изготовить наибольшее число комплектов, в состав каждого из которых входит 2 шт. детали длиной 2 м и 3 шт. детали длиной 1,25 м.

Есть два подхода к решению задач раскроя:

1. Раскрой делает ЭВМ.

2. Лицо, принимающее решение (ЛПР) принимает несколько различных вариантов раскроя, а ЭВМ выбирает лучший из них.

Подход 1. Раскрой делает ЭВМ

Постановка задачи.

1. В качестве показателя эффективности целесообразно взять число комплектов K, которое можно получить из заданного числа заготовок. Возможна другая постановка: в качестве показателя эффективности берётся число заготовок Z, которое необходимо иметь, чтобы получить заданное число комплектов.

2. В качестве управляемых переменных задачи следует взять x_A и x_B. Соответственно число деталей А и В, получаемых из одной заготовки.

3. Целевая функция:

W₁ = K® max;

или

W₂ = Z ® min.

4. Ограничения:

4.1. По длине заготовки, м:

2 x_A + 1,25 x_B £ 6,5.

4.2. По комплектности, шт.:

k x_A - 2 K ³ 0;

k x_B - 3 K ³ 0,

где

k - число заготовок.

Областные ограничения и требования целочисленности:

x_A ³ 0, x_B ³ 0, K ³ 0 - целые.

При решении задачи в первой постановке (k=50)

на ЭВМ получено: x_A=2; x_B=2; K=33. Это означает, что если из одной заготовки выкраивать детали длиной по 2 м и две детали по 1,25 м, то максимальное количество комплектов будет равно 33.

Подход 2. ЛПР принимает несколько различных вариантов раскроя, а ЭВМ выбирает лучший из них

Сырье может раскраиваться на заготовки различными способами - вариантами (картами) раскроя, которые сводятся в специальную таблицу. В этой таблице указывается требуемое число заготовок каждого вида и величина отходов для каждого варианта раскроя. Допустим, в нашем примере ЛПР разработал 4 варианта, которые приведены в табл. 10.1. Отметим, что вариант, предложенный ЭВМ в первом подходе, указан в таблице как одна из альтернатив.

Таблица 10.1.

Постановка задачи.

1. В качестве показателя эффективности целесообразно взять число комплектов K, которое можно получить из заданного числа заготовок. Возможна другие постановка: берётся число заготовок Z, которое необходимо иметь, чтобы получить заданное число комплектов или отходы O.

2. В качестве управляемых переменных задачи следует взять:

x₁ - число заготовок, раскраиваемых по 1 варианту;

x₂ - число заготовок, раскраиваемых по 2 варианту;

x₃ - число заготовок, раскраиваемых по 3 варианту;

x₄ - число заготовок, раскраиваемых по 4 варианту.

3. Целевая функция:

W₁ = K® max;

или

W₂ = Z ® min;

или

W₃ = O = 0,5 x₁ + 0 x₂ + 0,75 x₃ + 0,25 x₄ ® min.

4. Ограничения:

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

x₁ + x₂ + x₃ + x₄ = k,

где k - число заготовок.

4.2. По комплектности, шт.:

3 x₁ + 2 x₂ + x₃ - 2 K ³ 0;

2 x₂ + 3 x₃ + 5 x₄ - 3 K ³ 0.

Областные ограничения и требования целочисленности:

x_A ³ 0, x_B ³ 0, K ³ 0 - целые.

При решении задачи в первой постановке (k=50)

на ЭВМ получен результат, представленный в табл. 10.2.

Таблица 10..2.

Из таблицы 10.2 видно, что существует пять равноценных вариантов раскроя, которые приводят к получению 41 комплекта из 50 заготовок. Если данный результат сравнить с результатом, полученным по первому подходу (33 комплекта из тех же самых 50 заготовок), то получаем выигрыш в 8 комплектов. Следовательно, для лучшего использования сырья целесообразно использовать сочетание различных вариантов раскроя.

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