Моделювання оптимального розподілу інвестицій за допомогою динамічного програмування
Графічні моделі використаються тоді, коли завдання зручно представити у вигляді графічної структури.
2. ТЕОРЕТИЧНІ АСПЕКТИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ
2.1 Постановка задачі динамічного програмування. Основні умови й область застосування
Динамічне програмування – це метод дослідження операцій, на кожному етапі якого можна керувати перебігом досліджуваного процесу та оцінювати якість такого управління.
Загальна
постановка
задачі динамічного
програмування.
Досліджується
перебіг деякого
керованого
процесу, тобто
на стан і розвиток
якого можна
впливати через
певні проміжки
(в економічних
процесах управління
– перерозподіл
коштів, заміна
обладнання,
визначення
обсягів поставок
сировини на
період і т. ін.).
Приймається,
що процес управління
можна реалізувати
дискретно за
етапів. Будь-яку
багато етапну
задачу можна
реалізувати
по-різному або
відразу шукати
всі елементи
розв’язку для
всіх
етапів,
або знаходити
оптимальне
управління
поетапно, на
будь-якому
етапі визнаючи
розв’язок
стосовно лише
цього етапу
– такий варіант
простіший.
Параметри цих моделей доцільно розбити на дві множини: параметри стану (для дослідження властивостей яких була розбудована модель) та параметри управління (фактори, які можуть впливати на стан процесу).
Нехай
– кількість
етапів. На будь-якому
і-му етапі процес
може бути в
різних станах
{
}
,
кожний з яких
характеризується
скінченою
множиною параметрів.
Множину параметрів
доцільно розглядати
як компоненти
деякого вектора
,
де
– кількість
параметрів,
обраних для
характеристики
стану. На будь-якому
з
досліджуваних
етапів система
може бути в
кількох станах.
Перебіг
процесу визначається
певною послідовністю
переходів з
одного стану
в інший. Якщо
процес на і-му
етапі перебував
у деякому стані
,
то наступний
стан
на (і+1)-му кроці
визначається
не лише попереднім
станом, а й вибором
певного управління
при досягненні
(
;
).
У загальному
випадку будь-яке
управління
на будь-якому
етапі доцільно
розглядати
як
-мірний
вектор
.
Числові значення
компонент
вектора управління
будуть залежати
як від вихідного
стану
на і-му кроці,
так і від наступного
стану на (і+1)-му
кроці
![]()
,
тобто вектор
визначається
чотирма індексами
і має бути вибраний
з певної множини
допустимих
управлінь.
Для спрощення
записів вектори
можливих поточного
стану та управління
будемо позначати
лише одним
індексом, спів
ставляючи їх
певному кроку
(етапу), тобто
щодо стану
,
мається на
увазі один із
можливих станів
множини {
}
,
а щодо вектора
– один із можливих
векторів множини
{
}
,
(
).

Рисунок 1.5 – Можливі стани системи на кожному етапі
На рисунку
1.5 схематично
кругами зображені
можливі стани
на кожному
етапі, лініями
– можливі переходи
від одного
стану до іншого
за вибору певного
управління.
Таким чином,
стан процесу
на і-му етапі
визначається
певною функціональною
залежністю
від стану на
попередньому
кроці та значеннями
параметрів
управління
на початку
чергового
кроку, тобто
.
Процес управління
моделюється
як вибір за
кожного можливого
j-го стану на
і-му етапі певного
k-мірного вектора
з деяких допустимих
множин векторів
{
}
.
Для спрощення
він позначається
.
Множина послідовності
управлінь
позначається
–
,
які переводять
систему зі
стану
у стан
,
схематично
це представлено
на рисунку 1.6.

Рисунок
1.6 – Перехід системи
із стану
у стан
![]()
Будь-яку
послідовність
,
що переводить
систему зі
стану
у стан
,
називається
стратегією,
а вектори
– її складовими.
Ефективність
вибору послідовності
управлінь
(стратегії)
оцінюється
за вибраним
критерієм
певною цільовою
функцією
:
.
(2.1)
Модель динамічного програмування можна використовувати в тих випадках, коли є підстави прийняти такі допущення стосовно досліджуваної системи:
– Стан
системи в кінці
і-го кроку
визначається
лише попереднім
станом
та управлінням
на і-му кроці
і не залежить
від попередніх
станів та управлінь.
Формула (2.2) –
рівняння стану.
,
.
(2.2)
– Цільова
функція (2.1) є
адитивною
стосовно кожного
етапу і залежить
від того, яким
був стан системи
на початку
етапу та яке
було обране
управління.
Нехай
– показник
ефективності
і-го кроку.
,
.
(2.3)
Тоді цільова функція (2.1) буде представлена формулою (2.4)
.
(2.4)
Метод динамічного програмування також можна використовувати при розв’язанні задач з так званою “мультиплікативною” цільовою функцією, тобто:
.
(2.5)
Задача динамічного програмування за названих умов формується так: визначити таку допустиму стратегію управління:
.
(2.6)
Дана
стратегія
переводить
систему
зі стану
у стан
і за якої цільова
функція (2.4) досягає
екстремального
значення.
Нехай
розглядається
задача, що
розпадається
на m кроків або
етапів, наприклад
планування
діяльності
підприємства
на кілька років,
поетапне планування
інвестицій,
керування
виробничими
потужностями
протягом тривалого
строку. Показник
ефективності
задачі в цілому
позначиться
через W, а показники
ефективності
на окремих
кроках – через
,
.
Якщо W має властивість
адитивності,
тобто:
,
(2.7)
то можна знайти оптимальне рішення задачі методом динамічного програмування.
Таким чином, динамічне програмування – це метод оптимізації багатокрокових або багато етапних процесів, критерій ефективності яких має властивість (2.7). У задачах динамічного програмування критерій ефективності називається виграшем. Дані процеси керовані, і від правильного вибору керування залежить величина виграшу.
Змінна
від якої залежать
виграш на і-м
кроці й, отже,
виграш у цілому,
називається
кроковим керуванням,
.
Управлінням
процесу в цілому
називається
послідовність
крокових управлінь
.
Оптимальне
управління
–
це значення
управління
,
при якому значення