Методологічні основи дослідження операцій

ЗМІСТ

ЗМІСТ. 3

ВСТУП.. 6

1 МЕТОДОЛОГІЧНІ ОСНОВИ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ.. 7

1.1 Етапи дослідження операцій. 7

1.2 Математичне моделювання. Загальна структура. 8

1.3 Етапи математичного моделювання. Приклади. 11

1.4 Розділи і класи задач дослідження операцій. 17

1.5 Основні вимоги до математичних моделей і їх властивості 19

1.6 Формалізація принципів оптимальної поведінки в моделях

прийняття рішень. 22

2 ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ.. 25

2.1 Попередні відомості теорії лінійного програмування. 25

2.2 Графічна інтерпретація розв’язання задач ЛП.. 32

2.3 Змістовний опис симплекс-методу розв’язання задач ЛП.. 36

2.4 Знаходження початкового опорного плану. 37

2.5 Знаходження оптимального плану. 41

2.6 Застосування симплекс-таблиць. 46

2.7 Метод штучної бази. 54

2.8 Двоїсті (спряжені) задачі лінійного програмування. 55

3 ТРАНСПОРТНІ ЗАДАЧІ (Т-ЗАДАЧІ) 60

3.1 Математична структура Т-задач. 60

3.2 Визначення початкового опорного плану Т-задачі 62

3.3 Властивості опорних планів Т-задач. 64

3.4 Розв’язання Т-задач методом потенціалів. 65

3.5 Т-задачі з обмеженими пропускними здатностями. 69

3.6 Задача про оптимальні призначення. 73

3.7 Задача про максимальний потік. Метод Форда-Фалкерсона. 75

3.8 Задача про найкоротший шлях на мережi. Метод Мiнтi 77

4 ДИСКРЕТНЕ ПРОГРАМУВАННЯ.. 79

4.1 Задача дискретного ЛП. Метод Гоморi-1. 79

4.2 Задача частково дискретного ЛП. Метод Гоморi-2. 82

4.3 Задача дискретного ЛП. Метод Гоморi-3. 84

4.4 Задача частково дискретного ЛП. Метод Дальтона-Ллевелiна. 86

4.5 Задача дискретного ЛП. Метод гілок i границь. 87

5 НЕЛІНІЙНЕ ПРОГРАМУВАННЯ.

БЕЗУМОВНА ОДНОПАРАМЕТРИЧНА ОПТИМІЗАЦІЯ.. 91

5.1 Загальні відомості 91

5.2 Методи виключення інтервалів. 92

5.3 Поліноміальна апроксимація. 98

6 НЕЛІНІЙНЕ ПРОГРАМУВАННЯ.

МЕТОДИ УМОВНОЇ ОПТИМІЗАЦІЇ 105

6.1 Класична задача математичного програмування. 105

6.2 Задача опуклого квадратичного програмування. 107

6.3 Метод Франка - Вульфа розв’язання задач квадратичного

програмування (ЗКП) 111

7 ОСНОВИ ТЕОРІЇ ПРИЙНЯТТЯ РІШЕНЬ. 116

7.1. Теорія корисності і прийняття рішень. 116

7.1.1 Прийняття рішень в умовах ризику. 116

7.1.2 Критерій «очікуване значення – дисперсія». 118

7.1.3 Критерій граничного рівня. 119

7.2 Прийняття рішень в умовах невизначеності 120

7.2.1 Класичні критерії прийняття рішень. 121

7.2.2 Похідні критерії 124

8 ПРИЙНЯТТЯ РІШЕНЬ В ІГРОВИХ СИТУАЦІЯХ.. 129

8.1 Класифікація ігор. 129

8.2 Розв’язання матричних ігор у чистих стратегіях. 130

8.3 Змішане розширення матричної гри. 135

8.4 Властивості розв’язання матричних ігор. 137

8.5 Алгебраїчний метод розв’язання матричних ігор. 140

8.6 Графічний метод розв’язання ігор 2 ´ n і m ´ 2. 144

8.7 Матричний метод розв’язання ігор. 146

8.8. Ітеративні методи розв’язання ігор. 148

8.9 Метод послідовного наближення до ціни гри. 151

9 ВПРАВИ ДЛЯ САМОСТІЙНОЇ РОБОТИ ТА ДЛЯ

ПРАКТИЧНИХ І ЛАБОРАТОРНИХ ЗАНЯТЬ. 153

9.1 Побудова математичних моделей задач. 153

9.2 Розв’язання задач лінійного програмування. 154

9.3 Розв’язання транспортних задач. 156

9.5 Розв’язання задач нелінійного програмування. 163

9.6 Розв’язання матричних ігор. 164

9.7 Лабораторний практикум. 165

10 КОНТРОЛЬНА РОБОТА ДЛЯ СТУДЕНТІВ ЗАОЧНОЇ

ФОРМИ НАВЧАННЯ.. 166

10.1 Правила вибору задач контрольної роботи. 166

10.2 Варіанти завдань контрольної роботи. 167

ЛІТЕРАТУРА.. 181

ВСТУП

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

Математична модель – це спрощена схема реального об’єкта (системи, процесу), складена за допомогою математичних символів і співвідношень. Процес побудови математичної моделі називається формалізацією.

У науці немає універсальних методів загальної теорії або побудови математичних моделей – надто велика розмаїтість практичних задач і рівень їх складності. Тому процес формалізації – це один з найскладніших етапів прикладного математичного дослідження.

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

Таким чином, дослідження операцій – це значна галузь математики, куди входять споріднені за напрямком розділи (моделі і методи). Одним і найбільшим з них є розділ, що присвячений методам оптимізації. Як предмет «Методи оптимізації» виникли раніше «Дослідження операцій» і займаються так званими екстремальними задачами. Це найпростіші задачі прийняття рішення, суть яких полягає у пошуку екстремальних значень заданої функції (цільова функція) на заданій множині значень її аргументів (множина допустимих рішень).

Математичне програмування займається тими екстремальними задачами, де множина допустимих рішень задається (описується) за допомогою деяких рівнянь або нерівностей. Отже, математичне програмування є розділом методів оптимізації, Залежно від характеру цих рівнянь або нерівностей (обмеження задачі) виникають задачі лінійного, нелінійного, динамічного програмування та їх різновиди. Тут термін «програмування» має значення планування, оптимізації, порівняння варіантів і т.п. Тому його не треба плутати з терміном програмування мовами ЕОМ.

Перед дослідженнями операцій (і його розділами) стоять такі основні задачі:

- складання математичних моделей задач прийняття рішення;

- питання існування "оптимальних" рішень у різних класах задач;

- розроблення необхідних і достатніх ознак оптимальності;

- розроблення методів чисельного обчислення "оптимальних" рішень.

МЕТОДОЛОГІЧНІ ОСНОВИ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