Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

11.6. Зведення матричної гри до задачі лінійного програмування

Якщо гра 2 x n або m x 2 може бути розв’язана геометрично, то у випадку гри 3 x n (m x 3) геометрична інтерпретація переходить у простір, що ускладнює як її побудову, так і сприйняття. У випадку ж, коли n > 3, m > 3, геометрична інтерпретація взагалі неможлива. Для розв’язування гри m x n використовують прийом зведення її до задачі лінійного програмування.

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

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

Допустимо, що гравець А застосовує свою оптимальну стратегію, а гравець В — свою «чисту» j-ту стратегію Bj, тоді середній виграш гравця А дорівнюватиме:

. (11.10)

За цих обставин виграш має бути не меншим, ніж ціна гри. Отже, для будь-якого значення j величина виду (11.10) має бути не меншою, ніж u:

Розділивши всі обмеження на u, отримаємо:

Позначивши маємо:

.

Враховуючи умову, що , отримуємо .

Необхідно зробити виграш максимальним. Цього можна досягти, коли вираз набуватиме мінімального значення. Отже, врешті маємо звичайну задачу лінійного програмування.

Цільова функція:

(11.11)

за умов:

(11.12)

. (11.13)

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

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

Маємо таку лінійну модель задачі:

за умов:

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

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

Агрофірма «Зоря» розробила шість бізнес-планів (X1, X2, X3, X4, X5, X6) для їх здійснення у наступному році. Залежно від зовнішніх умов (погодного стану, ринку тощо) виділено п’ять ситуацій (Y1, Y2, Y3, Y4, Y5). Для кожного варіанта Xi бізнес-плану та зовнішньої ситуації Yj обчислені прибутки, які наведені у табл. 11.2:

Таблиця 11.2

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

Розв’язання.

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

Потім визначаємо:

а також

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

за умов:

Розв’язуємо цю задачу симплексним методом. Оптимальний розв’язок задачі: ; . Звідси отримаємо оптимальний розв’язок для початкової задачі: ; . Ціна гри .