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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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