Простейшая модель оптимального раскроя материала

 

На многих промышленных предприятиях при массовом производстве продукции необходимо получить наиболее рациональный раскрой материалов (доски, листы металла, трубы, прокат, рулоны ткани и т.д.). План раскроя считается оптимальным, если он обеспечивает наибольший выход заготовок или наименьший объём отходов.

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

На предприятие поступают однотипные рулоны материалов. Надо найти такой план раскроя рулонов материала по ширине, при котором будут наименьшие отходы.

Введём обозначения:

i – вид заготовки, m – число всех видов заготовок;

j – вариант раскроя рулона по ширине, n – число всех вариантов раскроя;

d_i – необходимое число заготовок i -го вида;

d_ij – число заготовок i -го вида, которое можно получить из одного рулона материала согласно j -му варианту раскроя;

С_j – отходы материала, полученные из рулона материала согласно j -му варианту раскроя;

A – общее количество рулонов, имеющихся в наличии;

x_j – искомое число рулонов, раскраиваемых согласно j -му варианту.

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

Это задача линейного программирования, для решения которой можно применить симплекс-метод.

Теперь рассмотрим модель оптимального раскроя партий материалов для изготовления комплектов.

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

s – номер партии материала, S – число всех партий материалов;

i – вид заготовки;

l_i – число заготовок i -го вида, необходимых для одного комплекта;

n – число всех комплектов;

d_s – количество материалов одного размера в одной партии s -го вида;

j – номер варианта раскроя;

n_s – число вариантов раскроя для каждой единицы s -й партии;

d_sij – число заготовок i -го вида, получаемых из единицы материала s -й партии согласно j -му варианту раскроя;

x_sj – искомое количество единиц материала s -й партии, раскраиваемых согласно j -му варианту.

При раскрое всех партий будет получено заготовок i -го вида.

Их достаточно для комплектов.

Поскольку число комплектов минимизируется теми заготовками, которые позволяют составить наименьшее число комплектов, то число полных комплектов равно:

.

Задача состоит в максимизации числа комплектов

при условии выполнения плана раскроя заготовок

,

а также неотрицательности компонент

 

.

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

 

при ограничениях