Бібліографія: сторінки 638-640 (40 назв)

Предметний вказівник: сторінки 642-647

ВСТУП.....13
Розділ 1. ПРОБЛЕМАТИКА ТА ПРАКТИЧНЕ ЗАСТОСУВАННЯ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ (ДО).....19
1.1. Предмет та задачі ДО.....20
1.2. Основні поняття ДО та етапи операційного дослідження.....22
1.3. Пряма та обернена задачі ДО. Детерміновані задачі ДО.....24
1.4. Проблема вибору розв’язків в умовах невизначеності.....25
1.5. Основні типи задач дослідження операцій за змістовним формулюванням.....28
1.6. Багатокритерійні задачі ДО та основні підходи до їх розв’язування.....30
1.6.1. Побудова множини Парето-оптимальних розв’язків.....33
1.6.2. Методи згортання критеріїв.....35
1.6.3. Метод переведення критеріїв в обмеження.....37
1.6.4. Метод контрольних показників.....38
1.6.5. Метод послідовних поступок.....39
1.6.6. Діалогові методи.....40
1.7. Контрольні запитання для самоперевірки.....41
1.8. Тестові завдання.....41
1.9. Задачі для самостійного виконання.....45
Розділ 2. ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ (ЛП) ЯК СКЛАДОВА ЧАСТИНА ЗАДАЧ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ ТА СИМПЛЕКС-МЕТОД ЇЇ РОЗВ’ЯЗУВАННЯ.....47
2.1. Терміни та означення.....49
2.2. Типи задач МП.....49
2.3. Формулювання задачі лінійного програмування.....53
2.4. Перетворення задачі ЛП із загальної форми в канонічну.....59
2.5. Побудова моделей задач ЛП.....60
2.6. Геометричне подання задач ЛП.....62
2.7. Розв’язування задачі ЛП симплекс-методом (CM).....67
2.7.1. Дві основні теореми.....68
2.7.2. Алгоритм симплекс-методу.....71
2.7.3. Правила трикутника та прямокутника.....76
2.7.4. Приклад розв'язування задачі ЛП за допомогою CM.....77
2.8. Методи визначення початкового базисного розв’язку (методи штучного базису).....80
2.8.1. Метод великих штрафів.....81
2.8.2. Двохетапний метод.....83
2.8.3. Приклад розв'язування задачі ЛП у випадку визначення ПБР методом великих штрафів.....83
2.8.4. Приклад розв’язування задачі ЛП у випадку визначення ПБР двохетапним методом.....86
2.9. Особливі випадки CM та їх відображення у симплекс-таблицях.....88
2.10. Модифікований CM (МСМ).....89
2.10.1. Алгоритм МСМ.....89
2.10.2. Особливості основної та допоміжної таблиць МСМ.....90
2.10.3. Приклад розв’язування задачі ЛП за допомогою МСМ.....92
2.11. Задачі дробово-лінійного програмування (ДЛП).....94
2.12. Контрольні запитання для самоперевірки.....97
2.13. Тестові завдання.....99
2.14. Задачі для самостійного виконання.....102
Розділ 3. ДВОЇСТІСТЬ (ДУАЛЬНІСТЬ)У ЛП. ДВОЇСТИЙ СИМПЛЕКС-МЕТОД.....104
3.1. Формулювання і побудова математичної моделі двоїстої задачі ЛП.....105
3.2. Зв’язок між розв’язками прямої і двоїстої задач ЛП.....108
3.3. Двоїстий симплекс-метод (ДСМ).....113
3.3.1. Алгоритм двоїстого симплекс-методу.....114
3.3.2. Приклад розв’язування задачі ЛП за допомогою ДСМ.....115
3.4. Контрольні запитання для самоперевірки.....117
3.5. Тестові завдання.....118
3.6. Задачі для самостійного виконання.....121
Розділ 4. ЦІЛОЧИСЛОВІ ТА ЗМІШАНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ.....123
4.1. Формулювання задачі цілочислового лінійного програмування (ЦЛП). Її інтерпретація та основні підходи до розв’язування.....124
4.2. Задача про наплічник.....127
4.3. Задача про ефективну експедицію.....128
4.4. Основні підходи до розв’язування цілочислових задач.....129
4.5. Графічний метод розв’язування задачі ЦЛП. Геометрична інтерпретація розв’язків цілочислових задач ЛП на площині.....130
4.6. Розв’язування лінійних задач цілочислового та змішаного програмування методом Гоморі.....132
4.6.1. Схема алгоритму методу Гоморі.....134
4.6.2. Алгоритм визначення розв’язку методом Гоморі для повністю цілочислових задач (перший алгоритм Гоморі).....135
4.6.3. Атгоритм визначення розв’язку методом Гоморі для частково цілочислових (змішаних) задач (другий алгоритм Гоморі).....136
4.6.4. Приклад розв’язування задачі цілочислового програмування за допомогою методу Гоморі.....137
4.7. Розв’язування лінійних задач змішаного програмування методом гілок і меж.....140
4.7.1. Основні елементи методу гілок і меж.....141
4.7.2. Приклад розв’язування задачі ЦЛП за допомогою методу гілок і меж.....147
4.8. Практичні реалізації методу гілок і меж для задач булевого програмування.....151
4.8.1. Розв’язування багатовимірної задачі про наплічник.....151
4.8.2. Формулювання задачі булевого програмування. Адитивний алгоритм Балаша.....157
4.8.3. Методи зведення цілочислових задач до булевих.....168
4.8.4. Задача комівояжера.....169
4.9. Контрольні запитання для самоперевірки.....188
4.10. Тестові завдання.....189
4.11. Задачі для самостійного виконання.....191
Розділ 5. ТРАНСПОРТНА ЗАДАЧА (ТЗ) ЛП.....193
5.1. Змістове та математичне формулювання транспортної задачі ЛП.....194
5.2. Методи визначення початкового опорного плану ТЗ.....198
5.2.1. Метод північно-західного кута.....198
5.2.2. Метод мінімального елемента (метод мінімальної вартості).....201
5.2.3. Метод подвійної переваги.....203
5.2.4. Евристичний метод Фогеля.....204
5.3. Метод потенціалів.....205
5.3.1. Алгоритм методу потенціалів.....207
5.3.2. Приклад розв’язування задачі за допомогою методу потенціалів.....208
5.4. Інтерпретація методу потенціалів як симплекс-методу.....210
5.5. Розв’язування задач методом потенціалів у випадку виродженого опорного плану.....211
5.6. Розв’язування транспортних задач з ускладненнями у формулюванні.....212
5.7. Метод диференціальних рент.....213
5.7.1. Алгоритм методу диференціальних рент.....214
5.7.2. Приклад розв’язування задачі за допомогою методу диференціальних рент.....215
5.8. Задача про призначення. Угорський метод її розв’язування.....219
5.8.1. Змістове та математичне формулювання задачі про призначення.....219
5.8.2. Алгоритм угорського методу.....220
5.8.3. Приклади розв'язування задач про призначення за допомогою угорського методу.....222
5.9. Контрольні запитання для самоперевірки.....227
5.10. Тестові завдання.....228
5.11. Задачі для самостійного розв’язування.....232
Розділ 6. ЗАДАЧІ ОПТИМІЗАЦІЇ В МЕРЕЖАХ.....235
6.1. Фізичне обґрунтування задач потокового типу. Основні поняття.....236
6.2. Означення потоку, розрізу та пропускної здатності розрізу. Теорема Форда-Фалкерсона.....238
6.3. Загальне формулювання та часткові випадки потокових задач.....242
6.4. Задача пошуку найкоротшого шляху в мережі.....244
6.4.1. Алгоритм Дейкстри.....245
6.4.2. Приклад визначення найкоротшого шляху за допомогою алгоритму Дейкстри.....246
6.5. Задача про багатополюсний найкоротший шлях. Алгоритм Флойда.....255
6.5.1. Алгоритм Флойда (версія, вдосконалена Ху).....256
6.5.2. Приклад знаходження найкоротнгих шляхів між всіма парами вузлів мережі за допомогою алгоритму Флойда.....258
6.6. Задача мінімізації мережі.....261
6.6.1. Алгоритм мінімізації мережі (жадібний алгоритм).....261
6.6.2. Приклад побудови остовного дерева за допомогою алгоритму мінімізації мережі.....262
6.7. Задача пошуку максимального потоку між парою вузлів.....263
6.7.1. Алгоритм розташування позначок.....263
6.7.2. Приклад знаходження максимального потоку та мінімального розрізу у мережі.....265
6.8. Узагальнення задачі про максимальний потік (МкП).....269
6.8.1. Задача про МкП з декількома джерелами і витоками.....269
6.8.2. Потік з обмеженнями зверху на пропускні здатності вузлів.....270
6.8.3. Задача про МкП для неорієнтованих st-мереж.....271
6.8.4. Задача про допустимі потоки.....272
6.9. Зведення узагальненої транспортної задачі до задачі про потік мінімальної вартості.....274
6.10. Задача про МкП з обмеженнями знизу та зверху на пропускні здатності дуг.....277
6.11. Задачі про багатополюсний МкП (визначення потоків між усіма парами вузлів мережі).....279
6.11.1. Алгоритм Гоморі-Ху.....280
6.11.2. Приклад знаходження багатополюсного максимального потоку та дерева розрізів.....280
6.12. Контрольні запитання для самоперевірки.....286
6.13. Тестові завдання.....286
6.14. Задачі для самостійного виконання.....291
Розділ 7. ІГРОВІ ЗАДАЧІ ДО.....293
7.1. Основні поняття теорії ігор.....294
7.2. Матричні ігри двох осіб з нульовою сумою. Матриця гри. Верхня та нижня ціни гри. Теорема про мінімакс (сідлову точку).....301
7.3. Змішані стратегії в іграх двох осіб з нульовою сумою.....304
7.4. Зображення гри у вигляді задач ЛП.....307
7.5. Ігри порядку 2 х 2, 2 х n та m х 2. Графічне розв’язування ігор.....312
7.6. Поняття про позиційні ігри.....318
7.7. Біматричні ігри та методи їх дослідження.....322
7.8. Некооперативна (безкоаліційна) біматрична гра двох осіб.....325
7.9. Кооперативна біматрична гра двох осіб. Переговорна множина.....329
7.10. Прийняття рішень в умовах невизначеності.....338
7.11. Контрольні запитання для самоперевірки.....343
7.12. Тестові завдання.....344
7.13. Задачі для самостійного розв’язування.....348
Розділ 8. ЗАДАЧА НЕЛІНІЙНОГО ПРОГРАМУВАННЯ (ЗНП).....350
8.1. Умови, які приводять до задач нелінійного програмування 351
8.2. Основні труднощі, які виникають під час розв’язування ЗНП 352
8.3. Формулювання ЗНП. Розв’язування ЗНП для випадку відсутності обмежень на знаки змінних та наявності обмежень-рівнянь. Метод множників Лагранжа.....355
8.4. Обмеження у вигляді нерівностей. Умови Куна-Таксра.....361
8.5. Необхідні умови існування сідлової точки.....363
8.6. Геометричний метод розв’язування ЗНП.....366
8.7. Методи прямого пошуку.....368
8.7.1. Методи прямого пошуку для функції однієї змінної. Методи апроксимації.....368
8.7.2. Методи прямого пошуку для функцій n змінних.....369
8.8. Методи, що використовують інформацію про напрямок пошуку.....370
8.9. Оптимізація з обмеженнями.....374
8.10. Контрольні запитання дія самоперевірки.....375
8.11. Тестові завдання.....376
8.12. Задачі для самостійного виконання.....378
Розділ 9. ЗАДАЧА ОПУКЛОГО ПРОГРАМУВАННЯ.....380
9.1. Опуклі комбінації та опуклі множини. Конус допустимих напрямків.....381
9.2. Формулювання задач опуклого та квадратичного програмування. Метод множників Лагранжа.....384
9.3. Градієнтні методи.....389
9.4. Знаходження розв’язку ЗНП, яка містить сепарабельні функції. Метод кусково-лінійної апроксимації.....396
9.5. Метод допустимих напрямків (метод Зойтендейка).....401
9.6. Контрольні запитання для самоперевірки.....408
9.7. Тестові завдання.....409
9.8. Задачі для самостійного виконання.....411
Розділ 10. ДИНАМІЧНЕ ПРОГРАМУВАННЯ.....413
10.1. Поняття про ДП. Багатокроковий процес ухвалення рішень. Ідея методу ДП.....414
10.2. Формулювання задачі ДП. Вимоги до задачі ДП.....417
10.3. Принцип оптимальності Беллмана. Рекурентні співвідношення.....420
10.4. Алгоритм розв’язування задач ДП.....421
10.5. Класи задач ДП.....424
10.5.1. Розв’язування задачі комівояжера методом ДП.....424
10.5.2. Задача про розподіл інвестицій між підприємствами.....427
10.6. Контрольні запитання для самоперевірки.....432
10.7. Тестові завдання.....432
10.8. Задачі для самостійного виконання.....434
Розділ 11. ЗАДАЧА СТОХАСТИЧНОГО ПРОГРАМУВАННЯ.....435
11.1. Види задач СП.....437
11.2. Математичне формулювання задачі СП.....438
11.3. Методи розв’язування стохастичних задач.....444
11.4. Контрольні запитання для самоперевірки.....447
11.5. Тестові завдання.....447
11.6. Задачі для самостійного виконання.....449
Розділ 12. ЛАБОРАТОРНИЙ ПРАКТИКУМ.....450
12.1. Лабораторна робота № 1.....451
12.2. Лабораторна робота № 2.....474
12.3. Лабораторна робота № 3.....475
12.4. Лабораторна робота № 4.....479
12.5. Лабораторна робота № 5.....491
12.6. Лабораторна робота № 6.....492
12.7. Лабораторна робота № 7.....503
12.8. Лабораторна робота № 8.....514
Розділ 13. РОЗВ’ЯЗУВАННЯ ЗАДАЧ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ З РОЗДІЛІВ 1 ТА 2.....518
13.1. Розв’язування задач з розділу 1.....518
13.2. Розв’язування задач з розділу 2......520
Розділ 14. РОЗВ’ЯЗУВАННЯ ЗАДАЧ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ З РОЗДІЛІВ З ТА 4.....531
14.1. Розв’язування задач з розділу 3.....531
14.2. Розв’язування задач з розділу 4.....542
Розділ 15. РОЗВ’ЯЗУВАННЯ ЗАДАЧ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ З РОЗДІЛУ 5.....559
Розділ 16. РОЗВ’ЯЗУВАННЯ ЗАДАЧ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ З РОЗДІЛІВ 6 17.....584
16.1. Розв’язування задач з розділу 6.....584
16.2. Розв’язування задач з розділу 7.....598
Розділ 17. РОЗВ’ЯЗУВАННЯ ЗАДАЧ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ З РОЗДІЛІВ 8-11.....605
17.1. Розв’язування задач з розділу 8.....605
17.2. Розв’язування задач з розділу 9.....611
17.3. Розв’язування задач з розділу 10.....620
17.4. Розв’язування задач з розділу 11.....623
ГЛОСАРІЙ.....625
СПИСОК ЛІТЕРАТУРИ.....638
ВІДПОВІДІ ДО ТЕСТОВИХ ЗАВДАНЬ.....641
ПРЕДМЕТНИЙ ВКАЗІВНИК.....642

Подано теоретичний га практичний матеріал для вивчення дисципліни “Дослідження операцій”: математичну основу для розв’язання задач оптимального управління, які можуть бути зведені до задач лінійного та нелінійного програмування, що охоплюють цілочислове та змішане, динамічне, дискретне та стохастичне програмування, а також до задач оптимізації у мережах та теорії ігор. Кожний розділ теоретичної складової підручника містить термінологію, теореми та конкретні методи й алгоритми розв’язування задач, запитання для самоперевірки та низку тестів. В окремих розділах наведено по 30 варіантів до 8-ми лабораторних робіт та розв’язування задач для самостійного виконання.
Підручник призначений для студентів спеціальності “Інженерія програмного забезпечення”, може бути корисним для фахівців-початківців, що працюють у галузі конструювання й аналізу алгоритмів, аспірантів і науковців, а також розробників програмного забезпечення.