46

Моделі динамічного програмування

1. Історична довідка

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

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

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

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

• 1) розподіл капіталовкладень між можливими напрямами їх використання;

• 2) управління запасами;

• 3) календарне планування виробництва при коливанні попиту на продукцію;

• 4) закупівля запасних частин для забезпечення неперервної експлуатації обладнання;

• 5) планування профілактичного ремонту обладнання економічно значимих підприємств (ТЕЦ, АЕС та ін.);

• 6) вибір методів проведення реклами;

• 7) планування вилучення основних фондів з експлуатації.

Динамічне програмування виникло у 1950-1953рр. на базі робіт Р.Белманом та його співробітників, але перші роботи з використанням основних ідей ДП з'явилися раніше; Массе (Франція, 1946), Вальд (США, 1947), Ероу і Блекуел (США, 1949).

2. Методика розв’язання динамічних задач

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

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

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

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

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

1. Визначається умовний оптимальний ефект на останньому n-му кроці;

2. Виконується умовна оптимізація (n-1)-го, (n-2)-го і т.д. кроків, за рекурентними залежностями:

(1)

де j – номер кроку;

f_j(s,x_j) – значення функції на цьому кроці;

Z_j-1(s,x_j) – вже відомий ефект попередніх кроків.

3. Здійснюється безумовна оптимізація управління у «зворотному» напрямі – від початкового стану до кінцевого для відшукання оптимального плану.