Зміст модуля

- Предмет теорії графів. Основні означення.

- Ейлерові та гамільтонові графи.

- Дерева та ліс. Алгоритм побудови остовного дерева графа.

- Екстремальні задачі на графах.

- Розрахунок сітьових (мережевих) моделей.

- Максимальна течія у мережі, її обчислення та застосування (транспортна задача).

- Метод гілок та меж та його застосування (задача про рюкзак, задача комівояжера).

- Задача про призначення та її розв’язання.

- Матричні ігри. Основні теореми теорії ігор.

- Розв’язання матричних ігор (алгебраїчний метод, геометричний та наближений).

- Методи розв’язання задач теорії масового обслуговування.

Цільова настава

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

Контрольні заходи модуля

Індивідуальні завдання:

1 Екстремальні задачі на графах.

2 Мережевий граф та його розрахунок.

3 Задача комівояжера.

4 Задача про призначення.

ІІІ Питання для перевірки теоретичних знань.

1 Студент повинен знати: означення (о), властивості (в).

Студент повинен вміти: записати формулу (ф), сформулювати теорему (т).

1.1 Предмет теорії операції (о).

1.2 Математична модель операції (о).

1.3 Навести приклади типових задач теорії дослідження операцій.

1.4 Поняття графа (о), орграф, неорграф (о).

1.5 Засоби завдання графа.

1.6 Частини графа (о).

1.7 Маршрути в графі (о).

1.8 Властивості графів (зв’язність, ізоморфізм) (о).

1.9 Кількість вершин та ребер графа об’єднання та перетин графів (о, в).

1.10 Ейлерові та гамільтонові графи (о, в).

1.11 Дерева та ліс (о, в).

1.12 Алгоритм побудови остовного дерева графа.

1.13 Сітьові (мережеві) моделі (о, в).

1.14 Розрізи графа (о, в).

1.15 Течія у графі (о, в).

1.16 Максимальна течія у графі (о, в).

1.17 Алгоритм пошуку максимальної течії у графі.

1.18 Теорема Форда-Фалкерсона (т).

1.19 Метод гілок та меж (о).

1.20 Задача про рюкзак та метод її розв’язання (о, ф).

1.21 Задача комівояжера та метод її розв’язання (о, ф).

1.22 Задача про призначення та метод її розв’язання (о, ф).

1.23 Гра з нульовою сумою (о).

1.24 Матричні ігри (о).

1.25 Платіжна матриця (о).

1.26 Оптимальні стратегії (о).

1.27 Нижня та верхня ціни гри (о).

1.28 Мінімальні стратегії (о).

1.29 Основні теореми теорії ігор (ф).

1.30 Розв’язання задач (ф):

а) 2х2;

б) 2хn;

в) mх2.

1.31 Наближене розв’язання задач теорії гри (ф).

1.32 Основні задачі теорії масового обслуговування (о):

а) одноканальна система з відмовами;

б) N-канальна система з відмовами (о, в);

в) багатоканальна система з необмеженою та обмеженою чергами

(о, в).

1.33 Основні характеристики систем масового обслуговування (о, ф).

2 Студент повинен показати практичні навики:

2.1 Побудова матриць графів.

2.2 Побудова остовного дерева графа.

2.3 Побудова максимального і мінімального остовного дерева графа.

2.4 Знаходження найкоротшого та найбільшого шляху у орієнтованому графі.

2.5 Знаходження максимальної течії у графі.

2.6 Розв’язання задачі про рюкзак.

2.7 Розв’язання задачі комівояжера.

2.8 Розв’язання задачі про призначення.

2.9 Розв’язання матричної гри 2х2.

2.10 Розв’язання гри 2хn і mх2.

2.11 Розв’язання ігор mхn (різні методи).

2.12 Знаходження характеристик систем масового обслуговування.