Досліджено властивості задач евклідової комбінаторної оптимізації з дробово-лінійними цільовими функціями на переставних множинах. Розвинуто метод комбінаторного відсікання та вперше побудовано алгоритми розв'язування таких задач. Зроблено перехід від задачі з дробово-лінійною функцією цілі до задачі з лінійною функцією цілі. Для останньої сформульовано та доведено властивості області допустимих розв'язків задачі, опукла оболонка якої є багатогранником: теорема про грані багатогранника, критерій вершини, критерій суміжності граней. Встановлено незвідну систему лінійних обмежень цього багатогранника. Алгоритми, побудовані за методом комбінаторного відсікання, програмно реалізовано на ПЕОМ. Проаналізовано алгоритми за результатами числових експериментів. Побудовано моделі прикладних задач з дробово-лінійною цільовою функцією на переставних множинах.

  Скачати повний текст

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

  Скачати повний текст

  Скачати повний текст

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

  Скачати повний текст

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

  Скачати повний текст

Досліджено задачі геометричного проектування, а саме: нелінійних задач розміщення 2D об'єктів з урахуванням можливості обертання об'єктів. Створено математичну модель задачі розміщення неорієнтованих багатокутників і кругів у прямокутній області розміщення. Розвинуто єдиний підхід до розв'язання задач, який передбачає застосування методів локальної та глобальної оптимізації. Розроблено алгоритмічне та програмне забезпечення для розв'язання цих задач. Наведено результати розв'язання тестових задач.

  Скачати повний текст

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

  Скачати повний текст

  Скачати повний текст

Розвинуто відомі та розроблено нові декомпозиційні методи, в яких задача розв'язується за декілька етапів: розбиття вхідної множини точок на підмножини обмеженої розмірності ( 500 - 2 000 точок), для яких одержуються високоякісні часткові розв'язки з невеликими часовими затратами, зшивання часткових розв'язків у початковий розв'язок, та його покращання розробленими методами оптимізації. Розроблено прикладну програмну систему УVRP ModelerФ для розв'язування задачі комівояжера (ЗК) великих розмірностей, яка є спеціальним програмним забезпеченням, що дозволяє розв'язувати реальні ЗК, їх моделювати, досліджувати й інтегрувати нові методи. Розроблені методи та програмні засоби кластеризації вхідних даних, побудови макромаршруту, знаходження початкового розв'язку та його оптимізації можна застосовувати для широкого кола прикладних задач, де використовується ЗК та близькі до неї.

  Скачати повний текст

  Скачати повний текст

Запропоновано нові комбінаторні множини - композиційні k-образи комбінаторних множин, а також засоби опису та класифікацію цих множин. На множині елементів композиційних образів комбінаторних множин задано відношення лінійного порядку. Наведено підхід до оптимізації лінійних функцій на композиційних образах комбінаторних множин. Досліджено екстремальні властивості й одержано оцінки мінімуму опуклих функцій на класах композиційних образів комбінаторних множин. Побудовано математичну модель основної задачі геометричного проектування в інтервальному вигляді. Виконано класифікацію задач оптимізації на інтервальних комбінаторних множинах. Розроблено метод розв'язання задач комбінаторної оптимізації з лінійною цільовою функцією та лінійними обмеженнями на основні покриття області припустимих розв'язків. Розв'язано базові задачі оптимізації на класах інтервальних комбінаторних множин. Запропоновано метод розв'язання інтервальних задач комбінаторної оптимізації в евклідовому просторі. Розвинуто метод розв'язання інтервальної задачі комбінаторної оптимізації як задачі двокритеріальної оптимізації в евклідовому просторі.

  Скачати повний текст

