Лекція 6. Динамічне програмування.Розподілення капіталовкладень.

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

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

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

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

- розробка правил управління запасами, що встановлюють момент поповнення запасів і розмір поповнюючого запасу;

- при розробці принципів календарного планування виробництва і вирівнювання зайнятості в умовах коливного попиту на продукцію;

- при розподілі дефіцитних капітальних вкладень між можливими новими напрямками їхнього використання;

- при складанні календарних планів поточного і капітального ремонту складного устаткування і його заміни;

- при розробці довгострокових правил заміни основних фондів, що вибувають з експлуатації (заміна устаткування);

- оптимізації маршрутів інформації й ін.

У загальному вигляді задачу ДП можна сформулювати в такому вигляді. Розглядається керований процес. У результаті керування система (об'єкт керування) S переводиться з початкового стану s₀ у стан s’. Припустимо, що керування можна розбити на n кроків, тобто рішення приймається послідовно на кожному кроці, а керування, що переводить систему S з початкового стану в кінцевий являє собою сукупність n покрокових управлінь.

Позначимо через Х_k керування на k- ому кроці (k =1, 2,... n). Змінні Х_k задовольняють деяким обмеженням, тобто є припустимими. Нехай Х(Х₁, Х₂, … Х_n) – керування, що переводить систему S зі стану s₀ у стан s’. Позначимо через s_k стан системи після k- го кроку керування. Одержимо послідовність станів s₀, s₁, … s_k-1, s_k, …, s_n-1, s_n = s’...

Показник ефективності розглянутої керованої операції – цільова функція – залежить від початкового стану і керування: Z = F(s₀, X).

Задача покрокової оптимізації (задача ДП) формулюється так: визначити таке припустиме керування Х, що переводить систему S зі стану s₀ у стан s’, при якому цільова функція приймає найбільше (найменше) значення.

Модель ДП. має такі особливості:

1. Задача оптимізації інтерпретується як n- кроковий процес керування.

2. Цільова функція дорівнює сумі цільових функцій кожного кроку.

3. Вибір керування на k- ому кроці залежить тільки від стану системи до цього кроку, не впливає на попередні кроки (немає зворотного зв'язку).

4. Стан s_k після k- го кроку керування залежить тільки від попереднього стану s_k-1 і керування Х_k (відсутність післядії).

5. На кожному кроці керування Х_k залежить від кінцевого числа керуючих перемінних, а стан s_k – від кінцевого числа параметрів.

Замість загальної постановки задачі ДП із фіксованим числом кроків n і початковим станом s₀ розглянемо послідовність задач задаючи послідовно n = 1, 2, … при різних s - однокрокову, двокрокову і т.ін. – використовуючи принцип оптимальності, сформульований Р. Беллманом у 1953 р.

Принцип оптимальності:

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

Уведемо деякі додаткові позначення.

На кожному кроці будь-якого стану системи s_k-1 рішення Х_k потрібно вибирати з урахуванням того, як цей вибір впливає на наступний стан s_k і подальший процес керування, що залежить від s_k, тому що це випливає з принципу оптимальності.

Однак є крок, останній, котрий можна планувати оптимально для будь-якого стану s_n-1, виходячи тільки з міркувань цього кроку.

Розглянемо n -й крок: s_n-1 - стан системи до початку n - го кроку, s_n = s’ - кінцевий стан, Х_n - керування на n -му кроці, f_n(s_n-1, Х_n) - цільова функція (виграш) n - го кроку.

Відповідно до принципу оптимальності, Х_n потрібно вибирати так, щоб для будь-яких станів s_n-1 одержати максимум (мінімум) цільової функції на цьому кроці.

Позначимо через Z*_n (s_n-1) максимум цільової функції - показника ефективності n -го кроку за умови, що до початку останнього кроку система S була в довільному стані s_n-1, а на останньому кроці керування було оптимальним.

Z*_n (s_n-1) називається умовним максимумом цільової функції на n -му кроці. Очевидно, що

Z*_n (s_n-1) = max f_n(s_n-1, Х_n) (5.1)

{Х_n}

Максимізація ведеться по всіх припустимих керуваннях Х_n.

Рішення Х_n, при якому досягається Z*_n (s_n-1), також залежить від s_n-1 і називається умовним оптимальним керуванням на n -му кроці. Воно позначається через Х*_n (s_n-1).

Вирішивши одномірну задачу локальної оптимізації по рівнянню (5.1), знайдемо для всіх можливих станів s_n-1 дві функції: Z*_n (s_n-1) і Х*_n (s_n-1).

Розглянемо тепер двокрокову задачу: приєднаємо до n -го кроку (n-1) -й.

Для будь-яких станів s_n-2, довільних керувань Х_n-1 і оптимальному керуванні на n -му кроці значення цільової функції на двох останніх кроках дорівнює:

f_n-1(s_n-2, Х_n-1) + Z*_n (s_n-1) (5.2)

Відповідно до принципу оптимальності для будь-яких s_n-2 рішення потрібно вибирати так, щоб воно разом з оптимальним керуванням на останньому (n -му) кроці приводило б до максимуму цільової функції на двох останніх кроках. Отже, потрібно знайти максимум виразу (5.2) по всіх припустимих керуваннях Х_n-1. Максимум цієї суми залежить від s_n-2, позначається через Z*_n-1 (s_n-2) і називається умовним максимумом цільової функції при оптимальному керуванні на двох останніх кроках. Відповідне керування Х_n-1 на (n-1) -му кроці позначається через Х*_n-1 (s_n-2) і називається умовним оптимальним керуванням на (n-1) -му кроці.

Z*_n-1 (s_n-2) = max {f_n-1 (s_n-2, Х_n-1) + Z*_n (s_n-1)} (5.3)

{Х_n-1}

У результаті максимізації тільки за однією змінною відповідно до рівняння (5.3) знову виходять дві функції: Z*_n-1 (s_n-2) і Х*_n-1 (s_n-2).

Далі розглядається трикрокова задача: до двох останніх кроків приєднується
(n - 2) -й і т.д.

Позначимо через Z*_k (s_k-1) умовний максимум цільової функції, отриманої при оптимальному керуванні на n-k+1 кроках, починаючи з к -го до кінця, за умови, що до початку к -го кроку система знаходився в стані s_k-1. Фактично ця функція дорівнює

n

Z*_k (s_k-1) = max ∑ f_i (s_i-1, Х_i)

{(x_k, …x_n)} i=k

Тоді

n

Z*_k+1 (s_k) = max ∑ f_i (s_i-1, Х_i)

{(x_k+1, …x_n)} i=k+1

Мал. 5.1.

Цільова функція на n-k останніх кроках при довільному керуванні Х_k на k -му кроці й оптимальному керуванні на наступних n-k кроках дорівнює

f_k(s_k-1, Х_k) + Z*_k+1 (s_k)

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

Z*_k (s_k-1) = max {f_k (s_k-1, Х_k) + Z*_k+1 (s_k)} (5.4)

{Х_k}

k = n-1, n-2, … 2, 1.

Рівняння (5.4) називається рівнянням Беллмана.

Керування Х_k на k-м кроці, при якому досягається максимум у (5.4), позначається через Х*_k (s_k-1) і називається умовним оптимальним керуванням на k -му кроці.

Якщо з (5.1) знайти Z_n*(s_n-1), то при k = n- 1 з (5.4) можна визначити вираз для
Z_n-1*(s_n-2) і відповідні Х*_n-1 (s_n-2) вирішивши задачу максимізації для всіх можливих значень s_n-2. Після цього з Z_n-1*(s_n-2) з використанням (5.4) знаходяться рівняння станів.

Процес рішення рівнянь (5.1) і (5.4) називається умовною оптимізацією.

У результаті умовної оптимізації виходять дві послідовності.

1. Умовних максимумів цільової функції на останньому, на двох останніх, на …, на n кроках: