Модели и алгоритмы многоцелевого линейного программирования

Abstract

Досліджено окремий випадок постановки задачі векторної оптимізації — задачу багатоцільового лінійного програмування (ЛП), наведено її постановку, а також два найбільш поширені підходи до її розв’язання. Автор, використовуючи свої результати в області знаходження компромісних розв’язків для одного класу задач комбінаторної оптимізації за умов невизначеності, модифікував їх для розв’язання задачі багатоцільового ЛП, обмеження якої задаються у вигляді опуклого компакту. В результаті цієї модифікації доведено два твердження, які дозволили отримати наступні результати: (а) для задачі багатоцільового ЛП в детермінованій постановці: знайдено нову властивість компромісного критерію, який є лінійною зваженою згорткою лінійних критеріїв; наведено п’ять нових критеріїв отримання компромісного розв’язку. Для кожного з наведених компромісних критеріїв сформульовано задачі ЛП, розв’язки яких є оптимальним компромісним розв’язком за відповідним критерієм; (б) сформульовано задачі багатоцільового ЛП в умовах невизначеності (при цьому невизначеність формалізується як в термінах теорії ймовірностей шляхом введення багатовимірних дискретних випадкових величин, так і в термінах теорії нечітких множин шляхом введення відповідних функцій приналежності нечітких дискретних множин). Наведено компромісні критерії та алгоритми отримання компромісних розв’язків як розв’язки відповідних задач ЛП для невизначеності обох типів; (в) наведено також змішані моделі багатоцільового ЛП для випадку, коли частина лінійних критеріїв детермінована, а решта задана в умовах невизначеності. У розглянутих критеріях використовуються експертні ваги, які запропоновано знаходити за емпіричною матрицею парних порівнянь за допомогою моделей оптимізації та відповідних критеріїв знаходження найкращого рішення, розроблених автором та його учнями.This paper examines a special case of the vector optimization problem formulation, the multipurpose linear programming (LP) problem. Its formulation is provided, as well as two most common approaches to its solution. The author uses his results in the field of finding compromise solutions for one class of combinatorial optimization problems under uncertainty. He has modified the results to solve the multipurpose LP problem with the constraints given in the form of a convex compact. As a result of this modification, two statements were proved, which made it possible to obtain the following results: (a) for the multipurpose LP problem in a deterministic formulation: a new property was found of the compromise criterion which is a linear weighted convolution of linear criteria; five new criteria for obtaining a compromise solution are provided; for each of the given compromise criteria, the LP problems are formulated, their solution is the optimal compromise solution for the corresponding criterion; (b) the problems of a multipurpose LP under uncertainty are formulated (the uncertainty is formalized both in terms of probability theory by introducing multidimensional discrete random variables, and in terms of fuzzy sets theory by introducing the corresponding membership functions of fuzzy discrete sets); compromise criteria and algorithms for obtaining compromise solutions by solving the corresponding LP problems for both types of uncertainty are presented; (c) mixed models of multipurpose LP are also given for the case when some of the linear criteria are deterministic, and the rest are specified uncertainly. The proposed criteria use expert weights, which are proposed to be found by the empirical matrix of paired comparisons using optimization models and the corresponding criteria for finding the best solution developed by the author and his students.