Алгоритм решения игры mxn методом Шепли-Сноу.

1) Исходную платежную матрицу редуцируем, исключив из нее строго доминируемые строки и столбцы.

2) К каждому элементу платежной матрицы прибавляем константу d, чтобы исключить равенство нулю цены игры.

3) Из полученной матрицы вырезаются вспомогательные квадратные матрицы размерностью от 2х2 до rxrr=min(m,n)

4) Для каждой из полученных матриц составить системы уравнений.

5) Решение каждой из систем проверить на неотрицательность и принадлежность к выполнению условий оптимальности …..

6) Найденные решения систем являются оптимальными, но не обязательно крайними. Полный перебор квадратных подматриц приведет к накоплению некоторых множеств S_a^0*иS_b^0*оптимальных стратегий, включающих в себя множества крайних оптимальных стратегий extS_a S_a^0*итд.

7) Выпуклые оболочки найденных оптимальных стратегий являются множествами всех оптимальных стратегий игроков.

47. Решение игры mxn приближенным методом Брауна-Робинсон.

Для матриц большой размерности применение методов линейного программирования приводит к громоздким вычислениям, поэтому удобнее использовать приближенные методы решения. Одним из таких методов является итеративный метод Брауна-Робинсона, или метод фиктивного разыгрывания. Идея метода – многократное фиктивное разыгрывание игры. В первой партии каждый игрок выбирает произвольную чистую стратегию, в k -ой партии каждый выбирает ту стратегию, которая принесла максимальный суммарный выигрыш (для первого игрока) или минимальный суммарный проигрыш (для второго игрока) в (k -1)-ой партии.

Можно доказать, что , где v – цена игры, k – номер партии, – максимальное значение суммарного выигрыша 1-го игрока в k -ой партии при выборе различных стратегий, – минимальное значение суммарного проигрыша 2-го игрока в k -ой партии при выборе различных стратегий.

За приближенные оптимальные стратегии игроков принимают векторы, координатами которых являются относительные частоты выбора соответствующих чистых стратегий.

Преимущество метода – его простота, недостаток – малая скорость сходимости вследствие немонотонности последовательностей и

Т о сведении решения матричной игры к решению пары двойственных друг другу стандартных задач линейного программирования

Имеется игры с платежной матрицей

1. н-ти при огран-иях x_i≥0, i=1,…,m, ≥1, j=1,…,n; 2. н-ти при огран-иях y_j≥0, j=1,…,n; ≤1, i=1,…,m, где элементы мат-цы Aa_ij>0, i=1,…,m, j=1,…,n. (3)Точнее говоря, если - опт.решения задачи 1, а - опт. решение задачи 2, то (4) — цена игры с матрицей A, (5)- опт. стр. иг-ка А, (6)- опт.стр. иг-ка B.

Верно и обратное утверждение.

Определение и Т о симметричной матричной игре.

Матричная игра называется симметричной, если ее платежная мат-ца кососимметрическая.

Т. Для симметричной матричной игры справедливы следующие утверждения:

1. Число чистых стр-ий иг-ка А (m) совпадает с числом чистых стр-ий иг-ка В (n): m=n. 2. Размерности векторов смеш. стр-ий обоих иг-ов одинаковы. 3. Мн-ва смеш. стр-ий иг-ов совпадают: S_A=S_B. 4. Симметричная матричная игра справедлива, т. е. ее цена V=0. 5. Мн-ва опт.стр-ий иг-ов совпадают:

Т о сведении решения пары взаимно двойственных задач линейного программирования к решению симметричной матричной

Игры.

Т. Решение следующей пары взаимно двойственных задач линейного программирования:

1. найти max при ограничениях x_j≥0, j=1,…,m, , i=1,…,n;

2. найти min при ограничениях y_i≥0, i=1,…,n, , j=1,…,m,

эквивалентно решению симметричной матричной игры с матрицей , где , , - квадратные нулевые мат-цы соответствующих порядков, и — соответственно мат-ца коэффициентов при неизвестных и вектор-столбец свободных членов системы ограничений в задаче 1; - вектор-строка коэффициентов при неизвестных целевой ф-ии задачи 1.

Можно уточнить вышеизложенное:

Если (1) — опт.стр. любого иг-ка в игре с матрицей D и >0, то (2) — опт. решение задачи 1, а

(3) — опт.решение задачи 2.

Обратно, если — опт.решение задачи 1, а -опт. решение задачи 2, то (4) где (5) является опт. стратегией любого иг-ка в игре с матрицей D. Для того, чтобы пара взаимно двойственных задач линейного программирования 1 и 2 имела опт.решение ⇔чтобы в игре с матрицей D∃а опт. стр. (1), в которой >0.