ЗАГАЛЬНА ХАРАКТЕРИСТИК РОБОТИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
Сагун Андрій Вікторович
УДК 621.7.01:519.876.5(043)
МОДЕЛІ ТА МЕТОДИ ОПТИМІЗАЦІЇ В ЗАДАЧАХ ОДНОВИМІРНОГО РОЗКРОЮ МАТЕРІАЛУ НА МАШИНОБУДІВНИХ ПІДПРИЄМСТВАХ
01.05.02 – математичне моделювання та обчислювальні методи
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Черкаси – 2008
Дисертацією є рукопис.
Робота виконана в Черкаському державному технологічному університеті
Міністерства освіти і науки України.
Науковий керівник – доктор технічних наук, професор
Кожухівський Андрій Дмитрович,
Черкаський державний технологічний університет,
завідувач кафедри інформатики та інформаційної безпеки.
Офіційні опоненти – доктор технічних наук, професор
Середенко Валерій Миколайович,
Черкаський національний університет
ім. Богдана Хмельницького,
завідувач кафедри прикладної математики;
кандидат технічних наук, науковий співробітник
Панкратов Олександр Вікторович,
Інститут проблем машинобудування ім. А.М. Підгорного НАН України, м. Харків,
науковий співробітник відділу математичного моделювання та оптимального проектування.
Захист відбудеться « 26 » червня 2008 року о 14 год 30 хв. на засіданні спеціалізованої вченої ради К73.052.01 в Черкаському державному технологічному університеті за адресою: бул. Шевченка, 460, м. Черкаси, 18006.
З дисертацією можна ознайомитись у бібліотеці Черкаського державного технологічного університету за адресою: бул. Шевченка, 460, м. Черкаси, 18006.
Автореферат розісланий « 22 » травня 2008 року.
Вчений секретар
спеціалізованої вченої ради В.В. Пала гін
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми дослідження. Проблема оптимального використання сировини має велике значення для багатьох галузей промисловості. Для дискретних промислових підприємств це питання загострюється в зв’язку з прогресуючим подорожчанням сировини та матеріалів.
Вирішення задачі оптимізації розкроїв є важливою задачею організації виробництва. Відомі розв’язки задач отримання карт одновимірного розкрою матеріалу різної довжини, які не враховують факторів корекції технологічного процесу, але розв’язків задачі отримання карт одновимірного розкрою за умов їх системного поєднання з задачами стратегічного управління виробничим процесом та врахуванням корекції факторів зовнішнього впливу не існує. Тому оптимізація в задачах отримання одновимірних розкроїв є актуальною, а їх розв’язок доцільно здійснювати засобами лінійного програмування з використанням евристик на базі методу безперервної релаксації (БР) та врахуванням факторів корекції, які мають здатність швидко оптимізувати цей процес та уточнювати розв’язок за рахунок оптимального алгоритму отримання розв’язків при великій номенклатурі заготовок та деталей.
Проблемами одновимірного розкрою матеріалів займалися і займаються відомі вчені та дослідники: Л.В.Канторович, Д.М. Малишев, С.Г. Нікітов, А.М.Павлов, Г.Н. Бєлов, Ю.В. Бугаєв, В.А. Кузнєцов, А.І. Єрмаченко, Т.М.Сіразетдінов, К.Г. Андрєєва, Е.А. Мухачова, В.Л. Рвачов, Т.Є.Романова, О.В. Панкратов та інші.
В дисертаційній роботі розглядається загальний випадок отримання оптимальних карт одновимірного розкрою, коли на підприємстві використовується матеріал різної довжини, а оптимальність отриманих карт розкрою (КР) враховує вплив на математичну модель факторів зовнішнього середовища. При цьому задача одновимірного розкрою розв’язується в складі підсистеми АСУ виробництвом.
Зв’язок роботи з науковими програмами, планами, темами. Дисертаційну роботу виконано згідно з планом науково-дослідних робіт Черкаського державного технологічного університету в рамках госпрозрахункової науково-дослідної теми № 1-2007 (державний реєстраційний номер № 0107U008093) «Моделювання задачі плоского розкрою матеріалу в структурі інформаційної системи керування виробничим процесом», в якій автор був безпосереднім виконавцем.
Мета і завдання дослідження полягають у розробці та дослідженні математичної моделі одновимірного промислового розкрою матеріалу різної довжини на основі лінійного програмування (ЛП) та методу січних площин (МСП) з врахуванням факторів корекції математичної моделі.
Для досягнення мети розв’язані такі задачі:
1. Проаналізовані особливості існуючих математичних моделей та розроблена оптимізована математична модель одновимірного розкрою матеріалу різної довжини в АСУ дискретних виробництв;
2. Адаптовані та модифіковані існуючі методи та алгоритми дискретної оптимізації для задачі одновимірного розкрою матеріалу різної довжини в розв’язках безперервної релаксації;
3. Досліджені та сформульовані фактори корекції зовнішніх впливів на математичну модель одновимірного розкрою матеріалу;
4. Синтезовано алгоритм знаходження оптимальних планів розкрою на базі лінійного програмування та методу січних площин;
5. Досліджено ефективність розробленого алгоритму на основі серій тестових прикладів, характерних для машинобудівних підприємств;
6. Проведене комп’ютерне моделювання з метою перевірки достовірності теоретичних результатів дослідження ефективності застосування отриманого алгоритму.
Об’єктом дослідження є технологічні процеси оперативного розкрою у реальному вимірі часу, що враховують перерозподіл матеріалу при впровадженні нових виробів у виробництво.
Предметом досліджень є моделі та алгоритми розкрою в складі задачі АСУ машинобудівного підприємства за умов врахування впливу зовнішнього середовища.
Методи дослідження ґрунтуються на використанні теорії і методів системного аналізу виробничих систем, матричного аналізу, методів динамічного та лінійного програмування, методів дискретної оптимізації, теорії і методів дослідження операцій, теорії ймовірностей та математичної статистики, теорії інформаційної взаємодії.
Наукова новизна одержаних результатів полягає в тому, що автором вперше розв’язана задача оптимального одновимірного розкрою матеріалу різної довжини на машинобудівних підприємствах за умов системного поєднання задач стратегічного управління виробничим процесом, корекцією факторів зовнішнього впливу та мінімізацією відходу матеріалу.
Автором отримані наукові результати, які полягають в наступному:
- вперше розроблена бікритеріальна математична модель процесу одновимірного розкрою матеріалу різних довжин на базі лінійного програмування та методів дискретної оптимізації, яка дає змогу отримувати оптимальні розв’язки задачі майже у 4 рази швидше, порівняно з існуючими однокритеріальними математичними моделями;
- удосконалена математична модель одновимірного розкрою матеріалу різної довжини за рахунок введення в неї корегуючих коефіцієнтів, які враховують вплив факторів зовнішнього середовища та підвищують точність отримуваного розв’язку до 10%;
- набула подальшого розвитку модифікація критерію, за яким здійснюється процедура перевірки оптимальності розв’язків, що забезпечує можливість застосування методу послідовного уточнення оцінок для випадку групових одновимірних розкроїв матеріалу різної довжини;
- набула подальшого розвитку модифікація методу генерування карт розкрою за наявності матеріалу різної довжини на основі методу січних перерізів при неявно заданій матриці обмежень, що полягає в комбінації методу ЛП та евристик безперервної релаксації і дозволяє отримувати точний розв’язок задачі генерування групових одновимірних розкроїв засобами ЛП;
- запропонований метод розрахунку верхньої межі цільової функції при застосуванні МСП і евристик, що дає можливість одержання меж цільової функції (ЦФ) та конкретизації математичної моделі одновимірного розкрою матеріалу різної довжини.
Практичне значення одержаних результатів роботи полягає в тому, що на основі запропонованої математичної моделі, методів та критеріїв отримано:
- функціональну схему модуля одновимірного розкрою в складі АСУ машинобудівних виробництв, що дає змогу інтегрувати розроблену математичну модель до існуючої АСУ машинобудівного підприємства;
- програмне забезпечення, яке дає змогу збільшити коефіцієнт корисного використання сировини розкрою до 99,8% для окремих класів задач та збільшити частку отримуваних оптимальних КР засобами ЛП до 90% (замість 60%, які існують на сьогоднішній час);
- сформульовані еталонні результати, що дають змогу детермінувати класи практичних задач, що є оптимальними для практичного застосування запропонованої математичної моделі;
- результати порівняння продуктивності розроблених моделей та методів на широкому класі задач з аналогічними, описаними в фахових наукових джерелах.
Модель, що розроблена автором в 2006 році, успішно впроваджена у виробництво на ЗАТ «Кіровоградський завод дозуючих автоматів» у складі інформаційної системи «Інтеграл» та на ВАТ «Черкаський приладобудівний завод».
Особистий внесок здобувача. Дисертація є самостійно виконаною завершеною роботою здобувача. Наукові розробки, узагальнення, висновки та пропозиції, що містяться в дисертацій роботі, одержані автором самостійно.
В публікаціях, написаних в співавторстві, здобувачеві належать: [5] – сформульована методика отримання корегуючого коефіцієнту, що враховує вплив факторів зовнішнього середовища на математичну модель одновимірного розкрою; [6] – сформулюванні процедури цілочисельного округлення безперервного рішення, розширення задачі залишку з врахуванням коефіцієнту технологічної корекції.
Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались Міжнародній науково-практичній конференції «Сучасні наукові досягнення - 2007» (Дніпропетровськ, 2007); Міжнародній науково-практичній конференції «Обробка сигналів і негаусівських процесів» (Черкаси, 2007).
Публікації. Основні наукові результати опубліковані у восьми наукових роботах, серед яких – шість у наукових виданнях, які входять до переліку ВАК України та двох виданнях міжнародних науково-практичних конференцій.
Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, списку використаних літературних джерел і додатків (102 найменування). Дисертація містить 24 таблиці, 18 рисунків, 5 додатків на 49 сторінках. Повний обсяг дисертації становить 197 сторінок, у тому числі 146 сторінок основного тексту.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обґрунтовано актуальність теми дисертаційної роботи, визначено мету і задачі дослідження, сформульовано наукову новизну і практичне значення отриманих результатів, наведені відомості про апробацію, публікації та використання результатів дослідження. У вступі також обґрунтовано доцільність вдосконалення існуючих математичних моделей розкрою матеріалу для машинобудівних підприємств з метою отримання ефективніших ЛП – алгоритмів, що зменшить часову та ресурсну місткості таких задач.
У першому розділі проведено загальний аналіз моделей та методів розкрою та пакування матеріалу та простору. На основі даного аналізу наведена класифікація відомих методів розкрою-комплектування, що дозволяє обмежити розгляд математичних методів, моделей та задач розкрою до лінійної задачі, серед яких можна виділити евристичні та точні методи.
Виявлено, що проблеми одновимірного розкрою виникають в умовах: формування оперативно – календарного планування ремонтного виробництва; планування роботи виробництва упаковки; оптимізації АСУ заготівельного, основного та допоміжного виробництва тощо.
Різноманітність моделей одновимірного розкрою викликає необхідність розробки спеціальних засобів вирішення, пов’язаних з ними оптимізаційних задач, які містять елементи: методу гілок та меж, динамічного програмування, генерації стовпців матриці обмежень, використання евристичних та спеціальних алгоритмів генерації розкроїв, інтерактивного рішення задачі в діалозі з оператором, методів перебору.
Включення до математичної моделі лінійного розкрою корегуючого технологічного коефіцієнту дозволяє точніше визначити кількість первинного заготівельного матеріалу, кількість відходу та відсотку браку крою. Даний коефіцієнт слід використати в якості цільового при отримані розв’язків ЦФ.
Виявлено, що реалізація симплексного методу (СМ) в отриманні карт одновимірного та плоского розкрою є ускладненою через відсутність ефективних евристик. Знаходження або модифікація таких евристик для даного методу ЛП є важливими та необхідними.
В другому розділі виконано аналіз основних існуючих обчислювальних методів, математичних моделей та методик розв’язку задач одновимірного розкрою, що дозволяє зробити висновок про можливість отримання оптимальних розв’язків таких задач за рахунок застосування дискретного програмування.
Зроблено постановку задачі одновимірного розкрою та сформульована математична модель у вигляді:
, (1)
де - коефіцієнт ЦФ (вектор ціни), - вектор розкрою. Виразу (1) відповідають нерівності:
, , (2)
, , (3)
де - кількість КР;
- кількість заготовок;
- стовбець матриці обмежень, що характеризує КР;
- вектор комплектності заготовок і матеріалу;
- вектор розв’язку.
Обмеженням ЦФ, яке має вигляд:
, (4)
де - корегуючий технологічний коефіцієнт при розкрої матеріалу;
Для того, щоб сформулювати ЛП – задачу, до виразів (1-4) необхідно додати критерій оптимальності розв’язку. ЦФ має вигляд: при , зокрема - вектор цін матеріалу карти розкрою, - множина векторів КР, - корегуючий коефіцієнт логістичної обробки, що впливає на остаточний залишок наступного матеріалу для крою після проведення партії розкроїв.
В основі алгоритму розв’язку лежить послаблення задачі до рівня лінійної, що дозволяє отримати оцінки її розв’язку .
Процес обчислення ЦФ розкрою закінчується, коли кожна підмножина векторів не містить жодного кращого рішення, ніж ті, що є в наявності.
В зв’язку з тим, що одновимірний розкрій розглядається як цілочисельна задача, то її рішення визначаються лінійною релаксацією ЛП. Тому рішення можливо отримувати як розв’язки на кінцевій множині (дерево перебору) з використанням гілкових схем. Використання такої схеми потребує розробки ефективних методів розрахунку верхньої і нижньої межі задачі. ЛП - межа обчислюється шляхом відміни вимоги цілочисельності змінних таким чином:
, (5)
за умов, що:
, і ,, (6)
де - залишкова змінна для -го обмеження.
Вирази (6) є нижньою межею і основою для оцінки евристичного розв’язку початкової задачі.
Щоб з’ясувати, чи є оптимальним симплекс-розв’язок, розв’язується така задача генерації розкрою , за умов, що - вектор подвійних оцінок одиничних деталей крою, - стовбець трансформованого коефіцієнту ЦФ обмеження стовбцем , - розкрійна матриця.
Розрахунок верхньої межі вимагає розробки ефективного евристичного алгоритму її розрахунку, а нижньої – покращення релаксації МСП. Наявність виникаючих в процесі релаксації обмежень підзадачі розкрою потребує виділення нових обмежень динамічного характеру у вигляді бінарних змінних. Це дає можливість ефективного одержання границь та конкретизації моделі.
Алгоритм МСП для задачі лінійного розкрою (ЛР) можна представити у вигляді:
Крок 1. Нехай комплектність , кількість ітерацій МСП , найкраще відоме значення ЦФ .
Крок 2. Здійснюємо безперервну релаксацію (БР): вектор безперервного розв’язку , де - кількість січних площин. Обчислення БР відбувається згідно виразу:
,
де - матриця обмежень безперервної релаксації в - ітерації;
- комплектність матеріалу в -й ітерації;
- вектор безперевного рішення в - ітерації МСП.
Крок 3. Виконується округлення поелементно до нижніх цілих і формулювання з не отриманих заготовок задачі залишку. Шляхом евристичного рішення задачі залишку та з врахуванням нижньої границі конструюємо допустиме цілочисельне рішення . У випадку, якщо , необхідно встановити нове значення верхньої границі ЦФ: .
Крок 4. Якщо найкраще відоме значення ЦФ відповідає найменшій лінійній невід’ємній комбінації цін матеріалу, що є більшою або рівною :
де - комплектність матеріалу;
- кількість типу матеріалу;
- вектор найкращого відомого значення ЦФ основної задачі розкрою;
- комплектність заготовок;
- номер елементу, що вноситься в симплексному методі,
тоді оптимальне рішення знайдене, робота алгоритму закінчується.
Крок 5. Виконується конструювання січних та додавання їх до матриці , видалення неактивних січних і збільшення кількості ітерацій на 1. Далі виконується перехід до кроку 2.
За умови відміни вимоги цілочисельності в (5) може бути застосований симплекс-метод (крок 1). При цьому обчислюється нижня ЛП – межа ЦФ. При додаванні січних (введенні умов) вона стає точнішою, а безперервне рішення стає більш близьким до цілочисельного, що полегшує побудову евристичного допустимого рішення (крок 2). Тест оптимальності рішення використовує відповідну ЛП – границю (крок 3).
Для генерації січних Гоморі в математичних моделях одновимірного розкрою з існуючою неявною матрицею обмежень можна використати процедуру округлення (C-GRP).
Для побудови - векторів перерізів беруться рядки оптимальної зворотної базисної матриці, тобто базисні перерізи.
З додатковими обмеженнями задача ЛР набуває наступного виду , або в канонічному вигляді:
,
де - множина всіх наявних розв’язків матриці задачі генерування КР.
В -й ітерації методу отримаємо порядкові коефіцієнти перерізів для залишкової змінної , , .
Перерізи, побудовані з першого кроку БР, недостатні, тому з оптимального базису розширеної матриці обмежень створюються перерізи більш високого рангу. Причому коефіцієнти таких перерізів залежать від попередніх перерізів таким чином:
, , (7)
де - - та компонента вектора , що генерує січні;
- номер вектора, що генерує січні.
Вираз (7) виконується за умови, що .
При визначенні оптимального рішення релаксації багато з перерізів не є активними, тобто вони не обмежують даного рішення, і відповідна подвійна змінна дорівнює 0. Через це в матриці обмежень видаляти можна лише ті перерізи, які не потрібні для побудови перерізів більш високого рангу.
Принцип видалення зайвих перерізів з базисного рішення можна сформулювати так: , для всіх . Далі виконується . В результаті виконання (7) перерізи не змінюються, а в оптимальному безперервному рішенні багато перерізів виконуються як рівності і не видаляються, але при цьому і не виступають активними (не обмежують розв’язку), якщо нормуючий параметр , а генерація стовпців КР при розв’язках БР в рамках існуючого симплексного розв’язку при знаходженні розв’язків БР полягає в необхідності пошуку КР, тобто відповідних стовпців матриці з мінімальним трансформованим коефіцієнтом ЦФ:
,
де - трансформований коефіцієнт ЦФ (ТКЦФ) матриці обмежень .
У випадку приблизно рівних відношень подвійних змінних до довжин заготовок () в методі гілок та меж генерація стовпців КР потребує постановки відповідної задачі, тобто необхідно, окрім власних КР, розглядати ще і залишкові змінні для введення в базис: .
При генерації власної КР розглядається зворотна задача:
,
де - значення ТКЦФ при цілочисельному розв’язку.
Кроки при виборі стовпця матриці полягають в наступному:
- обчислення найкращого ТКЦФ з протилежним знаком на множині залишкових стовпців .
- обчислення верхньої межі для ТКЦФ , де - ціна матеріалу - го типу, - довжина -ї заготовки;
- якщо верхня межа краща, ніж значення для додаткових змінних, тобто , тоді генеруються КР.
Для всіх рішення динамічного програмування (ДП) відповідає умові , якщо заготовка не обмежена розміром підрюкзака і за умови, що , отримаємо рівняння ДП для генерації КР:
,
де ;
- довжина -ї заготовки;
- значення подвійної змінної для -ї заготовки.
Для уточнення цілочисельних рішень і формування ознаки оптимальності необхідна добудова рішень СМ за рахунок евристичних алгоритмів. Оптимальною евристикою в такому випадку є метод дискретних точок при кожній генерації разом з розрахунком ЦФ.
Для того, щоб визначити максимум функції для даної довжини прутка , необхідний додатковий прохід, що визначається за формулою:
,
де визначається аналогічно , але із заготовками з -ї половини списку; РПМ – множина растрових пунктів. Потім вибирається кращий тип прутка згідно виразу: .
В цьому випадку є сенс програмувати динамічну таблицю, що генерує січні як динамічний ланцюг.
Щоб заощадити пам'ять, - значення зі всіх РП – перерізів для кожної що задовольняють умові , не зберігаються. Рішення відновлюється потім за методом гілок та меж (МГМ) за відомою ЦФ з деяким чисельним допуском.
Власні КР шукаються як розв’язок зворотної задачі:
,
де - коефіцієнт перерізів для стовбців матриці обмежень в МСП.
Функція є не сепарабельною за компонентами вектора , тому ДП в стандартній концепції є не доцільним в застосуванні. В цьому випадку застосовується метод гілок та меж.
Будь-яка остаточна змінна з негативним ТКЦФ вводиться до базису. При цьому розв’язок оберненої задачі набуває спрощення, приріст при додаванні заготовки в карту обмежень подвійної змінної має вигляд:
, .
В цьому випадку, через спрощення, виникає необхідність розрахунку верхньої межі для запобігання повного перебору.
У випадку генерування стовпців КР за наявності січних з декількома типами матеріалу, що підлягає розкрою, необхідно розв’язати для кожного типу прутка за умов відповідну зворотну задачу виду:
,
або розглядати всі заготовки в одному процесі розгалуження.
В методі гілок та меж для генерації стовпців при наявності перерізів зберігається той же принцип лексикографічного перебору, що і для варіанту без перерізів, а ЦФ може бути лінійно апроксимована шляхом опущення функції округлення в формулі коефіцієнтів перерізів. Наближені коефіцієнти перерізів є рекурсивними і формулюються так:
,
де - - та компонента вектора , що генерує січні в найменшій растровій точці цін матеріалу;
- компонента вектора , яка відповідає кількості одиничних заготовок в найменшій растровій точці цін матеріалу.
В цьому випадку, вектор перерізів набуває лінійності і має вид: для всіх , де - -й одиничний вектор, а апроксимуюча ЦФ має вид:
.
Коли безперервний оптимум задачі розкрою знайдений, що стає ясним із порівняння значень ЦФ та , то розв’язок знайдений.
Принцип домінантності виведення неоптимальних розв’язків БР в задачі ЛР формулюється розв’язком зворотної задачі:
, (8)
за умови існування обмежень виду ,
де - довжина матеріалу одиничної заготовки.
Якщо для заготовок, які мають індекси , виконуються умови:
та , (9)
тоді заготовка з індексом може бути виключена із задачі, а нова верхня межа встановлюється для заготовки типу за умов задачі (8) і умов (9) згідно виразу:
.
При перевірці домінантності для КР з січними замість правої частини у виразі (9) чисельно перевіряється умова:
,
де - - допуск на подвійні змінні;
- нижня межа приросту ЦФ;
- верхня межа приросту ЦФ за умови додавання заготовки до - тої КР.
Тест домінантності в такому випадку не набуває ознак оптимальності через те, що значення подвійних змінних і сильно різняться.
В останньому циклі алгоритму в новий масив включаться тільки вхідні вектори матеріалу, які мають вільний простір (), що може поліпшити ЦФ (), та мають позитивну комплектність .
Оцінити зміну ЦФ можна формулюючи нові межі приросту ЦФ, тобто слід розглянути можливість зміни ТКЦФ за умови додавання заготовки з номером до масиву .
В третьому розділі математична модель ЛР оптимізується як складна стохастична система з елементами нелінійності через необхідність врахування ряду факторів технологічного процесу. В умовах діючого виробництва виявляється доцільним використання методу діаграм Парето.
Аналіз задачі передбачає застосування методу оптимізації, заснованого на методиці розв’язку задач нелінійного програмування з врахуванням технологічних факторів технологічного процесу машинобудівного підприємства, що перетворюють її на модель нелінійного програмування.
Формулювання задачі розкрою за методом Банаха передбачає, що якщо є один шматок матеріалу і на ньому можна розмістити один-два асортиментних набора, то критерій мінімуму відходів є визначальним. В цьому випадку критерій максимуму асортиментних наборів є визначальним, а сума відходів складає:.
В результаті знаходження матриці оптимального розв’язку , що максимізувала б лінійну форму (1) за умов , ,, ,та , отримаємо умову оптимального розв’язку оптимізаційної задачі:
.
В цьому випадку необхідно врахувати чинники за методом Парето. Нерівність, що характеризує подвійний допуск, можна записати так:
,
а корегуючий (технологічний) коефіцієнт матриці обмежень для виразу (4) має вид: .
Реалізація математичної моделі ЛР, що враховує ознаки нелінійності за Бронфельдом, на ЗАТ «Кіровоградський завод дозавтоматів» при розкрої матеріалів практично відразу після введення інформації привела до отримання оптимальних КР, тоді як фахівці підприємства виконували розкрій за допомогою калькуляторів в межах 1 – 2 годин. Відсоток відходів, одержуваних по розрахунках фахівців на основі нормативного методу, укладався в 1,5 %, тобто 98,5 % від довжини рулонів складало корисне використання матеріалу.
З метою врахування наявних ознак нелінійності математичної моделі одновимірного розкрою введемо узагальнюючий кореляційний коефіцієнт – КЛО (коефіцієнт логістичної обробки). При формулюванні КЛО маємо справу з випадками, коли процес протікає в дискретні моменти часу. Параметрична модель КЛО формулюється таким чином:
,,
де - коефіцієнт очікуваної наявності мінімального складського запасу сировини, - коефіцієнт відхилення фактичної площі сировини, - обсяг виробничої програми.
Після врахування ознак стохастичності, , особливостей технології розкрою матеріалу математична модель розкрою потребує формулювання процедури цілочисельного округлення безперервного рішення, розширення задачі залишку та формулювання методу уточнення оцінок задля досягнення оптимуму шляхом тесту оптимальності, а отримання нижньої межі задачі можливо при використанні ефективних евристик.
Евристика складається з трьох фаз: округлення симплекс-розв’язку ; збільшення заокруглених компонент; застосування конструктивного методу для комплектностей з ітеративним розширенням задачі залишку. Значення попередніх оцінок беруться як середньозважені подетальні норми витрати матеріалу.
Перед кожною корекцією встановлюється збільшення на одиницю з кожною генерацією. При декількох типах матеріалу виникає задача вибору правильної комбінації прутків. Вираз для корекції попереднього уточнення оцінок ітерацій при отриманні КР має вигляд:
,
де - найбільший розмір прутка;
- стовбець матриці трансформованих базисних стовбців при цілочисельні трансформації базису.
Після генерації останньої карти плану оцінки не корегуються.
Автором запропоновано модифікацію існуючого методу генерації логічних тестів в МГМ. Растрові точки (РТ) конструюються як біти, встановлені в 1 в деякому бітовому полі. За допомогою зсуву регістрового поля на довжину і бітової операції «або» генеруються РТ для даної довжини матеріалу на основі вже наявних. Ціни матеріалу приймаються тотожними довжинам і цілочисельними.
При тесті оптимальності растрова точка повинна визначатися згідно чисельно задовольняючої умови з допуском (аналогічно допуску на подвійні змінні), де - оптимальне безперервне значення цільової функції в - й ітерації МСП. У цьому способі вигідно врахувати найбільший загальний дільник (НЗД) цін матеріалу у вигляді алгоритму Евкліда, щоб заощадити пам’ять.
В четвертому розділі проводиться комп’ютерне моделювання експериментальних даних, запропонованих в розділах 2 і 3 розробленого алгоритму в структурі евристичного розв’язку СМ і генерації стовпців КР, застосований до задачі ЛР.
Процедура трансформації базисної матриці ЦФ в СМ, що використовує евристики БР в модернізованому СМ з врахуванням трансформованих обмежень виду , має вигляд , де - матриця-множник для - ї ітерації.
В модернізованому СМ зберігаються тільки зворотний базис або і матриця трансформованих базисних стовбців цілочисельної трансформації базису . Матриця , що містить трансформовані базисні стовпці, не обчислюється в кожному кроці. Виходячи з одиничної матриці в першому кроці, її елементи перемножуються послідовно з матрицею - множником , а відповідний стовпець, що виноситься, замінюється на , де - одиничний вектор, - елемент, що виноситься з базису. Звідки отримаємо параметричну модель опису матриці трансформованих базисних стовпців при цілочисельній трансформації базису .
Через похибки округлення або переповнювання мантиси знижується точність матриці та, отже, і точність подвійних змінних.
Розв’язок є оптимальним, якщо не існує стовпця з від’ємним ТКЦФ. Через чисельні похибки необхідно порівнювати їх з достатньо малою константою – . Її величина залежить від подвійних змінних, які обчислюються за формулою: , де - ціни базисних стовпців, .- індексна множина базисних компонентів В цьому випадку необхідно перемножити чисельні похибки елементів зворотного базису з цими цінами таким чином: .
Нижче приводимо дані порівняльного експерименту для генетичного групового алгоритму (GGA) і МСП задачі ЛР (табл.1) для різних верхніх () та нижніх () обмежень задачі (генерувалося по 100 прикладів на клас).
Таблиця 1
Порівняння коефіцієнтів розкрою МСП з генетичним алгоритмом GGA
МСП | GGA | МСП | GGA | МСП | GGA | МСП | GGA
0,5 | 0,997 | 0,997 | 0,998 | 0,998 | 0,998 | 0,997 | 0,940 | 0,792
0,6 | 0,997 | 0,999 | 0,998 | 0,988 | 0,998 | 0,993 | 0,801 | 0,980
0,7 | 0,991 | 0,998 | 0,997 | 0,999 | 0,995 | 0,998 | 0,894 | 0,996
0,8 | 0,997 | 0,997 | 0,996 | 0,998 | 0,995 | 0,996 | 0,985 | 0,990
Алгоритм на основі СМ та евристик БР з корегуючим коефіцієнтом КЛО цільової функції мультиплікативної природи дозволяє отримувати оптимальні рішення на ряді задач з двома і більше вхідними векторами матеріалу. Введення до математичної моделі коефіцієнту технологічної корекції математичної моделі одновимірного розкрою уточнює матрицю обмежень лінійної форми.
Програмна реалізація розробленого алгоритму показала його переваги перед використовуваними на практиці алгоритмами, що застосовуються для розв’язку аналогічних задач одновимірного розкрою матеріалу на широкому класі задач ЛР. Виявлені переваги на деяких класах задач перед генетичним методом GGA та цілочисельним алгоритмом на базі січних площин.
Аналіз роботи алгоритму розкрою показує, що майже 90 % прикладів з 100 типами заготовок були вирішені оптимально з лімітом часу в 60-90 секунд. Середнє значення розриву між нижньою і верхньою межами для невирішених задач складає не більше 0,39% від найбільшої ціни прутка навіть для класів задач, де висока дискретизація цін матеріалу утрудняє оптимальне рішення.
Найбільш складним для розв’язку алгоритму в часовому аспекті є клас з маленькими межами для всіх типів прутка (). Цей клас має близько 35-40% невирішених прикладів навколо всіх випадково генерованих тестових задач.
Порівняння з алгоритмом на базі методу branch-and-price для випадку з єдиним типом прутка дало майже однакові результати по середньому часу обчислень. Максимальний час менше в розробленому алгоритмі, а кількість ітерацій набагато менше кількості опрацьованих вузлів дерева рішень в методі branch-and-price, що говорить про кращу спрямованість пошуку.
За результатами проведених тестових експериментів виявлено, що для основного класу прикладів 60 % прикладів були вирішені оптимально за 10 секунд і 90 % - за 75 секунд.
У класах з високою комбінаторною складністю (всі довжини заготовок не більш 0,25 найбільших довжин прутків) ЛП-межа дуже сильна і перерізи ніколи не стають активними. У інших класах тестових задач ЛП-межа слабка і її значення повинно бути поліпшено за допомогою перерізів.
Ефективність реалізації алгоритму як за кількістю оптимально вирішених задач, так і за коефіцієнтом корисного використання матеріалу можливо при застосуванні алгоритму у задачах дво - та тривимірного розкрою.
ВИСНОВКИ
Проведені в роботі дослідження щодо розробки моделей та методів оптимізації одновимірного розкрою матеріалу на машинобудівних підприємствах дозволяють зробити висновки, які мають значення для мінімізації кількості відходів крою матеріалу та мають значення для подальшого розвитку теорії та впровадження в практичну діяльність машинобудівних підприємств, а саме:
1. Проведено систематизацію загальних характеристик задач одновимірного розкрою та їх специфічні особливості, що пов’язані з варіантами мінімізації ЦФ розкрою, формуванням матриці обмежень, що складає основу подальшого дослідження;
2. Розроблена бікритеріальна математична модель одновимірного розкрою, яка враховує вплив стохастичних чинників на технологічний процес машинобудівних підприємств;
3. Сформульовано корегуючі чинники математичної моделі, що дає можливість врахувати мультиплікативний вплив технологічних та стохастичних складових на математичну модель, враховуючи важливість знаходження цілочисельних розв’язків задачі одновимірного розкрою шляхом формулювання методу послідовного уточнення оцінок розв’язку та формулювання корегуючих коефіцієнтів і ;
4. Модифіковано методику генерування КР з використанням верхньої границі ЦФ, яка виконується з метою генерування стовбців КР за наявності січних та обмеження перебору і стратегії дострокового переривання роботи алгоритму;
5. На базі методів ЛП та евристик БР сформульовані ознаки оптимальності математичної моделі одновимірного розкрою, які дають можливість отримати точні результати базисних планів розкрою;
6. Розроблена функціональна схема модуля одновимірного розкрою матеріалу в складі системи АСУ(ОКП) машинобудівного виробництва, що враховує оптимізацію математичної моделі;
7. На основі розв’язків оберненої задачі з модифікованою верхнею межею і матрицею обмежень удосконалена перевірка домінантності заготовок, що знижує розмір задачі генерації розкрою в середньому до 60% без перерізів і до 90% з перерізами;
8. Для тесту оптимальності цілочисельних рішень вдосконалений метод генерації лінійних комбінацій цін матеріалу на основі бітових полів, що зменшує обчислювальну складність задачі;
9. Виявлено переваги розробленого алгоритму на задачах з великим розривом оптимальності і слабкіші результати на задачах з малими комплектностями (поліпшення коефіцієнту корисного використовування матеріалу в середньому на 8-15% ціни найбільшого прутка) та зменшення часу отримання розв’язку;
10. Отримані еталонні результати запропонованого методу, які випробувані на визначеному наборі задач, характерних для машинобудівного підприємства;
11. Запропонована модифікація верхньої межі цільової функції в генерації карт розкрою за наявності перерізів, яка розширила область задач, що мають розв’язок за прийнятний з точки зору комерційного продукту час.
Моделі та методи оптимізації задач одновимірного розкрою матеріалу ввійшли до складу підсистеми одновимірного розкрою матеріалу АСУ «Інтеграл» на ЗАТ «Кіровоградський завод дозавтоматів», м. Кіровоград та ВАТ «Черкаський приладобудівний завод», м. Черкаси.
В результаті практичного застосування розроблених моделей та методів в практичних умовах машинобудівного підприємства досягнуто збільшення коефіцієнта використання сировини і зменшення часу отримання оптимальних КР, що підтверджується в наведених довідках про впровадження.
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ
1. Сагун А.В. Аналіз прикладних задач оптимального плану лінійного розкрою і комплектування / А.В. Сагун // Праці Луганського відділення Міжнародної академії інформатизації. – Луганськ, 2007. – № 1(14). – С. 63 – 66.
2. Сагун А.В. Моделювання задачі оптимізації карт розкрою з одновимірним характером / А.В. Сагун // Праці Луганського відділення Міжнародної Академії інформатизації. – Луганськ, 2007. – № 2 (15), частина ІІ. – С. 135 – 139
3. Сагун А.В. Метод генерування стовпців в задачі лінійного розкрою з урахуванням стохастичного характеру виробничої моделі / А.В. Сагун // Вісник Хмельницького нац. університету. – 2007.– Т. 2. – №3. – С. 163 – 166.
4. Сагун А.В. Порівняльний аналіз алгоритмів лінійного розкрою матеріалу / А.В. Сагун // Вісник Хмельницького нац. університету. – 2007. – Т. 1. – №6. – С. 194 – 198.
5. Сагун А.В. Математична модель одновимірного розкрою матеріалу з врахуванням коефіцієнта логістичної обробки / А.Д. Кожухівський, Н.А.Єфіменко, А.В. Сагун // Вісник ЧДТУ. – Черкаси, – 2006 - № 4. – С. 39 – 41.
6. Сагун А.В. Оптимізація моделі плоского розкрою матеріалу в задачі оперативного планування виробничого процесу / Кожухівський, А.Д., Сагун, А.В. // Вісник ЧДТУ. – Черкаси, 2006 – № 1 – 2. – С. 67-71.
7. Сагун А.В. Характеристика алгоритму безперервної релаксації задачі залишку лінійного розкрою / А.В. Сагун // «Современные научные достижения – 2007»: II междунар. науч.-практ. конф., 01-14 февраля 2007 г.: тезисы докл. – Днепропетровск, 2007. – Т 6. – С. 71 – 73.
8. Сагун А.В. Генерування стовпців карт лінійного розкрою з врахуванням стохастичності математичної моделі / А.В. Сагун // «Обробка сигналів і негаусівських процесів»: міжн. наук.-практ. конф., 21-26 травня 2007 р.: тези доп. – Черкаси: ЧДТУ, 2007. – С. 50 – 52.
АНОТАЦІЯ
Сагун А.В. Моделі та методи оптимізації в задачах одновимірного розкрою матеріалу на машинобудівних підприємствах. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи.– Черкаський державний технологічний університет. – Черкаси, 2008.
Робота присвячена питанням оптимізації моделей та методів одновимірного розкрою матеріалу на базі лінійного програмування та методу безперервної релаксації з врахуванням факторів корекції технологічного процесу, завдяки чому відбувається оптимізація та уточнення отриманих розв’язків при застосуванні швидкого алгоритму отримання розв’язків та великої номенклатури заготовок та деталей.
Процес генерації карт розкрою за наявності перерізів, корегуючого технологічного коефіцієнту та коефіцієнту логістичної обробки ведеться в модернізованому цілочисельному базисі симплексної таблиці з використанням методів дискретної оптимізації.
Запропонована ефективна модифікація методу попереднього уточнення оцінок ітерацій в кроках симплексного методу та критерій домінантності розкрою в складі тесту оптимальності цілочисельних рішень на основі вдосконаленого методу генерації лінійних комбінацій цін матеріалу в бітових полях, що зменшують обчислювальну складність задачі отримання оптимальних планів розкрою.
Характеристика і еталонні результати розробленого алгоритму випробувані на визначеному наборі задач, характерних для машинобудівного підприємства.
В результаті практичного застосування розробленого алгоритму в умовах машинобудівного підприємства досягнуто збільшення коефіцієнта використання сировини і зменшення часу отримання оптимальних карт розкрою в структурі автоматизованої системи управління машинобудівним підприємством.
Ключові слова: бікритеріальна математична модель, січна, цільова функція, карта розкрою, коефіцієнт корекції.
АННОТАЦИЯ
Сагун А.В. Модели и методы оптимизации в задачах одномерного раскроя материала на машиностроительных предприятиях. – Рукопись.
Диссертация на соискание учёной степени кандидата технических наук по специальности 01.05.02 – математическое моделирование и численные методы. – Черкасский государственный технологический университет. – Черкассы, 2008.
Работа посвящена вопросам оптимизации моделей и методов одномерного раскроя материала на базе линейного программирования и метода непрерывной релаксации с учётом факторов коррекции технологического процесса, благодаря чему происходит оптимизация и уточнение полученных решений при применении быстрого алгоритма получения решений и большой номенклатуре заготовок и деталей.
Процесс генерации карт раскроя при наличии сечении, корректирующего технологического коэффициента и коэффициента логистической обработки в применяемом методе секущих плоскостей ведется в модернизированном целочисленном базисе симплексной таблицы при использовании методов дискретной оптимизации.
Предложена эффективная модификация метода предварительного уточнения оценок итераций в шагах симплекса и критерия доминантности раскроя в составе теста оптимальности целочисленных решений на базе усовершенствованного метода генерации линейных комбинаций цен материала в битовых полях, что уменьшает вычислительную сложность задачи получения оптимальных планов раскроя.
В результате проведенного компьютерного моделирования разработанной математической модели получены сравнительные характеристики алгоритма, разработанного на базе данной модели и аналогичного линейного алгоритма с использованием метода секущих и генетического алгоритма. Сравнение данных коэффициентов раскроя и графические характеристики производительности показывают преимущества модели, методов, разработанных в диссертации над аналогичными существующими моделями и методами.
Характеристика и эталонные результаты разработанного алгоритма протестированы на определённом наборе задач, характерных для машиностроительного предприятия.
В результате практического применения разработанного алгоритма в практических условиях машиностроительного предприятия достигнуто увеличение коэффициента использования сырья и уменьшение времени получения оптимальных карт раскроя в составе автоматизированной системы управления машиностроительным предприятием.
Ключевые слова: бикритериальная математическая модель, секущая, целевая функция, карта раскроя, коэффициент коррекции.
ABSTRACT
Sagun A.V. The Models and Methods of optimization in tasks of one-dimension cutting stock at machine-building enterprizes. – Manuscript.
Dissertation research for seeking a scientific degree of the Candidate of Technical Science, Specialty 01.05.02 – Mathematical modeling and computing methods. – Cherkassky State Technological University. – Cherkassy, 2008.
The dissertation research is devoted to optimization of mathematical model and methods of one-dimensional material cutting on the basis of linear programming and unlimited relaxation methods with taking into account factors of technological correction.
The generation of cutting patterns when cutting planes and correction coefficients are available realizes in advanced integrity basis of simplex table in corresponds to discrete optimization methods.
The effective modification in method of preliminary accusation of iteration
