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

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

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

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) досягає екстремального значення.