Найти max F = y1 + y2 + … + yn при неотрицательных переменных

Решим данную задачу в Excel с помощью поиска решения. Для этого введем данные и формулы на лист Excel. Окно поиска решения и результаты представлены на рисунке ниже:
Таким образом, цена игры v = 4,6,
Оптимальная смешанная стратегия игрока 2
q = (0; 0; 0,5; 0,05; 0; 0; 0,45).
Ответ
Цена игры v = 4,6,
оптимальная смешанная стратегия игрока 1: р = (0; 0,2; 0; 0,18; 0; 0,24; 0,38),
оптимальная смешанная стратегия игрока 2: q = (0; 0; 0,5; 0,05; 0; 0; 0,45).
Решение методом фиктивной партии
В 1-ой партии оба игрока выбирают произвольную чистую стратегию. Пусть сыграно k партий, причем выбор стратегии в каждой партии запоминается. В (k + 1)-ой партии каждый игрок выбирает ту чистую стратегию, которая максимизирует его ожидаемый выигрыш, если противник играет в соответствии с эмпирическим вероятностным распределением, сформировавшимся за k партий. Оценивается интервал для цены игры и, если он достаточно мал, процесс останавливается. Полученные при этом вероятностные распределения определяют смешанные стратегии игроков.
Решение игры методом Брауна (методом фиктивной партии) начинается со случайного выбора стратегии одной из сторон.
Пусть сторона А выбрала стратегию Аi. Выпишем элементы этой стратегии под игровой матрицей.
Сторона В, минимизируя свой проигрыш, выберет стратегию Вj, соответствующую минимальному элементу стратегии Аi. Выпишем элементы стратегии В справа от матрицы. Сторона А находит среди элементов стратегии В; максимальный элемент и выбирает стратегию Ak соответствующую максимальному выигрышу. Элементы стратегии Аk прибавляются к элементам стратегии А, и записываются под матрицей.
Аналогичные итерации повторяются столько раз, сколько необходимо для решения игры с требуемой точностью. На каждой итерации определяются накопленный максимальный выигрыш стороны А и накопленный минимальный проигрыш стороны В.
Подсчитав число отмеченных элементов в каждой стратегии сторон, получим частоту использования каждой стратегии путем деления числа отмеченных элементов стратегии на общее число итераций.
При достаточно большом числе итераций частоты стратегий сводятся к вероятностям, которые и являются оптимальными решениями матричной игры . За N проведенных итераций будут получены оптимальные стратегии:
Рассмотрим несколько итераций для нашей матрицы.
Пусть на 1-м шаге игрок 1 выбирает стратегию 1 i = 1.
k i A1 A2 A3 A4 A5 A6 A7 j B1 B2 B3 B4 B5 B6 B7 v min
v max
v
1 1 5 2 -3 7 12 9 -4 7 -4 14 12 8 1 0 1 -4 14 5
Минимальный выигрыш достигается в 7-м столбце, т.е. чтобы уменьшить выигрыш 1-го игрока игрок 2 должен выбрать 7-ю стратегию j = 7, далее выписываем значения 7-го столбца матрицы. Определяем минимум из A, затем максимум из В, цена игры на 1-м шаге v = (v min + v max)/(2k)
На 2-м шаге игрок 1 выбирает стратегию, которая увеличивает проигрыш игрока 2 i = 2.
k i A1 A2 A3 A4 A5 A6 A7 j B1 B2 B3 B4 B5 B6 B7 v min
v max
v
1 1 5 2 -3 7 12 9 -4 7 -4 14 12 8 1 0 1 -4 14 5
2 2 4 6 -7 13 20 16 10 3 -7 10 2 9 -4 9 9 -7 10 0,75
Далее записывается накопленный выигрыш игрока 1 – к предыдущим значениям прибавляются элементы 2-й строки. Минимальный выигрыш достигается в 3-м столбце, т.е. чтобы уменьшить выигрыш 1-го игрока игрок 2 должен выбрать 3-ю стратегию j = 3, далее выписываем накопленный проигрыш игрока 2 – к предыдущим значениям прибавляются элементы 3-го столбца. Определяем минимум из A, затем максимум из В, цена игры на 2-м шаге
v = (v min + v max)/(2k)
На 3-м шаге игрок 1 выбирает стратегию, которая увеличивает проигрыш игрока 2 i = 2.
k i A1 A2 A3 A4 A5 A6 A7 j B1 B2 B3 B4 B5 B6 B7 v min
v max
v
1 1 5 2 -3 7 12 9 -4 7 -4 14 12 8 1 0 1 -4 14 5
2 2 4 6 -7 13 20 16 10 3 -7 10 2 9 -4 9 9 -7 10 0,75
3 2 3 10 -11 19 28 23 24 3 -10 6 -8 10 -9 18 17 -11 18 1,166667
Далее записывается накопленный выигрыш игрока 1 – к предыдущим значениям прибавляются элементы 2-й строки. Минимальный выигрыш достигается в 3-м столбце, т.е. чтобы уменьшить выигрыш 1-го игрока игрок 2 должен выбрать 3-ю стратегию j = 3, далее выписываем накопленный проигрыш игрока 2 – к предыдущим значениям прибавляются элементы 3-го столбца. Определяем минимум из A, затем максимум из В, цена игры на 2-м шаге
v = (v min + v max)/(2k)
И т.д