Использование линейного программирования при решении задач теории игр

Лекция 5 (ММвТУиИО) ИСПОЛЬЗОВАНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ РЕШЕНИИ ЗАДАЧ ТЕОРИИ ИГР 1. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗЛП) Определение 1. Общей задачей линейного программирования называется задача, которая ставится следующим образом: Необходимо определить максимальное (минимальное) значение функции (1) при условиях (2) (3) (4) где - заданные постоянные величины и Определение 2. Функция (1) называется целевой функцией (или линейной формой), а условия (2) – (4) – ограничениями данной задачи. Определение 3. Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (2) и (4), где k = m и l = n (т.е. все ограничения имеют вид , а переменные неотрицательны). Определение 4. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (3) и (4), где k = 0 и l = п (т.е. все ограничения имеют вид равенств (=), а переменные неотрицательны) . Определение 5. Совокупность чисел , удовлетворяющих ограничениям задачи (2) – (4), называется допустимым решением (или планом). Определение 6. План , при котором целевая функция задачи (1) принимает свое максимальное (минимальное) значение, называется оптимальным. 1 Лекция 5 (ММвТУиИО) Значение целевой функции (1) при плане Х будем обозначать через . Следовательно, X* – оптимальный план задачи, если для любого Х выполняется неравенство . Указанные выше три формы задачи линейного программирования эквивалентны в том смысле, что каждая из них с помощью несложных преобразований может быть приведена к форме другой задачи. Это означает, что если имеется способ нахождения решения одной из указанных задач, то может быть определен и оптимальный план любой из этих трех задач. Чтобы перейти от одной формы задачи линейного программирования к другой, нужно уметь: 1) сводить задачу минимизации функции к задаче максимизации; 2) переходить от ограничений-неравенств к ограничениям-равенствам и наоборот; 3) избавляться от переменных, которые не удовлетворяют условию неотрицательности. Рассмотрим, как это может быть сделано. Шаг 1. В том случае, когда требуется найти минимум функции можно перейти к нахождению максимума функции , поскольку . Шаг 2. Ограничение-неравенство исходной задачи линейного программирования, имеющее вид “ ”, можно преобразовать в ограничениеравенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида “ ” – в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничение-неравенство преобразуется в ограничение-равенство (5) а ограничение-неравенство – в ограничение-равенство (6) Наоборот, каждое уравнение системы ограничений, заданное равенством можно записать в виде неравенств: (7) Число вводимых дополнительных неотрицательных переменных при преобразовании ограничений-неравенств в ограничения-равенства равно числу преобразуемых неравенств. Замечание. Вводимые дополнительные переменные имеют определенный экономический смысл. Так, если в ограничениях исходной задачи линейного 2 Лекция 5 (ММвТУиИО) программирования отражается расход и наличие производственных ресурсов, то числовое значение дополнительной переменной в плане задачи, записанной в форме основной, равно объему неиспользуемого ресурса. Шаг 3. Если переменная , не подчинена условию неотрицательности, то ее можно заменить двумя неотрицательными переменными и vk, приняв Рассмотрим теперь ЗЛП в стандартной форме: f  c1 x1  ...  cn xn  max (1) a11 x1  ...  a1n x n  b1  a 21 x1  ...  a 2 n x n  b2  ... a x  ...  a x  b mn n m  m1 1  x j  0, j  1, n  (2) Напомним, что в этой задаче:       требуется максимизировать целевую функцию; все ограничения являются неравенствами со знаком «»; задача содержит n переменных и m ограничений; все переменные х1, …, хn неотрицательны; коэффициенты при переменных в целевой функции: с1, …, сn; свободные члены: b1, …, bm. Рассмотрим теперь следующую («производную» от исходной) задачу линейного программирования: g  b1 y1  ...  bm y m  min (3) a11 y1  ...  a m1 y m  c1  a 21 y1  ...  a m 2 y m  c 2  ... a y  ...  a y  c mn m m  1n 1  y i  0, i  1, m (4) В этой задаче:     требуется найти минимум целевой функции; все ограничения – неравенства со знаком «»; переменные y1, …, ym неотрицательны; задача содержит m переменных и n ограничений; 3 Лекция 5 (ММвТУиИО)  коэффициенты при переменных в целевой функции: b1, …, bm (т.е. являются свободными членами исходной задачи линейного программирования), а свободные члены этой задачи: с1, …, cn (т.е. являются коэффициентами целевой функции исходной задачи линейного программирования);  матрица коэффициентов aij двойственной задачи транспонирована, т.е. строки заменены столбцами, а столбцы – строками. Задача (3) - ( 4) называется двойственной к задаче (1) - (2). А обе задачи (1) - (2) и (3) - ( 4) называются парой взаимно двойственных задач линейного программирования. Пара взаимно двойственных задач обладает следующими свойствами (по определению): 1. Если одна из задач является задачей на минимум, то двойственная ей задача будет задачей на максимум. 2. Если в ограничения одной из задач входит n неизвестных и m ограничений, то в ограничения двойственной задачи входит m неизвестных и n ограничений. 3. Матрицы из коэффициентов при неизвестных в левых частях системы ограничений двойственных задач являются транспонированными по отношению друг к другу:  a11 a12 ... a1n     a 21 a 22 ... a 2 n  À ... ... ... ...     a a ... a  mn   m1 m 2  a11 a 21 ... a m1     a12 a 22 ... a m 2  T À  ... ... ... ...     a a ... a  mn   1n 2 n 4. В правых частях специальных ограничений каждой из двойственных задач стоят коэффициенты при неизвестных целевой функции другой задачи. 5. Каждая из двойственных задач может быть задана в стандартной форме. Причем, если в первой задаче все неравенства будут типа , то во второй задаче неравенства будут типа . Для двойственных задач верна следующая теорема. Теорема (двойственности). Если одна из взаимно двойственных задач имеет оптимальное решение х*, то другая также имеет оптимальное решение y*. При этом соответствующие им оптимальные значения целевых функций f*=f(x*) и g*=g(y*) равны: f(x*) = g(y*). Пример 5.1. Пусть дана задача линейного программирования: f  3x1  4 x 2  max 4 Лекция 5 (ММвТУиИО)  x1  x 2  16 4 x  x  48 2  1  x  4 x  48 2  1  x j  0, j  1,2  Требуется составить двойственную задачу линейного программирования и привести ее к канонической форме. Решение: 1) Каноническая форма исходной задачи – f  3x1  4 x 2  max  x3  x1  x 2  16  x  4 x  x  48 1 2  4  x  x  4 x  48 1 2  5  x j  0, j  1,5  2) Составим двойственную задачу к исходной g  16 y1  48 y 2  48 y3  min  y1  4 y 2  y 3  3   y1  y 2  4 y 3  4   y j  0, j  1,3 3) Приведем эту задачу к канонической форме g  16 y1  48 y2  48 y3  max  y1  4 y 2  y 3  y 4  3   y1  y 2  4 y 3  y 5  4   y j  0, j  1,5 2. ПРИВЕДЕНИЕ МАТРИЧНОЙ ИГРЫ К ЗЛП Пусть теперь наша игра задана платежной матрицей (aij) и искомая оптимальная смешанная стратегия игрока А: 𝑃 = {𝑝1 , 𝑝2 , … , 𝑝𝑚 } где - 𝑝1 + 𝑝2 + ⋯ + 𝑝𝑚 = 1 5 Лекция 5 (ММвТУиИО) Оптимальная стратегия Р обеспечивает игроку А выигрыш не меньший чем цена игры ν и выигрыш равный ν, если игрок В придерживается своей оптимальной стратегии. Будем считать, что все выигрыши aij положительны. Этого всегда можно добиться, добавляя ко всем членам матрицы достаточно большое число М; от этого цена игры увеличится на М, а решения Р и Q в смешанных стратегиях не изменятся. Если все выигрыши aij положительны, то и цена игры, т.е. средний выигрыш при оптимальной стратегии тоже положителен: ν > 0. Пусть игрок В использует чистую стратегию Bk, а игрок А использует смешанную стратегию Р, т.е. выбирает чистые стратегии A1, A2, …, Am с вероятностями 𝑝1 , 𝑝2 , … , 𝑝𝑚 . Средний выигрыш игрока А (математическое ожидание выигрыша): 𝑎1𝑘 𝑝1 + 𝑎2𝑘 𝑝2 + ⋯ + 𝑎𝑚𝑘 𝑝𝑚 - не может быть меньше цены игры ν и это справедливо для каждой из чистых стратегий Bk, k=1, …, n, игрока В, т.е. 𝑎11 𝑝1 + 𝑎21 𝑝2 + ⋯ + 𝑎𝑚1 𝑝𝑚 ≥ 𝜈 𝑎12 𝑝1 + 𝑎22 𝑝2 + ⋯ + 𝑎𝑚2 𝑝𝑚 ≥ 𝜈 … {𝑎1𝑛 𝑝1 + 𝑎2𝑛 𝑝2 + ⋯ + 𝑎𝑚𝑛 𝑝𝑚 ≥ 𝜈 Теперь каждое из этих неравенств поделим на ν и введем обозначения 𝑝1 𝑝2 𝑝𝑚 𝑦1 = , 𝑦2 = , …, 𝑦𝑚 = 𝜈 𝜈 𝜈 В этих обозначениях предыдущая система запишется в виде: 𝑎11 𝑦1 + 𝑎21 𝑦2 + ⋯ + 𝑎𝑚1 𝑦𝑚 ≥ 1 𝑎12 𝑦1 + 𝑎22 𝑦2 + ⋯ + 𝑎𝑚2 𝑦𝑚 ≥ 1 … {𝑎1𝑛 𝑦1 + 𝑎2𝑛 𝑦2 + ⋯ + 𝑎𝑚𝑛 𝑦𝑚 ≥ 1 (5) Поделим также выражение 𝑝1 + 𝑝2 + ⋯ + 𝑝𝑚 = 1 на ν, получим 1 𝑦1 + 𝑦2 + ⋯ + 𝑦𝑚 = = 𝑔 𝜈 (6) Игрок А стремится максимизировать значение ν или, что то же самое, минимизировать 𝑔 = 1 𝜈 . Таким образом, приходим к следующей постановке исходной игровой задачи: Требуется найти такие значение неотрицательных переменных 𝒚𝟏 , 𝒚𝟐 , … , 𝒚𝒎 , которые удовлетворяют ограничениям (5) и дают минимальное значение функции (6). Т.о. исходная игра записывается как задача линейного программирования: 1 𝑔 = = 𝑦1 + 𝑦2 + ⋯ + 𝑦𝑚 → 𝑚𝑖𝑛 𝜈 6 Лекция 5 (ММвТУиИО) 𝑎11 𝑦1 + 𝑎21 𝑦2 + ⋯ + 𝑎𝑚1 𝑦𝑚 ≥ 1 𝑎12 𝑦1 + 𝑎22 𝑦2 + ⋯ + 𝑎𝑚2 𝑦𝑚 ≥ 1 … {𝑎1𝑛 𝑦1 + 𝑎2𝑛 𝑦2 + ⋯ + 𝑎𝑚𝑛 𝑦𝑚 ≥ 1 Оптимальная стратегия игрока В ищется аналогично по следующей схеме. Пусть игрок В придерживается своей оптимальной стратегии 𝑄 = {𝑞1 , 𝑞2 , … , 𝑞𝑚 }, а игрок А выбирает только свои чистые стратегии, тогда средний проигрыш игрока В не может быть больше цены игры ν, т.е. 𝑎11 𝑞1 + 𝑎12 𝑞2 + ⋯ + 𝑎1𝑛 𝑞𝑛 ≤ 𝜈 𝑎21 𝑞1 + 𝑎22 𝑞2 + ⋯ + 𝑎2𝑛 𝑞𝑛 ≤ 𝜈 … {𝑎𝑚1 𝑞1 + 𝑎𝑚2 𝑞2 + ⋯ + 𝑎𝑚𝑛 𝑞𝑚 ≤ 𝜈 Вероятности 𝑞1 , 𝑞2 , … , 𝑞𝑛 удовлетворяют условию 𝑞1 + 𝑞2 + ⋯ + 𝑞𝑛 = 1 Поделив данное равенство и все неравенства предыдущей системы на ν и введя обозначения 𝑞1 𝑞2 𝑞𝑚 𝑥1 = , 𝑥2 = , …, 𝑥𝑚 = 𝜈 𝜈 𝜈 получим систему: 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 1 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 1 … {𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑚 ≤ 1 1 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑚 = = 𝑓 𝜈 (7) (8) Цель игрока В состоит в минимизации проигрыша, т.е. в максимизации величины 1 𝑓= . 𝜈 Таким образом, теперь исходная игровая задача сводится к нахождению неотрицательных переменных 𝑥1 , 𝑥2 , … , 𝑥𝑛 , обеспечивающих максимальное значение функции (8) при выполнении ограничений (7). 1 𝑓 = = 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑚 → 𝑚𝑎𝑥 𝜈 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 1 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 1 … {𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑚 ≤ 1 7 Лекция 5 (ММвТУиИО) Сравнивая две полученные т.о. задачи линейного программирования (5) - (6) и (7) (8), видим, что для записи ограничений используется одна и та же матрица 𝑎11 𝑎12 … 𝑎1𝑛 𝑎21 𝑎22 … 𝑎2𝑛 𝐴=( … … … … ), 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 только в системе (7) используются строки матрицы А, а в системе (5) – столбцы. Задачи (6) - (5) и (8) - (7) являются парой взаимно двойственных задач. Пример 5.2. Предприятие может выпускать 3 вида продукции A1, A2, A3. Спрос на продукцию предприятия зависит от многих факторов и может находиться в одном из состояний В1, В2, В3, В4. Известна прибыль, которую приносит реализация каждого вида продукции при различных состояниях спроса: Состояния спроса В2 В3 3 6 10 4 7 5 В1 В4 Виды A1 3 8 продукции A2 9 2 A3 7 4 Требуется формализовать данную задачу. Решение. Эта экономическая задача сводится к игре предприятия (игрок А), которое должно определить вид выпускаемой продукции в зависимости от состояния спроса (игрок В). Платежная матрица: 3 3 6 8 A=(9 10 4 2) 7 7 5 4 Анализируя стратегии игроков, замечаем, что стратегия В1 доминирует над стратегией В2, т.к. все элементы столбца В1 меньше или равны соответствующих элементов столбца В2, поэтому столбец можно исключить из рассмотрения. В результате получаем платежную матрицу: 3 6 8 A=(9 4 2) 7 5 4 Определим верхнюю и нижнюю цену игры. В1 В2 A1 3 6 A2 9 4 A3 7 5 β 9 6 Нижняя и верхняя цена игры не совпадают: В3 8 2 4 8 α 3 2 4 8 Лекция 5 (ММвТУиИО) α = 4 < β = 6, поэтому матрица не имеет седловой точки и игра не имеет решения в чистых стратегиях. Найдем смешанные стратегии 𝑃 = {𝑝1 , 𝑝2 , 𝑝3 } и 𝑄 = {𝑞1 , 𝑞2 , 𝑞3 }. Введем обозначения 𝑦𝑖 = 𝑝𝑖 𝜈 , 𝑖 = 1,2,3; 𝑥𝑗 = 𝑞𝑗 𝜈 , 𝑗 = 1,2,3 и составим две задачи линейного программирования: Игрок А (предприятие) 𝑔 = 𝑦1 + 𝑦2 + 𝑦3 → 𝑚𝑖𝑛 3𝑦1 6𝑦1 8𝑦1 { 𝑦𝑖 + 9𝑦2 + 4𝑦2 + 2𝑦2 ≥ 0, + 7𝑦3 ≥ 1 + 5𝑦3 ≥ 1 + 4𝑦3 ≥ 1 𝑖 = 1,2,3 Игрок B (спрос) 𝑓 = 𝑥1 + 𝑥2 + 𝑥3 → 𝑚𝑎𝑥 3𝑥1 + 6𝑥2 9𝑥1 + 4𝑥2 7𝑥1 + 5𝑥2 { 𝑥𝑖 ≥ 0, + 8𝑥3 ≤ 1 + 2𝑥3 ≤ 1 + 4𝑥3 ≤ 1 𝑗 = 1,2,3 3. РЕШЕНИЕ ЗАДАЧ ЗЛП Классификацию подходов к решению задач линейного программирования можно представить в виде следующей таблицы: Метод решения Примечание 1. Графический Решение при двух переменных (x1, x2) метод 2. Метод Гомори Решение полностью целочисленных задач ЗЛП (1950г.) Алгоритм решения: метод отсечений Формы записи: симплексная таблица 3. Симплексный Алгоритм решения: метод искусственного базиса метод (экспоненциальная сложность) 4. Метод Алгоритм полиномиальной сложности не получил развития, но эллипсоидов привёл к созданию целого класса эффективных алгоритмов ЛП (1979г., Хачиян Л.) ИТЕРАЦИОННЫЙ МЕТОД РЕШЕНИЯ МАТРИЧНЫХ ИГР Опишем эвристический метод отыскания решения матричной игры, основанный на накопления опыта постепенной выработки игроками хороших стратегий в результате многих повторений конфликтных ситуаций. 9 Лекция 5 (ММвТУиИО) Основная идея этого метода заключается в том, чтобы смоделировать «практическое обучение» игроков в ходе самой игры, когда каждый из них на опыте учитывает поведение противника и старается отвечать на него наиболее выгодным для себя образом - всякий раз при возобновлении игры игрок выбирает наиболее выгодную для себя стратегию, опираясь на предыдущий выбор противника. Проиллюстрируем этот метод на примере игры, заданной матрицей 2 0 3 ( ) 1 3 −3 В этой игре нижняя цена игры равна 0, верхняя цена игры – 2. Следовательно, седловой точки нет. Опишем правила выбора ходов игроками. Пусть, для определенности, начинает игрок А: ход игрока А – стратегия А1 - (2 𝟎 3) Игрок В, учитывая это, выбирает свою стратегию так, чтобы выигрыш игрока А был минимален, т.е. (в данном случае) равен нулю: ход игрока В – стратегия В2 – ( ) 𝟑 Игрок А выбирает свою стратегию так, чтобы его выигрыш при стратегии В2 игрока В был максимален: ход игрока А – стратегия А2 - (1 3 −3) Игрок В выбирает свою стратегию так, чтобы «накопленный» выигрыш игрока А при стратегиях А1 и А2 был минимален: (2 0 3) + (1 3 −3) = (3 3 𝟎) 3 ход игрока В – стратегия В3 = ( ) −3 Игрок А выбирает свою стратегию так, чтобы его «накопленный» выигрыш при стратегиях В2 и В3 игрока В был максимален: 3 𝟑 ( )+( )=( ) 3 −3 ход игрока А – стратегия А1 = (2 0 3) Игрок В выбирает свою стратегию так, чтобы «накопленный» выигрыш игрока А при стратегиях А1, А2 и А1 был минимален: (3 3 0) + (2 0 3) = (5 𝟑 3) ход игрока В – стратегия В2 = ( ) 𝟑 10 Лекция 5 (ММвТУиИО) и т.д. Разобьем последовательные ходы игроков А и В на пары (ход игрока А, ход игрока В) и запишем результаты в таблице, где: n 1 1 2 3 4 5 6 7 8 9 10 11 12 … i 2 1 2 1 1 2 1 1 2 1 1 2 1 B1 3 2 3 5 7 8 10 12 13 15 17 18 20 B2 4 3 3 3 6 6 6 9 9 9 12 12 B3 5 3 3 6 3 6 9 6 9 12 9 12 ν*(n) 6 0,00 0,00 1,00 0,75 0,60 1,00 0,86 0,75 1,00 0,90 0,82 1,00 k 7 2 3 2 2 3 2 2 3 2 2 3 2 A1 8 3 3 3 6 6 6 9 9 9 12 12 A2 9 3 3 6 3 6 9 6 9 12 9 12 ν*(n) 10 3,00 1,50 1,00 1,50 1,2 1,00 1,44 1,13 1,00 1,20 1,09 1,00 ν(n) 11 1,50 0,75 1,00 1,12 0,9 1,00 1,15 0,93 1,00 1,05 0,96 1,00 1-ый столбец – номер n шага (пары последовательных ходов игроков А и В); 2-ой столбец – номер i стратегии, выбранной игроком А; 3-ий столбец – «накопленный» суммарный выигрыш игрока А за первые n шагов при выборе игроком В стратегии В1; 4-ый столбец – «накопленный» суммарный выигрыш игрока А за первые n шагов при выборе игроком В стратегии В2; 5-ый столбец – «накопленный» суммарный выигрыш игрока А за первые n шагов при выборе игроком В стратегии В3; (минимальный из этих выигрышей выделяется полужирным шрифтом), 6-ой столбец – минимальный средний выигрыш игрока А, равный минимальному накопленному им выигрышу за первые n шагов, деленному на число этих шагов; 7-ой столбец – номер k стратегии, выбранной игроком В; 8-ой столбец – «накопленный» суммарный выигрыш игрока А за первые n шагов при выборе им стратегии А1; 9-ый столбец – «накопленный» суммарный выигрыш игрока А за первые n шагов при выборе им стратегии А2; (максимальный из этих выигрышей выделяется полужирным шрифтом), 10-ый столбец – максимальный средний выигрыш игрока А, равный максимальному накопленному им выигрышу за первые n шагов, деленному на число этих шагов; 11 Лекция 5 (ММвТУиИО) 11-ый столбец – среднее арифметическое минимального среднего выигрыша и максимального среднего выигрыша игрока А. Решение игры определяется приближенно по окончании любого из шагов:  за приближенную цену игры берется среднее арифметическое ν(n), полученное на n-м шаге;  смешанные стратегии противников определяются частотами появления чистых стратегий. Например, после 9-го шага имеем ν(9) = 1,00 При этом игрок А 6 раз использовал стратегию А1 и 3 раза стратегию А2. В свою очередь игрок В 6 раз применял стратегию В2, 3 раза стратегию В3, а стратегией В1 не пользовался вообще. Отсюда получаем, что 2 1 2 1 𝑃9 ≈ { , } , 𝑄9 ≈ {0, , } 3 3 3 3 Соответственно, после 10-го шага получаем ν(10) = 1,05 7 3 7 3 𝑃9 ≈ { , } , 𝑄9 ≈ {0, , } 10 10 10 10 Т.к. эта игра легко решается графически, то можно сравнить полученные результаты с точными: ν=1 2 1 2 1 𝑃 = { , }, 𝑄 = {0, , } 3 3 3 3 Сравнивая результаты, полученные на 9-м, 10-м, а также 11-м и 12-м шагах: ν(11) = 0,96 7 4 7 4 𝑃11 ≈ { , } , 𝑄11 ≈ {0, , } 11 11 11 11 ν(12) = 1,00 2 1 2 1 𝑃12 ≈ { , } , 𝑄11 ≈ {0, , } 3 3 3 3 можно заметить, что по мере увеличения числа шагов приближенные значения все меньше отличаются от точных. 12 Лекция 5 (ММвТУиИО) Замечания: 1) При увеличении числа шагов все три величины ν*(n), ν*(n) и ν(n) будут приближаться к цене игры ν, но среднее арифметическое ν(n) будет приближаться к ν сравнительно быстрее. 2) Хотя сходимость итераций достаточно медленна, тем не менее, даже «неглубокий» расчет дает возможность находить ориентировочное значение цены игры и доли чистых стратегий. 3) Сравнительно медленную скорость сходимости можно объяснить рядом причин. Укажем одну из них, психологически наиболее интересную. Если, к примеру, игрок А уже нашел свою оптимальную смешанную стратегию, то он не склонен останавливаться на ней – он продолжит попытки выиграть у противника В побольше, особенно если последний еще не достиг своего оптимума. Тем самым игрок А может (невольно) ухудшить свое положение. 4) Основные преимущества описанного метода: - простота и универсальность (с его помощью можно относительно легко найти приближенное решение любой матричной игры); - объем и сложность вычислений сравнительно слабо растут по мере увеличения числа стратегий игроков (размеров матрицы игры). 13