Моделювання оптимального розподілу інвестицій за допомогою динамічного програмування

Графічні моделі використаються тоді, коли завдання зручно представити у вигляді графічної структури.

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). У задачах динамічного програмування критерій ефективності називається виграшем. Дані процеси керовані, і від правильного вибору керування залежить величина виграшу.

Змінна від якої залежать виграш на і-м кроці й, отже, виграш у цілому, називається кроковим керуванням, .

Управлінням процесу в цілому називається послідовність крокових управлінь .

Оптимальне управління – це значення управління , при якому значення