Модель задачи оптимального раскроя

ЗНАЧЕНИЕ УПАКОВКИ В ПИЩЕВОЙ ПРОМЫШЛЕННОСТИ

УПАКОВОЧНЫХ МАТЕРИАЛОВ

Тема 6. ОПТИМИЗАЦИЯ ВАРИАНТОВ РАСКРОЯ

Продукция пищевой промышленности выпускается, как правило, в упакованном виде. Увеличение выпуска фасованной продукции влечет за собой увеличение производства упаковочного материала.

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

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

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

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

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

П₁ размером 20 х 30 см,

П₂ – 30 х 40 см,

П₃ – 40 х 40 см.

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

П₁ П₁ П₁ П₁ П₁

П₁

П₂ П₂ П₃ П₃ П₃

П₁

П₁ П₁ П₁

П₂ П₃ П₁ П₁

П₁ П₁ П₁

П₁ П₁

П₁ П₁ П₁ П₁ П₁

Рис. 7.1. Способы раскроя картона на заготовки.

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

При каждом способе раскроя (Mi) получено определенное количество заготовок:

М₁ – П₁ - 3, П₂ – 2, П₃ – 1;

М₂ – П₁ - 4, П₃ – 2;

М₃ – П₁ - 5, П₂ – 1, П₃ – 1;

М₄ – П₁ - 10.

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

Таблица 7.1

Исходные данные для решения задачи раскроя материала

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

Если через X_j (j=1, 2, 3, 4) обозначить число листов картона, раскраиваемых соответственно способами M_j, то исходную систему уравнений можно записать в виде:

3Х₁ + 4Х₂ + 5Х₃ + 10Х₄ = 240

2Х₁ + Х₃ = 100 ( 7.1 )

Х₁ + 2Х₂ + Х₃ = 80

Целевая функция, предусматривающая минимизацию отходов:

F = 200 Х₁ + 400 Х₂ + 200 Х₃ = min. ( 7.2 )

Все неизвестные удовлетворяют условию неотрицательности X_j ³ 0, j=1,2,3,4. ( 7.3 )

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

X_j—число листов или другого материала, раскраиваемых j-м способом;

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

b_i—число потребных заготовок i-го размера (вида);

C_j— величина (размер) отходов материала, получаемых при раскрое j-м способом.

В этом случае задача оптимального раскроя материалов формализуется следующим образом.

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

F = = min . ( 7.4 )

Система уравнений, характеризующая:

, i = 1,2,…,m ( 7.5 )

Неотрицательность неизвестных X_j ³ 0, j = 1,2,…,n . ( 7.6 )

Задача состоит в определении неотрицательные значения неизвестных Х_j, (j = 1,2,…,n) с m линейными ограничениями, заданными системой уравнений ( 7.5 ) и обеспечивающие минимальное значение целевой функции, выраженной уравнением ( 7.4 ).