Визначення методу ДП

Синтез оптимальних систем на основі динамічного

Програмування (ДП)

Динамічне програмування являє собою математичний метод оптимізації систем, функціонування яких представляє певну низку багатокрокових операцій (навпаки, ЛІТ призначено для пошуку оптимуму саме однокрокових операцій).

Уявимо собі, що досліджувані операції являють собою процес, що розвивається в часі і який розділяється на ряд «кроків». Наприклад, економічна діяльність підприємства (Q) протягом ряду років планується й оптимізується на кожний рік, що є природним кроком розвитку підприємства. Природно, що керування діяльністю підприємства буде складатися з елементарних «крокових» управлінь, сукупність яких називається стратегією управління.

Нехай на початку періоду, що розглядається, на розвиток системи підприємств, які виконують певні функції виробництва одного виду продукції, виділені деякі кошти К₀. Ці кошти повинні бути розподілені між підприємствами. У процесі функціонування ці кошти частково витратяться (тобто амортизуються). Крім того, кожне підприємство приносить доход, що залежить від вкладених коштів. На початку кожного наступного року наявні кошти, що залишилися, можуть знову якось розподіляться між підприємствами.

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

Нехай на початку і- го року підприємствам П₁, П_2, … П_к виділені відповідні кошти:

(k - му підприємству в i - й рік).

Сукупність цих значень являє собою не що інше, як крокове Управління на i -му кроці:

Керування ж системою підприємств за період Т, що містить m кроків фоків) являє собою сукупність

і являє собою стратегію управління.

Ефективність цієї стратегії на і-му кроці визначається показник ефективності (наприклад, отриманим доходом):

Тоді за весь період Т (за т - кроків) показник ефективності визначається як

Згідно з типовою задачею ДП необхідно вибрати стратегію управління усіма к підприємствами на і - му кроці:

що забезпечує z = z_max.

Поставлену задачу можна вирішити по різному:

- відразу знайти оптимальне рішення и (для оптимальної стратегії приймемо її позначку маленькою буквою и);

- на кожнім і- -му кроці будемо оптимізувати тільки відповідно управління (u_i), у результаті такого розгляду т кроків знайдена оптимальна стратегія.

при якій

Здавалося б рішення тривіальне: необхідно оптимізувати крок управління u_i щороку (це просто, із застосуванням ЛП) і в результат оптимізації всіх кроків одержимо оптимальну стратегію управління и.

Але принцип ДП аж ніяк не припускає, що кожен крок оптимізується окремо, незалежно від інших. Навпаки, крокове управління повинно вибиратися з урахуванням усіх його наслідків у майбутньому. Цей принцип сформульований американським вченим Робертом Беллманом говорить, що незалежно від того, який стан системи і яке прийнято рішення в початковий момент, наступні рішення і отже поводження системи має бути оптимальним з урахуванням саме майбутніх наслідків.

Однак з цього загального правила є одне єдине виключення: останній крок, який може просто плануватися як оптимальний у рамках ЛП (без урахування наслідків), і який має приносити безумовно максимальну вигоду.

Таким чином, спланувавши цей останній крок, можна до нього пристроювати передостанній, потім передпередостанній і т.д. до початкового кроку.

Саме тому процес ДП розвертається, як правило, від кінця до початку. Але як же це спланувати, не знаючи передостаннього? Очевидно, потрібно зробити певні припущення щодо результатів передостаннього (т- 1)-го кроку і для нього знайти таке управління, що забезпечить максимальний виграш на останньому m -му кроці.

Нехай це процедура виконання для кожного з можливих станів системи на (т-1) кроці і для кожного з них ми знаємо оптимальне керування на т-му кроці. Тепер ми можемо оптимізувати керування на (т- 1) кроці, зробивши всі можливі припущення щодо стану системи на (т-2)-у кроці. Для кожного з цих припущень знаходимо оптимальний вектор управління u_m-1.

Іншими словами, на кожнім i -у кроці шукається управління и_І9 яке забезпечує оптимальне продовження процесу на (i +1) - кроці відносно досягнутого стану на i -му кроці.

Управління, що забезпечує оптимальне продовження процесу називається умовним оптимальним управлінням на даному кроці (УОУ).

Тепер припустимо, що УОУ на кожному кроці нам відомо: ми знаємо як йти далі, у якому би стані не був процес до початку кожного кроку. Тоді, якщо початковий стан S₀ нам відомий, то ми знаємо, як знайти вже не умовне, а дійсно оптимальне управління на 1-му кроці. Потім, спираючись на нього, можна знайти оптимальне управління на другому кроці і т.д. У результаті ми прийдемо до кінцевого стану S_m і знайдемо оптимальний вектор управління u, що забезпечить оптимальне протікання процесу протягом усіх т кроків управління.

Таким чином, при оптимізації систем методом ДП багатокроковий процес проходить двічі:

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

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

Розглянемо декілька прикладів застосування методу ДП.

Дата добавления: 2014-12-29