Уведено до розгляду новий клас евклідових задач комбінаторної оптимізації - задачі лексикографічної комбінаторної оптимізації на розміщеннях. Побудовано моделі практичних задач як евклідових задач лексикографічної комбінаторної оптимізації на розміщеннях. Розроблено методи відсікання для розв'язування задач лінійної та опуклої оптимізації на розміщеннях. Запропоновано розбиття многогранних множин за допомогою відношення еквівалентності, на базі якого створено метод побудови лексикографічної еквівалентності для розв'язування повністю комбінаторних задач лексикографічної оптимізації на розміщеннях. Обгрунтовано алгоритми методів відсікання та побудови лексикографічної еквівалентності для розв'язування задач оптимізації на розміщеннях та доведено їх скінченність.

  Скачати повний текст

Розглянуто методи розв'язування екстремальних задач на різних комбінаторних конфігураціях двох типів - екстремальних одно- та багатокритеріальних. Досліджено властивості комбінаторних конфігурацій з використанням теорії графів. Розроблено на базі властивостей нові методи генерування комбінаторних конфігурацій, що будують послідовності елементів конфігурацій і в яких різниця між двома послідовними елементами мінімальна, а також яка базується на переміщенні максимального елемента множини з якої утворюється конфігурація. Запропоновано новий метод розв'язування екстремальних комбінаторних задач - метод спрямованого структурування. Встановлено, що даний метод застосовано для розв'язання задач з лінійною та дробово-лінійною цільовими функціями на різних комбінаторних конфігураціях: перестановках, розбиттях, сполученнях і розміщеннях.

  Скачати повний текст

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

  Скачати повний текст

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

  Скачати повний текст

Наведено класифікацію методів розв'язання задач комбінаторної оптимізації (ЗКО) на основі понять метаевристик першого та другого роду. Розроблений підхід дозволяє класифікувати не лише існуючі, але й розроблювані алгоритми комбінаторної оптимізації (АКО). Розроблено нові наближені алгоритми стохастичного локального пошуку, які належать до метаевристик першого роду. Запропоновано підхід до побудови гібридних алгоритмів на базі генетичних алгоритмів і GS-алгоритмів, які відносяться до метаевристик другого роду. Проведено теоретичний аналіз ефективності та досліджено практичну застосовність розроблених алгоритмів. Розроблено математичну модель оптимізації прийняття рішень за планування технологічних процесів на великому металургійному комбінаті (МК), яка враховує найбільш суттєві обмеження та технологічні норми на типовому МК.

  Скачати повний текст

Досліджено опуклі оболонки областей визначення оптимізаційних задач, моделями яких є задачі евклідової оптимізації на переставних множинах. Визначено незвідні системи лінійних обмежень загального переставного і загального поліпереставного багатогранників та їх нові властивості. Одержано нові властивості переставного багатогранника. Викладено новий метод точного розв'язування задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів, розроблено алгоритм його реалізації на ПЕОМ.

  Скачати повний текст

Показано що базовим задачам проблеми комівояжера - симетричним задачам комівояжера (СЗК) і задачам пошуку гамільтонового циклу мінімальної вартості в графі зі зваженими ребрами (ГЗК) - притаманні алгоритмічні особливості, які потребують подальшого вивчення, а саме з'ясовано, що властивість симетрії суттєво впливає на час і точність наближеного розв'язку СЗК, а ГЗК не завжди розв'язана. Висока точність розв'язку СЗК забезпечується шляхом побудови алгоритму, що складається з двох стадій. Трудомісткість наближеного розв'язку СЗК залежить від алгоритмічних властивостей релаксації та способу перетворення. Запропоновано двохетапний алгоритм пошуку розв'язку ГЗК, який спочатку перевіряє з урахуванням структурних характеристик транспортної мережі умови її негамільтоновості. Якщо жодна з них не виконується, то алгоритмом типу гілок і меж здійснюється відсічення негамільтонових циклів. Для обчислення нижніх оцінок вартості шуканого маршруту запропоновано модифікований метод розв'язання задачі про призначення, який встановлює нерозв'язність ГЗК у вершинах дерева розгалужень. За допомгою розробленої програми системи проведено обчислювальний експеримент і аналіз одержаних даних.

  Скачати повний текст

  Скачати повний текст

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

  Скачати повний текст