Methods of tropical optimization in multicriteria problems of raiting alternatives from pairwise comparisons

N. Krivulin ; V. A. Ageev

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 15 (2019) no. 4, pp. 472-488

Résumé

The paper deals with the application of methods and results of tropical mathematics, which focuses on the theory and applications of algebraic systems with idempotent operations, to the development of a multicriteria decision-making procedure. A problem is considered to evaluate ratings of alternatives from pairwise comparisons of the alternatives under several criteria, and from pairwise comparisons of the criteria. To solve the problem, a decision-making procedure is proposed based on the Chebyshev approximation, in logarithmic scale, of pairwise comparison matrices by reciprocally symmetrical matrices of unit rank (consistent matrices), which determine the elements in the vectors of weights of criteria and ratings of alternatives. First, the approximation problem for the matrix of pairwise comparison of criteria is solved to find the weights of criteria. Then, the weighted pairwise comparison matrices of alternatives are approximated by a common consistent matrix, which gives the required vector of ratings of alternatives. If the result is not unique (up to a positive factor), an additional problem of analyzing the solutions is solved to find vectors that can be considered, in a sense, as the worst and best solutions. In the framework of the proposed procedure, the problems of approximation and analysis of solutions are formulated as tropical optimization problems, which have direct analytical solutions in a compact vector form. An example of the application of the procedure to solve the known problem by T. Saaty on selecting a school is given.

Détail

Keywords: idempotent semifield, tropical optimization, pairwise comparison matrix, log-Chebyshev metric, multicretiria decision making problem.
Mots-clés : matrix approximation

Bibliographie

[1] M. Ehrgott, Multicriteria optimization, 2nd ed., Springer, Berlin, 2005, 323 pp. | DOI | MR | Zbl

[2] V. D. Nogin, Decision-making in multicriteria framework, 2nd ed., rev. and enl., Fizmatlit, M., 1994, 176 pp. (In Russian)

[3] L. L. Thurstone, “A law of comparative judgment”, Psychological Review, 34:4 (1927), 273–286 | DOI

[4] T. L. Saaty, The analytic hierarchy process: planning, priority setting, resource allocation, McGraw-Hill, New York, 1980, 281 pp. | MR | Zbl

[5] T. L. Saaty, L. G. Vargas, “Comparison of eigenvalue, logarithmic least squares and least squares methods in estimating ratios”, Math. Modelling, 5:5 (1984), 309–324 | DOI | MR | Zbl

[6] W. W. Koczkodaj, M. Orlowski, “Computing a consistent approximation to a generalized pairwise comparisons matrix”, Comput. Math. Appl., 37:3 (1999), 79–85 | DOI | MR | Zbl

[7] J. González-Pachón, M. I. Rodríguez-Galiano, C. Romero, “Transitive approximation to pairwise comparison matrices by using interval goal programming”, J. Oper. Res. Soc., 54:5 (2003), 532–538 | DOI | MR

[8] G. Dahl, “A method for approximating symmetrically reciprocal matrices by transitive matrices”, Linear Algebra Appl., 403 (2005), 207–215 | DOI | MR | Zbl

[9] M. Gavalec, J. Ramík, K. Zimmermann, Decision making, optimization, Lecture Notes in Economics and Mathematical Systems, 677, Springer, Cham, 2015, 225 pp. | DOI | MR | Zbl

[10] V. P. Maslov, V. N. Kolokol'tsov, Idempotent analysis and its applications in optimal control, Fizmatlit, M., 1994, 144 pp. (In Russian) | MR

[11] J. S. Golan, Semirings and affine equations over them, Mathematics and its Applications, 556, Springer, New York, 2003, 256 pp. | MR

[12] B. Heidergott, G. J. Olsder, J. van der Woude, Max Plus at work, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, 2006, 226 pp. | MR | Zbl

[13] N. K. Krivulin, Methods of idempotent algebra for problems in modeling and analysis of complex systems, St. Petersburg University Publ., St. Petersburg, 2009, 256 pp. (In Russian)

[14] P. Butkovič, Max-linear systems, Springer Monographs in Mathematics, Springer, London, 2010, 274 pp. | DOI | MR | Zbl

[15] N. K. Krivulin, I. V. Gladkikh, “Computation of the consistent pairwise comparison matrix in marketing research by using methods of tropical mathematics”, Vestnik of Saint Petersburg University. Series 8. Management, 2015, no. 1, 3–43 (In Russian)

[16] N. Krivulin, “Rating alternatives from pairwise comparisons by solving tropical optimization problems”, 2015 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), IEEE, 2015, 162–167 | DOI

[17] N. Krivulin, “Using tropical optimization techniques to evaluate alternatives via pairwise comparisons”, 2016 Proceedings 7th SIAM Workshop on Combinatorial Scientific Computing, SIAM, 2016, 62–72 | DOI

[18] N. K. Krivulin, V. A. Ageev, I. V. Gladkikh, “Application of methods of tropical optimization for evaluating alternatives based on pairwise comparisons”, Vestnik of Saint Petersburg University. Applied Mathematics. Informatics. Control Processes, 13:1 (2017), 27–41 (In Russian) | MR

[19] P. J. M. van Laarhoven, W. Pedrycz, “A fuzzy extension of Saaty?s priority theory”, Fuzzy Sets and Systems, 11:1–3 (1983), 229–241 | DOI | MR | Zbl

[20] V. D. Nogin, “A simplified variant of a method for the analysis of hierarchies, based on a nonlinear convolution of criteria”, Journal of Computational Mathematics and Mathematical Physics, 44:7 (2004), 1261–1270 (In Russian) | MR

[21] S. Kubler, J. Robert, W. Derigent, A. Voisin, Y. Le Traon, “A state-of the-art survey and testbed of fuzzy AHP (FAHP) applications”, Expert Syst. Appl., 65 (2016), 398–422 | DOI

[22] B. S. Ahn, “The analytic hierarchy process with interval preference statements”, Omega, 67 (2017), 177–185 | DOI

[23] V. V. Podinovski, “Interval articulation of superiority and precise elicitation of priorities”, European J. Oper. Res., 180:1 (2007), 406–417 | DOI | MR | Zbl

[24] N. Krivulin, S. Sergeev, “Tropical optimization techniques in multicriteria decision making with analytical hierarchy process”, UKSim-AMSS 11th European Modelling Symposium on Computer Modelling and Simulation, EMS 2017, IEEE, 2017, 38–43 | DOI

[25] N. Krivulin, “Methods of tropical optimization in rating alternatives based on pairwise comparisons”, Operations Research Proceedings 2016, Springer, Cham, 2018, 85–91 | DOI | MR | Zbl

[26] N. Krivulin, S. Sergeev, “Tropical implementation of the analytical hierarchy process decision method”, Fuzzy Sets and Systems, 377 (2019), 31–51 | DOI | MR

[27] N. Krivulin, “Tropical optimization problems”, Advances in Economics and Optimization, Economic Issues, Problems and Perspectives, Nova Sci. Publ., New York, 2014, 195–214 | MR