- •7.080401 «Інформаційні управляючі системи та технології»
- •Математичні методи дослідження операцій у будівництві: б12 Навчальний посібник. – к: кнуба, 2006. – 107 с.
- •2.5. Алгоритм розрахунку псевдоплану для двоїстого
- •4.2. Класифікація методів розв’язання задач цілочислового
- •5.5. Задача прогнозування термінів ремонту будівельних
- •6.4. Задача про найкоротший шлях для орієнтованих та
- •6.5. Задача про найкоротший шлях для багатополюсних мереж.
- •6.7. Задача про максимальний потік для однополюсних мереж.
- •7.5. Сепарабельне програмування.
- •8.2. Загальний алгоритм складання розкладу занять
- •1. Загальні визначення, класифікація моделей і методів
- •1.1. Загальні визначення дослідження операцій
- •1.2. Приклади постановок задач лінійного програмування та їх геометрична інтерпретація Задача про рекламу
- •Задача про бетонно-розчинний вузол (брв)
- •1.3. Основні етапи та класифікація моделей та методів дослідження операцій
- •Контрольні запитання
- •2. Лінійне програмування
- •Розглянемо приклад розв’язання задачі лінійного програмування:
- •2.1. Графічний метод розв’язання задач лінійного програмування
- •2.2. Алгоритм зведення до канонічного вигляду задач лінійного програмування
- •2.3. Метод симплекс-таблиць
- •2.4. Двоїста задача лінійного програмування
- •Отримавши результат – вектор y, можна на базі описаної системи знайти вектор X. Для розв’язання прямої задачі потрібно:
- •2.5. Алгоритм розрахунку псевдоплану для двоїстого симплекс-методу
- •3*10 – Розмірність задачі см.
- •2.6. Двоїстий симплекс-метод
- •Контрольні запитання
- •3. Задачі спеціального лінійного програмування
- •Задача призначення (про розподілення обладнання). Між чотирма кар’єрами потрібно розподілити п’ять екскаваторів таким чином, щоб їх виробітка була максимальною.
- •3.2. Задача про призначення
- •Алгоритм угорського методу задачі призначення має такі етапи.
- •3.3. Методи пошуку опорного рішення транспортної задачі
- •Метод Північно–Західного Кута (мпзк) має такі етапи:
- •Метод мінімального елемента (мме) має такі етапи:
- •3.4. Метод потенціалів транспортної задачі
- •Примітка. Цільова функція має постійно покращуватися (крім випадку, коли спрямовуючий елемент рівний ). Контроль правильності розрахунку має завжди дорівнювати:
- •Розглянемо алгоритм розв’язання задач методом потенціалів.
- •3.5. Угорський метод транспортної задачі
- •3.6. Різновиди транспортної задачі та їх використання
- •Контрольні запитання
- •4. Задачі цілочислового лінійного програмування
- •4.1. Загальне визначення цілочислового лінійного програмування
- •4.2. Класифікація методів розв’язання задач цілочислового лінійного програмування
- •Розв’язавши графічно, одержимо:
- •4.3. Метод відтинаючих площин
- •У комп’ютерній програмі стратегія реалізується таким чином.
- •Контрольні запитання
- •5. Динамічне програмування
- •5.1. Загальні визначення та алгоритм динамічного програмування
- •До особливостей розв’язку задач дп можна віднести.
- •5.2. Задача про інвестиції
- •5.3. Задача розрахунку траєкторії літака
- •5.4. Задача про рюкзак (завантаження транспортного засобу)
- •5.5. Задача прогнозування термінів ремонту будівельних конструкцій
- •Контрольні запитання
- •6. Методи аналізу мереж та потокове програмування
- •6.1. Загальні визначення потокового програмування
- •6.2. Способи представлення мереж
- •6.3. Типові задачі оптимізації на мережах
- •1. Задача визначення найкоротшого шляху в мережі:
- •6.4. Задача про найкоротший шлях для орієнтованих та біорієнтованих мереж. Алгоритми Дейкстра 1 та 2
- •6.5. Задача про найкоротший шлях для багатополюсних мереж. Алгоритм Флойда
- •6.6. Задача про мінімальний остов
- •6.7. Задача про максимальний потік для однополюсних мереж. Алгоритм Дейкстра 4
- •6.8. Задача про максимальний потік для багатополюсних мереж. Мінімальний розріз. Алгоритм Гоморі-Ху
- •Контрольні запитання
- •7. Розв’язання задач нелінійного програмування
- •7.1. Загальні визначення нелінійного програмування
- •7.2. Правило множників Лагранжа
- •7.3. Узагальнене правило Лагранжа
- •7.4. Умова Куна-Такера
- •7.5. Сепарабельне програмування. Метод кусочно-лінійної апроксимації
- •7.6. Загальна класифікація задач нелінійного програмування
- •8. Розв’язання багатокритеріальних задач
- •8.1. Основні визначення та моделі багатокритеріальних задач
- •8.2. Загальний алгоритм складання розкладу занять з використанням методів дослідження операцій
- •8.3. Класифікація методів технічного пошуку рішень
- •8.4. Моделювання гнучкості для забезпечення властивості бути керованим
- •Список літератури
4.2. Класифікація методів розв’язання задач цілочислового
лінійного програмування ..............................................................47
4.3. Метод відтинаючих площин .......................................................49
4.4. Метод розгалужень та обмежень ................................................52
Контрольні запитання .......................................................................57
5. ДИНАМІЧНЕ ПРОГРАМУВАННЯ. ..............................................58
5.1. Загальні визначення та алгоритм динамічного програмування …………………………………………………...58
5.2. Задача про інвестиції .....................................................................60
5.3. Задача розрахунку траекторії літака ........................................61
5.4. Задача про рюкзак (завантаження транспортного засобу) ....63
5.5. Задача прогнозування термінів ремонту будівельних
конструкцій ......................................................................................65
Контрольні запитання .......................................................................66
6. МЕТОДИ АНАЛІЗУ МЕРЕЖ ТА ПОТОКОВЕ ПРОГРАМУВАННЯ. .........................................................................66
6.1. Загальні визначення потокового програмування ...................66
6.2. Способи представлення мереж ....................................................68
6.3. Типові задачі оптимізації на мережах ........................................69
6.4. Задача про найкоротший шлях для орієнтованих та
біорієнтованих мереж. Алгоритми Дейкстра 1 та 2 .................71
6.5. Задача про найкоротший шлях для багатополюсних мереж.
Алгоритм Флойда ...........................................................................74
6.6. Задача про мінімальний остов .....................................................78
6.7. Задача про максимальний потік для однополюсних мереж.
Алгоритм Дейкстра 4 .....................................................................79
6.8. Задача про максимальний потік для багатополюсних мереж.
Мінімальний розріз. Алгоритм Гоморі-Ху ................................81
Контрольні запитання ......................................................................84
7. РОЗВ’ЯЗАННЯ ЗАДАЧ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ. .........................................................................86
7.1. Загальні визначення нелінійного програмування ………….86
7.2. Правило множників Лагранжа ………………………………..88
7.3. Узагальнене правило Лагранжа ................................................89
7.4. Умова Куна-Такера ......................................................................90
7.5. Сепарабельне програмування.
Метод кусочно-лінійної апроксимації ........................................91
7.6. Загальна класифікація задач нелінійного програмування ...............................................................................94
Контрольні запитання ......................................................................95
8. РОЗВ’ЯЗАННЯ БАГАТОКРИТЕРІАЛЬНИХ ЗАДАЧ. ...............95
8.1. Основні визначення та моделі багатокритеріальних задач ..................................................................................................95