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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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