Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Решение задачи

Содержательная постановка задачи

 

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

 

Формальная постановка задачи

 

Платёжная матрица:

Необходимо:

– решить игру, используя сведение к двойственным задачам ЛП;

– решить задачу в среде EXCEL.

 

Решение задачи

 

Решение: maxi (minj aij) = maxj (7, 11, 13) = 13

minj (maxi aij) = minj (19, 14, 19) = 14

Пусть (р1, р2, р3) – смешанная стратегия игрока А, (q1, q2, q3) – смешанная стратегия игрока В. Учтём, что р1 + р2 + р3 = 1 и q1 + q2 + q3 = 1.

Для игрока А:

12,5р1 + 19р2 + 15р3 ≥ v

11р1 + 14р2 + 13р3 ≥ v

1 + 11р2 + 19р3 ≥ v

F = v → max

Преобразуем ограничения, разделив все члены неравенств на v (обозначим
y1 = р1/v, y2 = р2/v, y3 = р3/v; заметим, что v = 1/(y1 + y2+ y3)).


12,5y1 + 19y2 + 15y3 ≥ 1

11y1 + 14y2 + 13y3 ≥ 1

7y1 + 11y2 + 19y3 ≥ 1

F = y1+ y2+ y3→ min

Для игрока Б:

12,5q1 + 11q2 + 7q3 ≤ v

19q1 + 14q2 + 11q3 ≤ v

15q1 + 13q2 + 19q3 ≤ v

F = v → min

Преобразуем ограничения, разделив все члены неравенств на v (обозначим
х1 = q1/v, х2 = q2/v, x3= q3/v; заметим, что v = 1/(x1 + x2+x3)).

Итак, задача принимает вид:

12,5o9x1 + 11x2 + 7x3 ≤ 1

19x1 + 14x2 + 11x3 ≤ 1

15x1 + 13x2 + 19x3 ≤ 1

F = x1+x2+x3 → max

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

Для того, чтобы решить задачу в среде Excel, следует воспользоваться программой «Поиск решения».

Введём платёжную матрицу, установим необходимые ограничения в программе «Поиск решения». Результаты для игрока Б представлены на рисунке 1.

Рисунок 1 – Результаты решения для игрока Б

Результаты для игрока А представлены на рисунке 2.

Рисунок 2 – Результаты решения для игрока А

 

Для игрока Б:

х1 = 0, х2 = 0,065, х3 = 0,0081

v = 1/(x1 + x2 + x3) = 13,67

q1 = 0, q2 = 0,89, q3 = 0,11

 

Для игрока А:

y1 = 0, y2 = 0,0488, y3 = 0,0244

v = 1/(y1 + y2 + y3) = 13,67

p1 = 0, p2 = 0,67, p3 = 0,33