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

--PAGE_BREAK--2. ТЕОРЕТИЧНІ АСПЕКТИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ

2.1 Постановка задачі динамічного програмування. Основні умови й область застосування
Динамічне програмування – це метод дослідження операцій, на кожному етапі якого можна керувати перебігом досліджуваного процесу та оцінювати якість такого управління.

Загальна постановка задачі динамічного програмування. Досліджується перебіг деякого керованого процесу, тобто на стан і розвиток якого можна впливати через певні проміжки (в економічних процесах управління – перерозподіл коштів, заміна обладнання, визначення обсягів поставок сировини на період і т. ін.). Приймається, що процес управління можна реалізувати дискретно за <img border=«0» width=«19» height=«19» src=«ref-1_1712648134-97.coolpic» v:shapes="_x0000_i1048"> етапів. Будь-яку багато етапну задачу можна реалізувати по-різному або відразу шукати всі елементи розв’язку для всіх <img border=«0» width=«19» height=«19» src=«ref-1_1712648134-97.coolpic» v:shapes="_x0000_i1049">етапів, або знаходити оптимальне управління поетапно, на будь-якому етапі визнаючи розв’язок стосовно лише цього етапу – такий варіант простіший.

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

Нехай <img border=«0» width=«19» height=«19» src=«ref-1_1712648134-97.coolpic» v:shapes="_x0000_i1050"> – кількість етапів. На будь-якому і-му етапі процес може бути в різних станах {<img border=«0» width=«21» height=«25» src=«ref-1_1712648425-108.coolpic» v:shapes="_x0000_i1051">}<img border=«0» width=«8» height=«24» src=«ref-1_1712648533-75.coolpic» v:shapes="_x0000_i1052">, кожний з яких характеризується скінченою множиною параметрів. Множину параметрів доцільно розглядати як компоненти деякого вектора <img border=«0» width=«112» height=«27» src=«ref-1_1712648608-237.coolpic» v:shapes="_x0000_i1053">, де <img border=«0» width=«9» height=«19» src=«ref-1_1712648845-82.coolpic» v:shapes="_x0000_i1054"> – кількість параметрів, обраних для характеристики стану. На будь-якому з <img border=«0» width=«19» height=«19» src=«ref-1_1712648134-97.coolpic» v:shapes="_x0000_i1055"> досліджуваних етапів система може бути в кількох станах.

Перебіг процесу визначається певною послідовністю переходів з одного стану в інший. Якщо процес на і-му етапі перебував у деякому стані <img border=«0» width=«27» height=«28» src=«ref-1_1712649024-122.coolpic» v:shapes="_x0000_i1056">, то наступний стан <img border=«0» width=«36» height=«28» src=«ref-1_1712649146-141.coolpic» v:shapes="_x0000_i1057"> на (і+1)-му кроці визначається не лише попереднім станом, а й вибором певного управління при досягненні <img border=«0» width=«27» height=«28» src=«ref-1_1712649024-122.coolpic» v:shapes="_x0000_i1058"> (<img border=«0» width=«57» height=«27» src=«ref-1_1712649409-156.coolpic» v:shapes="_x0000_i1059">;<img border=«0» width=«51» height=«25» src=«ref-1_1712649565-149.coolpic» v:shapes="_x0000_i1060">). У загальному випадку будь-яке управління на будь-якому етапі доцільно розглядати як <img border=«0» width=«16» height=«17» src=«ref-1_1712649714-90.coolpic» v:shapes="_x0000_i1061">-мірний вектор <img border=«0» width=«111» height=«28» src=«ref-1_1712649804-236.coolpic» v:shapes="_x0000_i1062">. Числові значення компонент вектора управління будуть залежати як від вихідного стану <img border=«0» width=«27» height=«28» src=«ref-1_1712649024-122.coolpic» v:shapes="_x0000_i1063"> на і-му кроці, так і від наступного стану на (і+1)-му кроці <img border=«0» width=«36» height=«28» src=«ref-1_1712649146-141.coolpic» v:shapes="_x0000_i1064"><img border=«0» width=«77» height=«27» src=«ref-1_1712650303-197.coolpic» v:shapes="_x0000_i1065">, тобто вектор <img border=«0» width=«13» height=«23» src=«ref-1_1712650500-93.coolpic» v:shapes="_x0000_i1066"> визначається чотирма індексами <img border=«0» width=«67» height=«21» src=«ref-1_1712650593-161.coolpic» v:shapes="_x0000_i1067"> і має бути вибраний з певної множини допустимих управлінь.

Для спрощення записів вектори можливих поточного стану та управління будемо позначати лише одним індексом, спів ставляючи їх певному кроку (етапу), тобто щодо стану <img border=«0» width=«17» height=«27» src=«ref-1_1712650754-103.coolpic» v:shapes="_x0000_i1068">, мається на увазі один із можливих станів множини {<img border=«0» width=«21» height=«25» src=«ref-1_1712648425-108.coolpic» v:shapes="_x0000_i1069">}<img border=«0» width=«8» height=«24» src=«ref-1_1712648533-75.coolpic» v:shapes="_x0000_i1070">, а щодо вектора <img border=«0» width=«17» height=«23» src=«ref-1_1712651040-99.coolpic» v:shapes="_x0000_i1071"> – один із можливих векторів множини {<img border=«0» width=«25» height=«25» src=«ref-1_1712651139-114.coolpic» v:shapes="_x0000_i1072">}<img border=«0» width=«27» height=«25» src=«ref-1_1712651253-101.coolpic» v:shapes="_x0000_i1073">, (<img border=«0» width=«176» height=«27» src=«ref-1_1712651354-322.coolpic» v:shapes="_x0000_i1074">).
<img border=«0» width=«598» height=«342» src=«ref-1_1712651676-13429.coolpic» v:shapes="_x0000_i1075">

Рисунок 1.5 – Можливі стани системи на кожному етапі




На рисунку 1.5 схематично кругами зображені можливі стани на кожному етапі, лініями – можливі переходи від одного стану до іншого за вибору певного управління. Таким чином, стан процесу на і-му етапі визначається певною функціональною залежністю від стану на попередньому кроці та значеннями параметрів управління на початку чергового кроку, тобто <img border=«0» width=«97» height=«27» src=«ref-1_1712665105-234.coolpic» v:shapes="_x0000_i1076">. Процес управління моделюється як вибір за кожного можливого j-го стану на і-му етапі певного k-мірного вектора <img border=«0» width=«25» height=«28» src=«ref-1_1712665339-119.coolpic» v:shapes="_x0000_i1077"> з деяких допустимих множин векторів {<img border=«0» width=«13» height=«23» src=«ref-1_1712650500-93.coolpic» v:shapes="_x0000_i1078">}<img border=«0» width=«16» height=«25» src=«ref-1_1712665551-89.coolpic» v:shapes="_x0000_i1079">. Для спрощення він позначається <img border=«0» width=«16» height=«23» src=«ref-1_1712665640-99.coolpic» v:shapes="_x0000_i1080">. Множина послідовності управлінь позначається – <img border=«0» width=«112» height=«27» src=«ref-1_1712665739-235.coolpic» v:shapes="_x0000_i1081">, які переводять систему зі стану <img border=«0» width=«20» height=«23» src=«ref-1_1712665974-105.coolpic» v:shapes="_x0000_i1082"> у стан <img border=«0» width=«23» height=«23» src=«ref-1_1712666079-114.coolpic» v:shapes="_x0000_i1083">, схематично це представлено на рисунку 1.6.
<img border=«0» width=«594» height=«72» src=«ref-1_1712666193-8802.coolpic» v:shapes="_x0000_i1084">

Рисунок 1.6 – Перехід системи із стану <img border=«0» width=«20» height=«23» src=«ref-1_1712665974-105.coolpic» v:shapes="_x0000_i1085"> у стан <img border=«0» width=«23» height=«23» src=«ref-1_1712666079-114.coolpic» v:shapes="_x0000_i1086">
Будь-яку послідовність <img border=«0» width=«112» height=«27» src=«ref-1_1712665739-235.coolpic» v:shapes="_x0000_i1087">, що переводить систему зі стану <img border=«0» width=«20» height=«23» src=«ref-1_1712665974-105.coolpic» v:shapes="_x0000_i1088"> у стан <img border=«0» width=«23» height=«23» src=«ref-1_1712666079-114.coolpic» v:shapes="_x0000_i1089">, називається стратегією, а вектори <img border=«0» width=«16» height=«23» src=«ref-1_1712665640-99.coolpic» v:shapes="_x0000_i1090"> – її складовими.

Ефективність вибору послідовності управлінь <img border=«0» width=«13» height=«23» src=«ref-1_1712650500-93.coolpic» v:shapes="_x0000_i1091"> (стратегії) оцінюється за вибраним критерієм певною цільовою функцією <img border=«0» width=«16» height=«17» src=«ref-1_1712675860-91.coolpic» v:shapes="_x0000_i1092">:
<img border=«0» width=«99» height=«30» src=«ref-1_1712675951-357.coolpic» v:shapes="_x0000_i1093">.                                                                                             (2.1)
Модель динамічного програмування можна використовувати в тих випадках, коли є підстави прийняти такі допущення стосовно досліджуваної системи:

– Стан <img border=«0» width=«17» height=«27» src=«ref-1_1712650754-103.coolpic» v:shapes="_x0000_i1094"> системи в кінці і-го кроку визначається лише попереднім станом <img border=«0» width=«28» height=«27» src=«ref-1_1712676411-118.coolpic» v:shapes="_x0000_i1095"> та управлінням <img border=«0» width=«16» height=«23» src=«ref-1_1712665640-99.coolpic» v:shapes="_x0000_i1096"> на і-му кроці і не залежить від попередніх станів та управлінь. Формула (2.2) – рівняння стану.
<img border=«0» width=«125» height=«31» src=«ref-1_1712676628-471.coolpic» v:shapes="_x0000_i1097">, <img border=«0» width=«58» height=«30» src=«ref-1_1712677099-233.coolpic» v:shapes="_x0000_i1098">.                                                                         (2.2)
– Цільова функція (2.1) є адитивною стосовно кожного етапу і залежить від того, яким був стан системи <img border=«0» width=«28» height=«27» src=«ref-1_1712676411-118.coolpic» v:shapes="_x0000_i1099"> на початку етапу та яке було обране управління. Нехай <img border=«0» width=«17» height=«24» src=«ref-1_1712677450-98.coolpic» v:shapes="_x0000_i1100"> – показник ефективності і-го кроку.
<img border=«0» width=«124» height=«31» src=«ref-1_1712677548-399.coolpic» v:shapes="_x0000_i1101">, <img border=«0» width=«58» height=«30» src=«ref-1_1712677947-231.coolpic» v:shapes="_x0000_i1102">.                                                                         (2.3)
Тоді цільова функція (2.1) буде представлена формулою (2.4)
<img border=«0» width=«147» height=«53» src=«ref-1_1712678178-580.coolpic» v:shapes="_x0000_i1103">.                                                                                   (2.4)
Метод динамічного програмування також можна використовувати при розв’язанні задач з так званою “мультиплікативною” цільовою функцією, тобто:
<img border=«0» width=«147» height=«52» src=«ref-1_1712678758-551.coolpic» v:shapes="_x0000_i1104">.                                                                                   (2.5)
Задача динамічного програмування за названих умов формується так: визначити таку допустиму стратегію управління:
<img border=«0» width=«154» height=«32» src=«ref-1_1712679309-475.coolpic» v:shapes="_x0000_i1105">.                                                                                 (2.6)
Дана стратегія переводить систему <img border=«0» width=«15» height=«19» src=«ref-1_1712679784-91.coolpic» v:shapes="_x0000_i1106"> зі стану <img border=«0» width=«20» height=«23» src=«ref-1_1712665974-105.coolpic» v:shapes="_x0000_i1107"> у стан <img border=«0» width=«23» height=«23» src=«ref-1_1712666079-114.coolpic» v:shapes="_x0000_i1108"> і за якої цільова функція (2.4) досягає екстремального значення.

Нехай розглядається задача, що розпадається на m кроків або етапів, наприклад планування діяльності підприємства на кілька років, поетапне планування інвестицій, керування виробничими потужностями протягом тривалого строку. Показник ефективності задачі в цілому позначиться через W, а показники ефективності на окремих кроках – через <img border=«0» width=«17» height=«24» src=«ref-1_1712680094-97.coolpic» v:shapes="_x0000_i1109">, <img border=«0» width=«49» height=«25» src=«ref-1_1712680191-141.coolpic» v:shapes="_x0000_i1110">. Якщо W має властивість адитивності, тобто:
<img border=«0» width=«83» height=«54» src=«ref-1_1712680332-435.coolpic» v:shapes="_x0000_i1111">,                                                                                                 (2.7)
то можна знайти оптимальне рішення задачі методом динамічного програмування.

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

Змінна <img border=«0» width=«17» height=«24» src=«ref-1_1712680767-91.coolpic» v:shapes="_x0000_i1112"> від якої залежать виграш на і-м кроці й, отже, виграш у цілому, називається кроковим керуванням, <img border=«0» width=«49» height=«25» src=«ref-1_1712680191-141.coolpic» v:shapes="_x0000_i1113">.

Управлінням процесу в цілому <img border=«0» width=«24» height=«21» src=«ref-1_1712680999-107.coolpic» v:shapes="_x0000_i1114"> називається послідовність крокових управлінь <img border=«0» width=«144» height=«24» src=«ref-1_1712681106-243.coolpic» v:shapes="_x0000_i1115">.

