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

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

Дисертація присвячена моделюванню і оптимізації маршрутів у транспортних мережах, а саме розробці алгоритмів розв'язування та експериментальногопрограмного комплексу для побудови оптимальних шляхів за критерієм вартості в залежних від часу мережах авіаперельотів з урахуванням обмежень користувача і необхідності виконання розрахунків у реальному часі. Сформульовано спеціальну задачу пошуку оптимального за критерієм вартості шляху мандрівника з користувацькими умовами: початковий і цільовийпункт подорожі, часове вікно, максимальна кількість транзитних пунктів і тривалість подорожі, бажані і заборонені проміжні пункти. Відмінність даної задачівід існуючих постановок полягає у врахуванні таких властивостей транспортної мережі, як залежність її характеристик від часу. Аналіз подання моделей різнихтранспортних мереж виявив їх відмінності і можливість застосування евристичних алгоритмів розв'язування поставленої задачі.Запропоновано алгоритм на основі міток і ряд алгоритмів на основі модифікації оптимізації мурашиними колоніями. Алгоритм міток показав задовільні результати для невеликих мереж, але значне зростання часу виконання у порівнянні з мурашиним алгоритмом з ростом мережі. Алгоритм мурашиних системмодифіковано з урахуванням специфіки задачі, а саме операції бектрекінгу, локального пошуку, табу-списків, добудови допустимого маршруту, відсікання простору пошуку методом гілок і меж. Для покращення точності обчислень для міжрегіональних маршрутів запропоновано диверсифікований алгоритммурашиних систем. При пошуку кільцевих або міжрегіональних маршрутів пропонується застосовувати розроблений двонаправлений алгоритм системмурашиних колоній (АСМК).Задоволення вимог адаптивності та роботи в реальному часі програмного комплексу досягається запропонованим алгоритмом з попередньою обробкоюданих, який використовує АСМК для пошуку оптимальних шляхів для всіх пар вершин мережі, а потім використовує цю інформацію для побудови відноснихоцінок якості кожного сполучення за критерієм вартості. Оцінки якості використовуються для пошуку маршруту в реальному часі. Така задача та методи їїрозв'язування актуальні для пошуку оптимальних маршрутів мандрівників в реальному часі в мережі громадського транспорту.^UThe dissertation is devoted to the topic of modeling and optimizing routes in transportation networks, in particular, application development for constructing optimalroutes by cost criteria in time-dependent air networks, taking into account user's limitations and real time calculations requirement.Time dependent optimal traveler's path by cost criteria problem is defined with given user's limitations: source and target points, travel time window, maximum number of transit points and duration of the trip, desired and prohibited intermediate points. The main difference of this problem from existing ones is taking into account network properties, since it's time dependent and costs are dynamic.Analysis of models presentations of various transport networks showed their differences and the possibility of applying heuristic approaches to the problem.Multicriterial labelling based algorithm and several ant colony system (ACS) based modifications were proposed to solve the problem. The labeling algorithm showedsatisfactory results for small networks, however execution time significantly increased with network growth, comparing to ant algorithm.Developed ACS-based algorithm has been modified with consideration of the specifics of the problem, applying backtracking operation, route fixing, method ofbranches and bounds, several local search procedures, tabu-lists. To reduce error ratio for international routes, a diversified algorithm of ant colony systems was proposed. To find return or multiregional routes, bidirectional ACS was proposed.To meet the requirements of adaptability and real-time execution, a preliminary data processing algorithm was proposed that uses ACS to search for optimal paths forall pairs of vertices of the network and then uses this information to build relative estimates of the quality of each connection based on cost criteria. Quality ratios are used to find the route in real time. Described problem and solution approaches are relevant for development of techniques for finding optimal traveler's routes in real time in the public transportnetwork.

Дисертаційна робота присвячена питанню побудови нечітких моделей комбінаторної оптимізації за наявності якісної та кількісної інформації з урахуванням положень репрезентативної теорії вимірювань. На основі аналізу сучасних підходів до побудови нечітких моделей виокремлені проблеми подання, єдиності та адекватності. Введено поняття адекватної формальної моделі та поняття недовизначених нечітких множин і запропоновано підхід до побудови адекватних нечітких моделей з урахуванням допустимих перетворень результатів вимірювань. Проведено класифікацію слабкоструктурованих задач в умовах невизначеності, яка пов'язана з наявністю кількісної та якісної інформації. Запропоновано поняття нечітких комбінаторних об'єктів та їхню класифікацію.^UDissertation work is devoted to construction of fuzzy models of combinatorial optimization in the presence of qualitative and quantitative information taking into account the provisions of representative theory of measurement. Based on the analysis of modern approaches to the construction of formal models on fuzzy sets, problems of representation, uniqueness and adequacy have been identified. The concept of not predetermined fuzzy set is introduced, the essence of which is related to consideration of permissible transformations of measurement results. The classification of ill-structured problems with quantitative and qualitative information is proposed. Original approach to determination of the concept «fuzzy combinatorial object» is offered, which allows to strictly formalizing both the known and new classes of problems of combinatorial optimization.

Дисертаційна робота присвячена дослідженню питань планування місій за участі команд гетерогенних БПЛА та гібридних систем. Запропоновані в дисертації математичні моделі та методи оптимізації рішень при плануванні використання БПЛА та їх груп застосовуються для розв’язування задач комбінаторної оптимізації, що полягають у створенні плану місій гібридних систем та команд БПЛА. Створення таких місій є дуже важливим та затребуваним у таких галузях, як логістика та розвідка. Розроблений обчислювальний блок дозволяє формувати плани місій та передавати їх до розповсюджених систем керування, що здійснюють безпосередню взаємодію із БПЛА та гібридними системами. Розроблені алгоритми дозволяють планувати місії на персональних компʼютерах чи серверах за обмежений час, що дозволяє створювати план без підключення до мережі Інтернет та оперативно коригувати його у разі необхідності. Проведений чисельний експеримент дозволив виявити більш ефективні алгоритми та методи для подальшої реалізації обчислювального блоку.Значна частина результатів дисертації може бути використана у навчальному процесі вищих навчальних закладів України, де викладаються такі дисципліни як "Теорія прийняття рішень", "Комбінаторна оптимізація" та "Дослідження операцій".^UThe thesis is devoted to the study of planning missions of UAV teams and hybrid systems. The mathematical models and methods for optimising decisions in planning proposed in this thesis are used to solve combinatorial optimisation problems involving the creation of a mission plan for hybrid systems and UAV teams. The creation of such missions is very important and in demand in such industries as logistics and intelligence. The developed computing unit allows to generate mission plans and transfer them to widespread control systems that directly interact with UAVs and hybrid systems. The developed algorithms allow for mission planning on personal computers or servers in a limited amount of time, which allows for the creation of a plan without an Internet connection and prompt adjustment if necessary. The numerical experiment allowed us to identify more efficient algorithms and methods for further implementation of the computing unit.A significant part of the results of the thesis can be used in the educational process of higher educational institutions of Ukraine, where such disciplines as Decision Theory, Combinatorial Optimisation and Operations Research are taught.