Відмінності між версіями «Задача оптимального розкрою матеріалів»

Версія за 19:27, 10 травня 2012

Задача оптимального розкрою матеріалів

• На підприємстві здійснюється розкрій Неможливо розібрати вираз (невідома помилка): m

різних партій ма-теріалів у обсягах Неможливо розібрати вираз (невідома помилка): b_i(i=\overline{1,m})
 одиниць однакового розміру в кожній партії.

• Із матеріалів усіх партій потрібно виготовити максимальну кількість комплектів Неможливо розібрати вираз (невідома помилка): Z , у кожен з яких входить Неможливо розібрати вираз (невідома помилка): p

різних видів окремих частин в кількості Неможливо розібрати вираз (невідома помилка): k_r(r=\overline{1,p})
 одиниць,

• враховуючи, що кожну одиницю матеріалу можна розкроїти на окремі частини Неможливо розібрати вираз (невідома помилка): n

різними способами, 

• причому у разі розкрою одиниці Неможливо розібрати вираз (невідома помилка): i -ої партії Неможливо розібрати вираз (невідома помилка): j -им способом отримуємо Неможливо розібрати вираз (невідома помилка): a_{ijr}

деталей Неможливо розібрати вираз (невідома помилка): r

-го виду.

Запишемо математичну модель задачі. Позначимо через:
• Неможливо розібрати вираз (невідома помилка): x_{ij}

— кількість одиниць матеріалу Неможливо розібрати вираз (невідома помилка): i

-ої партії, що будуть розкроєні Неможливо розібрати вираз (невідома помилка): j -им способом.
• Тоді з Неможливо розібрати вираз (невідома помилка): i -ої партії за Неможливо розібрати вираз (невідома помилка): j -го способу розкрою отримаємо Неможливо розібрати вираз (невідома помилка): a_{ijr}

Неможливо розібрати вираз (невідома помилка): x_{ij}
деталей Неможливо розібрати вираз (невідома помилка): r

-го виду.
• З усієї ж Неможливо розібрати вираз (невідома помилка): i -ої партії у разі застосування до неї всіх Неможливо розібрати вираз (невідома помилка): n

способів розкрою отримаємо Неможливо розібрати вираз (невідома помилка):  \sum_{j=1}^n a_{ijr}  x_{ij}
 деталей Неможливо розібрати вираз (невідома помилка): r

-го виду,
• а з усіх Неможливо розібрати вираз (невідома помилка): m

партій їх буде отримано Неможливо розібрати вираз (невідома помилка): Z_r=\sum_{i=1}^m \sum_{j=1}^n a_{ijr} x_{ij}

.

У кожен комплект має входити Неможливо розібрати вираз (невідома помилка): k_r(r=\overline{1,p})

деталей, тому відношення Неможливо розібрати вираз (невідома помилка): Z_r/k_r(r=\overline{1,p})
визначає кількість комплектів, які можна виготовити з деталей Неможливо розібрати вираз (невідома помилка): r

-го виду. Кількість повних комплектів для всіх видів деталей визначається найменшим з цих відношень.

У разі повного комплекту має виконуватися рівність відношень:

звідки Неможливо розібрати вираз (невідома помилка): p

— 1 відношення можна виразити через будь-яке з них, наприклад, через перше:

Неможливо розібрати вираз (невідома помилка): (r=\overline{2,p})
або Неможливо розібрати вираз (невідома помилка): Z_r=k_rZ_1/k_1 
Неможливо розібрати вираз (невідома помилка): (r=\overline{2,p}) 

Замінивши Неможливо розібрати вираз (невідома помилка): Z_r

та Неможливо розібрати вираз (невідома помилка): Z_1
їх значеннями, отримаємо Неможливо розібрати вираз (невідома помилка): p
– 1 обмеження стосовно комплектів:

Враховуючи наявну кількість одиниць матеріалу в партіях, запишемо Неможливо розібрати вираз (невідома помилка): m

обмежень щодо ресурсів:

Неможливо розібрати вираз (невідома помилка): (i=\overline{1,m})

(Обмеження щодо використання ресурсів можуть бути рівняннями чи нерівностями залежно від того, повністю чи не повністю необхідно використати наявний обсяг ресурсів).
Всі Неможливо розібрати вираз (невідома помилка): x_{ij}

мають задовольняти умову невід’ємності: 

Неможливо розібрати вираз (невідома помилка): x_{ij}\ge 0(i=\overline{1,m},j=\overline{1,n})

та цілочисловості.
Отже, необхідно знайти найбільше значення функції:

за обмежень: