Моделювання задачі на розкрій однорідного матеріалу

Заготовки деталей довжиною l_i виробляються з однорідного матеріалу, що має один вимір (фіксовану довжину L). Необхідно знайти такий технологічно допустимий план розкрою матеріалу на заготовки, при якому забезпечується планова потреба в заготовках і досягається максимальна ефективність використання ресурсу.

Ця задача власне складається з двох задач:

· знаходження множини технологічних способів розкрою матеріалу на заготовки;

· знаходження інтенсивності використання технологічних способів розкрою.

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

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

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

В загальному випадку формування множини альтернативних технологічних способів можна здійснити у такій послідовності:

1. Впорядковуємо заготовки за спаданням їх довжин:

.

2. Фіксуємо i, тобто вибираємо заготовку найбільшої довжини.

3. Фіксуємо j, тобто формуємо певний технологічний спосіб.

4. Знаходимо максимальне число заготовок a_ij, які можна виготовити з одиниці матеріалу:

, (65)

де [ ] - ант’є, ціла частина числа.

5. Розраховуємо залишок матеріалу d_j:

. (66)

6. Якщо , , то вибираємо впорядковану групу заготовок, довжини яких не більші за залишок матеріалу d_j і переходимо до п.8.

7. Якщо , то сформовано технологічний спосіб. Переходимо до п.11.

8. Вибираємо із групи заготовок заготовку найбільшої довжини.

9. Розраховуємо максимальне число заготовок a_ij, які можна виготовити із залишку матеріалу d_j:

.

10. Переходимо до п.5.

11. Зменшуємо число заготовок найбільшої довжини на одиницю:

.

12. Якщо , то переходимо на п.3.

13. Якщо , то переходимо на п.2.

14. Процес продовжується до встановлення (перебору) всіх можливих технологічних способів.

Після встановлення множини альтернативних варіантів технологічних способів визначається інтенсивність їх використання, тобто кількість одиниць матеріалу, яка буде розрізатися за тим чи іншим технологічним способом.

Для побудови формальної моделі введемо такі позначення:

x_j - шукана кількість одиниць матеріалу, яка розрізається за j -им технологічним способом (інтенсивність використання j -го способу);

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

Обмеження на планову потребу в заготовках має вид:

. (67)

В якості функції мети можна розглядати "мінімум залишку матеріалу":

. (68)

Якщо врахувати, що x_j може набирати цілі невід’ємні значення, то (67), (68) можна розглядати як найпростішу модель задачі на розкрій.

У випадку можливості виробництва певної кількості заготовок у запас обмеження (67) зведеться до такого вигляду:

, (69)

, (70)

де u_i - додаткова змінна величина, яка характеризує надлишок заготовок i -го виду;

z_i - розрахункова чисельність заготовок i -го виду.

З урахуванням обмежень (69), (70) функція мети (68) зведеться до такого виду:

, (71)

тобто мінімізується довжина матеріалу, який знаходиться у залишку або в запасі.

Зауважимо, що в якості функції мети можна розглядати "мінімум одиниць матеріалу, які підлягають розкрою":

. (72)

Цю задачу можна доповнити умовою комплектності виробництва заготовок, яка має вид:

, (73)

де l₁,..., l_m - коефіцієнти пропорційності виробництва заготовок.

 

Приклад 4.

Необхідно розкроїти металеві прутки довжиною L₁ =200 см на заготовки трьох видів довжиною l₁ =80 см, l₂ =60 см, l₃ =50 см. Планова потреба в заготовках становить: першого виду - 120 шт.; другого виду - 140 шт.; третього виду - не менше 235 шт.

Для побудови економіко-математичної моделі задачі попередньо визначимо множину альтернативних технологічних способів розкрою металевого прутка (табл.2.)

Таблиця 2.

Варіанти технологічних способів розкрою металевого прутка, L₁ =200 см

j i	x1	x2	x3	x4	x5	x6	x7	Планова потреба в заготовках, шт.
l1 =80 см				-	-	-	-
l2 =60 см	-						-
l3 =50 см	-	-		-
Залишок, см								-

 

Числова модель задачі має вид:

де z₃ - число деталей третього виду;

u₃ - додаткова змінна, яка характеризує розмір виробництва деталей третього виду понад планову потребу.