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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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