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

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

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

Игроки 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)

ПланБазисBx1x2x3x4x5x6
0x4-10-3-2100
x5-1-30-1010
x6-1-1-5-1001
Индексная строкаF(X0)0111000
В столбце свободных членов есть отрицательные элементы. Используем двойственный симплекс-метод. Выберем из них наибольший по модулю, а в его строке – любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитаем таблицу.
В качестве ведущего выберем столбец, соответствующий переменной x2.
1-ая строка является ведущей.
ПланБазисBx1x2x3x4x5x6min
x21 /3012 /3-1 /3000
x5-1-30-10100
x6 2 /3 -1021/3-12/3010
Индексная строкаF(X)-1 /3101 /31 /3 000
Представим расчет каждого элемента в виде таблицы:
x 1x 2x 3x 4x 5 x 6
1 /3 : 10 : 11 : 12 /3 : 1-1 /3 : 10 : 1 0 : 1
-1-(1/3 • 0):1-3-(0 • 0):10-(1 • 0):1 -1-(2/3 • 0):10-(-1/3 • 0):1 1-(0 • 0):10-(0 • 0):1
2 /3-(1/3 • 0):1 -1-(0 • 0):10-(1 • 0):1 21/3-(2/3 • 0):1 -12/3-(-1/3 • 0):1 0-(0 • 0):11-(0 • 0):1
-1 /3-(1/3 • 0):1 1-(0 • 0):10-(1 • 0):1 1 /3-(2/3 • 0):11 /3-(-1/3 • 0):1 0-(0 • 0):10-(0 • 0):1
В столбце свободных членов есть отрицательные элементы. Используем двойственный симплекс-метод. Выберем из них наибольший по модулю, а в его строке – любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитаем таблицу.
В качестве ведущего выберем столбец, соответствующий переменной x1.
2-ая строка является ведущей.
ПланБазисBx1x2x3x4x5x6min
x21 /3012 /3 -1 /3 000
x11 /3 101 /30 -1 /3 0 0
x6 10022/3-12/3-1 /3 10
Индексная строкаF(X) -2 /30001 /3 1 /300
Представим расчет каждого элемента в виде таблицы:
Bx 1x 2x 3x 4x 5x 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
В базисном столбце все элементы положительные. Переходим к основному алгоритму симплекс-метода.
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
ПланБазисBx1x2x3x4x5x6
1x2 1 /3012 /3-1 /300
x1 1 /3 10 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 /31 /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)

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

Задать вопрос или оставить комментарий Помощь в решении Поиск Поддержать проект