Оптимальне управління <img border=«0» width=«23» height=«19» src=«ref-1_1712681349-100.coolpic» v:shapes="_x0000_i1116">– це значення управління <img border=«0» width=«13» height=«15» src=«ref-1_1712601872-84.coolpic» v:shapes="_x0000_i1117">, при якому значення <img border=«0» width=«45» height=«21» src=«ref-1_1712681533-149.coolpic» v:shapes="_x0000_i1118"> є максимальним (або мінімальним, якщо потрібно зменшити програш):
<img border=«0» width=«193» height=«25» src=«ref-1_1712681682-708.coolpic» v:shapes="_x0000_i1119">,<img border=«0» width=«52» height=«22» src=«ref-1_1712682390-193.coolpic» v:shapes="_x0000_i1120">,                                                             (2.8)
де – область припустимих управлінь.

Оптимальне управління <img border=«0» width=«23» height=«19» src=«ref-1_1712681349-100.coolpic» v:shapes="_x0000_i1121"> визначається послідовністю оптимальних крокових управлінь:
<img border=«0» width=«231» height=«29» src=«ref-1_1712682683-591.coolpic» v:shapes="_x0000_i1122">.                                                                 (2.9)
В основі методу динамічного програмування лежить принцип оптимальності Беллмана, що формулюється в такий спосіб: керування на кожному кроці треба вибирати так, щоб оптимальною була сума виграшів на всіх кроках, що залишилися до кінця процесу, включаючи виграш на даному кроці [1].

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

Інший момент, котрий варто враховувати при виборі управління на даному кроці, – це можливі варіанти закінчення попереднього кроку. Ці варіанти визначають стан процесу. Наприклад, при визначенні кількості коштів, вкладених у підприємство в і-му році, необхідно знати, скільки коштів залишилося в наявності до цього року і який прибуток отриманий у попередньому (і-1)-м році. Таким чином, при виборі крокового управління необхідно враховувати:

– можливі результати попереднього кроку;

– вплив управління на всі кроки, що залишилися, до кінця процесу.

У задачах динамічного програмування перший пункт враховують, роблячи на кожному кроці умовні припущення про можливі варіанти закінчення попереднього кроку й проводячи для кожного з варіантів умовну оптимізацію. Виконання другого пункту забезпечується тим, що в задачах динамічного програмування умовна оптимізація проводиться від кінця процесу до початку. Спершу оптимізується останній m-й крок, на якому не треба враховувати можливі впливи обраного управління <img border=«0» width=«20» height=«24» src=«ref-1_1712683274-98.coolpic» v:shapes="_x0000_i1123"> на всі наступні кроки, тому що ці кроки просто відсутні. Роблячи припущення про умови закінчення (m-1)-го кроку, для кожного з них проводять умовну оптимізацію m-го кроку й визначають умовне оптимальне управління <img border=«0» width=«20» height=«24» src=«ref-1_1712683274-98.coolpic» v:shapes="_x0000_i1124">. Аналогічно діють для (m-l)-го кроку, роблячи припущення про стан закінчення (m-2)-го кроку й визначаючи умовне оптимальне управління на (m-1)-му кроці, що приносить оптимальний виграш на двох останніх кроках – (m-1)-му і m-му. Так само діють на всіх інших кроках до першого. На першому кроці, як правило, не треба робити умовних припущень, тому що стан системи перед першим кроком звичайно відомо.

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

<img border=«0» width=«12» height=«15» src=«ref-1_1712683470-83.coolpic» v:shapes="_x0000_i1125"> – стан процесу;

<img border=«0» width=«17» height=«24» src=«ref-1_1712683553-97.coolpic» v:shapes="_x0000_i1126">– безліч можливих станів процесу перед і-м кроком;

<img border=«0» width=«19» height=«24» src=«ref-1_1712683650-107.coolpic» v:shapes="_x0000_i1127">– виграш із і-го кроку до кінця процесу, <img border=«0» width=«49» height=«25» src=«ref-1_1712680191-141.coolpic» v:shapes="_x0000_i1128">.

Можна визначити наступні основні етапи складання математичної моделі задачі динамічного програмування [1].

– Розбивка задачі на кроки (етапи). Крок не повинен бути занадто дрібним, щоб не проводити зайвих розрахунків і не повинен бути занадто великим, ускладнюючий процес крокової оптимізації.

– Вибір змінних, що характеризують стан <img border=«0» width=«12» height=«15» src=«ref-1_1712683470-83.coolpic» v:shapes="_x0000_i1129"> моделюємого процесу перед кожним кроком, і виявлення обмежень, що накладаються на них. У якості таких змінних варто брати фактори, що представляють інтерес для дослідника, наприклад річний прибуток при плануванні діяльності підприємства.

