Методические указания к решению задач. 1. Элементы теории матричных игр
Задания по выполнению Контрольной работы.
Студент изучает теоретические вопросы и решает задачи по следующим темам:
Элементы теории матричных игр.
Теория графов.
На титульном листе тетради необходимо написать наименование дисциплины, факультета, курс, фамилия, имя и отчество студента.
Перед решением каждой задачи следует полностью записать ее условие.
Решение задач должно быть представлено подробно и сопровождаться краткими пояснениями.
После получения отрецензированной работы студент обязан сделать работу над ошибками.
Контрольная работа, выполненная не в соответствии с таблицей 1 и оформленная на ПК, не рецензируется и не зачитывается.
В конце работы привести список используемой литературы и поставить подпись и дату написания работы.
Задание 1
Найти хотя бы одно целое значение , при которой матричная игра с платежной матрицей Аi ={аik} размерности 3х4 имеет решение в чистых стратегиях. Найти это решение (если решение существует), платежные матрицы и данные к ней указаны в табл.2.
Таблица 2
Первая буква имени | а | в | с |
А, Б, В | |||
Г, Д, Е | |||
Ж, З, И | |||
К, Л, М | |||
Н, О, П | |||
Р, С, Т | |||
У, Ф, Х | |||
Ц, Ч, Ш | |||
Э, Ю, Я |
Платежные матрицы выбирать по первой букве фамилии:
Задачи 1-25
В ходе деловой игры возникла конфликтная ситуация двух юридических лиц. У одного из них имеется 4 стратегии, у другого 5. Платежная матрица этой игры задана в виде . Определить оптимальные стратегии и цену игры.
Указания. Платежные матрицы свести к разностям: 2x5 или 5x2, исключая дублирующие и доминирующие столбцы или строки соответственно. Затем задачу решить в смешанных стратегиях.
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
![]() |
Задачи № 51-75
Для заданного графаG = (X, U)указать вершины и дуги, поставить значения пропускных способностей дуг из табл. 8, записать в аналитической форме, составить матрицы смежности, инциденций, пропускных способностей дуг и достижимостей. Определить экстремальные пути и маршруты из х1 в х6.Найти максимальный поток и указать минимальный разрез для сети. Данные к задачам табл. №8.
Таблица 8
№№ задач | Значения пропускных способностей дуг | |||||||||
U1 | U2 | U3 | U4 | U5 | U6 | U7 | U8 | U9 | U10 | |
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. Элементы теории матричных игр.
Математическая модель конфликтной ситуации называется игрой. Игра ведется по четко сформулированным правилам. Ходом в игре называют выбор и осуществление игроком одного из предусмотренных правилами игры действий. В игре двух партнеров ходы строго чередуются. Результат одного хода и ответ на него является не итогом игры, а лишь изменением ситуации.
Стратегией игрока называется последовательность всех ходов до окончания игры. Выбор наилучшей стратегии игроком должен быть активным, с определенной перспективой, поэтому игрок должен найти для себя линию поведения, определяющую выбор варианта действий при каждом личном ходе в зависимости от сложившийся ситуации.
Игра называется конечной, если в распоряжении каждого игрока имеется конечное число стратегий, в противном случае она будет бесконечной.
Оптимальной называется стратегия, которая обеспечивает игроку максимально возможный выигрыш. В задачу теории игр входит выявление оптимальных стратегий игроков.
Смешанной называется стратегия, в которой чистые стратегии игрока чередуются случайным образом с некоторой вероятностью.
Х = ( x1 , х2, ... ,хn)
где n- число чистых стратегий игрока, xi- вероятность применения стратегии Ai , входящей в состав его смешанной стратегии в игре.
Игра с нулевой суммой - это игра, в которой сумма выигрышей всех участников игры равна нулю, т.е. один игрок выигрывает за счет других игроков.
Антагонистической игрой называется парная игра с нулевой суммой.
Матричная игра - это конечная антагонистическая игра. В парной игре при выборе любой стратегии каждым из двух игроков можно задать выигрыш первого игрока (проигрыш второго игрока) с помощью платежной матрицы.
А = {aik}
Теорема фон Неймана (основная теорема теории матричных игр). Любая конечная антагонистическая игра с нулевой суммой (матричная игра) имеет по крайней мере одно решение в смешанных стратегиях, две оптимальные стратегии игроков и соответствующую им цену игры (х*, у*,v*).
Методы решения матричных игр:
- Игра, имеющая седловую точку в платежной матрице. Игрок А имеет максиминную чистую стратегию, игрок В имеет чистую минимаксную стратегию, при этом v==.
Матричная игра, в которой нижняя цена игры равна верхней, т.е. ==v, называется игрой с седловой точкой, а v называется чистой ценой игры. Стратегии игроков Аi и Вк, принимающие эти значения, называются чистыми или оптимальными. Элемент аik платежной матрицы являются минимальными в i –той строке и максимальным в к- том столбце.
- Игра с платежной матрицей порядка 2x2, не имеющая седловой точки. В этом случае не существует оптимального решения в чистых стратегиях, поэтому решение отыскивается в смешанных стратегиях.
- Игра с платежной матрицей n x m (m>2, n>2). В таких задачах матричная игра сводится к решению задач линейного программирования.
Пусть задана платежная матрица порядка 2x2
На первом этапе решения задачи отыскивается седловая точка в координатных осях. Если она есть, то оптимальное решение задачи найдено. Если нет решения матричной игры в чистых стратегиях, то оптимальное решение находят в смешанных стратегиях, вычисляя соответствующие вероятности, по следующим формулам:
|
![](images/image-099-2903.gif)
![](images/image-101-2874.gif)
Решение игры с матрицей (2x2) можно найти графически. На оси абсцисс откладывается отрезок, длина которого равна единице. Левый конец отрезка (точка х = 0) соответствует стратегии А1 правый (х = 1) стратегии А2 (рис 1.1). Промежуточные точки х соответствует некоторым смешанным стратегиям (х1, х2), где х1 = 1- х, х2 = х. На концах выбранного отрезка проводятся прямые, перпендикулярные оси абсцисс, на которых откладывается выигрыш при соответствующих чистых стратегиях. Если игрок В применяет стратегию В1, то выигрыш при использовании чистых стратегий А1 и А2 составляет соответственно а11 и а21. Откладываются эти точки на прямых и соединяются полученные точки прямой В1 В1. Аналогично можно построить прямую В2 В2. соответствующую стратегии В2 игрока В. Ломанная B1 К В2. - нижняя граница выигрыша, получаемого игроком А. Точка К. в которой он максимален, определяет цену игры и ее решения. Для определения оптимальной стратегии игрока В применяются формулы (1.2).
Рис. 1.1
(1.2)
Отрезок KM = V - цена игры.
Пример 1.1. Определить при каких значениях матричная игра с платежной матрицей А={аik} размерности 3х4 имеет решение в чистых стратегиях. Найти это решение для одного из определенных .
а=14, в=12, с=10
Решение.
Составим платежную матрицу (подставим а,в,с в матрицу А)
.
Из трех элементов матрицы А, содержащих и удостоверяющих условиям седловой точки, является -1, т.е. -114 (меньше минимального в строке) и -110 (больше максимального в столбце), тогда 1115.
Составим платежную матрицу для =12
Оптимальные стратегии игроков А1 и В2, цена игры V имеют вид:
А1=(15, 11, 12, 14)
= (11, 9, 10)
V= 11
Ответ: А1=(15, 11, 12, 14) = (11, 9, 10) V= 11
Пример 1.2. В ходе деловой игры возникла конфликтная ситуация двух юридических лиц. У одного из них имеется 4 стратегии, у другого - 5. платежная матрица А имеет вид:
Определить оптимальные стратегии игроков и цену игры.
Решение
- Проверяем: есть ли седловая точка, определяя нижнюю и верхнюю цены игры, т.е.
и
. Седловая точка отсутствует, т.к.
. Следовательно, задачу решаем в смешанных стратегиях.
- Сокращаем размер матрицы, исключая доминируемую и дублирующую стратегии для первого игрока, т.е. вычеркиваем 3-ю и 4-ю строки матрицы А..
Расчетная матрица имеет вид:
B1 B2 B3 B4 B5
![]() |
3. Находим нижнюю границу игры в координатных осях XOY. (Рис. 1.2) На оси абсцисс строим отрезок единичной длины, точки которого соответствуют различным вероятностям смешанных стратегий игрока 1.
На оси OУ и прямой x1 = 1 откладываем выигрыши, соответствующие стратегиям игрока В. Ломанная В1КNB5 определяет нижнюю границу игры.
Построенные отрезки показывают смешанные стратегии игрока 1, соответствующие стратегиям В1 В2, В3, В4 и В5 игрока 2. Точка К пересечения отрезков B1 B1 и В3 В3 соответствует оптимальной стратегии игрока 1. Выделяем матрицу 2x2 и по формулам (1.1) находим решение игры
![]() |
Рис. 1.2
Отрезок KM соответствует цене игры. Точка К дает решение игры:
V =КМ= 14/3; х1= МО1 = 2/3; x2= ОМ = 1/3
Составим матрицу 2х2, которая определяет оптимальные стратегии игроков:
На основании формул (1.1) получаем значения вероятностей и цену игры:
Проверка
Ответ :
Пример 1.3
Найти решение игры, заданной платежной матрицей А.
Решение
1. Находим седловую точку, определяя максиминную стратегию одного игрока ( = 4) и минимаксную (
= 6) - другого. Седловой точки нет, т.к.
.
2. Задачу решаем в смешанных стратегиях, уменьшая размер матрицы (5x2), исключая доминирующую и дублирующую стратегии второго игрока (3-й и 4-й столбцы матрицы А), т.е. платежная матрица имеет вид:
Решение задачи находим для игрока В.
Аналогично Задаче 1.1 может быть решена игра с матрицей 5х2, только в этом случае строим верхнюю границу выигрыша и на ней определяем минимум (точка К рис. 1.3).
Находим верхнюю границу игры графическим способом в координатных осях YOX (Рис. 1.3). Эту границу определяет ломанная A5KNA1
![]() |
Рис. 1.3
Определим оптимальные стратегии Аi первого игрока, т.к. такие стратегии для второго игрока найдены исключением дублирующих и доминирующих стратегий. Для этого отыскиваем верхнюю границу игры из условия максиминного критерия оценок.
4. Определяем вероятности оптимальных стратегий на основании матрицы а, являющейся матрицей оптимальных стратегий, по формулам (1.1)
х2 = =
х5 =
=
y1 = = 0,7 y2 =
= 0,3
V = =
= 4,2
О
твет: ,
,
,
,
V*=4,2
Контрольные вопросы.
- Какие игры называются стратегическими?
- Сформулируйте основную теорему теории матричных игр.
- Назовите основные методы решения задач теории матричных игр.
- Каким образом уменьшаются размеры платежной матрицы?
- Геометрические способы решения игр с матрицами размера (m х 2) и (2 х n) .
- Какие стратегии называются чистыми?
- Что определяет игру в смешанных стратегиях?