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

Будемо вважати, що всі елементи платіжної матриці невід'ємні (якщо це не так, то можна до всіх елементів матриці додати деяке достатньо велике число 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)

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

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

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

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

Моделювання вхідного потоку замовлень

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

1. пуасонівські потоки та близькі до них часто зустрічаються на практиці;

2. для пуасонівського потоку отримані оцінки, які є найзручнішими для практичного використання;

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

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

Враховуючи три названі властивості пуасонівського процесу можна вивести імовірність появи k вимог в системі на протязі часового інтервалу t:

(5.1)

Знайдемо математичне сподівання числа замовлень, які поступили протягом часу t

(5.2)

При t=1 отримуємо . Отже визначає середнє число замовлень в одиницю часу (інтенсивність потоку). Встановимо імовірність появи однієї вимоги в системі на протязі часу t:

(5.3)

де - нескінченно мала величина в порівнянні з t.

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

(5.4)

Це означає, що інтервалу між поступленнями замовлень в систему підлягає експоненціальному закону.

Моделювання обслуговування замовлень

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

Знайдемо середнє значення (математичне сподівання) часу обслуговування:

(5.5)

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

Знайдемо оцінку імовірності обслуговування замовлення протягом часу t:

(5.6)

Відповідно імовірність того, що обслуговування замовлення не буде закінчена протязі часу t дорівнює:

(5.7)