МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ
Практическая работа №10
«Теория игр»
по дисциплине
«Теория принятия решений»
|
Студент |
|
|
|
Филатов А.А. |
|
||||||||
|
|
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
|
Группа |
|
АС-09 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
||||||||
|
Принял |
|
|
|
|
|
||||||||
|
|
|
|
|
Корнеев А.М. |
|
||||||||
|
ученая степень, звание |
|
подпись, дата |
|
фамилия, инициалы |
|
Липецк 2012
1. Задание
Определить основные понятия теории игр, свойства смешанных стратегий. Изучить метод решение матричных игр в смешанных стратегиях путем сведения к паре двойственных задач линейного программирования.
Порядок выполнения работы:
-
Исходные данные взять из приложения 3. Четные числа оставить положительными, а нечетные – сделать отрицательными.
2) При решении матричной игры нужно выделить следующие этапы:
1. Проверить, имеет ли игра решение в чистых стратегиях.
2. Упростить платежную матрицу.
3. Если среди элементов платежной матрицы есть отрицательные, то ко всем элементам матрицы необходимо прибавить такое число L>0, чтобы все элементы стали неотрицательными. При этом цена игры v увеличится на L, а оптимальные смешанные стратегии не изменятся.
4. Составить пару взаимно двойственных задач ЛП, эквивалентных данной матричной игре.
5. Определить оптимальные планы двойственных задач.
6. Найти решение игры.
2. Решение
Вариант 17 |
Игрок B |
|||||
Игрок A |
4 |
9 |
7 |
10 |
6 |
|
11 |
8 |
12 |
9 |
5 |
||
6 |
9 |
13 |
5 |
9 |
||
7 |
4 |
6 |
11 |
6 |
||
13 |
8 |
6 |
4 |
7 |
1) Задана платежная матрица, определим нижнюю и верхнюю цены игры:
|
||||||
4 |
-9 |
-7 |
10 |
6 |
-9 |
|
-11 |
8 |
12 |
-9 |
-5 |
-11 |
|
6 |
-9 |
-13 |
-5 |
-9 |
-13 |
|
-7 |
4 |
6 |
-11 |
6 |
-11 |
|
-13 |
8 |
6 |
4 |
-7 |
-13 |
|
6 |
8 |
12 |
10 |
6 |
Нижняя цена игры -9,
Верхняя цена игры 6.
Так как, , то седловой точки не существует, и игра не имеет оптимального решения в чистых стратегиях.
2) Упростим платежную матрицу:
|
|||||
4 |
-9 |
-7 |
10 |
6 |
|
-11 |
8 |
12 |
-9 |
-5 |
|
6 |
-9 |
-13 |
-5 |
-9 |
|
-7 |
4 |
6 |
-11 |
6 |
|
-13 |
8 |
6 |
4 |
-7 |
Так как исключаемых строк и столбцов не найдено.
3) Так как, среди элементов платежной матрицы есть отрицательные, то ко всем элементам матрицы прибавим такое число , чтобы все элементы стали неотрицательными. При этом цена игры увеличится на , а оптимальные смешанные стратегии не изменятся.
Платежная матрица будет иметь вид:
|
|||||
17 |
4 |
6 |
23 |
19 |
|
2 |
21 |
25 |
4 |
8 |
|
19 |
4 |
0 |
8 |
4 |
|
6 |
17 |
19 |
2 |
19 |
4) Составим пару взаимно двойственных задач ЛП, эквивалентных данной матричной игре.
Подпишем над столбцами матрицы переменные , , , , соответствующие смешанным стратегиям игрока , а рядом со строками матрицы − переменные , , , соответствующие смешанным стратегиям игрока :
|
|||||
17 |
4 |
6 |
23 |
19 |
|
2 |
21 |
25 |
4 |
8 |
|
19 |
4 |
0 |
8 |
4 |
|
6 |
17 |
19 |
2 |
19 |
Целевая функция прямой задачи исследуется на максимум и равна сумме переменных : . Ограничения выписываются по строкам и не превышают единицы.
Целевая функция двойственной задачи исследуется на минимум и равна сумме переменных : . Ограничения выписываются по столбцам и не превышают единицы:
Решим прямую задачу симплекс-методом. Приведем ее к каноническому виду.
Среди переменных задачи можно выделить базисные переменные: .