Решение двухкритериальной задачи оценки альтернатив с помощью тропической оптимизации

  • Николай Кимович Кривулин Санкт-Петербургский государственный университет, Санкт-Петербург, Россия http://orcid.org/0000-0003-3070-9355
  • Маргарита Александровна Цобенко Санкт-Петербургский государственный университет, Санкт-Петербург, Россия
Ключевые слова: тропическая математика, парные сравнения, двухкритериальные задачи, Парето-оптимальное решение, Парето-фронт

Аннотация

Рассматривается задача оценки рейтингов (приоритетов, весов) альтернатив на основе результатов парных сравнений в соответствии с двумя критериями. Описывается формальное построение и вычислительные процедуры решения задачи с использованием методов тропической математики, которая изучает алгебраических систем со специальным образом определенными операциями сложения и умножения. Задача сводится к одновременной аппроксимации двух матриц парных сравнений общей согласованной матрицей в метрике Чебышева в логарифмической шкале. Сначала вводятся вспомогательные переменные для обозначения минимумов целевых функций и составляется
параметризованное неравенство, которое определяет множество решений исходной задачи оптимизации. Необходимые и достаточные условия существования решений неравенства используются для определения значений параметров, соответствующих Парето-фронту задачи. Все решения неравенства при найденных значениях параметров берутся в качестве Парето-оптимального решения задачи. Для иллюстрации применяемых вычислительных процедур приводятся численные примеры определения рейтингов альтернатив для задач с матрицами третьего порядка.

Биографии авторов

Николай Кимович Кривулин, Санкт-Петербургский государственный университет, Санкт-Петербург, Россия

доктор физико-математических наук, профессор кафедры статистического моделирования СПбГУ, nkk@math.spbu.ru

Маргарита Александровна Цобенко, Санкт-Петербургский государственный университет, Санкт-Петербург, Россия

бакалавр математико-механического факультета СПбГУ, margaritatsobenko@yandex.ru

Литература

V. V. Podinovskii and V. D. Nogin, Pareto-optimal’nye resheniya mnogokriterial’nykh zadach [Paretooptimal solutions to multicriteria problems], Moscow: Nauka, 1982 (in Russian).

T. Saaty, Prinyatie reshenii. Metod analiza ierarkhii [Making decisions. Hierarchy Analysis Method], Moscow: Radio i svyaz’, 1993 (in Russian).

V. D. Nogin, Prinyatie reshenii v mnogokriterial’noi srede: kolichestvennyi podkhod [Decision making in a multi-criteria environment: a quantitative approach], Moscow: Fizmatlit, 2002 (in Russian).

M. Ehrgott, Multicriteria Optimization, Berlin: Springer, 2005; doi: 10.1007/3-540-27659-9

L. L. Thurstone, “A law of comparative judgment,” Psychological Review, vol. 34, no. 4, pp. 273–286, 1927; doi: 10.1037/h0070288

T. L. Saaty, “A scaling method for priorities in hierarchical structures,” J. Math. Psych., vol. 15, no. 3, pp. 234–281, 1977; doi: 10.1016/0022-2496(77)90033-5

R. A. Cuninghame-Green, Minimax Algebra, Berlin: Springer-Verlag, 1979; doi: 10.1007/978-3-642-48708-8

F. L. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and Linearity. Wiley Series in Probability and Statistics, Chichester, UK: Wiley, 1993.

V. P. Maslov and V. N. Kolokol’tsov, Idempotentnyi analiz i ego primenenie v optimal’nom upravlenii [Idempotent analysis and its application in optimal control], Moscow: Fizmatlit, 1994 (in Russian).

J. S. Golan, Semirings and Affine Equations Over Them (Vol. 556 of Mathematics and Its Applications), New York: Springer, 2003; doi: 10.1007/978-94-017-0383-3

B. Heidergott, G. J. Olsder, and J. van der Woude, Max Plus at Work (Princeton Series in Applied Mathematics), Princeton, NJ: Princeton Univ. Press, 2006.

N. K. Krivulin, Metody idempotentnoi algebry v zadachakh modelirovaniya i analiza slozhnykh sistem [Idempotent algebra methods in modeling and analysis of complex systems], Saint-Petersburg: Izd-vo

S.-Peterb. un-ta, 2009 (in Russian).

L. Elsner and P. van den Driessche, “Max-algebra and pairwise comparison matrices, II,” Linear Algebra Appl., vol. 432, no. 4, pp. 927–935, 2010; doi: 10.1016/j.laa.2009.10.005

B. B. Gursoy, O. Mason, and S. Sergeev, “The analytic hierarchy process, max algebra and multi-objective optimisation,” Linear Algebra Appl., vol. 438, no. 7, pp. 2911–2928, 2013; doi: 10.1016/j.laa.2012.11.020

N. K. Krivulin and I. V. Gladkikh, “Postroenie soglasovannoi matritsy parnykh sravnenii v marketingovykh issledovaniyakh na osnove metodov tropicheskoi matematiki” [Building a consistent matrix

of paired comparisons in marketing research based on methods of tropical mathematics], Vestn. S. Peterb. un-ta. Ser. 8. Menedzhment, vol. 1, pp. 3-–43, 2015 (in Russian).

N. Krivulin, “Using tropical optimization techniques to evaluate alternatives via pairwise comparisons,” in 2016 Proc. 7th SIAM Workshop on Combinatorial Scientific Computing, A. H. Gebremedhin, E. G. Boman, and B. Ucar eds., Philadelphia, PA: SIAM, 2016, pp. 62–72; doi: 10.1137/1.9781611974690.ch7

N. K. Krivulin, V. A. Ageev, and I. V. Gladkikh, “Primenenie metodov tropicheskoi optimizatsii dlya otsenki al’ternativ na osnove parnykh sravnenii” [Application of tropical optimization methods to evaluate alternatives based on pairwise comparisons], Vestn. S.- Peterb. un-ta. Prikladnaya matematika. Informatika. Protsessy upravleniya, vol. 13, no. 1, pp. 27–41, 2017 (in Russian).

N. K. Krivulin, Using tropical optimization techniques in bi-criteria decision problems,” Comput. Manag. Sci., 2018; doi: 10.1007/s10287-018-0341-x

N. K. Krivulin and S. N. Sergeev, “Tropical implementation of the Analytical Hierarchy Process decision method,” Fuzzy Sets and Systems, vol. 377, pp. 31–51, 2019; doi: 10.1016/j.fss.2018.10.013

N. Krivulin, “A multidimensional tropical optimization problem with nonlinear objective function and linear constraints,” Optimization, vol. 64, no. 5, pp. 1107–1129, 2015; doi: 10.1080/02331934.2013.840624

Опубликован
2019-12-28
Как цитировать
Кривулин, Н. К., & Цобенко, М. А. (2019). Решение двухкритериальной задачи оценки альтернатив с помощью тропической оптимизации. Компьютерные инструменты в образовании, (4), 15-32. https://doi.org/10.32603/2071-2340-2019-4-15-32
Выпуск
Раздел
Алгоритмическая математика и математическое моделирование

Наиболее читаемые статьи этого автора (авторов)