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

Задачи комбинаторной оптимизации игрового типа, в которых на стратегии игроков накладываются комбинаторные ограничения, являются актуальным классом задач комбинаторной оптимизации. Для решения этого класса задач разработаны итерационные методы, которые построены на принципе разыгрывания игры и подобны методу Брауна-Робинсон в матричных играх. Эти методы реализованы в программном комплексе. Численные эксперименты, проведенные с его помощью, показывают, что итерационный алгоритм является сходящимся. Это же обосновано и теоретическим исследованием сходимости. Целью дан- ной публикации является определение априорной оценки скорости сходимости итерационного метода решения задач комбинаторной оптимизации игрового типа с ограничениями-перестановками на стратегии одного игрока, а также распространение этой оценки на задачи данного класса с другими комбинаторными ограничениями. С помощью разработанной программной реализации было проведено сравнение полученной теоретической оценки скорости сходимости метода с результатами, полученными экспериментально. Согласно полученным результатам, полученная теоретическая оценка скорости сходимости подтвердилась экспериментально. Так, в частности, на задачах с порядком квадратной матрицы, равным 10, было обнаружено, что скорость сходимости не превышает ее теоретическую оценку уже на 5-й итерации. В работе рассмотрены доказательства сходимости, оценки скорости сходимости итерационного метода решения комбинаторных оптимизационных задач с ограничениями-перестановками, которые накладываются на стратегии одного игрока. Поскольку комбинаторные ограничения на стратегии игроков могут быть представлены различными комбинаторными множествами проведено обобщение оценки скорости сходимости итерационных методов решения задач комбинаторной оптимизации игрового типа с различными типами комбинаторных ограничений.