6.2. Знаходження розв'язку задач методом динамічного програмування

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

Будемо вважати, що стан розглянутої системи Б на к-му кроці

(к = 1,п) визначається сукупності чисел X® = (х/к), х2(к|, х„(к|), які отримані в результаті реалізації керування иь що забезпечило перехід системи Б зі стану Х^-1' у стан Х**'. При цьому будемо припускати, що стан Х(к|, у який перейшла система в, залежить від даного стану X11-1' і обраного керування і не залежить від того, яким чином система Б прийшла в стан Х^"1'.

Далі будемо вважати, що якщо в результаті реалізації к-го кроку забезпечені певний дохід або виграш, що також залежать від вихідного стану системи Х(к-Г| і обраного керування ик і рівний \Ук(Х(к-1), ик), то загальний дохід або виграш за п кроків становить

^ = Х ^(Х(і-1>,ні). (6.4)

Таким чином, ми сформулювали дві умови, яким повинна задовольняти розглянута задача динамічного програмування. Першу умову звичайно називають умовою відсутності наслідку, а другу -умовою адитивності цільової функції задачі.

Виконання для задачі динамічного програмування першої умови дозволяє сформулювати для неї принцип оптимальності Беллмана. Перш ніж зробити це, дамо визначення оптимальної стратеги керування. Під такою стратегією будемо розуміти сукупність керувань и» = (ні*, иг», її,,»), У результаті реалізації яких система Б за п кроків переходить із початкового стану Х<0> у кінцеве X® і при цьому функція (6.4) приймає найбільше значення.

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

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

урахуванням   цього   вибрати   керування    «„,   що забезпечує

максимальне значення функції \УП(ХІП~1>, ііп). Таке керування и„,

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

Щоб це можна було здійснити практично, необхідно дати математичне формулювання принципу оптимальності. Для цього введемо  деякі  додаткові  позначення.  Позначимо  через Рп(Х°)максимальний дохід, одержуваний за п кроків при переході системи 8 з початкового стану Х10) у кінцевий стан Х<п> при реалізації оптимальної стратегії керування II = (иі, и2,и„), а через Р„_1((Х<1:)) -максимальний дохід, який можливо одержати при переході зі стану Х**' у кінцевий стан Х*п) при оптимальній стратегії керування на останніх п - 1с кроках. Тоді

Рп(х(0)) = тахК(х(0)))и1) + ... + №п(х(п-1>))ип)]

(6.5)

^.^х^^тахК^Сх^и^О+Р^Сх^1»)], к=0^П

(6.6)

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

Покладаючи к=п-І у рекурентному співвідношенні (6.6), одержуємо наступне функціональне рівняння:

Р1(х<пІ))=тахК(х<п"),и„) + Р0(х<п))]

(6.7)

У цьому рівнянні Р0(Х(п)) будемо вважати відомим. Використовуючи  тепер  рівняння     (6.7)  і розглядаючи всілякі

припустимі стани системи Б на (п - 1)-м кроці Х\"~1), А"^"-1', Хт'^ у •■• знаходимо умовні оптимальні рішення

.....и:(хГ>\...

і відповідні значення функції (6.7)

дЧх1(я-1>),дЧх«''-1)).....і^рг^),...

Таким чином, на п-м кроці знаходимо умовно оптимальне керування при будь-якому припустимому стані системи 5 після (п-І)-то кроку. Іншими словами, у якому би стані система не виявилася після (п-І)-то кроку, нам уже відомо, яке варто прийняти рішення на п-м кроці. Відомо також і відповідне значення функції (6.7).

Переходимо тепер до розгляду функціонального керування при к=п-2:

Р2(х'л1)) = тах[№п,(х^2'),ип,) + Р1(х'л1))] (6.8)

Для того, щоб знайти значення Т2 для всіх припустимих значень

Х<п " 2), мабуть, необхідно знати «'п.1(х("-2)), иа4) і Р,(х(п1)). Що

стосується значень ЕДх'""1'), то ми їх уже визначили. Тому потрібно

