logo search
Опорний конспект ОММ 4 Ф

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

Таблиця 1.

В1

В2

В3

В4

А1

3

3

6

8

А2

9

10

4

2

А3

7

7

5

4