Методические указания к решению задач. 1. Элементы теории матричных игр

Задания по выполнению Контрольной работы.

Студент изучает теоретические вопросы и решает задачи по следующим темам:

Элементы теории матричных игр.

Теория графов.

На титульном листе тетради необходимо написать наименование дисциплины, факультета, курс, фамилия, имя и отчество студента.

Перед решением каждой задачи следует полностью записать ее условие.

Решение задач должно быть представлено подробно и сопровождаться краткими пояснениями.

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

Контрольная работа, выполненная не в соответствии с таблицей 1 и оформленная на ПК, не рецензируется и не зачитывается.

В конце работы привести список используемой литературы и поставить подпись и дату написания работы.

Задание 1

Найти хотя бы одно целое значение λ, при которой матричная игра с платежной матрицей А_i ={а_ik} размерности 3х4 имеет решение в чистых стратегиях. Найти это решение (если решение существует), платежные матрицы и данные к ней указаны в табл.2.

Таблица 2

Первая буква имени	а	в	с
А, Б, В
Г, Д, Е
Ж, З, И
К, Л, М
Н, О, П
Р, С, Т
У, Ф, Х
Ц, Ч, Ш
Э, Ю, Я

Платежные матрицы выбирать по первой букве фамилии:

Задачи 1-25

В ходе деловой игры возникла конфликтная ситуация двух юридических лиц. У одного из них имеется 4 стратегии, у другого 5. Платежная матрица этой игры задана в виде . Определить оптимальные стратегии и цену игры.

Указания. Платежные матрицы свести к разностям: 2x5 или 5x2, исключая дублирующие и доминирующие столбцы или строки соответственно. Затем задачу решить в смешанных стратегиях.

Задачи № 51-75

Для заданного графа G = (X, U) указать вершины и дуги, поставить значения пропускных способностей дуг из табл. 8, записать в аналитической форме, составить матрицы смежности, инциденций, пропускных способностей дуг и достижимостей. Определить экстремальные пути и маршруты из х₁ в х₆. Найти максимальный поток и указать минимальный разрез для сети. Данные к задачам табл. №8.

Таблица 8

№№ задач	Значения пропускных способностей дуг
U₁	U₂	U₃	U₄	U₅	U₆	U₇	U₈	U₉	U₁₀
51,64
52,65
53,66
54,67
55,68
56,69
57,70
58,71
59,72
60,73
61,74
62,75

Схемы задач

х₁

Методические указания к решению задач. 1. Элементы теории матричных игр.

Математическая модель конфликтной ситуации называется игрой. Игра ведется по четко сформулированным правилам. Ходом в игре называют выбор и осуществление игроком одного из предусмотренных правилами игры действий. В игре двух партнеров ходы строго чередуются. Результат одного хода и ответ на него является не итогом игры, а лишь изменением ситуации.

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

Игра называется конечной, если в распоряжении каждого игрока имеется конечное число стратегий, в противном случае она будет бесконечной.

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

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

Х = (x₁, х₂,...,х_n)

где n - число чистых стратегий игрока, x_i - вероятность применения стратегии A_i, входящей в состав его смешанной стратегии в игре.

Игра с нулевой суммой - это игра, в которой сумма выигрышей всех участников игры равна нулю, т.е. один игрок выигрывает за счет других игроков.

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

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

А = {a_ik}

Теорема фон Неймана (основная теорема теории матричных игр). Любая конечная антагонистическая игра с нулевой суммой (матричная игра) имеет по крайней мере одно решение в смешанных стратегиях, две оптимальные стратегии игроков и соответствующую им цену игры (х*, у*,v*).

Методы решения матричных игр:

Игра, имеющая седловую точку в платежной матрице. Игрок А имеет максиминную чистую стратегию, игрок В имеет чистую минимаксную стратегию, при этом v=α=β.

Матричная игра, в которой нижняя цена игры равна верхней, т.е. α=β =v, называется игрой с седловой точкой, а v называется чистой ценой игры. Стратегии игроков А_i и В_к, принимающие эти значения, называются чистыми или оптимальными. Элемент а_ik платежной матрицы являются минимальными в i –той строке и максимальным в к- том столбце.

Игра с платежной матрицей порядка 2x2, не имеющая седловой точки. В этом случае не существует оптимального решения в чистых стратегиях, поэтому решение отыскивается в смешанных стратегиях.
Игра с платежной матрицей n x m (m>2, n>2). В таких задачах матричная игра сводится к решению задач линейного программирования.

Пусть задана платежная матрица порядка 2x2

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

(1.1)

