Упростить платежную матрицу 1 используя принцип доминирования и дублирования стратегий

1) Игроки B1 B2 B3 a = min(Ai)
A1 5 1 21 1
A2 16 9 3 3
A3 9 12 14 9
A4 8 6 21 6
b = max(Bi) 16 12 21
a = max(ai) = 9, b = min(bj) = 12. Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 9 ≤ y ≤ 12. Находим решение игры в смешанных стратегиях. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
16 9 3
9 12 14
8 6 21
В платежной матрице отсутствуют доминирующие столбцы. Мы свели игру 4 x 3 к игре 3 x 3.
2) найти минимум функции F(x) при ограничениях (для игрока II): 16x1+9x2+8x3 ≥ 1 9x1+12x2+6x3 ≥ 1 3x1+14x2+21x3 ≥ 1 F(x) = x1+x2+x3 → min найти максимум функции Z(y) при ограничениях (для игрока I): 16y1+9y2+3y3 ≤ 1 9y1+12y2+14y3 ≤ 1 8y1+6y2+21y3 ≤ 1 Z(y) = y1+y2+y3 → max Решим двойственную задачу линейного программирования симплексным методом, с использованием симплексной таблицы. каноническая форма. 16y1+9y2+3y3+y4 = 1 9y1+12y2+14y3+y5 = 1 8y1+6y2+21y3+y6 = 1 Решим систему уравнений относительно базисных переменных: y4, y5, y6 Полагая, что свободные переменные равны 0, получим первый опорный план: Y0 = (0,0,0,1,1,1)
Базис B y1 y2 y3 y4 y5 y6
y4 1 16 9 3 1 0 0
y5 1 9 12 14 0 1 0
y6 1 8 6 21 0 0 1
Z(Y0) 0 -1 -1 -1 0 0 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной y3, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: min (1 : 3 , 1 : 14 , 1 : 21 ) = 1/21 Следовательно, 3-ая строка является ведущей. Разрешающий элемент равен (21) и находится на пересечении ведущего столбца и ведущей строки . Формируем следующую часть симплексной таблицы. Вместо переменной y6 в план 1 войдет переменная y3.
Базис B y1 y2 y3 y4 y5 y6
y4 6/7 104/7 57/7 0 1 0 -1/7
y5 1/3 11/3 8 0 0 1 -2/3
y3 1/21 8/21 2/7 1 0 0 1/21
Z(Y1) 1/21 -13/21 -5/7 0 0 0 1/21
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной y2, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (6/7 : 81/7 , 1/3 : 8 , 1/21 : 2/7 ) = 1/24 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (8) и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы. Вместо переменной y5 в план 2 войдет переменная y2. :
Базис B y1 y2 y3 y4 y5 y6
y4 29/56 89/8 0 0 1 -57/56 15/28
y2 1/24 11/24 1 0 0 1/8 -1/12
y3 1/28 1/4 0 1 0 -1/28 1/14
Z(Y2) 13/168 -7/24 0 0 0 5/56 -1/84
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной y1, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (29/56 : 111/8 , 1/24 : 11/24 , 1/28 : 1/4 ) = 29/623 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (111/8) и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы. Вместо переменной y4 в план 3 войдет переменная y1.
Базис B y1 y2 y3 y4 y5 y6
y1 29/623 1 0 0 8/89 -57/623 30/623
y2 38/1869 0 1 0 -11/267 104/623 -197/1869
y3 15/623 0 0 1 -2/89 -8/623 37/623
Z(Y3) 170/1869 0 0 0 7/267 39/623 4/1869
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Оптимальный план можно записать так: y1 = 29/623, y2 = 38/1869, y3 = 15/623 Z(Y) = 1*29/623 + 1*38/1869 + 1*15/623 = 170/1869 Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи