Дана матрица игры Найти оптимальные стратегии игроков А и В двумя методами (графическим и аналитическим) 819543 3612 1-й способ Проверяем

Дана матрица игры. Найти оптимальные стратегии игроков А и В двумя методами (графическим и аналитическим)
819543 3612
1-й способ

Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
Игроки B1 B2 B3 B4 B5 a = min(Ai)
A1 8 1 9 3 6 1
A2 5 4 3 1 2 1
b = max(Bi) 8 4 9 3 6 Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 1, которая указывает на максимальную чистую стратегию A1.Верхняя цена игры b = min(bj) = 3.Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 1 ≤ y ≤ 3. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.Находим решение игры в смешанных стратегиях.Решим задачу геометрическим методом, который включает в себя следующие этапы:1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый – стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2).2. На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B2B2 и B4B4, для которых можно записать следующую систему уравнений:y = 1 + (4 – 1)p2y = 3 + (1 – 3)p2Откудаp1 = 3/5p2 = 2/5Цена игры, y = 11/5Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B1,B3,B5, которая дает явно больший проигрыш игроку B, и, следовательно, q1 = 0,q3 = 0,q5 = 0.q2+3q4 = y4q2+q4 = yq2+q4 = 1илиq2+3q4 = 11/54q2+q4 = 11/5q2+q4 = 1Решая эту систему, находим:q2 = 2/5.q4 = 3/5.Ответ: Цена игры: y = 11/5, векторы стратегии игроков: Q(0, 2/5, 0, 3/5, 0), P(3/5, 2/5)
2-й способ
Находим решение игры в смешанных стратегиях.Математические модели пары двойственных задач линейного программирования можно записать так:найти минимум функции F(x) при ограничениях:8×1+5×2 ≥ 1×1+4×2 ≥ 19×1+3×2 ≥ 13×1+x2 ≥ 16×1+2×2 ≥ 1F(x) = x1+x2 → minнайти максимум функции Ф(y) при ограничениях:8y1+y2+9y3+3y4+6y5 ≤ 15y1+4y2+3y3+y4+2y5 ≤ 1Ф(y) = y1+y2+y3+y4+y5 → maxРешаем эти системы симплексным методом.Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.Определим максимальное значение целевой функции F(X) = x1 + x2 + x3 + x4 + x5 при следующих условиях-ограничений.8×1 + x2 + 9×3 + 3×4 + 6×5≤15×1 + 4×2 + 3×3 + x4 + 2×5≤1Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).В 1-м неравенстве смысла (≤) вводим базисную переменную x6. В 2-м неравенстве смысла (≤) вводим базисную переменную x7. 8×1 + 1×2 + 9×3 + 3×4 + 6×5 + 1×6 + 0x7 = 15×1 + 4×2 + 3×3 + 1×4 + 2×5 + 0x6 + 1×7 = 1
Базис B x1 x2 x3 x4 x5 x6 x7
x6 1 8 1 9 3 6 1 0
x7 1 5 4 3 1 2 0 1
F(X0) 0 -1 -1 -1 -1 -1 0 0
Переходим к основному алгоритму симплекс-метода.Итерация №0.1. Проверка критерия оптимальности.Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.2. Определение новой базисной переменной.В качестве ведущего выберем столбец, соответствующий переменной x5, так как это наибольший коэффициент по модулю.3. Определение новой свободной переменной.Вычислим значения Di по строкам как частное от деления: bi / ai5и из них выберем наименьшее:min (1 : 6 , 1 : 2 ) = 1/6Следовательно, 1-ая строка является ведущей.Разрешающий элемент равен (6) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 min
x6 1 8 1 9 3 6 1 0 1/6
x7 1 5 4 3 1 2 0 1 1/2
F(X1) 0 -1 -1 -1 -1 -1 0 0 0
4. Пересчет симплекс-таблицы.Формируем следующую часть симплексной таблицы.Вместо переменной x6 в план 1 войдет переменная x5.Строка, соответствующая переменной x5 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=6На месте разрешающего элемента в плане 1 получаем 1.В остальных клетках столбца x5 плана 1 записываем нули.Таким образом, в новом плане 1 заполнены строка x5 и столбец x5.Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.НЭ = СЭ – (А*В)/РЭСТЭ – элемент старого плана, РЭ – разрешающий элемент (6), А и В – элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7
x5 1/6 4/3 1/6 3/2 1/2 1 1/6 0
x7 2/3 7/3 11/3 0 0 0 -1/3 1
F(X1) 1/6 1/3 -5/6 1/2 -1/2 0 1/6 0
Итерация №1.1. Проверка критерия оптимальности.Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.2. Определение новой базисной переменной.В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.3. Определение новой свободной переменной.Вычислим значения Di по строкам как частное от деления: bi / ai2и из них выберем наименьшее:min (1/6 : 1/6 , 2/3 : 32/3 ) = 2/11Следовательно, 2-ая строка является ведущей.Разрешающий элемент равен (32/3) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 min
x5 1/6 11/3 1/6 11/2 1/2 1 1/6 0 1
x7 2/3 21/3 32/3 0 0 0 -1/3 1 2/11
F(X2) 1/6 1/3 -5/6 1/2 -1/2 0 1/6 0 0
4. Пересчет симплекс-таблицы.Формируем следующую часть симплексной таблицы.Вместо переменной x7 в план 2 войдет переменная x2.Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x7 плана 1 на разрешающий элемент РЭ=32/3На месте разрешающего элемента в плане 2 получаем 1.В остальных клетках столбца x2 плана 2 записываем нули.Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7
x5 3/22 27/22 0 3/2 1/2 1 2/11 -1/22
x2 2/11 7/11 1 0 0 0 -1/11 3/11
F(X2) 7/22 19/22 0 1/2 -1/2 0 1/11 5/22
Итерация №2.1. Проверка критерия оптимальности.Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.2. Определение новой базисной переменной.В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю.3. Определение новой свободной переменной.Вычислим значения Di по строкам как частное от деления: bi / ai4и из них выберем наименьшее:min (3/22 : 1/2 , – ) = 3/11Следовательно, 1-ая строка является ведущей.Разрешающий элемент равен (1/2) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 min
x5 3/22 15/22 0 11/2 1/2 1 2/11 -1/22 3/11
x2 2/11 7/11 1 0 0 0 -1/11 3/11 –
F(X3) 7/22 19/22 0 1/2 -1/2 0 1/11 5/22 0
4. Пересчет симплекс-таблицы.Формируем следующую часть симплексной таблицы.Вместо переменной x5 в план 3 войдет переменная x4.Строка, соответствующая переменной x4 в плане 3, получена в результате деления всех элементов строки x5 плана 2 на разрешающий элемент РЭ=1/2На месте разрешающего элемента в плане 3 получаем 1.В остальных клетках столбца x4 плана 3 записываем нули.Таким образом, в новом плане 3 заполнены строка x4 и столбец x4.Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7
x4 3/11 27/11 0 3 1 2 4/11 -1/11
x2 2/11 7/11 1 0 0 0 -1/11 3/11
F(X3) 5/11 23/11 0 2 0 1 3/11 2/11
Проверка критерия оптимальности.Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.Оптимальный план можно записать так:x4 = 3/11×2 = 2/11F(X) = 1•3/11 + 1•2/11 = 5/11Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.Из теоремы двойственности следует, что Y = C*A-1.Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
A = (A4, A2) = 3 1
1 4
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
D = A-1 = 4/11 -1/11
-1/11 3/11
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.Тогда
Y = C*A-1 =(1, 1) x 4/11 -1/11
-1/11 3/11
= (3/11;2/11)
Оптимальный план двойственной задачи равен:y1 = 3/11y2 = 2/11Z(Y) = 1*3/11+1*2/11 = 5/11Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:qi = g*yi; pi = g*xi.Цена игры: g = 1 : 5/11 = 11/5p1 = 11/5 • 3/11 = 3/5p2 = 11/5 • 2/11 = 2/5Оптимальная смешанная стратегия игрока I: P = (3/5; 2/5)q1 = 11/5 • 0 = 0q2 = 11/5 • 2/11 = 2/5q3 = 11/5 • 0 = 0q4 = 11/5 • 3/11 = 3/5q5 = 11/5 • 0 = 0Оптимальная смешанная стратегия игрока II:Q = (0; 2/5; 0; 3/5; 0)Цена игры: v=11/5

Часть выполненной работы