Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






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



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

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

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

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

.

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

,

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

. (6.23)

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

. (6.24)

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

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

за умов

,

,

.

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

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

З (6.23) маємо:

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

Нехай , тоді

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

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

.

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

(6.25)

за умов

(6.26)

. (6.27)

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

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

.

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

за умов

.

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

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

Задача 6.35.

Агрофірма «Зоря» розробила шість бізнес-планів (А1, А2, А3, А4, А5, А6) для реалізації в наступному році. Залежно від зовнішніх умов (погодних умов, стану ринку тощо) виокремлено п’ять ситуацій (В1, В2, В3, В4, В5). Для кожного варіанту Аі бізнес-плану та зовнішньої ситуації обчислено прибутки, наведені в такій таблиці:



 

Варіант бізнес-плану Зовнішні ситуації
В1 В2 В3 В4 В5
Прибутки тис. грн.
А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

 

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

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

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

;

;

,

а також

;

;

.

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

за умов

.

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

Стохастичне програмування

Економічні системи функціонують і розвиваються в умовах невизначеності, які породжують ризикованість прийманих рішень. Невизначеність може бути різного ступеня залежно від того, яку інформацію маємо про досліджуваний процес чи явище. Розрізняють шість інформаційних ситуацій. Скажімо, перша інформаційна ситуація характеризується заданим розподілом відповідних параметрів. У такому разі для прийняття рішень застосовують методи стохастичного програмування, сутність яких полягає у тому, що рішення залежать не тільки від керованих змінних , а від ряду випадкових некерованих параметрів . Наприклад, плануючи діяльність сільськогосподарських підприємств, маємо змогу встановлювати площі посівів сільськогосподарських культур, рівні внесення добрив, поголів’я тварин (керовані змінні), але результат такої діяльності значною мірою залежить від погодних умов, податків, процентної ставки кредиту (некеровані змінні).



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


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!