Теория игр

  • 20 нояб. 2016 г.
  • 1624 Слова
РЕФЕРАТ ПО ТЕОРИИ ИГР
Задание 1Проверить наличие седловых точек в данной матричной игре. Найти решение игры с заданной платежной матрицей А с помощью графического метода, упростив предварительно матрицу игры по принципу доминирования.
.
Решение
Проверим наличие седловых точек в матрице игры, для этого найдем нижнюю и верхнюю цену игры и сравним их значения. Итак,

соответственно

Таккак , игра седловой точки не имеет. Теперь упростим матрицу игры, используя принцип доминирования. Для определенности сначала сравним между собой элементы строк и доминируемые строки, если такие имеются, вычеркнем. Итак, все элементы третьей строки строго больше соответствующих элементов второй строки, значит, третья строка доминирует над второй, то есть третья строка является доминирующей, а вторая- доминируемой, поэтому вторую строку вычеркиваем. Аналогично третья строка доминирует над четвертой, значит, вычеркиваем и четвертую строку. Остальные строки не являются доминируемыми или доминирующими. В оставшейся матрице порядка 24 сравниваем между собой соответствующие элементы столбцов. Второй и третий столбцы доминируют над первым и четвертым, значит, второй и третий столбцы являетсядоминирующими, а первый и четвертый - доминируемыми, следовательно, вычеркиваем второй и третий столбцы. В результате получаем квадратную матрицу второго порядка, которую больше не упростить:

.
С помощью графического метода найдем решение полученной игры порядка 22. Построим графики для первого и второго игроков.

Рисунок 1 – Графики для определения стратегий игроков, цены игры
Сделаем проверкуаналитически, для этого нужно решить две системы уравнений; для первого игрока:

Для второго игрока:

Сравнивая найденные значения с графиками, убеждаемся в правильности найденного решения.
Таким образом, цена игры , а полученные оптимальные стратегии игроков соответственно равны: . Нулевые вероятности соответствуют вычеркнутым при упрощении строкам и столбцам.
Ответ: ,. .

Задание 2Найти ценуигры и оптимальные стратегии игроков для заданной матрицы игры Н, предварительно упростив ее по возможности; для решения применить симплекс-метод, составив соответствующую ЗЛП (задачу линейного программирования).

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

Так как седловой точки нет, решение будем искать в области смешанных стратегий. Составим пару двойственных задач линейного программирования,соответствующих данной матрице игры:

Решение найдем, используя симплекс – метод. Сначала нужно найти решение прямой задачи (вектор ), а затем по симплексной таблице записать решение двойственной задачи (вектор ).
В ограничениях перейдем от неравенств к равенствам, для этого введем базисные переменные y3, y4:

Заполним симплексную таблицу по исходным данным (таблица 1).
Таблица 1 – Итерация №0Базисные
переменные Свободные
члены Свободные переменные
-y1 -y2
y3 1 0 3
y4 1 1 0
Целевая функция 0 -1 -1
 
Так как среди элементов строки целевой функции (не считая свободного члена) имеются отрицательные, решение не является оптимальным. Итак, в качестве разрешающего столбца возьмем второй, тогда разрешающая строка – первая, так как имеем всего одно неотрицательное симплексное отношение, таким образом, разрешающий элемент – «3». Используя правила симплексных преобразований, заполним новую симплексную таблицу (таблица 2):
Таблица 2 – Итерация №1
Базисные
переменные Свободные
члены Свободные переменные
-y1 -y3
y2 1/3 0 1/3
y4 1 1 0
Целевая функция 1/3 -1 1/3
 
Так как среди элементов строки целевой функции (не считая свободного члена) имеются...
tracking img