Поиск локально оптимальных стратегий в линейной игровой задаче с благоприятными ситуациями

Рассматривается линейная игровая задача двух игроков. Два игрока поочерёдно выбирают свои стратегии из соответствующих множеств. Сначала первый игрок выбирает свою стратегию, затем, зная стратегию первого игрока, второй игрок выбирает свою стратегию. Множество стратегий второго игрока зависит от стратегии первого игрока. Целью первого игрока является выбор стратегии для того, чтобы максимизировать выпуклую кусочно линейную функцию (функцию минимума по стратегии второго игрока). Цель второго игрока  — минимизировать линейную функцию. Предложен алгоритм, позволяющий строить стратегии для этой, а также для двойственной задачи, удовлетворяющие необходимым условиям оптимальности «высокого порядка». Этот алгоритм использует формулу приращения целевой функции двойственной задачи. Доказаны теоремы о конечности предложенного алгоритма и его модификации. Приведён пример, иллюстрирующий работу алгоритма. Также приведены результаты численного эксперимента по построению стратегий, удовлетворяющих необходимым условиям оптимальности «высокого порядка» в задачах, элементы которых генерировались датчиком случайных чисел. По результатам численного эксперимента можно сделать вывод, что при исполнении предложенного алгоритма зачастую имеется возможность перехода от одной локально оптимальной стратегии первого игрока к другой стратегии, обеспечивающей возрастание целевой функции. Табл. 1, ил. 1, библиогр. 21.