Лабораторне заняття №21

Тема заняття: Розв’язання задач теорії ігор.

(Зведення задач теорії ігор до задач ЛП та вирішення останніх симплексним методом).

Мета: сформувати вміння та навички розв’язання задач теорії ігор симплексним методом.

Методичні рекомендації: Вивчити лекцію №6 та ознайомиться з наступною літературою [3 с. 224-250], [4 с. 239-251].

Постановка завдання:

Якщо матрична гра не має сідлової точки, то знаходження її розв’язку, особливо за великої кількості стратегій, — доволі складна задача, яку можна ефективно розв’язати методами лінійного програмування.

Задача розглядається в такому формулюванні: знайти вектори ймовірностей і з метою визначення оптимального значення ціни гри та оптимальних стратегій.

Зауважимо, що доведено основну теорему теорії ігор: кожна скінчена гра має принаймні один розв’язок, який можливий в області змішаних стратегій.

Отже, нехай маємо скінченну матричну гру з платіжною
матрицею

Оскільки оптимальні стратегії гравців А і В дозволяють отримати виграш

то використання оптимальної змішаної стратегії гравцем А має забезпечувати виграш не менший за ціну гри в разі вибору гравцем В будь-яких стратегій. Математично ця умова записується так:

. (1)

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

. (2)

Ці два співвідношення застосовують для знаходження розв’язку гри.

Отже, потрібно знайти , щоб

за умов

Зауважимо, що ціна гри невідома і має бути визначена під час розв’язування задачі.

Модель ігрової задачі може бути спрощена.

З (1) маємо:

Поділивши всі обмеження на , дістанемо:

Нехай , тоді

Згідно з умовою , звідки .

Отже, цільова функція початкової задачі набирає такого вигляду:

У результаті задача лінійного програмування:

(3)

за умов

(4)

. (5)

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

За аналогією запишемо задачу лінійного програмування для визначення оптимальної стратегії гравця В. Нехай

Тоді маємо таку лінійну модель:

за умов

Очевидно, що задача лінійного програмування для гравця В є двоїстою до задачі гравця А, а тому оптимальний розв’язок однієї з них визначає оптимальний розв’язок спряженої.

Розглянемо приклад на застосування методів лінійного програмування до знаходження оптимального розв’язку гри.

Приклад 1.

Агрофірма «Зоря» розробила шість бізнес-планів
(А ₁, А ₂, А ₃, А ₄, А ₅, А ₆) для реалізації в наступному році. Залежно від зовнішніх умов (погодних умов, стану ринку тощо) виокремлено п’ять ситуацій (В ₁, В ₂, В ₃, В ₄, В ₅). Для кожного варіанту А_і бізнес-плану та зовнішньої ситуації обчислено прибутки, наведені в такій таблиці:

Варіант бізнес-плану	Зовнішні ситуації
В ₁	В ₂	В ₃	В ₄	В ₅
Прибутки тис. грн.
А ₁	1,0	1,5	2,0	2,7	3,2
А ₂	1,2	1,4	2,5	2,9	3,1
А ₃	1,3	1,6	2,4	2,8	2,1
А ₄	2,1	2,4	3,0	2,7	1,8
А ₅	2,4	2,9	3,4	1,9	1,5
А ₆	2,6	2,7	3,1	2,3	2,0

Потрібно вибрати варіант бізнес-плану або комбінацію з розроблених планів.

Розв’язування. Маємо гру, платіжною матрицею якої є відповідні елементи наведеної таблиці. Легко переконатися, що домінуючих стратегій у цій грі немає.

Далі визначаємо:

;

а також

;

Отже, , тобто сідлової точки немає, а це означає, що потрібно скористатися моделлю (3)—(5):

за умов

Розв’язуємо цю задачу симплексним методом.

Задача 1

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

В_j А_i	В₁	В₂	В₃	В₄
А₁
А₂
А₃

Визначити оптимальні обсяги виготовлення продукції, які гарантуватимуть середню величину прибутку при будь-якому попиті, вважаючи його невизначеним.

Задача 2

Швейне підприємство планує масове виготовлення нової моделі одягу. Попит на цю модель не може буди точно визначений, тобто, його величина характеризується трьома можливими станами: І, ІІ, ІІІ. У залежності від цих станів аналізуються три можливих варіанти виготовлення цієї моделі: А, В, С. Кожний з цих варіантів вимагає своїх витрат і має різну ефективність. Прибуток (тис.грн.), який отримає підприємство при заданому обсязі виготовлення моделі одягу і відповідному стані попиту, визначається матрицею:

	І	ІІ	ІІІ
А
В
С

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

Задача 3

Побудувати гру, задану задачею лінійного програмування:

3.1. ; 3.2. .

ДОДАТКОВІ ЗАВДАННЯ:

Задача 4

Взуттєва фабрика планує виготовлення двох моделей взуття А і В. попит на ці моделі невизначений, і може перебувати в одному із станів: І, ІІ. В залежності від цих станів прибуток фабрики різний і визначається матрицею:

	І	ІІ
А
В

Знайти оптимальне співвідношення між обсягами виготовлення кожної із моделей взуття, за яким фабриці гарантується середня величина прибутку при будь-якому попиті.

Задача 5

Торгівельне підприємство розробило декілька варіантів плану продажі товарів на ярмарці з врахуванням кон’юнктури ринку і попиту покупців, які постійно змінюються. Доходи підприємства в залежності від цих показників наведені у таблиці: