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

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

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

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

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

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

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

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

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

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

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

У загальному вигляді задачу ДПможна сформулювати в такому вигляді. Розглядається керований процес. У результаті керування система (об'єкт керування)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кроках:

Z_n*(s_n-1), Z_n-1*(s_n-2), …, Z₂*(s₁), Z₁*(s₀).

2. Умовних оптимальних керувань на n-ому, (n-1)– ому, … 1-мукроках:

Х_n*(s_n-1), Х_n-1*(s_n-2), …, Х₂*(s₁), Х₁*(s₀).

Цей спосіб відповідає рішенню задачі ДПпо «зворотній схемі» (алгоритм «зворотного прогону»), коли рішення починається з завершального етапу. Помінявшиn-й і 1-й кроки місцями, одержимо «пряму схему» (алгоритм «прямого прогону») рішення задачіДП.

Використовуючи ці послідовності, можна знайти рішення задачі ДП при данихnіs₀. За визначенням (5.1)Z₁*(s₀)– умовний максимум цільової функції заnкроків за умови, що до початку 1-го кроку система була в станіs₀, тобто

Z_max = Z₁*(s₀).

Після цього, використовуючи послідовність умовно оптимальних керувань, при фіксованому s₀одержуємоХ₁* = Х₁*(s₀), потім, з огляду на відсутність післядії, знаходимоs*₁ і підставляємо цей стан у послідовність умовних оптимальних керувань і т.д. Одержуємо:

Х₁* = Х₁*(s₀) à s*₁ è Х*₂ = Х₂*(s₁)à s*₂ è … à s*_n-1 è Х*_n= Х_n*(s_n-1).

Одержуємо оптимальне рішення задачі ДП:

Х*(Х*₁, Х*₂, … Х*_n).

Загальна схема застосування методу ДП має такий вид.

1. Вибрати спосіб розподілу процесу керування на кроки.

2. Визначити параметри стану s_k і змінні керування Х_kна кожному кроці.

3. Записати рівняння станів.

4. Увести цільові функції k-го кроку і сумарну цільову функцію.

5. Ввести в розгляд умовні максимуми (мінімуми) Z_k* (s_k-1)і умовне оптимальне керування наk-ому кроці:Х_k*(s_k-1), k=n, n-1, … 2, 1...

6. Записати основні рівняння (Беллмана) для обчислювальноїсхеми ДП дляZ_n*(s_n-1)іZ_k* (s_k-1),k = n-1, … 2, 1...

7. Вирішити послідовно рівняння (Беллмана) (умовна оптимізація) і отримати дві послідовності функцій:{Z_k* (s_k-1)} і {Х_k*(s_k-1)}.

8. Після виконання умовної оптимізації одержати оптимальне рішення для конкретного початкового стану s₀:

а) Z_max = Z₁*(s₀)і

б) по ланцюжку s₀èХ*₁ à s*₁ èХ*₂ à s*₂ è …è Х*_n-1 à s*_n-1 è Х*_n à s*_n оптимальне керування: Х*(Х*₁, Х*₂, … Х*_n).

Приклад 1.Задача розподілу капіталовкладень.

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

Планується здійснити капіталовкладення в розмірі 3 мільйонів гр.о.

Знайтитакий розподіл капіталовкладень, щоб дістати максимальний прибуток від реалізації всіх проектів.

	1 млн.	2 млн.	3 млн.
1	140	250	350
2	200	320	400
3	300	350	450
4	180	270	330

Рішення. Дану задачу можна вирішити шляхом прямого перебору всіх можливих варіантів рішення. Однак такому способупритаманнінедоліки:

6. для задач великої розмірності потрібний значний обсяг обчислень;

7. інформація, отримана при аналізі окремих проміжних варіантів, ніяк надалі не використовується.

Метод ДП дозволяєв значній мірі позбутися цих недоліків. В основу методу покладена ідея поступової покрокової оптимізації. Дана задача розбивається на 4 етапи. Свідомо неоптимальні рішення, отримані на проміжних етапах, відкидаються. Використання інформації про ряд рішень дозволяє в значній мірі скоротити обсяг обчислень.

Задача вирішується з застосуванням сіткової моделі.

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

I етап. Засоби вкладаються тільки в перший проект.

II етап. Засоби вкладаються в перший і другий проекти разом.

III етап. Засоби вкладаються в перший, другий, третій проекти разом.

IV етап. Засоби вкладаються в усі чотири проекти.

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

Х₁ – обсяг капіталовкладень розподілених на етапі 1;

Х₂ – обсяг капіталовкладень розподілених на етапах 1 і 2;

Х₃ – обсяг капіталовкладень розподілених на етапах 1, 2 і 3;

Х₄ – обсяг капіталовкладень розподілених на етапах 1, 2, 3 і 4.

На кожному етапі знаходиться умовно оптимальнерішення.

Умовно оптимальний виграш для вершини 1 II етапу:

Z₂* (1) = max {0+200; 140+0} = 200.

Дуги другого етапу характеризуються величинами Х₁ іХ₂. РізницяΔХ₂=Х₁-Х₂- інвестиції в другий проект.

Умовно оптимальний виграш для вершини 2 II етапу:

Z₂* (2) = max {0+320; 140+200; 250+0} = 340.

Найкраще рішення для II етапу:

Z₂* (Х₂) = max { Z₁* (Х₁) + П₂}.

Найкраще рішення для III етапу:

Z₃* (Х₃) = max { Z₂* (Х₂) + П₃}.

ΔХ₁ = 0; ΔХ₂ = 1; ΔХ₃ = 1; ΔХ₄ = 1.

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