Пример:

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

Решение.

При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу

Составим теперь пару взаимно-двойственных задач :

Решим вторую из них

Из оптимальной симплекс-таблицы следует, что

(y₁, y₂, y₃) =(0; ;1),

а из соотношений двойственности следует, что

(x₁, x₂, x₃) = ( ; 1; 0).

Следовательно, цена игры с платёжной матрицей А₁ равна

.

а игры с платёжной матрицей А :

.

При этом оптимальные стратегии игроков имеют вид:

y* = (p₁, p₂, p₃) = (vx₁; vx₂; vx₃) = =

y* = (q₁, q₂, q₃) = (vy₁; vy₂; vy₃) = = = .

Графоаналитические методы решения игр с двумя стратегиями у одного из игроков.

Поясним метод на примерах.

Пример:

Рассмотрим игру, заданную платёжной матрицей.

На плоскости хОy введём систему координат и на оси Ох отложим отрезок единичной длины А₁А₂, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (p, 1  p). В частности, точке А₁ (1, 0) отвечает стратегия А₁, точке А₂ (0, 1) – стратегия А₂ и т.д.

Рис.1

В точках А₁ и А₂ восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока 1 при стратегии А₁, а на втором – при стратегии А₂. Если игрок 1 применит стратегию А₁, то выиграет при стратегии В₁ игрока 2 – 2, при стратегии В₂ – 3, а при стратегии В₃ – 11. Числам 2, 3, 11 на оси 0х соответствуют точки В₁, В₂ и В₃.

Если же игрок 1 применит стратегию А₂, то его выигрыш при стратегии В₁ равен 7, при В₂ – 5, а при В₃ – 2. Эти числа определяют точки В₁, В₂, В₃ на перпендикуляре, восстановленном в точке А₂.Соединяя между собой точки В₁ и В₁, В₂ и В₂, В₃ и В₃ получим три прямые, расстояние до которых от оси 0х определяет средний выигрыш при любом сочетании соответствующих стратегий. Например, расстояние от любой точки отрезка В₁В₁ до оси 0х определяет средний выигрыш v при любом сочетании стратегий А₁ А₂ (с частотами p и 1–p) и стратегией В₁ игрока 2. Это расстояние равно

2p + 7(1 p) = v

(Вспомните планиметрию и рассмотрите трапецию А₁ B₁ B₁ A₂). Таким образом, ординаты точек, принадлежащих ломанной

В₁ M  В₃ определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке ; следовательно этой точке соответствует оптимальная стратегия x* = (p, 1p), а её ордината равна цене игры v. Координаты точки  находим как точку пересечения прямых В₂ B₂ и В₃ B₃.

Соответствующие два уравнения имеют вид

.

Следовательно, x = ( ; ), при цене игры v= . Таким образом, мы можем найти оптимальную стратегию при помощи матрицы

Оптимальные стратегии для игрока 2 можно найти из системы

и, следовательно, y = (0; ; ). (Из рисунка видно, что стратегия B₁ не войдёт в оптимальную стратегию).

Литература

1. Гловацкая А.П. Методы и алгоритмы вычислительной математики / А.П. Гловацкая. – М.: Радио и связь, 1999. – 408с.

2. Солодовников А.С. Математика в экономике / А.С. Солодовников [ и др.]. – М.: Финансы и статистика, 2000. – 224с.

3. Эддоус М., Стенсфилд Р. Методы принятия решений / М.Эддоус., Р.Стенсфилд. – Аудит, ЮНИТИ, 1997. – 590с.

4. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование / Ю.Н. Кузнецов, В.И. Кузубов., А.Б. Волощенко. – М.: Высш.шк., 1980. – 300с.

5. Акулич И.А. Математическое программирование в примерах и задачах / И.А. Акулич. – М.: Высш.шк., 1986. – 317с.

6. Данко П.Е. Высшая математика в примерах и задачах / П.Е. Данко [и др.]. – М.: Высш.шк., 1999. – 304с.

7. Грешилов А.А. Как принять наилучшее решение в реальных условиях / А.А. Грешилов. – М.: Радио и связь, 1991. – 320с.

8. Капустин В.Ф. Практические занятия по курсу математического программирования / В.Ф. Капустин. – Л., изд-во Ленинград. ун-та, 1976. – 192с.

9. Калихман И.Л. Сборник задач по математическому программированию / И.Л. Калихман. – М.: Высш.шк., 1975. – 270с.

10. Бондарев В.М. Основы программирования / В.И. Бондарев [и др.]. – Харьков, 1997. – 368с.

11. Ефимов А.В. Сборник задач по математике для втузов / А.В. Ефимов [и др.]. – М.: Наука, 1990. – 304с.

12. Морозов В.В, Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях / В.В Морозов, А.Г. Сухарев, В.В. Федоров. – М.:Высш.шк., 1986. – 287с.

13. Петросян Л.А. Теория игр. / Л.А. Петросян – М.: Высш.шк.: книжный дом «Университет», 1998 . –304с.

14. Вентцель Е.С. Исследование операций. / Е.С. Вентцель. – М.:Высш.шк., 2001. – 208с.

Оглавление:

Линейное программирование. 1

Основная задача линейного программирования. 1

Графический метод решения задачи линейного программирования. 1

Cимплекс-метод. 3

Целочисленное программирование. 6

Теория двойственности в линейном программировании. 8

Транспортная задача. 14

Задача о назначениях. 16

Задача коммивояжера. Метод ветвей и границ. 18

Сетевые задачи. 21

Задача о многополюсной кратчайшей цепи. Алгоритм Флойда. 21

Задача о максимальном потоке. 23

Динамическое программирование. 24

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

Принцип оптимальности. Уравнение Беллмана. 25

Математическая формулировка принципа оптимальности. 25

Оптимальная политика замены оборудования. 25

Мультипликативная реализация метода динамического программирования. 27

Задачи о маршрутизации. 28

Принятие решений в условиях конфликта (Элементы теории игр). 30

Основные понятия. 30

Классификация игр. 31

Антагонистические матричные игры. 31

Решение матричной игры в чистых стратегиях. 31

Решение игры в смешанных стратегиях. 32

Свойства решений матричных игр. 33

Сведение матричной игры к задаче линейного программирования. 34

Графоаналитические методы решения игр с двумя стратегиями у одного из игроков. 36

Литература 38

40