- Цветы и растения
- Аквариум и рыбы
- Для работы
- Для сайта
- Для обучения
- Почтовые индексы Украины
- Всяко-разно
- Электронные библиотеки
- Реестры Украины
- Старинные книги о пивоварении
- Словарь старославянских слов
- Все романы Пелевина
- 50 книг для детей
- Стругацкие, сочинения в 33 томах
- Записи Леонардо да Винчи
- Биология поведения человека
Главная ![]() ![]() ![]() |
Математичне програмування - Наконечний С.І.
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
Варіант бізнес-плану |
Зовнішня ситуація |
||||
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 |
Необхідно вибрати найкращий варіант бізнес-плану або комбінацію із розроблених планів.
Розв’язання.
Маємо гру, платіжною матрицею якої є відповідні елементи вищенаведеної таблиці. Легко переконуємося, що домінуючих стратегій у цій грі немає.
Потім визначаємо:
а також
Отже, тобто немає сідлової точки, а це означає, що необхідно застосувати метод зведення гри до задачі лінійного програмування:
за умов:
Розв’язуємо цю задачу симплексним методом. Оптимальний розв’язок задачі: ;
. Звідси отримаємо оптимальний розв’язок для початкової задачі:
;
. Ціна гри
.
Created/Updated: 25.05.2018