1.4. Задача про мінімізацію відходів

Модель задачі про раціональний розкрій матеріалів має важливе значення для економії матеріалів і сировини. Розглянемо постановку задачі.

На розкрій надходить матеріал у вигляді певних одиниць стандартних розмірів. Потрібно з нього виготовити різних виробів. Задано асортимент цих виробів, тобто– відповідно нижня і верхня границі кількості виробівi-го виду. Кожна одиниця вихідного матеріалу може бути розкроєна різними способами, причому використанняj-го способу дає одиницьi-го виробу . Відома величина відходівз одиниці стандартного матеріалу приj-му способі розкрою.

Необхідно знайти план розкрою, що забезпечує заданий асортимент виробів при мінімальних сумарних відходах матеріалів.

За невідому беремочисло одиниць вихідного матеріалу, що потрібно розкроїти j-v способом, тоді – план розкрою.Через позначимо загальну кількість відходів. Кількість заготовокi-го виду запишемо у вигляді .

Тоді математична модель задачі має вигляд:

.

Характер моделі може змінитися, якщо в умові задати іншу мету. Наприклад, якщо ставиться задача про одержання заданої кількості виробів з найменшою кількістю вихідного матеріалу, то функція мети має вигляд:

Побудувати математичну модель задачі.

Задача 1.4. Рулони лінолеуму довжиною 30 м треба розрізати на шматки довжиною 15, 10 та 6 м. Причому шматків по 15 м необхідно не більш 20, шматків по 10 м – не менш 16, а шматків по 6 м – не менше 12 та не більше 22. Визначити оптимальний план розкрою лінолеуму з точки зору мінімізації відходів.

Рішення

Позначимо через a₁, a₂ та a₃ кількість шматків довжиною відповідно 15, 10 та 6 м, що можуть бути одержані з одного рулону лінолеуму. Відповідно до умови задачі, вектор визначає спосіб розкрою рулону лінолеуму тоді і тільки тоді, коли виконана умова 0 ≤ 30 – (15а₁ + 10а₂ + 6а₃) < min{15; 10; 6} = 6.

Для визначення усіх можливих способів розкрою побудуємо відповідне дерево пошуку.

0

30303000

30

20

К 2ількість шматків

д

1

овжиною 15 м

0

30

0

3

0

1

15

0

15

2

1

0

2

Кількість шматків

0

0

0

довжиною 10 м

10

5

Кількість шматків

0

2

1

довжиною 6 м

0

0

5

3

0

3

5

Величина

відходів

4

Рис. 1.1

Вершини, що є кінцями шляхів, визначають величину відходів, отриманих після розкрою матеріалу. З рисунка видно, що усього існує 7 допустимих способів розкрою рулону лінолеуму. Запишемо ці способи розкрою у табл. 1.7.

Таблиця 1.7

Кількість шматків довжиною, м	Способи розкрою рулону лінолеуму
	1	2	3	4	5	6	7
15	0	0	0	0	1	1	2
10	0	1	2	3	0	1	0
6	5	3	1	0	2	0	0
Величина відходів	0	2	4	0	3	5	0

Позначимо через x_j кількість рулонів лінолеуму, що розкроюються j-м способом ( j = 1, 2, …, 7).

План розкрою визначається вектором .

Умови забезпечення необхідного асортименту задаються нерівностями:

.

При реалізації плану сумарна величина відходів є значенням функції

.

Таким чином, ми отримали наступну математичну модель: