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

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

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

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

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

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

Розглянемо загальну постановку задачі цього програмування. Нехай досліджується деякий економічний процес, що має п послідовних етапів. На кожному 7-му етапі процес може бути в різних станах бі, кожний з яких характеризується скінченою множиною параметрів. З кожним етапом задачі пов'язане прийняття певного управлінського рішення хі, яке переводить систему з одного стану в інший. Припускається, що стан si системи в кінці 7-го етапу визначається лише попереднім станом si_1 та управлінням хі на 7-му етапі й не залежить від попередніх станів та управлінь. Тоді стан si системи записується у вигляді залежності

Si = ф(у, _ !, хі), і = 1, П.

Ефективність усього процесу управління може бути подана як сума ефективностей управлінських рішень окремих етапів, тобто

і=1

За названих умов задача динамічного програмування формулюється так: визначити таку допустиму послідовність управлінських рішень X = { х1, х2, хп }, котра переводить систему з початкового стану 50 у завершальний стан sn і за якої досягається максимальна ефективність управління.

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

Максимум цільової функції на заключному п-му етапі дорівнює

^п-О = шаХ /п ^п-и хп ).

Відповідно, на (п - 1)-етапі маємо

г*п-1(5п-2) = ШaХ((fn-1(sn-2,хп-1)+ г*п^п-1)) .

хп-1

Ураховуючи цю закономірність, для довільного к-то етапу можемо записати рекурентну залежність

г* (5і-1) = шахІ(Л (їк-1, хк ) + г*+1 )).

хк

Така рекурентна залежність являє собою математичний запис принципу оптимальності Белмана.

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

Основні особливості методу динамічного програмування

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

2. Метод динамічного програмування можна застосовувати за будь-якого способу завдання цільової функції та з будь-якою припустимою множиною станів та керувань. Цієї переваги позбавлені класичні методи оптимізації та інші обчислювальні методи математичного програмування.

3. Обчислювальні схеми методу динамічного програмування в дискретному випадку пов'язані з перебиранням оптимальних значень показника ефективності й керування на к-му кроці для всіх можливих значень змінної стану, але обсяг розрахунків при цьому значно менший, ніж за прямого перебирання варіантів. Це пов'язано з тим, що на етапі умовної оптимізації невдалі варіанти відразу відкидаються, а зберігаються лише умовно оптимальні на даному кроці.

4. Метод динамічного програмування дає можливість аналізу чутливості до зміни вихідних даних станів sk та їх кількості п. Фактично тут на кожному кроці розв'язується не одна задача, а множина однотипних задач для різних станів sk і різних к (1 < к < п). Тому зі зміною вихідних даних можна не розв'язувати задачу заново, а зробити лише нескладні додавання до вже виконаних розрахунків, тобто продовжити вже розв'язану задачу за рахунок збільшення кількості кроків п або кількості значень sk.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Нелінійне програмування	\|	ВИСНОВКИ

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.