– Визначення безлічі крокових управлінь <img border=«0» width=«17» height=«24» src=«ref-1_1712680767-91.coolpic» v:shapes="_x0000_i1130">, <img border=«0» width=«49» height=«25» src=«ref-1_1712680191-141.coolpic» v:shapes="_x0000_i1131"> й накладених на них обмежень, тобто області припустимих управлінь <img border=«0» width=«19» height=«17» src=«ref-1_1712601956-97.coolpic» v:shapes="_x0000_i1132">.

– Визначення виграшу:
<img border=«0» width=«70» height=«29» src=«ref-1_1712684310-362.coolpic» v:shapes="_x0000_i1133">,                                                                                                 (2.10)
який принесе на і-му кроці управління <img border=«0» width=«17» height=«24» src=«ref-1_1712680767-91.coolpic» v:shapes="_x0000_i1134">, якщо система перед цим перебувала в стані <img border=«0» width=«12» height=«15» src=«ref-1_1712683470-83.coolpic» v:shapes="_x0000_i1135">.

– Визначення стану <img border=«0» width=«15» height=«19» src=«ref-1_1712684846-88.coolpic» v:shapes="_x0000_i1136">, у яке переходить система зі стану <img border=«0» width=«12» height=«15» src=«ref-1_1712683470-83.coolpic» v:shapes="_x0000_i1137">під впливом керування <img border=«0» width=«17» height=«24» src=«ref-1_1712680767-91.coolpic» v:shapes="_x0000_i1138">:
<img border=«0» width=«77» height=«24» src=«ref-1_1712685108-184.coolpic» v:shapes="_x0000_i1139">,                                                                                                (2.11)
де <img border=«0» width=«17» height=«24» src=«ref-1_1712685292-97.coolpic» v:shapes="_x0000_i1140"> – функція переходу на і-му кроці зі стану <img border=«0» width=«12» height=«15» src=«ref-1_1712683470-83.coolpic» v:shapes="_x0000_i1141"> у стан <img border=«0» width=«15» height=«19» src=«ref-1_1712684846-88.coolpic» v:shapes="_x0000_i1142">.

– Складання управління, що визначає умовний оптимальний виграш на останньому кроці, для стану <img border=«0» width=«12» height=«15» src=«ref-1_1712683470-83.coolpic» v:shapes="_x0000_i1143"> моделюємого процесу:
<img border=«0» width=«182» height=«34» src=«ref-1_1712685643-760.coolpic» v:shapes="_x0000_i1144">.                                                                         (2.12)


– Складання основного функціонального рівняння динамічного програмування, що визначає умовний оптимальний виграш для даного стану <img border=«0» width=«12» height=«15» src=«ref-1_1712683470-83.coolpic» v:shapes="_x0000_i1145"> з і-го кроку й до кінця процесу через уже відомий умовний оптимальний виграш із (і+1)-го кроку й до кінця:
<img border=«0» width=«299» height=«34» src=«ref-1_1712686486-1062.coolpic» v:shapes="_x0000_i1146">.                                                (2.13)
У рівнянні (2.13) у вже відому функцію <img border=«0» width=«48» height=«24» src=«ref-1_1712687548-156.coolpic» v:shapes="_x0000_i1147">, що характеризує умовний оптимальний виграш із (і+1)-го кроку до кінця процесу, замість стану <img border=«0» width=«12» height=«15» src=«ref-1_1712683470-83.coolpic» v:shapes="_x0000_i1148"> підставлений новий стан <img border=«0» width=«77» height=«24» src=«ref-1_1712685108-184.coolpic» v:shapes="_x0000_i1149">, у яке система переходить на і-му кроці під впливом управління <img border=«0» width=«17» height=«24» src=«ref-1_1712680767-91.coolpic» v:shapes="_x0000_i1150">.

Структура моделі динамічного програмування відрізняється від статичної моделі лінійного програмування. Дійсно, у моделях лінійного програмування управляючі змінні – це одночасно й змінні стану моделюємого процесу, а в динамічних моделях окремо вводяться змінні управління <img border=«0» width=«17» height=«24» src=«ref-1_1712680767-91.coolpic» v:shapes="_x0000_i1151">, і змінні, що характеризують зміну стану <img border=«0» width=«12» height=«15» src=«ref-1_1712683470-83.coolpic» v:shapes="_x0000_i1152"> під впливом управління. Таким чином, структура динамічних моделей більш складна, що природно, тому що в цих моделях додатково враховується фактор часу.
    продолжение
--PAGE_BREAK--