Математичні підходи до розв’язання задач багатокритеріальної оптимізації

Abstract

Кваліфікаційну роботу присвячено дослідженню методів багатокритеріальної оптимізації та їх практичному застосуванню для розв’язання задачі розподілу вагонів між вантажними пунктами. Для розв’язку задачі багатокритеріальної оптимізації спочатку наведено огляд теорії Парето-ефективних розв’язків задачі. Потім досліджено різні методи вибору вагових коефіцієнтів або лінійної згортки (метод розподілу балів, метод ранжування критеріїв та метод попарних порівнянь). Також досліджено метод цільового програмування. Обидва підходи дозволяють звести багатокритеріальну задачу до однокритеріальної для подальшого застосування симплекс-методу. Теоретичні методи були застосовані для розв’язку практичної задачі розподілу вагонів по вантажним фронтам. Розроблено програмний скрипт мовою Python для пошуку Парето-ефективних розв’язків. Наукова новизна роботи полягає в аналітичному обґрунтуванні траєкторії переходу між двома цільовими стратегіями у багатокритеріальній задачі. Завдяки аналітичному визначенню граничних значень вагових коефіцієнтів доведено, що прямий перехід від стратегії «пріоритет залізниці» до «пріоритет клієнтів» є неможливим. Обґрунтовано, що цей процес відбувається виключно послідовно й обов'язково передбачає пошук компромісного рішення. У статті [9] до задачі розподілу вагонів було застосовано метод Парето та метод вагових коефіцієнтів (випадок рівної важливості критеріїв), тоді як у кваліфікаційній роботі застосовано метод вагових коефіцієнтів (випадки домінування одного з критеріїв) та метод цільового програмування як альтернативний підхід. У результаті дослідження було знайдено оптимальні розв'язки для задачі розподілу вагонів на основі методу лінійної згортки критеріїв. Завдяки проведеному аналізу було знайдено критичні значення вагових коефіцієнтів та визначено інтервали дії кожної зі стратегій.

This Bachelor’s Thesis investigates multi-objective optimization methods and their practical application in solving the wagon allocation problem among loading points. First, the work reviews the theory of Pareto-optimal solutions. Then, it examines different weighting methods: point allocation, ranking and pairwise comparisons. The goal programming method is also analyzed. Both approaches transform the multi-criteria problem into a single-criterion form. This allows using the simplex method to solve it. These theoretical methods were used to solve a practical problem of wagon allocation. A Python script was created to find the Pareto-optimal solutions. The scientific novelty is that the work explains how to transition between two main strategies. First, the boundary values of the weight coefficients are determined analytically. Based on these results, a direct shift from “railway priority” to “customer priority” is proven to be impossible. This transition is shown to be strictly sequential. The process always involves finding a compromise solution. In the article [9], the Pareto method and the weighted coefficients method were used for the wagon distribution problem. The weighted coefficients method was applied in the case of equal importance of the criteria. In the qualification thesis, the weighted coefficients method was also used, but for cases where one criterion dominates the others. Goal programming was applied as an alternative approach. As a result of the research, optimal solutions for the wagon allocation problem were found based on the linear scalarization method. Through the conducted analysis, the critical values of the weighting coefficients were identified, and the effective intervals for each strategy were determined.