SOLVING GAME-TYPE COMBINATORIAL OPTIMIZATION PROBLEMS ON PERMUTATIONS WITH CONSTRAINTS ON THE STRATEGIES OF ONE PLAYER

Abstract

Problems of combinatorial optimization for multiple permutations are increasingly encountered in practice and require research and solution, therefore there is a need to develop new and modify existing methods for their solution. The purpose of the work is to propose new methods of solving combinatorial optimization problems of the game type on multiple permutations, to build an algorithm for solving such problems. Conduct an analysis of its complexity, in particular, give a theoretical assessment of the method. Methodology. Combinatorial optimization and mathematical programming methods were used to create an algorithm for solving game-type combinatorial optimization problems on permutations with restrictions on the strategies of one player. Scientific novelty. As part of the study of game-type combinatorial optimization problems, the possibility of using a monotone iterative algorithm for solving this class of problems with multiple permutations was studied. The paper describes the algorithm of the developed monotonic iterative method for finding the price of the game for solving problems of combinatorial optimization of the game type on a set of permutations with restrictions on the strategy of one player. The considered monotonic iterative algorithm includes eleven steps and allows finding the price of the game given by a matrix of arbitrary dimension and a set of numbered permutations – the strategies of the first player. The complexity of the proposed algorithm was evaluated. For the convenience of presenting the material, the necessary designations and explanations have been introduced. When calculating the complexity of the algorithm, an asymptotic upper bound is determined with accuracy up to a constant factor. A theoretical estimation of the working time of the monotone iterative method was found. The results of the research are formulated in the form of a theorem with a consistently presented substantiated proof. An illustrative example is presented for the purpose of applying the developed algorithm. The solution of the task is described in detail according to the steps of the algorithm. The obtained result is compared with solutions by other methods, in particular, by moving from the game problem of combinatorial optimization of the game type with multiple permutations to a pair of dual problems of linear programming for a matrix game with a payment matrix and an iterative method. The correctness of the obtained results was confirmed based on the coincidence of the answers obtained in three different ways. Conclusions. The monotone iterative method allows us to quickly obtain the value of the price of the game with a given accuracy and the optimal strategy of the first player, and, as it was found, the number of steps of the method depends weakly on the dimension of the problem. The developed algorithm of the monotonic iterative method made it possible to compare the results with previously known methods to confirm their correctness.