Оцiнка швидкостi збiжностi iтерацiйного методу розв’язування комбiнаторних оптимiзацiйних задач iгрового типу

Журнал: 
Страница: 
31
УДК: 
519.83
Задачи комбинаторной оптимизации игрового типа, в которых на стратегии игроков накладываются комбинаторные ограничения, являются актуальным классом задач комбинаторной оптимизации. Для решения этого класса задач разработаны итерационные методы, которые построены на принципе разыгрывания игры и подобны методу Брауна-Робинсон в матричных играх. Эти методы реализованы в программном комплексе. Численные эксперименты, проведенные с его помощью, показывают, что итерационный алгоритм является сходящимся. Это же обосновано и теоретическим исследованием сходимости. Целью дан- ной публикации является определение априорной оценки скорости сходимости итерационного метода решения задач комбинаторной оптимизации игрового типа с ограничениями-перестановками на стратегии одного игрока, а также распространение этой оценки на задачи данного класса с другими комбинаторными ограничениями. С помощью разработанной программной реализации было проведено сравнение полученной теоретической оценки скорости сходимости метода с результатами, полученными экспериментально. Согласно полученным результатам, полученная теоретическая оценка скорости сходимости подтвердилась экспериментально. Так, в частности, на задачах с порядком квадратной матрицы, равным 10, было обнаружено, что скорость сходимости не превышает ее теоретическую оценку уже на 5-й итерации. В работе рассмотрены доказательства сходимости, оценки скорости сходимости итерационного метода решения комбинаторных оптимизационных задач с ограничениями-перестановками, которые накладываются на стратегии одного игрока. Поскольку комбинаторные ограничения на стратегии игроков могут быть представлены различными комбинаторными множествами проведено обобщение оценки скорости сходимости итерационных методов решения задач комбинаторной оптимизации игрового типа с различными типами комбинаторных ограничений.
info_eng: 
Combinatorial optimization problems of the gaming type in which combinatorial restrictions are imposed on the strategies of the players are an important class of combinatorial optimization problems. For solving this class of problems iterative methods were previously developed such as game-playing and those similar to the method of Brown - Robinson in matrix games. These methods are implemented in software. Numerical experiments conducted on it show that the iterative algorithm is convergent. It’s also proved through theoretical study of convergence. The purpose of this publication is to define the a priori estimate of the convergence rate of the iterative method for solving combinatorial optimization problems of the gaming type with restrictions and permutations on the strategy of one player, as well as to spread this estimate on problems of the same class with other combinatorial restrictions. Using the developed software implementation, the theoretical estimate of the convergence rate of the method was compared to the results obtained experimentally. According to the results, the theoretical estimate of the rate of convergence was confirmed experimentally. In particular, the problems with a square matrix of order A that is equal to 10, it was found that the rate of convergence does not exceed its theoretical estimate at the 5th iteration already. This article examines the proof of convergence, the estimate of the convergence rate of the iterative method for solving combinatorial optimization problems with restrictions and permutations that are imposed on the strategies of one player. Since combinatorial restrictions on strategies of players can be represented as different combinatorial sets, we carried out a synthesis of the estimate of the convergence rate of iterative methods for solving combinatorial optimization problems of the gaming type with different types of combinatorial restrictions.