зробити  обчислення для   «,п.1(х'п"2)), и^)   при деякому наборі

припустимих значень х<п"2> і відповідних керувань ип1. Ці обчислення

дозволять визначити умовно оптимальне керування ы°_, для кожного

х'""2). Кожне з таких керувань разом із уже обраним керуванням на останньому кроці забезпечує максимальне значення доходу на двох останніх кроках.

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

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

Щоб знайти оптимальну стратегію керування, тобто визначити оптимальний розв'язок задачі, потрібно тепер пройти всю послідовність кроків, тільки цього разу від початку до кінця. А саме:на першому кроці як оптимальне керування ил візьмемо знайдене умовно оптимальне керування . На другому кроці знайдемо стан X,*, у який переводить систему керування и*. Цей стан визначає знайдене умовно оптимальне керування , що тепер будемо вважати оптимальним. Знаючи и"2, знаходимо Х*2, а виходить, визначаємо щ

й т.д. У результаті цього знаходимо розв'язок задачі, тобто максимально можливий дохід і оптимальну стратегію керування II*, що включає оптимальні керування на окремих кроках: и* = (иі*, л^*, ...,и»*).

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

Використовуючи методи динамічного програмування, знайдемо розв'язання для окремих випадків задачі про використання обладнання й задачі про розподіл ресурсів.

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

Таблиця 6.1

 

 

Час ^ протягом якого використовується обладнання (іюків)

0

1

2

3

4

5

Щорічний випуск продукції Я (І) у

вартісному вираженні (мли. грн.)

80

75

65

60

60

55

Щорічні витрати Z(x), пов'язані з заміною і ремонтом обладнання (млн. грн.)

20

25

30

35

45

55

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

Розв 'язання. Цю задачу можна розглядати як задачу динамічного програмування, у якій в якості системи 5 виступає обладнання. Стан цієї системи визначаються фактичним часом використання обладнання (його віком), тобто описуються єдиним параметром т.

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

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

Для визначення умовних оптимальних розв'язків спочатку необхідно скласти функціональне рівняння Беллмана.

Тому що ми припустили, що до початку к — то року (£=1,5) може прийматися тільки одне із двох рішень — заміняти або не заміняти обладнання, то прибуток підприємства за к — й рік складе

де г" - вік обладнання до початку к-то року (£=1,5); ик-керування, реалізоване до початку к — го року; с„ - вартість нового обладнання.

Таким чином, у цьому випадку рівняння Беллмана має вигляд

Використовуючи тепер рівняння (6.9), приступаємо до розв'язання вихідної задачі. І починаємо з визначення умовно оптимального керування (рішення) для останнього (5-го) року п'ятирічки, у зв'язку із чим знаходимо множину припустимих станів обладнання на початок даного року п'ятирічки. Тому що до початку п'ятирічки є нове обладнання = 0), то вік обладнання до початку 5-го року може становити 1, 2, 3 і 4 роки. Тому припустимі стани системи на даний період часу такі:

г-,<5' = 1;г^5' = 2;тр = 3;г^5* = 4.Для кожного із цих станів знайдемо

умовно оптимальне рішення й відповідне значення функції Р$(т <5>). Використовуючи рівняння (6.9) і співвідношення Р6(т '&))=0 (тому що розглядається останній рік розрахункового періоду), одержуємо

Д(г<*>)-2(г<*>)«ри

д(г<*> = о)- г(тік) = о)- С„ при и

 

(6.9)

 

= тах-

д(г^ = о)-г(г<5> = о)-сл.

(6.10)

Підставляючи тепер у формулу    (6.10) замість  г15' його значення, що дорівнює 1, і з огляду на дані табл. 4.1, знаходимотах

[75-25 = тах^

[80-20-40

я(т{5)=о)-г{т{5)=о)-сп.

= 50,м') =Мі

Виходить, умовно оптимальне рішення в цьому випадку є «?.

Проведемо аналогічні обчислення для інших припустимих станів обладнання до початку 5-го року п'ятирічки:

^(г?')=тах(65-3°       1 = 35У=«і; 5У 2 '        [80-20-40 / 1

„і м\ [60-35 п 3 ' [80-20-40

= 25У =«,;

5У 4 '        [80-20-40 / 2 Отримані результати обчислень зводимо в табл. 6.2.

Таблиця 6.2

Вік обладнання И51

Знач( ння функції Т5(т

Умовно оптимальне

(років)

1'*) (млн. грн.)

рішення и°

1

50

І1

2

35

іі

3

25

Іі

4

20

и2

Розглянемо тепер можливі стани обладнання до початку 4-року п'ятирічки. Очевидно, припустимими станами є г,'4' = 1;г^4' = 2;г3'4' = 3. Для кожного з них визначаємо умовно оптимальне рішення й відповідне значення функції І-'Д г <4)). Для цьоговикористаємо рівняння (6.9) , а також дані табл. 4.1 і 4.2. Так, зокрема, для т*4) = 1 маємо

ДГі '   ™\Р.(^ = о)-і{^ =о)-сп +г^=і)

[75-25 + 35 [80-20-40 + 50

Аналогічно знаходимо = 85,і/ =щ.

, (4Іч [65-30+25

^ = 70,«и =«,; [80-20-40 + 50 ] 2

І и\\        [65-35 + 20      ] , п 3 ;        [80-20-40 + 50 | 2

Отримані результати обчислень записуємо в табл. 6.3.

Таблиця 6.3

В ік обладнання т14)

' іначення функції

У ловно оптимальне

(років)

Г4(ї-<4)) (млн. грн.)

рішення н°

1

85

Іі

2

70

І2

3

70

Щ

Визначимо тепер умовно оптимальне рішення для кожного із припустимих станів обладнання до початку 3-го року п'ятирічки.

Очевидно, такими станами є г/3' =1, Гг13) = 2. А тому, відповідно до рівняння (6.9), маємо

АТі }~ =о)-     =о)- ся +     =і) Г

Використовуючи дані табл. 6.1 та 6.3, одержуємо / м\        [75-25 + 70

тах

[80 - 20 - 40 + 85

65-30+70 80-20-40 + 85

= \20,и"=щ;

= 105У =и.

З останнього виразу видно, що якщо до початку 3-го року п'ятирічки вік обладнання становить два роки, те незалежно від того, чи буде ухвалене рішення і^або и2, величина прибутку виявиться однією й тією ж. Це означає, що як умовно оптимальне рішення можна взяти кожне, наприклад і2. Отримані значення для і*і(г 13>) і відповідні умовно

Таблиця 6.4

Вік обладнання И3'

Значення функції

Умовно оптимальне

(років)

У£т {гу) (млн. грн.)

рішення и*

1

120

Іі

2

105

и2

Нарешті, розглянемо припустимі стани обладнання до початку 2-го року п'ятирічки. Очевидно, на даний момент часу вік обладнання може бути дорівнює тільки лише одного року. Тому має бутипорівняти лише два можливих рішення: зберегти обладнання або зробити заміну. Аналіз такого порівняння характеризується даними табл. 6.5.

Таблиця 6.5

Вік обладнання т<2>

■ їначення функції

У мовно оптимальне

(років)

і'&Т (2))(млн. грн.)

рішення и°

1

155

Іі

Відповідно до умови, до початку п'ятирічки встановлене нове обладнання (г/1* =0). Тому проблеми вибору між збереженням і заміною обладнання не існує: обладнання варто зберегти. Виходить, умовно оптимальним рішенням є щ, а значення функції

= 80-20 + 155 = 215.

Таким чином, максимальний прибуток підприємства може бути рівним 215 млн. грн. Він відповідає оптимальному плану заміни обладнання, що випливає з даних, наведених у табл. 6.5, 6.4, 6.3 і 6.2, тобто в результаті реалізації другого етапу обчислювального процесу, що складає в проходженні всіх розглянутих кроків з початку 1-го до початку 5-го року п'ятирічки. Для 1-го року п'ятирічки рішення єдине - варто зберегти обладнання. Виходить, вік обладнання до початку 2-го року п'ятирічки дорівнює одного року. Тоді відповідно до даних табл. 6.5 оптимальним рішенням для 2-го року п'ятирічки є рішення про збереження обладнання. Реалізація такого рішення приводить до того, що вік обладнання до початку 3-го року п'ятирічки стає рівним двом рокам. При такому віці (див. табл. 6.4) обладнання в 3-м року п'ятирічки варто замінити. Після заміни обладнання його вік до початку 4-го року п'ятирічки складе один рік. Як видно з табл. 6.3, при такому віці обладнання його міняти не слід. Тому вік обладнання допочатку 5-го року п'ятирічки складе два роки, тобто міняти обладнання недоцільно (табл. 6.2).

Отже,   виходить   наступний   оптимальний    план заміни обладнання (табл. 6.6).

Таблиця 6.6

Роки п'ятирічки

_ Зберегти Зберегти

Оптимальн      / ,

облад- облад-

е рішення

нання

нання

Зробити заміну облад­нання

Зберегти Зберегти облад- облад­нання нання

Задача про розподіл ресурсів.  Знайти  розв'язання задачі, якщо Б = 700 млн. грн., п = 3, а значення X* і/і(Х.і) наведені в табл. 6.7.

Таблиця 6.7

Обсяг капіталовкладе

Приріст випуску продукції/і(Х.і) залежно від обсягу капіталовкладень (млі :, грн.)

ньХі (млн. грн.)

підприємство 1

підприємство 2

підприємство 3

0

0

0

0

100 200 300 400 500 600

30

50

90

110

170

180

50 80 90 150 190 210

40 50 110 120 180 220

700

210

220

240

Розв'язання. Для розв'язання даної задачі динамічного програмування варто скласти рекурентне співвідношення Беллмана. У розглянутому випадку це співвідношення приводить до наступних функціональних рівнянь:

Тут функції  (Рі\Х)  \і = 1,п — 1)  визначають максимальний

приріст випуску продукції при відповідних розподілах X мли. грн. капіталовкладень між і підприємствами. Тому значення функції фп(Х) обчислюється лише для одного значення X = 5, тому що обсяг капіталовкладень, що виділяються для всіх п підприємств, дорівнює 5 млн. грн.

Використовуючи тепер рекурентні співвідношення (6.11) і вихідні дані табл. 6.7, приступаємо до знаходження розв'язку задачі, тобто до визначення спочатку умовно оптимальних, а потім і оптимальних розподілів капіталовкладень між підприємствами.

Починаємо з визначення умовно оптимальних капіталовкладень, що виділяються для розвитку першого підприємства. Для цього знаходимо значення <Р\(Х) для кожного X, що приймає значення 0,

100,200, 300,400, 500, 600 і 700.

Нехай X = 0; тоді ^і(0) = 0. Візьмемо тепер Л=100. Тоді,

використовуючи табл. 6.7, одержуємо

9.1(x)=max{/(xift

 

(6.11)

 

 

= max

 

Тут перший рядок відповідає рішенню Х/=0, а другий рядок -рішенню Х}= 100. Тому що при першому рішенні приріст випуску продукції не забезпечується, а при другому дорівнює 30 млн. грн., теумовно оптимальним рішенням є Хі =100. Аналогічно знаходимо умовно оптимальні рішення для інших значень X:

0 30

(200 ) = тах

= 50,Х,0 = 200;

<ру (300 ) = тах

0

зо

50 [90]

= 90, X* = 300 ;

(400 ) = тах

0 30 50 90

РП

= 110 = 400 .

(500 )= тах

0

30

50

90

110

ІЇ70І

■ = 170 ,Х* = 500 ;

¥>,{б00 ) = max

,{700 )=

0

ЗО

50

90

110

170

0

зо

50

90

110

170

180

210

= 180 ,Х° =600

- 210        = 700

Результати обчислень і отримані відповідні умовно оптимальні рішення записуємо в табл. 6.8.

Таблиця 6.8

Обсяг капітало­вкладень  X, що виділяються першому підприємству (млн. грн.)

Максимальний приріст випуску <р ^продукції (млн. грн.)

Умовно оптимальний обсяг

капіталов кладень X/, що виді ляк ться першому підприємству (мли. грн.)

0

0

0

100

30

00

200

50

:;оо

300

90

300

400

110

400

500

170

:;оо

600

180

іЮО

700 I 210

Використовуючи тепер дані табл. 4.8 і 4.7, визначимо умовно оптимальні обсяги капіталовкладень, що виділяються другому підприємству.        Знайдемо#>2(х) = msa{f2(X2)+tpl(X — Х2)!для

кожного із припустимих значень X, рівних 0, 100, 200, 300, 400, 500, 600 і 700:

'00

^0)=0

Х2°=0;

<р2 (і00 )= max 0+30 [50 + 0 = 50,Х2° = 100 ;

<р2 (200 ) = max

0 + 50

[50 + 30 J 80+0 = 80,Х2° = 100;

9>2(300)= max

0 + 90 50 + 50

[80 + 30 J 90 + 0 = 110,Х° = 200;

q> 2 (400 ) = max

0 + 110 50 +90 80 + 50 90 + 30 [150 + Oj = 150 ,X% = 400 ;

^2(500 ) = max

0 + 170 50 +110 80 + 90 90 + 50 150 + 30 [190 + Oj

= 190 ,Х[> = 500 ;

g>2 (600 ) = max

0 + 180

50 +170 J 80+110 90 + 90 150+50 190 + 30 210+0

0 +120 50 + 180

= 220,^ = 100;

,(700 ) =

max

[80 +170 J 90 + 110 150 +90 190 + 50 210 + 30 220 + 0 = 250,      = 200;

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

ъ(х) = тж{&{Х3)+ъ(Х-Х3)}

використовуючи для цього відповідні дані табл. 6.9 і 6.7.

Тому що в цьому випадку число підприємств дорівнює 3, то проводимо обчислення лише для одного значення Х= 700:

,(700) =

0 + 250 40 + 220 50 +190 110+150 120+110 180 + 80

[220 +50] 240 +0

= 270,*,° = 600.

Отже, максимальний приріст випуску продукції становить 270 млн. грн. Це має місце тоді, коли третьому підприємству виділяється 600 млн. грн., а першому й другому підприємствам - 100 млн. грн. Тоді ( з табл. 6.9) 2-му підприємству варто виділити 100 млн. грн.

Таблиця 6.9

Обсяг капітало­вкладень X, що виділяються першим двом підприємствам (млн. грн.)

Максимальний приріст ^2(Х) випуску продукції (млн. грн.)

Уі ювно

оп гимальний обсяг ка іітало вкладень х::о, що

ви ціляються Другому

пі щриємству (млн.

о

100 200 300 400 500 600 700 0 50 80 110 150 190 220 250 0

100 100 200 400 500 100 200