Динамічне програмування

Динамічне програмування (динамічне планування) являє со­бою математичний метод оптимізацїї рішень, спеціально присто­сований до так званих «багатоступеневих» (чи «багатоетапних») операцій. Багато економічних процесів дійсним чином діляться на ступені. До них можна віднести планування і управління ви­робництвом чи окремими процесами, розвиток яких відбувається із врахуванням часу, тобто в динаміці. Тимчасовим ступенем в них може бути період стратегічного планування, п'ятирічка, рік, місяць, день і навіть години. В інших операціях ділення на ступені приходиться вводити штучно: наприклад, процес виведення ра­кети на орбіту можна умовно поділити на етапи, кожен з яких займає якийсь часовий відрізок [22].

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

Керування ніби складається із ряду елементарних, «ступеневих» керувань.

В економічній практиці зустрічаються завдання, які за по­становкою і методами розв'язання відносяться до завдань ди­намічного програмування перспективного оптимального і по­точного плануванням/розподілу тих чи інших ресурсів оптимізації ресурсів і вкладення їх у виробництво і т.п. Тут доцільно по­знайомитися з деякими завданнями, що розв'язуються методами динамічного програмування, викладені в загальному вигляді в роботі В.М. Колпакова [22].

1. Завдання перспективного планування

Планується діяльність промислового об'єднання, що склада­ється з кількох підприємств, на період реалізації поставленої мети. Необхідно розподілити наявні ресурси, які в подальшому витра­тяться і одержиться прибуток. Періодично ресурси можуть перероз­поділятися. Постає завдання розподілу ресурсів між підприємства­ми, що забезпечують максимальний прибуток всього об'єднання.

2. Завдання з оптимального керівництва поставками

В різних економічних, господарських ситуаціях з'являється завдання вибору часу (моменту подання) партії поставки і її об'єму, тобто, як прийнято називати, визначення оптимальної партійності деталей, конструкцій, сировини і матеріалів. З розміщенням замовлень пов'язані деякі фіксовані витрати, що не залежать від величини замовленої партії, а залежать тільки від факту замовлення. З утриманням матеріальних ресурсів пов'язані витрати, пропорціональні залишку нереалізованої продукції.

При розв'язанні цього завдання з багатьох можливих керу­вань вибирається таке, при якому досягається мінімум витрат на замовлення і утримання матеріальних ресурсів.

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

1. Розглядається система і її стан на кожному ступені без врахування того, яким шляхом вона прийшла в нього.

2. На кожному ступені вибирається одне рішення, під дією якого система переходить з попереднього стану в новий.

3. Дія на кожному ступені пов'язана з певним вигра­шем (прибутком) чи із втратою (витратами), за­лежними від стану на початок ступеня і прийнято­го рішення.

4. На показники стану і управління можуть бути на­кладені обмеження, що визначають ділянку допу­стимих рішень.

5. В ході розв'язання знаходиться допустиме керу­вання для кожного ступеня, що дозволяє одержа­ти (екстремальне) значення функції мети через не­обхідну кількість ступенів. Послідовність дій пер­соналу керування, що на кожному ступені перево­дить систему з початкового стану в кінцевий, на­зивають стратегією управління.

Динамічне програмування (планування) служить для вибору найкращого плану виконання багатоетапних дій. Для багатоетапних дій характерне протікання в часі. Крім дій, що дійсно носять багатоетапний характер (наприклад, перспективне плану­вання), в ряді завдань звертаються до штучного розчленування на етапи, для того щоб зробити можливим застосування методу динамічного програмування.

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

Є деяка керована операція (ціленаправлена дія), що розкла­дається (дійсно чи штучно) на т кроків — етапів. На кожному кроці здійснюється розподіл і перерозподіл учасників операції з метою покращення її результату в цілому. Ці розподіли в ди­намічному програмуванні називаються управлінням операцією і позначаються буквою V. Ефективність операції в цілому оціню­ється тим же показником, що і ефективність її управління W(U).

При цьому ефективність управління W(U) залежить від всієї сукупності керувань на кожному кроці операції:

Управління, при якому показник W досягає максимуму, на­зивається оптимальним управлінням. Оптимальне управління U є, як було сказано вище, багатоступеневим процесом і скла­дається із сукупності оптимальних ступеневих керувань:

Завдання динамічного програмування полягає у визначенні оптимального управління на кожному ступені U (і =1, 2, ..., m) і, тим самим, досягається оптимальне керування всією операцією (процесом) в цілому.

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

Інакше кажучи, в формалізованому вигляді процес можна

де ω_i – ефективність операції на i-му ступені.

При цьому у випадку оптимального управління

Суть розв'язання завдань динамічного програмування по­лягає в наступному:

· оптимізація проводиться методом послідовних набли­жень (ітерацій) в два круги; спочатку від останнього ступеня операції до першого, а потім, навпаки, — від першого до останнього ступеня;

· на першому крузі, йдучи від наступних ступенів до попе­редніх, знаходиться так зване умовне оптимальне уп­равління; умовне оптимальне управління вибирається таким, щоб всі попередні ступені забезпечували максимальну ефективність наступного ступеня. Інакше кажучи, на кожному кроці наявне таке управління, яке забезпечує оп­тимальне продовження операції. Цей принцип вибору ке­рування називається принципом оптимальності;

· так триває до першого кроку, але оскільки перший крок не має попереднього, то одержане для нього умовне оптимальне управління втрачає свій умовний характер і стає просто оптимальним управлінням, яке ми шукаємо;

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

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

Приклад завдання. Нехай маємо т типів різних вантажів, якими необхідно завантажити транспортний засіб (корабелі,, літак, автомобіль) таким чином, щоб загальна цінність вантажу IV була максимальною. Цінність вантажу є функцією від ванта­жопідйомності транспортного засобу:

s w:ascii="Cambria Math" w:h-ansi="Cambria Math"/><wx:font wx:val="Cambria Math"/><w:i/><w:color w:val="000000"/><w:spacing w:val="1"/><w:sz w:val="28"/><w:sz-cs w:val="28"/><w:lang w:val="EN-US"/></w:rPr><m:t>. (5.22)</m:t></m:r></m:oMath></m:oMathPara></w:p><w:sectPr wsp:rsidR="00000000"><w:pgSz w:w="12240" w:h="15840"/><w:pgMar w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>">

Відома маса вантажів і-го типу Р_і і її вартість С_і. Необхідно завантажити транспортний засіб таким чином, щоб загальна цінність вантажу була максимальною:

де х_i — кількість предметів вантажу i-го типу, що заванта­жуються в транспортний засіб; х_i виступає тут в ролі управління (U_i = хі). Обмежувальними умовами є:

Перша умова вимагає, щоб загальна маса вантажу не пере­вищувала вантажопідйомність транспортного засобу, а друга умова (5.23) — щоб предмети, що складають вантаж різних типів, були неподільні.