Решение игры в смешанных стратегиях 2 (стр. 4 из 5)

Доминирующие столбцы и строки можно удалить из матрицы.

Алгоритм решения

1. Проверить наличие седловой точки. Если есть седловая точка, то пишем ответ, если нет - продолжаем решение дальше

2. Удаляем доминирующие строки доминирующие столбцы. Их може6т быть несколько. На их место в оптимальной стратегии соответствующие компоненты будут равны 0

3. Решаем матричную игру (линейное программирование, графическое решение, приближенное решение)

В своей задаче я решаю матричную игру линейным программированием. (Симплекс метод)

Алгоритм решения симплекс методом (на максимум):

1. Привести задачу линейного программирования к каноническому виду.

2. Найти начальное опорное решение с базисом из единичных векторов и коэффициенты разложений векторов условий по базису опорного решения. Если опорное решение отсутствует, задача не имеет решения ввиду несовместности системы ограничений.

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

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается.

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора найти все оптимальные решения.

6. Если имеют место условия неограниченности целевой функции, то задача не имеет решения.

7. Если пункты 4—6 алгоритма не выполняются, найти новое опорное решение и перейти к пункту 3.

2 СПЕЦИАЛЬНАЯ ЧАСТЬ (РАСЧЕТНАЯ)

2.1 Исходные данные

Тема: Решение игры в смешанных стратегиях

2 -1 2 1

А = 1 3 -1 0

4 -2 2 -1

Найти оптимальную стратегию и цену игры, заданной платежной матрицей А.

2.2 Постановка задачи. Математическая модель

Математическая модель — это упрощенное описание реальности с помощью математических понятий. Математическая модель выражает существенные черты объекта или процесса языком уравнений и других математических средств.

Седловой точкой называется А_ij, которая является наименьшим элементом в своей строке и наибольшим элементом в столбце.

Доминирующая строка – все элементы этой строки не превосходят соответствующих элементов другой строки.

Доминирующий столбец – все элементы не меньше соответствующих элементов какого-либо другого столбца.

Доминирующие столбцы и строки можно удалить из матрицы.

Любой задаче линейного программирования называемой исходнойили прямой,можно поставить в соответствие другую задачу,которая называется двойственной или сопряженной. Обе эти задачи образуют пару двойственных (или сопряженных) задач. Каждая из задач является двойственной к другой задаче рассматриваемой пары.

Моя задача представляет собой матрицу. Что бы ее решить сначала построим математическую модель и решим симплексным методом.

В моей матрице есть доминирующий столбец. Это последний столбец матрицы так как сказано из определения все элементы не меньше соответствующих элементов какого-либо другого столбца. Это столбец доминирует над последним столбцом.

2 -1 2 1

А = 1 3 -1 0

4 -2 2 -1

Поэтому мы его вычеркиваем и составляем симметричные задачи по новой получившейся матрице А

-1 2 0

А^* = 3 -1 0

-2 2 -1

Использовать метод линейного программирования следует тогда, когда все элементы, хотя бы одной строки матрицы строго положительны. В этом случае задача будет иметь оптимальный план из которых можно получить оптимальные стратегии, иначе в исходной задаче целевая функция может быть неограниченна, что противоречит теории Джона фон Неймана.

С = 2

Прибавляем это число к элементам матрицы А^* и получаем матрицу А^**

1 4 3

А^** = 5 1 2

0 4 1

Коэффициенты при неизвестных в целевой функции и свободные члены неравенств должны быть равны 1

Составляем систему уравнений по данной матрице и целевую функцию (математическая модель).

F(x) = x₁ + x₂ + x₃ → max

2.3 Анализ модели. Составление пары симметричных двойственных задач

В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи)

Правила составления двойственных задач:

1.Во всех ограничениях исходной задачи свободные члены должны находиться в правой части, а члены с неизвестными — в левой.

2. Ограничения-неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону.

3. Если знаки неравенств в ограничениях исходной задачи «≤», то целевая функция Z(X) = с₀ + с₁ · x₁ + с₂ · x₂ + … + с_n · x_nдолжна максимизироваться, а если «≥», то минимизироваться.

4. Каждому ограничению исходной задачи соответствует неизвестное в двойственной задаче; при этом неизвестное, отвечающее ограничению-неравенству, должно удовлетворять условию неотрицательности, а неизвестное, отвечающее ограничению-равенству, может быть любого знака.

5. Целевая функция двойственной задачи имеет вид

где с₀— свободный член целевой функции Z(X) исходной задачи, b₁, b₂, …, b_m,— свободные члены в ограничениях исходной задачи, при этом b_i— свободный член именно того ограничения исходной задачи, которому соответствует неизвестная y_i, ay₁, y₂, …, y_m— неизвестные в двойственной задаче.

6. Целевая функция F(Y) двойственной задачи должна оптимизироваться противоположным по сравнению с Z(X) образом, т.е. если Z(X) → max, то
F(Y)→ min, и если Z(X)→ min, то F(Y) → max.

7. Каждому неизвестному х_j, j= 1, 2, ..., п исходной задачи соответствует ограничение в двойственной задаче. Совокупность этих п ограничений (вместе с условиями неотрицательности неизвестных y_i, соответствующих ограничениям-неравенствам исходной задачи) образует систему ограничений двойственной задачи. Все ограничения двойственной задачи имеют вид неравенств, свободные члены которых находятся в правых частях, а члены с неизвестными y_i у₂, ..., у_т— в левых. Все знаки неравенств имеют вид «≥», если F(Y) → min, и «≤», если
F(Y) → max.

Коэффициенты, с которыми неизвестные y_l у₂, …, у_твходят в ограничение, соответствующее неизвестному x_j, совпадают с коэффициентами при этом неизвестном х. в ограничениях исходной задачи, а именно: коэффициент при y_iсовпадает с тем коэффициентом при х_jс которым х_jвходит в ограничение исходной задачи, соответствующее неизвестному y_i.

Двойственность

1) Составляем матрицу из полученной математической модели

7 6 2 1

А = 1 3 6 1

0 2 5 1

1 1 1 F

2) Транспонируем матрицу A

7 1 0 1

А^-1 = 6 3 2 1

2 6 5 1

1 1 1 Z

3) Составляем двойственную задачу

Z = y₁ + y₂ +y₃ → Min

Вот и получили пару симметричных двойственных задач. Задача на максимум и на минимум

F(x) = x₁ + x₂ + x₃ → max Z(x) = y₁ + y₂ +y₃ → min

2.4 Решение симплекс методом

x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0

x0	x1	x2	x3	x4	x5	x6
x4	1	1	4	3	1	0	0	1/4
x5	1	5	1	2	0	1	0	1/5
x6	1	0	4	1	0	0	1
f	0	-1	-1	-1	0	0	0

X0

X1

X2

X3

X4