<<
>>

4.2.3 Решение задачи графическим методом

Симплекс-методом можно найти решение матричной игры произвольной размерности. Графическим же способом найти решение можно лишь для игры размерности 2 х n.

В ответе мы должны получить смешанные стратегии – два вектора PA = (p1, p2) и QB = (q1, q2, …, qn).

Причем, p2 = 1 – p1.

В этом случае выигрыш игрока А, соответствующий j-той чистой стратегии игрока В, будет вычисляться по формуле:

aj* = a1j p1 + a2j p2 = a1j p1 + a2j (1 – p1) = (a1j – a2j) p1 + a2j

Нахождение наименьшего гарантированного выигрыша для игрока А подразумевает минимизацию данного выражения.

По условию наша игра имеет размерность 2 х n. То есть j = . В итоге будем иметь n аналогичных выражений, которые надо минимизировать. После этого согласно принципу максимина из найденных минимумов нужно выбрать наибольший:

a =

Решим графическим способом предыдущий числовой пример.

В данном случае будем иметь четыре уравнения, соответствующие четырем возможным чистым стратегиям игрока В:a1* = р1 + 3

a2* = –4р1 + 7

a3* = 7р1 + 1

a4* = –р1 + 3

Чтобы определить наилучший результат из наихудших, построим нижнюю огибающую четырех заданных прямых (на рисунке выделена жирной линией). Эта огибающая представляет минимальный гарантированный выигрыш игрока А, независимо от того, что делает игрок В. Точка максимума нижней огибающей – это и есть решение задачи по принципу максимина. Координатами этой точки будут р1 – одна из вероятностей смешанной стратегии игрока А и a – выигрыш игрока А.

# Заметим, что содержательной является только часть графика, заключенная в интервале 0 ≤ р1 ≤ 1 . Все линии и точки, лежащие за пределами этого интервала не принимаются во внимание.

#

"На глаз" координаты точки максимума нижней огибающей видны плохо. Точка максимума нижней огибающей – это точка пересечения прямой 3 и прямой 4. Найдем её точные координаты, решив систему соответствующих уравнений:

???

Далее находим p2: p2 = 1 – p1 = 1 – =

Итак, для игрока А все ясно:

смешанная стратегия игрока А: Р = ,

выигрыш игрока А:a = .

Аналогичные рассуждения нужно повторить и для игрока В.

Точка максимума нижней огибающей – это точка пересечения прямой 3 и прямой 4. Значит оптимальная смешанная стратегия игрока В определяется двумя стратегиями В3 и В4 соответственно.

Проигрыш игрока В, соответствующий i-той чистой стратегии игрока A, будет вычисляться по формуле:

вi* = ai3 q3 + ai4 q4 = ai3 q3 + ai4 (1 – q3) = (ai3 – ai4) q3 + ai4

В данном случае будем иметь два уравнения, соответствующие двум возможным чистым стратегиям игрока А:

в1* = 6q3 + 2

в2* = –2q3 + 3

Решив систему этих двух уравнений, найдем q3 – одну из вероятностей смешанной стратегии игрока В и в – выигрыш игрока В:

? ??

Далее находим q4: q4 = 1 – q3 = 1 – =

Все выяснили также и для игрока В:

смешанная стратегия игрока В: Q =

проигрыш игрока В:в =

Выигрыш игрока А и проигрыш игрока В совпадают – это и будет ценой игры.

Ответ: смешанная стратегия для первого игрока Р = ,

смешанная стратегия для второго игрока Q = ,

цена игры n = .

Видим, что ответы в случае решения задачи симплекс-методом и в случае решения этой же задачи графическим методом совпали.

Мораль вышесказанного такова, что если имеем задачу размерности 2 х n и под рукой нет компьютера, то точное решение можно получить с помощью графического метода.

Если имеем задачу размерности m х 2 , то делаем то же самое, поменяв игроков местами и транспонировав платежную матрицу. #

Если же под рукой есть компьютер, то такие задачи удобнее решать симплекс-методом средствами MS Excel. Если же поставленная задача любой большей размерности, то решить ее можно только симплекс-методом либо вручную, либо опять таки средствами MS Excel.

Раздел 5

<< | >>
Источник: Ю.О. Матузко. Теория принятия решений.. 2009

Еще по теме 4.2.3 Решение задачи графическим методом:

  1. 1.2.2. Графический метод расчета воздухообмена в салоне
  2. §1.2. Решение задачи о перекрестном токе с неравномерными входными температурами.
  3. 1.3.3. Использование методов анализа сигналов для решения задачи поиска «цели»
  4. 2.3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
  5. 7.3. Графическое решение задачи линейного программирования
  6. 7.6. Методы нахождения опорного решения задачи линейного программирования
  7. 12.2. Аналитический метод решения задач параметрического программирования
  8. § 65. Симплекс-метод решения задач линейного программирования, М-метод
  9. Графические методы технического анализа
  10. Решение задачи Коши методом разделения переменных. (Метод Фурье.)
  11. Решение задачи Коши методом Даламбера. ( Жан Лерон Д’Ламбер (1717 – 1783) – французский математик)
  12. ГРАФИЧЕСКИЙ МЕТОД
  13. Экономический анализ задач с использованием графического метода
  14. Графический метод решения задач
  15. §1. Комбинаторные задачи и методы их решения
  16. § 3.13. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
  17. Графический метод. Основные понятия. Алгоритм метода