Приклад виключення невигідних стратегій

Нехай дано платіжну матрицю. Знайдемо оцінки стратегій а потім верхню та

	B1	B2	B3	B4	B5
A1
A2
A3
A4

 

нижню ціни гри. Оскільки вони різні , то сідлової точки не існує. Порівнюючи стрічки А2 та А3, А3 та А4, виключаємо стратегії А2 та А4, як заздалегідь невигідні відносно стратегії А3.

	B1	B2	B3	B4	B5
A1
A3

 

Оскільки гравець В мінімізує виграш гавця А, то для нього стратегії В1, В2, В3 заздалегідь невигідні в порівнянні із стратегією В5:

	B4	B5
A1
A3

Розв'язавши гру 2х2, формуємо загальні оптимальні мішані стратегії:

.

 

Розв'язання ігор

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

Отже розв'язок гри можна будувати наступним чином:

1) будується графічна модель гри;

2) виділяється ламана нижньої межі виграшу гравця А і знаходиться її максимум, що рівний ціні гри ;

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

4) параметри мішаних стратегій визначаються як для гри .

Розв'язок гри можна будувати подібно до попереднього. При цьому слід враховувати, що в цьому випадку шукається ламана верхньої межі прогашу гравця В і шукається її мінімальна точка.

 

Приклад розв'язку гри

 

 

	B1	B2	B3
A1
A2

 

, отже гра не має сідлової точки. Будуємо графічну модель

 

Ломана B₁NMB₂ це нижня межа виграшу гравця А. Точка N є точкою оптимуму, тобто активними стратегіями гравця В є стратегії В1 та В2. Оптимальну стратегію гравця А знаходимо із системи рівнянь

(4.16)

розв'язавши яку отримуєм:

Аналогічно знаходимо оптимальну стратегію гравця В із системи рівнянь

(4.17)

звідки

Приклад розв'язку гри

 

	B1	B2
A1	0,4	1,0	0,4
A2	0,5	0,5	0,5
A3	1,0	0,3	0,3
A4	0.8	0,3	0,3
	1,0	1,0

 

, отже гра не має сідлової точки. Стратегію А4 виключаємо як заздалегідь невигідну. Будуємо графічну модель

 

Ломана А₃NА₁ це верхня межа програшу гравця В. Точка N є точкою оптимуму, тобто активними стратегіями гравця А є стратегії А3 та А1. Оптимальну стратегію гравця В знаходимо із системи рівнянь

(4.18)

розв'язавши яку отримуєм:

Аналогічно знаходимо оптимальну стратегію гравця А із системи рівнянь

(4.19)

звідки

 

 

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

Будемо вважати, що всі елементи платіжної матриці невід'ємні (якщо це не так, то можна до всіх елементів матриці додати деяке достатньо велике число L. При цьому ціна гри збільшиться на L, а розв'язок задачі не зміниться. Оскільки тоді то . Нехай гравець В застосовує свою чисту стратегію, а гравець А – свою оптимальну стратегію. Тоді середній виграш гравця А дорівнює

(4.20)

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

(4.21)

 

Розділивши ліву і праву частини кожної з нерівностей (4.21) на , отримуєм:

(4.22)

де .

Оскільки , то при діленні на отримаємо

(4.23)

Враховуючи, що гравець прагне максимізувати ціну гри, отримуємо умову на цільову функцію

(4.24)

Отже задача теорії ігор звелася до задачі лінійного програмування (4.24), (4.22), розв'язавши яку знаходимо ціну гри та оптимальну мішану стратегію гравця А:

(4.25)

(4.26)

Для побудови оптимальної мішаної стратегії гравця В за допомогою міркувань аналогічних наведеним приходимо до задачі лінійного програмування, яка двоїстою до задачі (4.24), (4.22):

(4.27)

(4.28)

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

(4.29)

 

При цьому

(4.30)

(4.31)

 

Системи масового обслуговування

 

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

 

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

Вузол обслуговування може складатися з одного пристрою обслуговування (одно канальна система) або декількох пристроїв паралельного обслуговування (багатоканальна система), або послідовного багатоетапного.обслуговування (багатофазна система).