Решение игры с матрицей (2x2) можно найти графически. На оси абсцисс откладывается отрезок, длина которого равна единице. Левый конец отрезка (точка х = 0) соответствует стратегии А₁ правый (х = 1) стратегии А₂ (рис 1.1). Промежуточные точки х соответствует некоторым смешанным стратегиям (х₁, х₂), где х₁ = 1- х, х₂ = х. На концах выбранного отрезка проводятся прямые, перпендикулярные оси абсцисс, на которых откладывается выигрыш при соответствующих чистых стратегиях. Если игрок В применяет стратегию В₁, то выигрыш при использовании чистых стратегий А₁ и А₂ составляет соответственно а₁₁ и а₂₁. Откладываются эти точки на прямых и соединяются полученные точки прямой В₁ В₁. Аналогично можно построить прямую В₂ В₂. соответствующую стратегии В₂ игрока В. Ломанная B₁ К В₂. - нижняя граница выигрыша, получаемого игроком А. Точка К. в которой он максимален, определяет цену игры и ее решения. Для определения оптимальной стратегии игрока В применяются формулы (1.2).

Рис. 1.1

(1.2)

Отрезок KM = V - цена игры.

Пример 1.1. Определить при каких значениях λ матричная игра с платежной матрицей А={а_ik} размерности 3х4 имеет решение в чистых стратегиях. Найти это решение для одного из определенных λ.

а=14, в=12, с=10

Решение.

Составим платежную матрицу (подставим а,в,с в матрицу А)

Из трех элементов матрицы А, содержащих и удостоверяющих условиям седловой точки, является λ-1, т.е. λ-1≤14 (меньше минимального в строке) и λ-1≥10 (больше максимального в столбце), тогда 11≤λ≤15.

Составим платежную матрицу для λ=12

Оптимальные стратегии игроков А₁ и В₂, цена игры V имеют вид:

А₁=(15, 11, 12, 14)

= (11, 9, 10)

V= 11

Ответ: А₁=(15, 11, 12, 14) = (11, 9, 10) V= 11

Пример 1.2. В ходе деловой игры возникла конфликтная ситуация двух юридических лиц. У одного из них имеется 4 стратегии, у другого - 5. платежная матрица А имеет вид:

Определить оптимальные стратегии игроков и цену игры.

Решение

Проверяем: есть ли седловая точка, определяя нижнюю и верхнюю цены игры, т.е. и . Седловая точка отсутствует, т.к. . Следовательно, задачу решаем в смешанных стратегиях.
Сокращаем размер матрицы, исключая доминируемую и дублирующую стратегии для первого игрока, т.е. вычеркиваем 3-ю и 4-ю строки матрицы А..

Расчетная матрица имеет вид:

B₁ B₂ B₃ B₄ B₅

3. Находим нижнюю границу игры в координатных осях XOY. (Рис. 1.2) На оси абсцисс строим отрезок единичной длины, точки которого соответствуют различным вероятностям смешанных стратегий игрока 1.

На оси OУ и прямой x₁= 1 откладываем выигрыши, соответствующие стратегиям игрока В. Ломанная В₁КNB₅ определяет нижнюю границу игры.

Построенные отрезки показывают смешанные стратегии игрока 1, соответствующие стратегиям В₁ В₂, В₃, В₄ и В₅ игрока 2. Точка К пересечения отрезков B₁ B₁ и В₃ В₃ соответствует оптимальной стратегии игрока 1. Выделяем матрицу 2x2 и по формулам (1.1) находим решение игры

Рис. 1.2

Отрезок KM соответствует цене игры. Точка К дает решение игры:

V =КМ= 14/3; х₁= МО₁ = 2/3; x₂= ОМ = 1/3

Составим матрицу 2х2, которая определяет оптимальные стратегии игроков:

На основании формул (1.1) получаем значения вероятностей и цену игры:

Проверка

Ответ:

Пример 1.3

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

Решение

1. Находим седловую точку, определяя максиминную стратегию одного игрока ( = 4) и минимаксную ( = 6) - другого. Седловой точки нет, т.к. .

2. Задачу решаем в смешанных стратегиях, уменьшая размер матрицы (5x2), исключая доминирующую и дублирующую стратегии второго игрока (3-й и 4-й столбцы матрицы А), т.е. платежная матрица имеет вид:

Решение задачи находим для игрока В.

Аналогично Задаче 1.1 может быть решена игра с матрицей 5х2, только в этом случае строим верхнюю границу выигрыша и на ней определяем минимум (точка К рис. 1.3).

Находим верхнюю границу игры графическим способом в координатных осях YOX (Рис. 1.3). Эту границу определяет ломанная A₅KNA₁

Рис. 1.3

Определим оптимальные стратегии А_i первого игрока, т.к. такие стратегии для второго игрока найдены исключением дублирующих и доминирующих стратегий. Для этого отыскиваем верхнюю границу игры из условия максиминного критерия оценок.

4. Определяем вероятности оптимальных стратегий на основании матрицы а, являющейся матрицей оптимальных стратегий, по формулам (1.1)