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

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

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

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

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

. (8.10)

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

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

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

.

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

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

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

(8.11)

за умов:

(8.12)

. (8.13)

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

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

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

за умов:

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

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

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

Таблиця 8.2

Варіант бізнес-плану	Зовнішня ситуація
	Y1	Y2	Y3	Y4	Y5
	прибутки, тис. грн
Х1	1,0	1,5	2,0	2,7	3,2
Х2	1,2	1,4	2,5	2,9	3,1
Х3	1,3	1,6	2,4	2,8	2,1
Х4	2,1	2,4	3,0	2,7	1,8
Х5	2,4	2,9	3,4	1,9	1,5
Х6	2,6	2,7	3,1	2,3	2,0

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

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

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

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

а також

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

за умов:

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

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

Зрозуміло, що коли початкові умови задачі містять значну кількість невизначених параметрів, то математичне дослідження не може дати чіткого обґрунтування раціонального розв’язку, однак і за відсутності повної визначеності кількісний аналіз дає наукову основу для прийняття рішень. Т. Сааті — засновник науки «Дослідження операцій» (інструментарієм якої є «Математичне програмування») писав, що «Дослідження операцій» — це таке мистецтво, яке дає погані відповіді на такі практичні запитання, на які інші методи дають ще гірші відповіді.

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

Рекомендована література.

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

2. Ермолаев Ю.М. Методи стохастичного програмування. – М.: Наука, 1976.

3. Зайченко Ю.П. Исследование операций. – К.: Вища шк., 1988.

4. Кабак Л.Ф., Суворовский А.А. Математическое программирование. – К.: ІМКВО, 1992.

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

6. Карасев А.И., Аксютина З.М., Савельева Т.И. Курс высшей математики для экономических ВУЗов. – М.: Высш. шк., 1985.

7. Карманов В.Т. Математическое программирование. – М.: Наука, 1986.

8. Линейное и нелинейное программирование / Под ред. И.Н. Ляшенко. – К.: Вища шк., 1975.

9. Романюк Т.П., Терещенко Т.О., Присенко Г.В., Городкова І.М. Математичне програмування: Навч. посібник – К.: ІЗМН, 1996.

10. Цегелик Г.Г. Лінійне програмування. – Львів: Світ, 1995.

11. Таха Х. Введение в исследование операций. – М.: Мир, 1985. – 479 с.

12. Черноруцкий И. Г. Методы принятия решений. – СПб.: БХВ - Петербург, 2005

13. Приймак В.М. Прийняття управлінських рышень: Навчальний посібник. – К.: Атіка, 2008. – 240 с.

14. Гевко І.Б. Методи прийняття управлінських рішень: Піддручник. – К.: Кондор, 2009. – 187 с.

15. Бережна Л.В., Снитюк О.І. Економіко-математичні методи та моделі у фінансах. – К.: Кондор, - 2009. – 301 с.