- •Практичне заняття №13 пошук найкоротших відстаней на транспортних мережах та найкоротшої зв’язуючої мережі
- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
- •Практичне заняття №14 пошук максимального потоку у транспортній мережі
- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
- •Практичне заняття №15 розрахунок параметрів сітьового графіка
- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
- •Практичне заняття №16 рішення ігор 2n, m2 графоаналітичним методом
- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
- •Практичне заняття №17 рішення ігор mn методом лінійного програмування
- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
- •Практичне заняття №18 прийняття рішень в умовах невизначеності
- •Стисла теоретична довідка
- •Зміст практичного заняття та вихідні дані до його виконання
- •Приклад виконання завдання
- •Контрольні запитання
Приклад виконання завдання
Розглянемо приклад виконання завдання для умов, заданих платіжною матрицею 24 (таблиця 16.4).
Таблиця16.4 – Платіжна матриця гри (приклад)
-
В1
В2
В3
В4
А1
8
4
5
2
А2
–2
8
–1
4
Розв’язок.
Спочатку перевіримо, чи є у гри сідлова точка (рішення в чистих стратегіях). Для цього знаходимо нижню ціну гри та верхню ціну гри (таблиця 16.5).
Таблиця 16.5 – Перевірка наявності сідлової точки
|
В1 |
В2 |
В3 |
В4 |
|
|
А1 |
8 |
4 |
5 |
2 |
2 |
2 |
А2 |
–2 |
8 |
–1 |
4 |
–2 |
|
|
8 |
8 |
5 |
4 |
; ; . |
|
|
4 |
Так як нижня ціна гри не дорівнює верхній, тобто , то робимо висновок, що гра не має сідлової точки та рішення у чистих стратегіях.
Спробуємо спростити платіжну матрицю гри.
Розглянемо гру з позицій гравця В. Порівнюючи його активні стратегії В2 та В4 помічаємо, що стратегія В2 для гравця В є заздалегідь невигідною, оскільки при будь-якому ході гравця А він програє більше, використовуючи активну стратегію В2 ніж використовуючи активну стратегію В4 . Як кажуть, стратегія В4 домінує стратегію В2. Таким чином, стратегію В2 з гри можна виключити, в результаті отримуємо гру з платіжною матрицею 23 (таблиця 16.6).
Таблиця16.6 – Спрощена платіжна матриця
|
В1 |
В3 |
В4 |
А1 |
8 |
5 |
2 |
А2 |
–2 |
–1 |
4 |
Складаємо функціональні рівняння середньоочікуваних виграшів гравця А за формулою (16.4):
;
;
.
За складеними рівняннями у системі координат ( , ) будуємо відповідні графіки рівнянь (рисунок 16.1).
Рисунок 16.1 – Графіки рівнянь
Будуємо графік функції . Він охоплює нижню границю побудованих прямих та утворює контур ABCD (на рисунку 16.1 він показаний жирними лініями).
Екстремальна (максимальна) точка контуру – точка С. У ній перетинаються прямі та . Отже, отримуємо гру 22, у якій з боку гравця В маємо дві активні стратегії – В3 та В4 (таблиця 16.7).
Таблиця 16.7 – Гра 22
|
В3 |
В4 |
А1 |
5 |
2 |
А2 |
–1 |
4 |
Оптимальні змішані стратегії гравців знаходимо за формулами (16.3):
; ;
; ;
.
Тобто, , , . Автотранспортному підприємству слід з імовірністю 0,25 (25 днів зі 100) виділяти рухомий склад за третім варіантом, та з імовірністю 0,75 (75 днів зі 100) – за четвертим варіантом. При цьому рухомий склад 62,5% днів відпрацює на першому маршруті та 37,5% днів – на другому маршруті, а підприємство буде одержувати середній щоденний прибуток 2,75 у.г.о.