x = |
1 |
= |
25 42 |
= 25, |
42 |
|
|
|
|
|
|
|
y = |
2 |
= |
17 42 |
=17, |
|
42 |
|
|
|
|
|
|
|
λ = |
3 |
= |
|
383 42 |
= 383. |
|
|
|
|
|
42 |
|
|
|
Знаходимо частинні похідні другого порядку та формуємо матрицю H (x, y).
∂2 L |
=16; |
∂ |
2 L |
= 24; |
|
|
∂2 L |
= −1; |
∂2 L |
= −1. |
|
|
∂x2 |
∂y2 |
|
|
∂x∂y |
∂y∂x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
H (x, y)= 16 −1 . |
|
|
|
|
|
|
|
|
|
−1 24 |
|
|
|
|
H1 (x, y)=16; |
|
H2 (x, y)= |
|
16 |
−1 |
|
=16 24 −1 = 383. |
|
|
|
|
|
|
|
|
|
|
|
|
|
−1 |
24 |
|
|
|
|
|
|
Зважаючи на те, що |
|
H1 (x, y) |
|
=16 > 0, |
H2 (x, y)= 383 > 0, |
|
|
стверджуємо: знайдена точка екстремуму з координатами |
(25;17) |
є |
точкою мінімуму функції.
Отже, компанія понесе мінімальні сумарні затрати, якщо випускатиме продукції виду А – 25 одиниць, продукції виду В – 17 од. Ці затрати становитимуть:
Zmin = Z(25;17) =8 252 −25 17+12 172 =5000−425+3468=8043 (грн.).♦
6.4. Питання для самоконтролю
1.Запишіть загальну математичну модель задачі нелінійного програмування.
2.Які труднощі виникають при розв’язуванні задач нелінійного програмування?
3.Які методи нелінійного програмування ви знаєте?
4.В чому полягає ідея методу Лагранжа розв’язування задач нелінійного програмування?
5.Який вигляд має функція Лагранжа?
6.Сформулюйте необхідні і достатні умови існування сідлової точки для диференційованої функції.
7.Яка функція називається опуклою (вгнутою)?
8.Сформулюйте теорему Куна-Таккера.
9.Запишіть математичну модель задачі квадратичного програмування і охарактеризуйте особливості її розв’язування.
10.Поясніть економічний зміст множників Лагранжа.
211
Розділ 7. Динамічне програмування
7.1. Постановка задачі динамічного програмування
Динамічне програмування – це математичний апарат, який дозволяє швидко знаходити оптимальне рішення у випадку, коли ситуація, що вивчається, має велику кількість варіантів поведінки, які дають різні результати і серед них треба вибрати найкращий. Динамічне програмування використовують при розв’язуванні певного типу задач шляхом їх розкладу на менші та простіші підзадачі. Розв’язок такого виду задачі можна знайти шляхом перебору всіх можливих варіантів і вибору серед них найкращого, але в більшості випадків такий перебір є досить трудомістким. Тому процес прийняття оптимального рішення розбивається на етапи (кроки) і досліджується з допомогою методу динамічного програмування.
Динамічне програмування використовується для розв’язання таких задач: розподіл дефіцитних капітальних вкладень між новими напрямками їх використання; розробка сценаріїв управління попитом чи запасами; розробка принципів календарного планування виробництва і вирівнювання зайнятості в умовах нестабільного попиту на продукцію; складання календарних планів поточного та капітального ремонту устаткування та його заміни; формування послідовності розвитку комерційної операції і т.д.
Розглянемо деякий керований процес. Припустимо, що керування можна розбити на n кроків, тобто рішення приймається послідовно на кожному кроці, а процедура, яка переводить систему з початкового стану в кінцевий, є сукупністю n покрокових керувань. В результаті керування система переходить із стану S0 в Sn.
Позначимо через xk Uk |
керування на k-му кроці (k = |
|
), де |
1, n |
Uk – множина допустимих керувань на k-му кроці. |
Нехай x = (x1, x2 ,..., xn ) – |
керування, яке переводить систему з |
стану S0 в Sn. Позначимо через Sk стан системи після k-го кроку керування. Отримуємо послідовність станів S0 , S1,..., Sk −1, Sk , Sk+1,..., Sn
(рис.7.1.1).
S0 |
x1 |
S1 |
x2 |
… xk-1 |
Sk-1 |
xk |
Sk |
xk+1… xn-1 |
Sn-1 |
Sn |
|
|
|
|
|
xn |
Рисунок 7.1.1. Схематичне зображення процесу керування
Показник ефективності процесу керування залежить від
початкового стану системи і керованої змінної: |
|
Z = F (S0 , x) . |
(7.1) |
Власне, задача динамічного програмування |
формулюється |
таким чином: знайти таке значення керованої змінної x* , яке переводить систему з початкового стану S0 в кінцевий Sn, при якому цільова функція (7.1) набуває найбільшого (найменшого) значення.
Розглянемо характерні особливості математичної моделі динамічного програмування:
1)задача оптимізації формулюється як скінчений багатокроковий процес управління;
2)цільова функція (7.1) є адитивною від показника ефективності кожного кроку, тобто виграш від всієї операції складається з виграшів, отриманих на кожному кроці.
n |
|
Z = F(S0 , x) = ∑Fk (Sk −1, xk ), |
(7.2) |
k =1
де Fk (Sk −1, xk ) = Zk – показник ефективності на k-му кроці;
3)вибір керування хk на кожному кроці залежить тільки від стану системи до цього кроку і не впливає на попередні кроки (немає зворотного зв’язку);
4)стан системи Sk після кожного кроку керування залежить тільки від попереднього стану системи Sk-1 і керуючої дії хk на k-му кроці та не залежить від попередніх станів системи і керувань (відсутність післядії):
Sk =ϕk (Sk −1, xk ), k = |
|
, |
(7.3) |
1, n |
де ϕk – оператор переходу;
5)на кожному кроці керування хk залежить від скінченого числа керованих змінних, а стан системи Sk залежить від скінченого числа параметрів;
6)оптимальним керуванням є вектор x* , який знаходиться
шляхом послідовних оптимальних покрокових керувань: x* = (x1* , x2* ,..., xk* ,..., xn* ), кількість яких і визначає число кроків задачі.
7.2.Методи розв’язування задач динамічного програмування
Нехай процес оптимізації розбитий на n кроків. На кожному кроці потрібно визначити два типи змінних – змінну стану S та змінну керування x. Змінна стану S визначає, в яких станах може бути система на k-му кроці. Залежно від S на цьому кроці можна використати деякі керування, які характеризуються змінною x. Використання керування x на k-му кроці дає деякий результат fk (S, xk ) і переводить систему в деякий новий стан S′(S, xk ) . Для
кожного можливого стану на k-му кроці (з усіх можливих керувань) вибирається таке керування xk* , щоб результат, який отримаємо з k-го
по n-ий крок був оптимальним. Числова характеристика цього результату називається функцією Белмана Fk (S) та залежить від
номера кроку k і стану системи S. Отже, сутність принципу оптимальності Белмана полягає в тому, що яким би не був стан системи в результаті певної кількості кроків, на найближчому кроці керування потрібно вибирати так, щоб воно разом з оптимальним керуванням на всіх наступних кроках приводило до найкращого виграшу.
Весь розв’язок задачі розбивається на два етапи. На першому етапі знаходять функцію Белмана й оптимальне керування для всіх можливих станів на кожному кроці, починаючи з першого. На останньому n-му кроці знайти оптимальне керування і значення функції Белмана Fn (S) нескладно, оскільки Fn (S) = max{ fk (S, xn )}, де
максимум знаходять за всіма можливими значеннями xn.
Подальші розрахунки проводять згідно з рекурентним співвідношенням, яке пов’язує функцію Белмана на кожному кроці з тією ж функцією, обчисленою на попередньому кроці:
Fk |
(S) = max{ fk (S′, xk ) + Fk −1 (S, xk )}. |
(7.4) |
|
xk |
|
Цей максимум (чи мінімум) знаходиться за всіма можливими для k і S значеннями керованої змінної хk.
Після того, як функція Белмана і відповідне оптимальне керування знайдені для всіх кроків з першого до n-го (на першому кроці k=1 стан системи рівний її початковому стану S0), виконуємо другий етап розв’язання задачі згідно з алгоритмом зворотної прогонки. Знаючи оптимальне керування на n-му кроці xn, ми можемо
шукати оптимальне керування на (n–1) кроці доти, доки не дійдемо до першого.
Таким чином, в процесі оптимізації керування методом динамічного програмування багатокроковий процес «проходиться» двічі: перший раз – з початку до кінця, в результаті чого знаходимо умовні оптимальні керування і умовні оптимальні виграші; другий раз – від кінця до початку, коли нам залишається тільки «прочитати» вже готове керування, що складається з оптимальних покрокових управлінь.
7.3. Прикладні моделі динамічного програмування
Прикладне застосування методу динамічного програмування розглянемо на прикладі двох важливих економічних задач: оптимального розподілу фінансових ресурсів між інвестиційними проектами та оптимальної заміни устаткування.
7.3.1.Модель оптимального розподілу фінансових ресурсів між інвестиційними проектами
Розглянемо виробничу ситуацію, пов’язану з аналізом пропозицій відносно збільшення виробничих потужностей підприємств фірми. Для можливого розширення потужностей фірма виділяє фінансові ресурси розміром х, які необхідно розділити між проектами в такий спосіб, щоб одержати максимально можливий сумарний приріст випуску продукції.
Позначимо через хі – розмір інвестицій, виділених під і–ий проект (i =1,n), де і – індекс проекту. Отже, має місце рівність:
x1 + x2 +... + xn = x . |
(7.5) |
На основі попереднього аналізу встановлено, що |
приріст |
продукції внаслідок реалізації і–го проекту задається функцією fi (xi ) . Тоді сумарний приріст продукції фірми становитиме:
|
|
|
n |
|
|
|
|
F(x1, x2 ,...xn ) = ∑ fi (xi ). |
(7.6) |
|
|
|
i =1 |
|
Отже, наша |
задача полягає у заходженні таких значень |
xi ≥ 0 (i = |
|
, які |
задовольняють (7.5) і забезпечують |
максимум |
1,n) |
функції (7.6). |
|
|
Позначимо максимальний сумарний приріст продукції, одержаний при розподілі інвестицій розміром х для перших k проектів, через Fk (x), причому
x = x1 + x2 +... + xk , xi ≥ 0, i =1, k .
Для визначення функцій Fk (x) побудуємо рекурентне рівняння за допомогою кількох етапів.
Почнемо з розподілу наявних засобів для першого проекту. Знайдемо максимальне значення цього приросту за формулою:
F1 (x)= max f1 (x) = f1 (x).
0≤x1≤x
Переходимо до другого етапу розрахунків. Нам необхідно знайти оптимальний варіант розподілу інвестицій розміром х за умови, що вони виділені першому та другому проекту. Тут слід враховувати отриману найкращу ефективність для першого проекту. Припустимо, що на другий проект виділені інвестиції розміром х2, які дають f2(х2) приросту продукції, а залишок (х–х2) виділяється першому проекту, який дає F1(х–х2) приросту. Тоді максимальний приріст продукції, отриманий від оптимального розподілу всіх інвестицій між першим і другим проектами буде:
F2 (x)= max f2 (x2 )+ F1 (x − x2 ) .
0≤x2 ≤x
Переходимо до третього етапу, на якому необхідно знайти оптимальний варіант розподілу інвестицій за умови, що вони виділяються першим трьом проектам разом.
Нехай на третій проект виділено х3 одиниць коштів, які в свою чергу даватимуть для нього приріст продукції розміром f3 (x3 ).
Наявний залишок (x − x3 ) надамо першому та другому проектам, які при оптимальному розподілі дають приріст F2 (x − x3 ) грошових
одиниць. Отже, максимальний ефект, який отримаємо від розподілу інвестицій між першими трьома проектами буде:
F3 (x)= max f3 (x3 )+ F2 (x − x3 ) .
0≤x3≤x
Розглянемо загальний випадок розподілу інвестицій для перших k проектів. Нехай k–му проекту виділено хk одиниць інвестицій, які забезпечать йому приріст продукції розміром fk(хk). Залишок інвестицій (х–хk) віддамо першим (k–1) проектам і вони при оптимальному розподілі принесуть фірмі Fk-1(х–хk) приросту
продукції. При цьому фірма отримає сумарний приріст продукції рівний:
F |
(x)= max f |
k |
(x |
)+ F |
(x − x |
) . |
(7.7) |
k |
0≤x ≤x |
k |
k −1 |
k |
|
|
|
k |
|
|
|
|
|
|
Отже, ми отримали рекурентне співвідношення (7.7), яке представляє собою рівняння Белмана для задачі (7.5) – (7.6).
Приклад 7.1. Для збільшення випуску продукції фірма може виділити інвестиції розміром х=200 млн. грн. своїм чотирьом підприємствам на певний період. Приріст продукції, який може отримати кожне підприємство при виділенні йому відповідних інвестицій, представлений у таблиці 7.1. Потрібно знайти оптимальний варіант вкладів інвестицій і дати економічний аналіз ефективності проведених заходів.
|
|
|
|
|
Таблиця 7.1 |
Розмір інвестицій, |
|
Приріст продукції, млн.грн. |
млн. грн., х |
f1(х) |
|
f2(х) |
f3(х) |
|
f4(х) |
0 |
0 |
|
0 |
0 |
|
0 |
50 |
45 |
|
60 |
55 |
|
70 |
100 |
110 |
|
90 |
85 |
|
105 |
150 |
160 |
|
165 |
170 |
|
155 |
200 |
210 |
|
215 |
225 |
|
230 |
♦ Розв’язування.
Для знаходження оптимального варіанта розподілу наявних інвестицій використаємо функціональне рівняння (7.7). Розрахунки проведемо в чотири етапи. Насамперед знайдемо умовно оптимальне значення варіанта розподілу виділених інвестицій для першого підприємства. Вважаємо, що підприємство – це окремий проект.
Для прискорення розрахунків уcі значення Fk(xk) на наступних етапах представимо таблицею 7.2.
|
|
|
|
Таблиця 7.2 |
Розмір інвестицій, |
Значення приросту продукції, млн. грн. |
млн. грн., х |
F1(х) |
F2(х) |
F3(х) |
|
F4(х) |
0 |
0 |
0 |
0 |
|
- |
50 |
45 |
60 |
60 |
|
- |
100 |
110 |
110 |
115 |
|
- |
150 |
160 |
170 |
170 |
|
- |
200 |
210 |
220 |
230 |
|
240 |
Оскільки |
F |
(x) = max f |
(x) |
= f |
(x), то переходимо до |
|
1 |
0≤x |
≤x |
1 |
|
1 |
|
|
|
1 |
|
|
|
|
|
визначення умовно оптимального значення розподілу інвестицій, виділених двом першим підприємствам разом. Для цього використаємо формулу:
F2 (x)= max f2 (x2 )+ F1 (x − x2 ) ,
0≤x2 ≤x
у якій надамо х2 усіх можливих значень (0; 50; 100; 150; 200).
F2 (0) = 0 .
Розглянемо випадок розподілу інвестицій розміром 50 млн. грн. Отримаємо:
F (50) =max f2 |
(0) +F1(50) |
=0+45 |
=45 |
=60. |
2 |
|
(50) +F1(0) |
=60+0 |
=60 |
|
|
|
|
f2 |
|
|
Максимальне значення приросту продукції від вкладення 50 млн. грн. в перших два підприємства одержано за рахунок другого члена, тобто f2(50)+F1(0). Це означає, що другому підприємству слід виділити 50 млн. грн., а першому не надавати коштів.
Аналогічно проводимо обчислення F2(x) для інших значень вкладень (100; 150; 200).
Так, при виділенні першим двом підприємствам 100 млн. грн. маємо:
|
f |
2 |
(0) +F (100) |
=0 +110 =110 |
|
|
|
|
|
1 |
|
|
|
|
F2 |
|
|
|
|
|
=110. |
(100) =max f2 |
(50) +F1(50) =60+45 =105 |
|
f |
2 |
(100) + F (0) |
=90+0 =90 |
|
|
|
|
|
1 |
|
|
|
|
Одержаний результат показує, що першому підприємству інвестиції потрібно виділити розміром 100 млн. грн., а другому – коштів не давати. Приріст продукції при цьому буде 110 млн. грн.
|
f2 (0) + F1 (150) |
= 0 +160 =160 |
|
|
|
f |
2 |
(50) + F (100) |
= 60 +110 =170 |
|
F2 |
|
|
1 |
|
|
|
|
=170. |
(150) = max |
|
|
|
|
|
|
|
|
|
|
|
+ F1 |
|
|
|
|
f2 |
(100) |
(50) |
= 90 + 45 =135 |
|
|
|
f |
2 |
(150) |
+ F |
(0) |
=165 + 0 =165 |
|
|
|
|
|
1 |
|
|
|
|
|
При розподілі 150 млн. грн. доцільно 100 млн. грн. дати першому підприємству, а 50 – другому.
Проведемо аналогічні міркування для розподілу 200 млн. грн. Записуємо:
|
f2 |
(0) + F1 (200) = 0 + 210 = 210 |
|
|
f |
2 |
(50) + F (150) = 60 +160 |
= 220 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F2 |
(200) = max f2 |
(100) |
+ F1 |
(100) = 90 +110 = 200 = 220 . |
|
f |
|
(150) |
+ F |
(50) =165 + 45 |
= 210 |
|
|
|
2 |
(200) |
1 |
|
(0) = 215 + 0 = |
215 |
|
|
|
f |
2 |
+ F |
|
|
|
|
|
|
1 |
|
|
|
|
Згідно з виразом f2(50)+F1(150), який забезпечує максимальний приріст продукції обсягом 220 млн. грн., необхідно 150 млн. грн. віддати першому підприємству, а 50 млн. грн. – другому.
Перейдемо до третього етапу, в якому потрібно визначити оптимальний варіант розподілу інвестицій першим трьом підприємствам разом. Для розрахунку значень F3(х) використаємо
формулу: |
F3 (x) = max [f3 (x3 ) + F2 (x − x3 )]. |
|
|
|
|
|
0≤x3 ≤x |
|
|
|
Надаючи x3=(0; 100; 200; 300; 400; 500), відповідно одержимо: |
|
|
|
|
F3 (0) = 0 . |
|
|
|
f |
3 |
(0) + F (50) |
= 0 + 60 |
= 60 |
F3 |
(50) = max |
|
2 |
|
|
= 60 . |
|
|
(50) + F2 (0) |
|
|
|
f3 |
= 55 + 0 = 55 |
Бачимо, що вигідно всі 50 млн. грн. віддати першим двом підприємствам, а третьому не давати коштів. Максимальний приріст продукції буде 60 млн. грн.
Виконаємо відповідні обчислення при х3=100:
|
|
(0) + F2 (100) |
= 0 +110 =110 |
|
|
F3 |
f3 |
|
|
(100) = max f3 |
(50) + F2 (50) = 55 + 60 =115 |
=115. |
|
|
|
|
|
|
|
|
|
(100) + F2 (0) |
= 85 + 0 = 85 |
|
|
f3 |
|
|
Максимальний ефект дає вираз f3(50)+F2(50), а це означає, що 100 млн. грн. між першими трьома підприємствами потрібно розподілити таким чином: першим двом підприємствам віддати 50
млн. грн. і третьому 50 млн. грн. Приріст продукції становитиме 115 млн. грн.
Обчислимо F3 (150):
|
f |
3 |
(0) + F (150) = 0 +170 =170 |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
F3 |
f3 |
(50) + F2 (100) = 55 +110 =165 |
=170 . |
(150) = max |
f |
|
(100) |
+ F (50) = 85 + 60 =145 |
|
|
|
3 |
|
|
|
|
|
2 |
|
|
|
f |
3 |
(150) |
+ F (0) =170 + 0 =170 |
|
|
|
|
|
|
2 |
|
|
|
При розподілі 150 млн. грн. ми отримали два оптимальних варіанти:
1)між першими двома підприємствами розподілити 150 млн. грн., а третьому не надавати коштів;
2)150 млн. грн. віддати третьому підприємству, а першим двом не надавати коштів.
Вобох випадках максимальний приріст продукції становитиме 170 млн. грн.
На завершення цього етапу проведемо аналіз розподілу 200 млн. грн. між першими трьома підприємствами:
|
f3 |
(0) + F2 (200) = 0 + 220 = 220 |
|
|
|
f |
3 |
(50) + F (150) = 55 +170 |
= 225 |
|
|
|
|
|
2 |
|
|
|
|
|
F3 |
|
|
(100) |
+ F2 |
|
|
|
|
= 230 . |
(200) = max f3 |
(100) = 85 +110 =195 |
|
f |
3 |
(150) |
+ F |
(50) =170 + 60 |
= 230 |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f |
3 |
(200) |
+ F |
(0) = 225 + 0 = |
225 |
|
|
|
|
|
|
2 |
|
|
|
|
|
Ми бачимо, що найбільший приріст продукції 230 млн. грн. отримаємо, якщо 50 млн. грн. розподілимо між першими двома підприємствами, а в третє інвестуємо 150 млн. грн.
Переходимо до четвертого етапу, в якому необхідно проаналізувати ефективність розподілу наявних інвестицій уже між чотирма підприємствами фірми. Поклавши у (7.7) k=4, маємо рекурентне рівняння:
F4 (x)= max f4 (x4 )+ F3 (x − x4 ) .
0<x4 <x
