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

Нехай розглядається задача, що розпадається на m кроків або етапів, наприклад планування діяльності підприємства на кілька років, поетапне планування інвестицій, керування виробничими потужностями протягом тривалого строку. Показник ефективності задачі в цілому позначиться через W, а показники ефективності на окремих кроках – через

, . Якщо W має властивість адитивності, тобто:

, (2.7)

то можна знайти оптимальне рішення задачі методом динамічного програмування.

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

Змінна

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

Управлінням процесу в цілому

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

Оптимальне управління

– це значення управління , при якому значення є максимальним (або мінімальним, якщо потрібно зменшити програш):

, , (2.8)

де – область припустимих управлінь.

Оптимальне управління

визначається послідовністю оптимальних крокових управлінь:

. (2.9)

В основі методу динамічного програмування лежить принцип оптимальності Беллмана, що формулюється в такий спосіб: керування на кожному кроці треба вибирати так, щоб оптимальною була сума виграшів на всіх кроках, що залишилися до кінця процесу, включаючи виграш на даному кроці [1].

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

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

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

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

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

на всі наступні кроки, тому що ці кроки просто відсутні. Роблячи припущення про умови закінчення (m-1)-го кроку, для кожного з них проводять умовну оптимізацію m-го кроку й визначають умовне оптимальне управління . Аналогічно діють для (m-l)-го кроку, роблячи припущення про стан закінчення (m-2)-го кроку й визначаючи умовне оптимальне управління на (m-1)-му кроці, що приносить оптимальний виграш на двох останніх кроках – (m-1)-му і m-му. Так само діють на всіх інших кроках до першого. На першому кроці, як правило, не треба робити умовних припущень, тому що стан системи перед першим кроком звичайно відомо.

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

2.2 Складання математичної моделі динамічного програмування

Додатково вводяться наступні умовні позначки:

– стан процесу;

– безліч можливих станів процесу перед і-м кроком;

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

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

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

– Вибір змінних, що характеризують стан

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

– Визначення безлічі крокових управлінь

, й накладених на них обмежень, тобто області припустимих управлінь .

– Визначення виграшу:

, (2.10)

який принесе на і-му кроці управління

, якщо система перед цим перебувала в стані .

– Визначення стану

, у яке переходить система зі стану під впливом керування :

, (2.11)

де

– функція переходу на і-му кроці зі стану у стан .

– Складання управління, що визначає умовний оптимальний виграш на останньому кроці, для стану

моделюємого процесу:

. (2.12)

– Складання основного функціонального рівняння динамічного програмування, що визначає умовний оптимальний виграш для даного стану

з і-го кроку й до кінця процесу через уже відомий умовний оптимальний виграш із (і+1)-го кроку й до кінця:

. (2.13)

У рівнянні (2.13) у вже відому функцію

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

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

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