Определение рациональных способов раскроя материала.

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

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

Пусть к — индекс вида заготовки, к = 1,..., q;

i – индекс способа раскроя единицы материала, i = 1,..., q;

a_ik – количество (целое число) заготовок вида к, полученных при раскрое единицы материала i -м способом.

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

Способ раскроя v называется рациональным (оптимальным по Парето), если для любого другого способа раскроя i из соотношений a_ik >a_vk, к=1,..., q, следуют соотношения a_ik = a_vk, к=1,..., q.

 

Определение интенсивности использования рациональных способов раскроя.

Обозначения:

j – индекс материала, j = 1,..., n;

к – индекс вида заготовки, к = 1,..., q;

i – индекс способа раскроя единицы материала, i = 1,..., р;

a_jik – количество (целое число) заготовок вида к, полученных при раскрое единицы j -го материала i -м способом;

b_к – число заготовок вида к в комплекте, поставляемом заказчику;

d_j – количество материала j -го вида;

x_ji – количество единичного материала, раскраиваемых по i -му способу (интенсивность использования способа раскроя);

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

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

 

Модель А раскроя с минимальным расходом материалов:

 

(1)

, где к = 1,..., q (2)

, где j = 1,..., n; i = 1,..., р; (3)

 

Здесь (1) – целевая функция (минимум количества используемых материалов);

(2) – система ограничений, определяющих количество заготовок, необходимое для выполнения заказа;

(3) – условия неотрицательности переменных.

Специфическими для данной области приложения модели линейного программирования являются ограничения (2).

 

Модель В раскроя с минимальными отходами:

 

(4)

, где к = 1,..., q (5)

, где j = 1,..., n; i = 1,..., р; (6)

 

Здесь (4) – целевая функция (минимум отходов при раскрое материалов);

(5) – система ограничений, определяющих количество заготовок, необходимое для выполнения заказа;

(6) – условия неотрицательности переменных.

 

Модель С раскроя с учетом комплектации:

, (7)

, где j = 1,..., n; (8)

, где к = 1,..., q (9)

, где j = 1,..., n; i = 1,..., р; (10)

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

(8) – ограничения по количеству материалов;

(9) – система ограничений, определяющих количество заготовок, необходимое для формирования комплектов;

(10) – условия неотрицательности переменных.

Специфическими для данной области приложения модели линейного программирования являются ограничения (9).

 

 

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

 

Исходная постановка задачи

Фирма производит две модели А и Б сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем использования станков. Для каждого изделия модели А требуется 3 м² досок, а для изделия модели Б – 4 м². Фирма может получать от поставщиков до 1 700 м² досок в неделю. Для каждого изделия модели А требуется 12 мин. станочного времени, а для изготовления модели Б – 30 мин. В неделю можно использовать до 160 часов станочного времени.

Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А приносит 10 000 руб. прибыли, а каждое изделие модели Б – 20 000 руб. прибыли?

 

Составим для наглядности таблицу исходных данных.

 

	Модели полок	Общий объем в неделю
Модель А	Модель Б
Доски	3 м2	4 м2	1 700 м2
Станки	12 мин.	30 мин.	160 час.
Прибыль	10 000 руб.	20 000 руб.