Тема 6. Елементи теорії ігор

Лекція 13.

Тема лекції: Матричні ігри (продовження)

Мета: ознайомити студентів з методами розв’язання задач теоріі ігор та зведення їх до задач ЛП.

План лекції

3. Графічний метод розв’язання задач теорії ігор.

4. Зведення задач теорії ігор до задач ЛП.

5. Зведення задачі ЛП до матричної гри.

Література:

1. Лавріненко Н.М., Латинін С.М., Фортуна В.В., Безкровний О.І. Основи економіко-метематичного моделювання: Навч. Посіб. - Львів: «Магнолія 2006», 2010.- 540с.

2. Іванюта І. Д. Практикум з математичного програмування: Навчальний посібник / І. Д. Іванюта, В. І. Рибалка, І. А. Рудоміно-Дусятська. – К.: «Слово», 2008. - 296 с.

3.Кучма М. І. Математичне програмування: приклади і задачі: Навчальний посібник / М.І. Кучма. – Львів: «Новий Світ - 2000», 2006. - 344 с.

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

4. Графічний метод розв’язання теорії ігор.

Графічний метод можна застосовувати до ігор, в яких хоча б один гравець має тільки дві стратегії, тобто до ігор 2xn i mx2.

Основні етапи розв’язку ігор 2xn i mx2:

• Будуємо прямі, що відповідають стратегіям другого (першого) гравця.

• Визначаємо нижню (верхню) межу виграшу.

• Знаходимо дві стратегії другого (першого) гравця, яким відповідають дві прямі, що перетинаються в точці з найбільшою (найменшою) ординатою.

• Визначаємо ціну гри і оптимальні стратегії.

Приклад 3. Знайти розв’язок гри заданої матрицею

5. Зведення задач теорії ігор до задач лп.

Якщо один з гравців застосовує свою оптимальну стратегію х^*, то інший не може покращити своє становище, тобто для оптимальної стратегії справедливі співвідношення:

j= , x_i≥0, =1, i= за умов ν→Мах.

Перетворимо цю задачу, здійснивши підстановку p_i= , і отримаємо

→Min,тому що ν→Мах.

Таким чином, маємо задачу ЛП, розв’язуючи яку, отримаємо значення p_i, за допомогою яких шляхом оберної підстановки визначимо оптимальні значення ймовірностей, що складають оптимальну мішану стратегію.

А здійснивши підстановку q_j= і враховуючи, що гравець В прагне мінімізувати програш, отримаємо пару двоїстих задач ЛП, розв’язання яких дозволить визначити оптимальні стратегії гравців А та В:

.

Таким чином, процедура розв’язування гри двох осіб є наступною:

1. Розраховуємо нижню та верхню ціну гри; якщо вони рівні між собою, то гра розв’язана.

2. Спрощуємо гру шляхом виключення домінованих стратегій.

3. Формулюємо пару задач ЛП, розв’язавши одну з яких, встановлюємо оптимальну мішану стратегію одного з гравців (зручніше гравця В).

4. За розв’язком прямої задачі знаходимо розвязок двоїстої задачі.

5. Шляхом оберненої підстановки визначемо оптимальні стратегії для спрощеної гри та доповнюємо їх домінованими чистими стратегіями з ймовірністю використання, що рівні нулю.

Приклад 4. Підприємство виготовляє три види продукції А₁, А₂, А₃, отримуючи при цьому прибуток, що залежить від попиту. Попит може перебувати в одному з чотирьох станів В₁, В₂, В₃, В₄. Прибуток підприємства, який отриманий при виготовленні кожного виду продукції в залежності від попиту, наведено у таблиці 1. Визначити оптимальні обсяги виготовлення продукції, що гарантують середню величину прибутку при будь-якому попиті, вважаючи його невизначеним.

Таблиця 1.

	В1	В2	В3	В4
А1	3	3	6	8
А2	9	10	4	2
А3	7	7	5	4