Решение матричной игры симплексным методом

Найти решение матричной игры. Решить матричные игры симплексным методом.
Задание. Свести задачу, заданную платежной матрицей, к задаче линейного программирования (предварительно упростив задачу, убрав строго доминируемые стратегии, если это возможно) и решить симплекс методом.

Решение проводим с помощью калькулятора.

С позиции проигрышей игрока В стратегия B3 доминирует над стратегией B2, следовательно исключаем 3-ой столбец матрицы.

Игроки B1 B2 B3 a = min(Ai)
A1 0 3 1 0
A2 3 0 5 0
A3 2 1 1 1
b = max(Bi ) 3 3 5 0

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 1, которая указывает на максимальную чистую стратегию A3.
Верхняя цена игры b = min(bj) = 3.
Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 1 <= y <= 3. Находим решение игры в смешанных стратегиях..

Приведем матричную игру к задаче линейного программирования. Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях:
3x2+2x3 >= 1
3x1+x3 >= 1
x1+5x2+x3 >= 1
F(x) = x1+x2+x3 = min
найти максимум функции Ф(y) при ограничениях:
3y2+y3 <= 1
3y1+5y3 <= 1
2y1+y2+y3 <= 1
Ф(y) = y1+y2+y3 = max

Решаем эти системы двойственным симплекс-методом.
Определим минимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений.
3x2 + 2x3≥1
3x1 + x3≥1
x1 + 5x2 + x3≥1

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
0x1 + 3x2 + 2x3-1x4 + 0x5 + 0x6 = 1
3x1 + 0x2 + 1x3 + 0x4-1x5 + 0x6 = 1
1x1 + 5x2 + 1x3 + 0x4 + 0x5-1x6 = 1

Поскольку задача решается на минимум и элементы единичной матрицы отрицательны, сведем задачу к нахождению максимума. Для этого умножим все строки на (-1) и будем искать первоначальный опорный план.
0x1-3x2-2x3 + 1x4 + 0x5 + 0x6 = -1
-3x1 + 0x2-1x3 + 0x4 + 1x5 + 0x6 = -1
-1x1-5x2-1x3 + 0x4 + 0x5 + 1x6 = -1

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x4, x5, x6,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,-1,-1,-1)

План Базис B x1 x2 x3 x4 x5 x6
0 x4 -1 0 -3 -2 1 0 0
x5 -1 -3 0 -1 0 1 0
x6 -1 -1 -5 -1 0 0 1
Индексная строка F(X0) 0 1 1 1 0 0 0

В столбце свободных членов есть отрицательные элементы. Используем двойственный симплекс-метод. Выберем из них наибольший по модулю, а в его строке – любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитаем таблицу.
В качестве ведущего выберем столбец, соответствующий переменной x2.
1-ая строка является ведущей.
План Базис B x1 x2 x3 x4 x5 x6 min
x2 1 /3 0 1 2 /3 -1 /3 0 0 0
x5 -1 -3 0 -1 0 1 0 0
x6 2 /3 -1 0 21/3 -12/3 0 1 0
Индексная строка F(X) -1 /3 1 0 1 /3 1 /3 0 0 0

Представим расчет каждого элемента в виде таблицы:
x 1 x 2 x 3 x 4 x 5 x 6
1 /3 : 1 0 : 1 1 : 1 2 /3 : 1 -1 /3 : 1 0 : 1 0 : 1
-1-(1/3 • 0):1 -3-(0 • 0):1 0-(1 • 0):1 -1-(2/3 • 0):1 0-(-1/3 • 0):1 1-(0 • 0):1 0-(0 • 0):1
2 /3-(1/3 • 0):1 -1-(0 • 0):1 0-(1 • 0):1 21/3-(2/3 • 0):1 -12/3-(-1/3 • 0):1 0-(0 • 0):1 1-(0 • 0):1
-1 /3-(1/3 • 0):1 1-(0 • 0):1 0-(1 • 0):1 1 /3-(2/3 • 0):1 1 /3-(-1/3 • 0):1 0-(0 • 0):1 0-(0 • 0):1

В столбце свободных членов есть отрицательные элементы. Используем двойственный симплекс-метод. Выберем из них наибольший по модулю, а в его строке – любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитаем таблицу.
В качестве ведущего выберем столбец, соответствующий переменной x1.
2-ая строка является ведущей.
План Базис B x1 x2 x3 x4 x5 x6 min
x2 1 /3 0 1 2 /3 -1 /3 0 0 0
x1 1 /3 1 0 1 /3 0 -1 /3 0 0
x6 1 0 0 22/3 -12/3 -1 /3 1 0
Индексная строка F(X) -2 /3 0 0 0 1 /3 1 /3 0 0

Представим расчет каждого элемента в виде таблицы:
B x 1 x 2 x 3 x 4 x 5 x 6
1 /3-(1/3 • 0):1 0-(1 • 0):1 1-(0 • 0):1 2 /3-(1/3 • 0):1 -1 /3-(0 • 0):1 0-(-1/3 • 0):1 0-(0 • 0):1
1 /3 : 1 1 : 1 0 : 1 1 /3 : 1 0 : 1 -1 /3 : 1 0 : 1
1-(1/3 • 0):1 0-(1 • 0):1 0-(0 • 0):1 22/3-(1/3 • 0):1 -12/3-(0 • 0):1 -1 /3-(-1/3 • 0):1 1-(0 • 0):1
-2 /3-(1/3 • 0):1 0-(1 • 0):1 0-(0 • 0):1 0-(1/3 • 0):1 1 /3-(0 • 0):1 1 /3-(-1/3 • 0):1 0-(0 • 0):1

В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
План Базис B x1 x2 x3 x4 x5 x6
1 x2 1 /3 0 1 2 /3 -1 /3 0 0
x1 1 /3 1 0 1 /3 0 -1 /3 0
x6 1 0 0 22/3 -12/3 -1 /3 1
Индексная строка F(X1) -2 /3 0 0 0 1 /3 1 /3 0

Оптимальный план можно записать так:
x2 = 1/3
x1 = 1/3
x6 = 1
F(X) = 1•1/3 + 1•1/3 = 2/3

Составим двойственную задачу к прямой задаче.
3y2 + y3≤1
3y1 + 5y3≤1
2y1 + y2 + y3≤1
y1 + y2 + y3 => max
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу А-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 =

Оптимальный план двойственной задачи равен:
y1 = 1/3
y2 = 1/3
y3 = 0
Z(Y) = 1*1/3+1*1/3+1*0 = 2/3
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 2/3 = 11/2

p1 = 11/21/3 = 1/2
p2 = 11/21/3 = 1/2
p3 = 11/2 • 0 = 0
q1 = 11/21/3 = 1/2
q2 = 11/21/3 = 1/2
q3 = 11/2 • 0 = 0

Оптимальная стратегия игрока А:
P(1/2 ; 1/2; 0)

Оптимальная  стратегия  игрока B:
Q(1/2; 1/2; 0)

Перейти к онлайн решению своей задачи

загрузка...