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

Для изготовления парников используется материал в виде металлических стержней длиной 220 см. тот материал разрезается на стержни длиной 120, 100 и 70 см. Для выполнения заказа требуется изготовить 80 стержней длиной 120 см, 120 стержней длиной 100 см и 102 стержня длиной 70 см.

Вопросы:

1. Сколько существует рациональных способов раскроя?

2. Какое минимальное количество материала следует разрезать, чтобы выполнить заказ?

3. Сколько способов раскроя следует использовать при выполнении заказа?

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

Виды заготовок	Способы раскроя из стержня 220 см
	x1	x2	x3	x4	x5
Заготовка 120 см	1	1	0	0	0
Заготовка 100 см	1	0	2	1	0
Заготовка 70 см	0	1	0	1	3
Величина отходов, см	0	30	20	50	10

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

Для нахождения решения используем модель А для одного вида материала.

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

Константы

1. Пусть a_kj – количество (целое число) заготовок вида k, полученных при раскрое единицы k-го материала j-м способом; где k=1,2,3; j=1,2,3,4,5 (в данной задаче i=k).

	1	1	0	0	0
akj =	1	0	2	1	0
	0	1	0	1	3

2. Пусть b_k – число заготовок вида k в комплекте, поставляемом заказчику; k – индекс вида заготовки, к = 1,2,3.

b₁ =80 – число заготовок длиной 120 см;

b₂ =120 – число заготовок длиной 100 см;

b₃ =102 – число заготовок длиной 70 см;

Переменные

1. Обозначим через x_j – количество единиц материала, раскраиваемых по j-му способу (интенсивность использования способа раскроя), то есть:

x₁ – количество материала , раскраиваемого по способу 1;

… x₅ - количество материала , раскраиваемого по способу 5.

2. Обозначим через F_k фактическое количество заготовок k, то есть F₁ – фактическое количество заготовок 120 см; F₂ – фактическое количество заготовок 100 см; F₃ – фактическое количество заготовок 70 см.

3. Обозначим через N количество материала (количество металлических стержней длиной 220 см), которое следует разрезать, чтобы выполнить заказ.

Решение

1.Зададим математическую модель нахождения фактического количества заготовок k

или

2. Зададим математическую модель нахождения общего количества материала (количества металлических стержней длиной 220 см) N=x₁+x₂+x₃. Его минимизация является целью решения задачи. Следовательно, целевая функция будет иметь вид:

Ограничения

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

или

2. Количество заготовок должно быть целым числом.

3. Поскольку x₁, x₂, x₃, x₄, x₅,выражают количество заготовок, то они не могут быть отрицательны, то есть x₁≥0; x₂≥0; x₃≥0; x₄≥0, x₅≥0.