РОЗДІЛ 2. МЕТОДИ ТА ОСНОВНІ МАТЕМАТИЧНІ МОДЕЛІ РОЗВ'ЯЗКУ ЗАДАЧ ОДНОВИМІРНОГО РОЗКРОЮ
Згідно аналізу, проведеного в розділі 1, задачі одновимірного розкрою оптимально розв'язуються методами дискретної математики. Методи рішення задач дискретного програмування засновані на багатократному розв'язку задачі, послабленої до лінійної. Склад змінних, обмежень, векторів вхідних потоків комплектності та асортиментного набору послідовності задач розкрою в випадку ЛР набувають ознак варіювання [82]. Оптимальне рішення послідовності задач розкрою передбачає, що при розв'язку наступної задачі слід починати з повтору , за умови, що * - оптимальний розв'язок попередньої задачі, а для отримання допустимого базисного плану необхідно використовувати , де - вектор цін базисних змінних.
За наявною статистикою близько 40 % вирішуваних на практиці задач ЛП не мають допустимих розв'язків та сформульованих моделей [8,88]. Користувача не влаштовує повідомлення про суперечність введеної інформації, йому необхідно знати причини і рекомендації для корегування даних. Для цього можна, варіюючи коефіцієнти ЦФ штучних змінних початкового базисного плану, встановити пріоритети обмежень або надати їх підбір користувачу. В цьому випадку можна вирішувати багато різних задач, використовуючи один оптимізаційний модуль [42].
Існує необхідність врахування в моделі розкрою рівня витрат та цін, характеристик ТП, стохастичних факторів. Розкрій матеріалу пов'язаний із факторами, які набувають змін в ТП згідно з фазами циклу.
2.1. Постановка задачі одновимірного розкрою матеріалу
Задача визначається векторами довжини , комплектності та ціни матеріалу . Отже розмірність задачі . Перші компонент векторів та стосуються матеріалу, останні компонент описують відповідно довжини та комплектність заготовок. Карта розкрою описується вектором , де - множина допустимих значень цільової функції. Нехай - кількість допустимих власних КР, тоді, розкрійна матриця описує всі КР.
Відповідно, в задачі шуканими є набір власних карт розкрою, вектор інтенсивностей розкрою , що належить до наборів карт розкрою. Даний вектор мінімізує ціну сировини, що використовується в розкроях, за умов виконання комплектностей і не перевищенні допустимої кількості одиниць матеріалу карти розкроїв, В якості розв'язків приймаємо лише допустимі КР, адже завжди існує таке оптимальне рішення, яке використовує тільки такі карти [8].
Умова допустимості КР записується:
, .
В зв'язку з тим, що постановка задачі одновимірного розкрою зводиться до багатокритеріальної задачі лінійного програмування, формальний запис такої задачі лінійного програмування має вид [78]:
, , (2.1)
де - набір цільових функцій, що потребують оптимізації.
ЦФ математичної моделі розкрою мінімізується за умови впливу векторів технологічної корекції базисних планів розкроїв і корегуючого коефіцієнта залишкової задачі , що перетворює математичну модель на бікритеріальну.
Для того, щоб сформулювати ЛП - задачу до умов необхідно додати критерій оптимальності розв'язку. А ЦФ сформулювати у вигляді: при , тут - вектор цін матеріалу карти розкрою; - корегуючий коефіцієнт логістичної обробки, що впливає на остаточний залишок наступного матеріалу для крою після проведення партії розкроїв.
Вектор цін заготовок описується: , , .
З огляду на (2.1) математична модель одновимірного розкрою записується:
, (2.2)
де - коефіцієнт ЦФ;
з нерівностями
, , (2.3)
, , (2.4)
де - кількість КР;
- кількість заготовок;
- стовбець матриці обмежень, що характеризує КР;
- вектор комплектності заготовок і матеріалу;
- вектор розв'язку,
та обмеженням ЦФ виду:
, (2.5)
де - корегуючий технологічний коефіцієнт при розкрою матеріалу.
Обмеження (2.5) ЛП задачі математичної моделі характеризує власні карти розкрою , які необхідно отримати при розв'язку задачі.
Багатокритеріальна задача лінійного програмування розв'язується так, як і однокритеріальна, тобто с використанням покрокового методу. Відмінність полягає в способі завдання ідеального вектору, який визначається за формулою [78]:
, (2.6)
де - розмірність задачі.
Врахування відносної важливості ЦФ реалізується евристично на основі експертних оцінок.
2.2. Чисельні методи розв'язку задачі лінійного розкрою
Задачі розкроїв, як було відмічено раніше, найчастіше зводяться до задачі лінійної або дискретної оптимізації [34,82,96]. Розмірність таких задач утруднює пряме застосування відомих математичних методів. Задачі оптимізації розкроїв різняться за структурою змінних, зв'язків з загальної інформаційною системою технологічної підготовки виробництва, критерієм ефективності і ЦФ.
Одновимірний розкрій є цілочисельною або змішаною цілочисельною задачею у вигляді:
та ,
де - розмірність розкрійної матриці , - стовбець матриці обмежень ;
- рядок матриці , а - рядок - некеровані змінні задачі розкрою;
та - стовбці керованих змінних за умови, що , або , або .
Вираз трактується як " зіставно з 0" і означає, що всі компоненти вектора приймають лише цілочисельні значення.
За умови цілочисельності і дискретності розв'язків задача розкрою може бути розв'язана як лінійна. Тоді можна представити розв'язок задачі ЛР як лінійну релаксацію ЛП, в результаті чого отримаємо оптимальне рішення цієї лінійної задачі, що задовольняє умові цілочисельності [68,91]. Це можна зробити