- •1. Загальні принципи побудови систем
- •1.1 Поняття системи, її властивості та їх співвідношення. Прості та ієрархічні системи
- •1.3. Класифікації систем
- •Відкриті і закриті системи.
- •Цілеспрямовані системи.
- •Класифікації систем по складності.
- •1.4 Визначення й основні принципи системного підходу
- •1. Принцип пріоритету глобальної мети і послідовного просування
- •2. Принцип модульності систем
- •3. Принцип узгодження зв'язків
- •4. Усталеність систем
- •5. Принцип відсутності конфліктів між цілями окремих елементів чи підсистем і цілями всієї системи
- •1.5 Порівняльна характеристика класичного та системного підходів до формування системи
- •1.6 Основні задачі створення і дослідження систем
- •1.7. Основні етапи розробки систем
- •2. Термінологія і класифікація моделей об'єктів та систем
- •2.1 Закон і модель, їх співвідношення. Види моделей.
- •2.2 Побудова і аналіз статистичних моделей
- •2.2.1. Проведення експерименту відсіювання (вибір значущих факторів)
- •2.2.2. Вибір форми функціональної залежності
- •2.2.3. Визначення коефіцієнтів (параметрів) моделі
- •2.2.3.1 Метод найменших квадратів (мнк)
- •3. Регресійні моделі з однією змінною
- •3.1. Оцінка надійності коефіцієнтів моделі лінійної регресії
- •3.2 Приклад побудови моделі лінійної регресії
- •4. Моделі множинної лінійної регресії
- •4.1 Матрична форма моделі множинної регресії
- •4.2 Приклад побудови рівняння множинної регресії
- •4.3 Аналіз моделі множинної регресії
- •4.4 Визначення довірчих інтервалів коефіцієнтів множинної регресії
- •5. Композиція і декомпозиція складних об'єктів і систем
- •5.1 Еквівалентні перетворення моделей систем
- •1.Модель без додаткових зв’язків
- •2. Послідовне підключення моделей підсистем
- •7. Синтез оптимальних систем на основі динамічного
- •7.1 Визначення методу дп
- •7.2 Знаходження най коротшої відстані між двома вузлами на мережі доріг
- •7.3 Задачі розподілу ресурсів
- •Рішення
- •Рішення
- •9. Аналіз і синтез систем на основі імітаційного моделювання
- •9.1 Загальні питання імітаційного моделювання
- •9.2. Метод Монте-Карло
- •9.3 Види випадкових потоків
- •9.5 Імітаційне моделювання транспортних систем масового обслуговування
- •9.6 Алгоритм імітаційного моделювання смо
- •Підпрограма "Моделювання вхідного потоку"
- •Підпрограма "Моделювання вихідного потоку"
- •Підпрограма "Сортування каналів"
- •Підпрограма " Побудова діаграми №2 розподілу часових інтервалів вихідного потоку"
- •9.7. Приклад застосування програми імітаційного моделювання
- •10. Управління в організаційних системах. Принцип зворотного зв'язку
- •10.1 Основні принципи управління
- •10.1.1. Принцип управління по збуренню
- •10.1.2. Принцип управління по відхиленню (принцип зворотного зв'язку)
- •10.1.3. Принцип комбінованого управління
- •10.2 Приклад аналізу систем управління об'єктами економічного характеру
7. Синтез оптимальних систем на основі динамічного
Програмування (ДП)
7.1 Визначення методу дп
Динамічне програмування являє собою математичний метод оптимізації систем, функціонування яких представляє певну низку багатокрокових операцій (навпаки, ЛІТ призначено для пошуку оптимуму саме однокрокових операцій).
Уявимо собі, що досліджувані операції являють собою процес, що розвивається в часі і який розділяється на ряд «кроків». Наприклад, економічна діяльність підприємства (Q) протягом ряду років планується й оптимізується на кожний рік, що є природним кроком розвитку підприємства. Природно, що керування діяльністю підприємства буде складатися з елементарних «крокових» управлінь, сукупність яких називається стратегією управління.
Нехай на початку періоду, що розглядається, на розвиток системи підприємств, які виконують певні функції виробництва одного виду продукції, виділені деякі кошти К0. Ці кошти повинні бути розподілені між підприємствами. У процесі функціонування ці кошти частково витратяться (тобто амортизуються). Крім того, кожне підприємство приносить доход, що залежить від вкладених коштів. На початку кожного наступного року наявні кошти, що залишилися, можуть знову якось розподіляться між підприємствами.
Постає питання: як потрібно розподіляти кошти між підприємствами на протязі кожного року, щоб сумарний доход від усіх систем підприємств на період Т, був максимальним. Саме це є типовою задачею ДП. Перерозподіл коштів на початок кожного року і представляє поточний крок управління.
Нехай на початку і-го року підприємствам П1, П2, … Пк виділені відповідні кошти:
(k - му підприємству в i - й рік).
Сукупність цих значень являє собою не що інше, як крокове Управління на i-му кроці:
Керування ж системою підприємств за період Т, що містить m кроків фоків) являє собою сукупність
і являє собою стратегію управління.
Ефективність цієї стратегії на і-му кроці визначається показник ефективності (наприклад, отриманим доходом):
Тоді за весь період Т ( за т - кроків) показник ефективності визначається як
Згідно з типовою задачею ДП необхідно вибрати стратегію управління усіма к підприємствами на і - му кроці:
що забезпечує z = zmax.
Поставлену задачу можна вирішити по різному:
відразу знайти оптимальне рішення и (для оптимальної стратегії приймемо її позначку маленькою буквою и);
на кожнім і--му кроці будемо оптимізувати тільки відповідно управління (ui), у результаті такого розгляду т кроків знайдена оптимальна стратегія.
при якій
Здавалося б рішення тривіальне: необхідно оптимізувати крок управління ui щороку (це просто, із застосуванням ЛП) і в результат оптимізації всіх кроків одержимо оптимальну стратегію управління и.
Але принцип ДП аж ніяк не припускає, що кожен крок оптимізується окремо, незалежно від інших. Навпаки, крокове управління повинно вибиратися з урахуванням усіх його наслідків у майбутньому. Цей принцип сформульований американським вченим Робертом Беллманом говорить, що незалежно від того, який стан системи і яке прийнято рішення в початковий момент, наступні рішення і отже поводження системи має бути оптимальним з урахуванням саме майбутніх наслідків.
Однак з цього загального правила є одне єдине виключення: останній крок, який може просто плануватися як оптимальний у рамках ЛП (без урахування наслідків), і який має приносити безумовно максимальну вигоду.
Таким чином, спланувавши цей останній крок, можна до нього пристроювати передостанній, потім передпередостанній і т.д. до початкового кроку.
Саме тому процес ДП розвертається, як правило, від кінця до початку. Але як же це спланувати, не знаючи передостаннього? Очевидно, потрібно зробити певні припущення щодо результатів передостаннього (т-1)-го кроку і для нього знайти таке управління, що забезпечить максимальний виграш на останньому m-му кроці.
Нехай це процедура виконання для кожного з можливих станів системи на (т-1) кроці і для кожного з них ми знаємо оптимальне керування на т-му кроці. Тепер ми можемо оптимізувати керування на (т-1) кроці, зробивши всі можливі припущення щодо стану системи на (т-2)-у кроці. Для кожного з цих припущень знаходимо оптимальний вектор управління um-1.
Іншими словами, на кожнім i-у кроці шукається управління иІ9 яке забезпечує оптимальне продовження процесу на (i+1) - кроці відносно досягнутого стану на i-му кроці.
Управління, що забезпечує оптимальне продовження процесу називається умовним оптимальним управлінням на даному кроці (УОУ).
Тепер припустимо, що УОУ на кожному кроці нам відомо: ми знаємо як йти далі, у якому би стані не був процес до початку кожного кроку. Тоді, якщо початковий стан S0 нам відомий, то ми знаємо, як знайти вже не умовне, а дійсно оптимальне управління на 1-му кроці. Потім, спираючись на нього, можна знайти оптимальне управління на другому кроці і т.д. У результаті ми прийдемо до кінцевого стану Sm і знайдемо оптимальний вектор управління u, що забезпечить оптимальне протікання процесу протягом усіх т кроків управління.
Таким чином, при оптимізації систем методом ДП багатокроковий процес проходить двічі:
- від кінцевого кроку до початкового, при цьому знаходяться оптимальні умовні управління;
- від початкового кроку до кінцевого, при цьому знаходяться серед множини умовних оптимальних управлінь уже реальні оптимальні управління на кожному кроці з урахуванням результатів попереднього кроку (як початкові умови наступного).
Розглянемо декілька прикладів застосування методу ДП.