- •Тема 1. Постановка задач лінійного програмування
- •Задача про оптимальне виробництво
- •Задача по формуванню оптимальних складів
- •Класифікація злп
- •Тема 2. Основні методи розв’язування задач лінійного програмування
- •2.1 Графічний метод розв’язування задач лінійного програмування
- •2.2. Симплекс-метод
- •Тема 3. Транспортна задача
- •Метод потенціалів розв’язання транспортної задачі
- •Відкриті моделі транспортних задач
- •Варіант 5
- •Знайдемо
- •Тема 5. Системи масового обслуговування з відмовами
- •Найпростіший потік подій
- •Смо з відмовами.
- •Тема 6. Системи масового обслуговування з очікуванням
- •Тема 7. Сітьове планування
- •Варіант 1
- •Спрощення платіжної матриці гри
- •Розв’язування ігор 2×2
- •Графічне розв’язування ігор 2×n та m×2
Варіант 1

Варіант 2

Варіант 3

Варіант 4

Варіант 5

Варіант 6

Варіант 7

Варіант 8

Варіант 9

Варіант 10

Варіант 11

Варіант 12

Варіант 13

Варіант 14

Варіант 15

Варіант 16

Варіант 17

Варіант 18

Варіант 19

Варіант 20

Варіант 21

Варіант 22

Варіант 23

Варіант 24

Варіант 25

Варіант 26

Варіант 27

Варіант 28

Варіант 29

Варіант 30

Тема 8. Елементи теорії стратегічних ігор
Нехай ми маємо декілька суб’єктів (гравців), кожен з яких має вибір з певної кількості можливостей, які називаються стратегіями. Одноразове використання стратегії називають ходом. В результаті використання кожним з учасників певної стратегії, вони отримують виграш (програш будемо вважати виграшем зі знаком мінус). Гра називається антагоністичною, якщо в її результаті хтось виграє, а хтось програє. Ігри в яких виграш одних учасників дорівнює програшу інших називають іграми з нульовою сумою.
Розглянемо гру двох учасників з нульовою сумою, така гра однозначно задається платіжною матрицею (матрицею виграшів першого гравця).
-





…



…
…… …

…



…






-
стратегії першого гравця;
– стратегії другого гравця;
- виграш першого гравця, при умові, що
він застосовує стратегію
,
а другий гравець - стратегію
.
Зауваження 8.1. Матриця виграшів другого гравця – це транспонована матриця виграшів першого гравця помножена на - 1.
Перший гравець оцінює, який мінімальний виграш він отримає при застосуванні кожної стратегії, а потім обирає ту, при якій це число буде найбільшим.
,
.
Відповідна
стратегія називається максимінною, а
число
- нижньою ціною гри.
Аналогічно, другий гравець для кожної своєї стратегії знаходить число, що є максимальним виграшем першого гравця, а потім з цих виграшів обирає найменший:
,
.
Ця
стратегія називається мінімаксною, а
число
- верхньою ціною гри.
Якщо
,
то відповідне
називають ціною гри, клітину (i,j)
називають сідловою точкою. Якщо сідлова
точка - єдина, то кажуть, що гра може
бути розв’язана в чистих стратегіях,
тобто перший гравець завжди буде
застосовувати стратегію
,
а другий
.
Мішаною стратегією першого гравця називають
,
,
де
- ймовірність використання відповідної
стратегії
.
Аналогічно записуються мішані стратегії
другого гравця:
,
.
Зауваження 8.2. Чиста стратегія є частковим випадком мішаної, при цьому, ймовірність її застосування дорівнює 1, а ймовірності застосування інших стратегій - 0.
Будь-яка скінченна гра двох гравців з нульовою сумою має розв’язок у мішаних стратегіях.
Спрощення платіжної матриці гри
Кажуть, що певний рядок або стовпчик є домінуючим над іншим, якщо кожен з його елементів не менший за відповідний елемент цього іншого. Оскільки для першого гравця домінуючі стратегії за будь-яких умов вигідніші за ті, над якими вони домінують, то з платіжної матриці викреслюємо рядки для яких є домінуючі. Потім викреслюємо домінуючі стовпчики, оскільки для другого гравця вони менш вигідні ніж ті, над якими вони домінують. Дану процедуру повторюємо до тих пір, поки не отримаємо матрицю, в якій не має домінуючих рядків і стовпчиків.
Приклад 8.1. Перевірити гру з платіжною матрицею

на наявність сідлової точки та провести її спрощення.
Розв’язання. Спочатку перевіримо гру на наявність сідлової точки, для чого знайдемо нижню та верхню ціни гри.
При
застосуванні першим гравцем стратегій
,
,
його найменший виграш складе 2 одиниці
(найменші елементи
відповідних
рядків). При використанні другої
стратегії, найменший виграш – 3, а
четвертої – 1. Найбільше з цих чисел
і є нижньою ціною гри (отже
).
Для
визначення верхньої ціни гри, знаходимо
найбільший виграш першого гравця в
кожному стовпчику, що відповідає певній
стратегії другого гравця. Із цих чисел
обираємо найменше
.
Це число і буде верхньою ціною гри (
)
|
|
|
|
|
|
|
|
|
|
|
2 |
5 |
7 |
4 |
8 |
3 |
2 |
|
|
3 |
6 |
7 |
5 |
8 |
4 |
3 |
|
|
2 |
6 |
5 |
6 |
7 |
4 |
2 |
|
|
1 |
3 |
8 |
2 |
5 |
6 |
1 |
|
|
4 |
2 |
5 |
6 |
8 |
5 |
2 |
|
|
4
|
6 |
8 |
6 |
8 |
6 |
3 4 |
Г


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








2
5
7
4
8
3

3
6
7
5
8
4

2
6
5
6
7
4

1
3
8
2
5
6

4
2
5
6
8
5
Тепер ми бачимо, що другий рядок домінує над третім та четвертим, які і викреслюємо.
-



3
6


2
6


1
3

4
2
Подальше спрощення неможливе, оскільки немає домінуючих рядків і стовпчиків.
Відповідь.Нижня ціна гри – 3, верхня ціна гри – 4. Гра сідлової точки не має. Спрощена матриця гри
-



3
6

4
2
