вар 2. Решение игры в чистых стратегиях. Игроки
 Скачать 36.84 Kb.
|
|
Задание 1 1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 1, которая указывает на максимальную чистую стратегию A1. Верхняя цена игры b = min(bj) = 2. Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 1 ≤ y ≤ 2. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии). 2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы. С позиции проигрышей игрока В стратегия B1 доминирует над стратегией B2 (все элементы столбца 1 меньше элементов столбца 2), следовательно, исключаем 2-й столбец матрицы. Вероятность q2 = 0.
В платежной матрице отсутствуют доминирующие строки. Мы свели игру 2 x 4 к игре 2 x 3. 3. Находим решение игры в смешанных стратегиях. Решим задачу геометрическим методом, который включает в себя следующие этапы: 1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый - стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2). 2. На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2. Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет. Выделяем нижнюю границу выигрыша B1NB3. Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B1B1 и B3B3, для которых можно записать следующую систему уравнений: y = 1 + (2 - 1)p2 y = 5 + (-5 - 5)p2 Откуда p1 = 7/11 p2 = 4/11 Цена игры, y = 15/11 Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B2, которая дает явно больший проигрыш игроку B, и, следовательно, q2 = 0. q1+5q3 = y 2q1-5q3 = y q1+q3 = 1 или q1+5q3 = 15/11 2q1-5q3 = 15/11 q1+q3 = 1 Решая эту систему, находим: q1 = 10/11. q3 = 1/11.  Ответ: Цена игры: y = 15/11, векторы стратегии игроков: Q(10/11, 0, 1/11), P(7/11, 4/11) Поскольку из исходной матрицы были удалены и столбцы, то найденные векторы вероятности можно записать в виде: P(7/11,4/11) Q(10/11,0,0,1/11) Симплексный метод Математические модели пары двойственных задач линейного программирования можно записать так: найти минимум функции F(x) при ограничениях (для игрока II): 6x1+7x2 ≥ 1 9x1+3x2 ≥ 1 10x1 ≥ 1 F(x) = x1+x2 → min найти максимум функции Z(y) при ограничениях (для игрока I): 6y1+9y2+10y3 ≤ 1 7y1+3y2 ≤ 1 Z(y) = y1+y2+y3 → max Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции Z(Y) = y1+y2+y3 при следующих условиях-ограничений. 6y1+9y2+10y3≤1 7y1+3y2≤1 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). 6y1+9y2+10y3+y4 = 1 7y1+3y2+y5 = 1 Решим систему уравнений относительно базисных переменных: y4, y5 Полагая, что свободные переменные равны 0, получим первый опорный план: Y0 = (0,0,0,1,1)
Переходим к основному алгоритму симплекс-метода. Итерация №0. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной y3, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: min (1 : 10 , - ) = 1/10 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (10) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы. Вместо переменной y4 в план 1 войдет переменная y3. Получаем новую симплекс-таблицу:
Итерация №1. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной y1, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (1/10 : 3/5 , 1 : 7 ) = 1/7 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (7) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы. Вместо переменной y5 в план 2 войдет переменная y1. Получаем новую симплекс-таблицу:
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Оптимальный план можно записать так: y1 = 1/7, y2 = 0, y3 = 1/70 Z(Y) = 1*1/7 + 1*0 + 1*1/70 = 11/70 Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи. x1=1/10, x2=2/35 Это же решение можно получить, применив теоремы двойственности. Из теоремы двойственности следует, что X = C*A-1. Составим матрицу A из компонентов векторов, входящих в оптимальный базис. Определив обратную матрицу D = А-1 через алгебраические дополнения, получим: Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных. Тогда X = C*A-1 = = Оптимальный план двойственной задачи равен: x1 = 1/10, x2 = 2/35 F(X) = 1*1/10+1*2/35 = 11/70 Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков: qi = g*yi; pi = g*xi. Цена игры: g = 1 : 11/70 = 70/11 p1 = 70/11*1/10 = 7/11 p2 = 70/11*2/35 = 4/11 Оптимальная смешанная стратегия игрока I: P = (7/11; 4/11) q1 = 70/11*1/7 = 10/11 q2 = 70/11*0 = 0 q3 = 70/11*1/70 = 1/11 Оптимальная смешанная стратегия игрока II: Q = (10/11; 0; 1/11) Поскольку ранее к элементам матрицы было прибавлено число (5), то вычтем это число из цены игры. 64/11 - 5 = 14/11 Цена игры: v=15/11 Проверим правильность решения игры с помощью критерия оптимальности стратегии. ∑aijqj ≤ v ∑aijpi ≥ v M(P1;Q) = (1*10/11) + (4*0) + (5*1/11) = 1.364 = v M(P2;Q) = (2*10/11) + (-2*0) + (-5*1/11) = 1.364 = v M(P;Q1) = (1*7/11) + (2*4/11) = 1.364 = v M(P;Q2) = (4*7/11) + (-2*4/11) = 1.818 ≥ v M(P;Q3) = (5*7/11) + (-5*4/11) = 1.364 = v Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно. Поскольку из исходной матрицы были удалены и столбцы, то найденные векторы вероятности можно записать в виде: P(7/11,4/11) Q(10/11,0,0,1/11) Задание 2 v(1)=v(2)=v(3)=1 V(12) = 3 v(13) = 6 v(23) = 4 v(123) = 10 Найдём вектор Шепли по формуле  Расчет выполним в виде таблицы
Вектор Шепли  Ядро пустое |