Метод функціональних рівнянь Р.Белмана

Американським економістом Р.Белманом було показано, що знаходження оптимального розв'язку багатоетапного процесу зводиться до розв'язування деякого функціонального рівняння.

Нехай s _o і s_N - відповідно початковий і кінцевий етапи N- крокового процесу. Позначимо через f_N (s _o) екстремальне значення функції мети, отримане за N кроків при оптимальній стратегії u управління процесом, який знаходився в початковому стані s _o.

Припустимо, що на першому кроці ми отримали розв'язок u _о і процес перейшов із стану s _o в стан s ₁. Досягнутий при цьому ефект характеризується значенням r ₀(s _o, u _o) функції r_i (s_i, u_i). Припустимо, що після першого кроку для управління процесом застосовувалася оптимальна стратегія, при якій на решті N -1 етапів функція мети f_{N -1}(s ₁) досягала екстремального значення. При описаних умовах загальна оцінка якості управління за N кроків виразиться су­мою r ₀(s _o, u _o)+ f_{N -1}(s ₁), а екстремальне значення f_N (s_o) функції мети за N кроків дорівнюватиме:

f_N (s_o)=extr{ r ₀(s _o, u _o)+ f_{N -1}(s ₁): u _o} (2.20)

Позначимо через f_{N -1}(s_i) екстремум функції мети, отриманий на останніх N-i кроках, якщо початковим був стан s_i,. Тоді за аналогією з рівністю (2.20) одержимо:

f_N–i (s_i)=extr{ r_i (s_i, u_i)+ f_{N -( i +1)}(s_{i+ 1}): u_i }, i =0,…, N –1. (2.21)

Вираз (2.21) і є математичним записом принципу оптимальності. Його називають основним функціональним рівнянням динамічного програмування. Воно дає змогу описати процедуру прийняття покрокових рішень і поступово сформу­вати оптимальну стратегію управління всім N -кроковим процесом. Із (2.21) вид­но, що при обчисленні чергового значення функції f_N–i, аргументом вико­ристовується попереднє значення функції f_{N -( i +1)}. Співвідношення, які мають та­ку властивість, називають рекурентними. Вся послідовність обчислень, яка приводить до f_N (s _o), може бути виконана, якщо встановлено значення функцій f_{N -( i +1)}.

У кожній конкретній задачі функціональне рівняння (2.21) має свій специфічний вид. А метод функціональних рівнянь є одним із основних методів розв'язування задач динамічного програмування.

Задача розподілу ресурсів

Однією із задач динамічного програмування є оптимальний розподіл ресурсів. В загальному вигляді задача оптимального розподілу ресурсів може бути задана у такій формі.

Є певна кількість ресурсів (матеріальні, фінансові, трудові), які необхідно розподілити між різноманітними об’єктами їх використання на окремих проміжках планового періоду так, щоб одержати максимальну сумарну ефективність від вибраного способу розподілу. Показником ефективності може бути прибуток, собівартість, сумарні затрати, тощо.

Приклад. Територіальний орган управління підрозділами цивільного захисту одержав 7 пожежно-рятувальних автомобілів, які необхідно розподілити між 5 підрозділами. Кожен з цих підрозділів при надходженні до нього автомобілів в кількості u підвищує рівень технічної готовності, який залежить від u, тобто задано функцію f_i (u). Всі функції f_i (u), i =1,2,3,4,5, відомі (рис. 2.27). Яким повинен бути такий розподіл, щоб в сумі одержати найбільшу технічну готовність по всіх підрозділах?

u	f 1(u)	f 2(u)	f 3(u)	f 4(u)	f 5(u)
	0,74	0,85	0,90	0,88	0,70
	0,81	0,90	0,92	0,91	0,76
	0,85	0,93	0,93	0,92	0,80
	0,90	0,94	0,94	0,93	0,85
	0,92	0,95	0,95	0,94	0,88
	0,93	0,96	0,96	0,95	0,91
	0,94	0,97	0,96	0,95	0,93
	0,95	0,97	0,96	0,95	0,94

Рис. 2.27.

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

Система, якою керують в даній задачі – система розподілу техніки. Стан системи перед кожним кроком характеризується деяким числом – кількістю нерозподілених машин. Кроком управління є кількість автомобілів, які виділені управлінням: u ₁, u ₂,..., u_m. Необхідно знайти оптимальне управління, тобто сукупність чисел u ₁*, u ₂*,..., u_m *, яке дає максимальне підвищення рівня технічної оснащеності по управлінню в цілому W, що може бути записане у вигляді:

W = W ₁+ W ₂+...+ W ₅ = f ₁(u ₁)+ f ₂(u ₂)+...+ f ₅(u ₅) ® max

Почнемо оптимізацію з п’ятої частини (кроку). Нехай залишок машин перед цим кроком s. Очевидно, що всі s автомобілів треба передати п’ятій частині. Тому оптимальне управління на 5-му кроці:

u ₅(s) = s,

а умовний оптимальний виграш:

W ₅(s) = f ₅(s)

Для значень s =1,2,...,7 за таблицею (функцією технічної оснащеності f_i (u)) для кожного значення s визначимо u ₅(s) и W ₅(s):

u₅ (0) = 0, W ₅(0) = 0,70;

u₅ (1) = 1, W ₅(1) = 0,76;

u₅ (2) = 2, W ₅(1) = 0,80;

u₅ (3) = 3, W ₅(1) = 0,85;

u₅ (4) = 4, W ₅(1) = 0,88;

u₅ (5) = 5, W ₅(1) = 0,91;

u₅ (6) = 6, W ₅(1) = 0,93;

u₅ (7) = 7, W ₅(1) = 0,94.

Одержані дані запишемо в таблицю (Рис. 2.28). Останній крок оптимізовано.

s	i =5		i =4		i =3		i =2		i =1
	u 5(s)	W 5(S)	u 4(s)	W 4(S)	u 3(s)	W 3(S)	u 2(s)	W 2(S)	u 1(s)	W 1(S)
		0,70		1,58		2,48		3,33		4,36
		0,76		1,64		2,54		3,39		4,40
		0,80		1,68		2,58		3,44		4,41
		0,85		1,73		2,63		3,48		4,43
		0,88		1,76		2,66		3,53		4,40
		0,91		1,79		2,69		3,56		4,37
		0,93		1,78		2,72		3,59		4,33
		0,94		1,84		2,74		3,62		4,28

Рис. 2.28.

Перейдемо до передостанньої 4-ї частини (кроку). Нехає у нас є s нерозподілених автомобілів. Позначимо W ₄(s) умовний оптимальний виграш на двох останніх кроках: 4-му і 5-му (який вже оптимізовано). Якщо виділити на 4-му кроці 4-ій частині u автомобілів, то на останній крок залишиться s – u. Отже, виграш на двох останніх кроках буде:

W ₄(s) = f ₄(u)+ W ₅(s–u)

Знову для всіх значень s =1,2,3,...,7 та використовуючи дані першого стовпчика таблиці (Рис. 2.28), для кожного значення s обчислимо u ₄(s), W ₄(s) і виділимо максимальне значення, яке і є оптимальним виграшем за два останні кроки:

s =0: u ₄(0) = 0; W ₄(0) = 0.88+0.70+0.90 = 2.48;

s =1: u ₄(1) = 1; W ₄(1) = 0.70+0.91 = 1.64;

u ₄(1) = 0; W ₄(1) = 0.88+0.76 = 1.64;

s =2: u ₄(2) = 2; W ₄(2) = 0.92+0.70 = 1.62;

u ₄(2) = 1; W ₄(2) = 0.91+0.76 = 1.67;

u ₄(2) = 0; W ₄(2) = 0.88+0.80 = 1.68;

s =3: u ₄(3) = 3; W ₄(3) = 0.93+0.70 = 1.63;

u ₄(3) = 2; W ₄(3) = 0.92+0.76 = 1.0;

u ₄(3) = 1; W ₄(3) = 0.91+0.80 = 1.71;

u ₄(3) = 0; W ₄(3) = 0.88+0.85 = 1.73;

s =4: u ₄(4) = 4; W ₄(4) = 0.94+0.70 = 1.64;

u ₄(4) = 3; W ₄(4) = 0.93+0.76 = 1.69;

u ₄(4) = 2; W ₄(4) = 0.92+0.80 = 1.72;

u ₄(4) = 1; W ₄(4) = 0.91+0.85 = 1.76;

u ₄(4) = 0; W ₄(4) = 0.88+0.88 = 1.76;

s =5: u ₄(5) = 5; W ₄(5) = 0.95+0.70 = 1.65;

u ₄(5) = 4; W ₄(5) = 0.94+0.76 = 1.70;

u ₄(5) = 3; W ₄(5) = 0.93+0.80 = 1.73;

u ₄(5) = 2; W ₄(5) = 0.92+0.85 = 1.77;

u ₄(5) = 1; W ₄(5) = 0.91+0.88 = 1.79;

u ₄(5) = 0; W ₄(5) = 0.88+0.91 = 1.79;

s =6: u ₄(6) = 6; W ₄(6) = 0.95+0.70 = 1.65;

u ₄(6) = 5; W ₄(6) = 0.95+0.76 = 1.71;

u ₄(6) = 4; W ₄(6) = 0.94+0.80 = 1.74;

u ₄(6) = 3; W ₄(6) = 0.93+0.85 = 1.78;

u ₄(6) = 2; W ₄(6) = 0.92+0.88 = 1.80;

u ₄(6) = 1; W ₄(6) = 0.91+0.91 = 1.82;

u ₄(6) = 0; W ₄(6) = 0.88+0.93 = 1.81;

s =7: u ₄(7) = 7; W ₄(7) = 0.95+0.70 = 1.65;

u ₄(7) = 6; W ₄(7) = 0.95+0.76 = 1.71;

u ₄(7) = 5; W ₄(7) = 0.95+0.80 = 1.75;

u ₄(7) = 4; W ₄(7) = 0.94+0.85 = 1.79;

u ₄(7) = 3; W ₄(7) = 0.93+0.88 = 1.82;

u ₄(7) = 2; W ₄(7) = 0.92+0.91 = 1.83;

u ₄(7) = 1; W ₄(7) = 0.91+0.93 = 1.84;

u ₄(7) = 0; W ₄(7) = 0.88+0.94 = 1.82.

В другий стовпчик таблиці (Рис. 2.28) вносимо результати оптимізації на 4-му кроці.

Далі оптимізуємо третій та другий кроки:

W ₃(s) = max{ f ₃(u)+ W ₄(s–u)}, W ₂(s) = max{ f ₂(u)+ W ₃(s–u)}

Маємо наступні результати, які заносимо в третій та четвертий стовпчики таблиці (Рис. 2.28):

s =0: u ₃(0) = 0; W ₃(0) = 0.88+0.70 = 1.58;

s =1: u ₃(1) = 1; W ₃(1) = 0.92+1.58 = 2.50;

u ₃(1) = 0; W ₃(1) = 0.90+1.64 = 2.54;

s =2: u ₃(2) = 2; W ₃(2) = 0.93+1.58 = 2.51;

u ₃(2) = 1; W ₃(2) = 0.92+1.64 = 2.56;

u ₃(2) = 0; W ₃(2) = 0.90+1.68 = 2.58;

s =3: u ₃(3) = 3; W ₃(3) = 0.94+1.58 = 2.52;

u ₃(3) = 2; W ₃(3) = 0.93+1.64 = 2.57;

u ₃(3) = 1; W ₃(3) = 0.92+1.58 = 2.50;

u ₃(3) = 0; W ₃(3) = 0.90+1.73 = 2.63;

s =4: u ₃(4) = 4; W ₃(4) = 0.95+1.58 = 2.54;

u ₃(4) = 3; W ₃(4) = 0.94+1.64 = 2.58;

u ₃(4) = 2; W ₃(4) = 0.93+1.68 = 2.61;

u ₃(4) = 1; W ₃(4) = 0.92+1.73 = 2.65;

u ₃(4) = 0; W ₃(4) = 0.90+1.76 = 2.66;

s =5: u ₃(5) = 5; W ₃(5) = 0.96+1.58 = 2.57;

u ₃(5) = 4; W ₃(5) = 0.95+1.64 = 2.59;

u ₃(5) = 3; W ₃(5) = 0.94+1.68 = 2.62;

u ₃(5) = 2; W ₃(5) = 0.93+1.73 = 2.66;

u ₃(5) = 1; W ₃(5) = 0.92+1.76 = 2.68;

u ₃(5) = 0; W ₃(5) = 0.90+1.79 = 2.69;

s =6: u ₃(6) = 6; W ₃(6) = 0.96+1.58 = 2.57;

u ₃(6) = 5; W ₃(6) = 0.96+1.64 = 2.60;

u ₃(6) = 4; W ₃(6) = 0.95+1.68 = 2.63;

u ₃(6) = 3; W ₃(6) = 0.94+1.73 = 2.67;

u ₃(6) = 2; W ₃(6) = 0.93+1.76 = 2.69;

u ₃(6) = 1; W ₃(6) = 0.92+1.79 = 2.71;

u ₃(6) = 0; W ₃(6) = 0.90+1.82 = 1.72;

s =7: u ₃(7) = 7; W ₃(7) = 0.96+1.58 = 2.57;

u ₃(7) = 6; W ₃(7) = 0.96+1.64 = 2.60;

u ₃(7) = 5; W ₃(7) = 0.96+1.68 = 2.64;

u ₃(7) = 4; W ₃(7) = 0.95+1.73 = 2.68;

u ₃(7) = 3; W ₃(7) = 0.94+1.76 = 2.70;

u ₃(7) = 2; W ₃(7) = 0.93+1.79 = 2.72;

u ₃(7) = 1; W ₃(7) = 0.92+1.82 = 2.74;

u ₃(7) = 0; W ₃(7) = 0.90+1.84 = 2.74.

s =0: u ₂(0) = 0; W ₂(0) = 0.85+2.48 = 3.33;

s =1: u ₂(1) = 1; W ₂(1) = 0.90+2.48 = 3.38;

u ₂(1) = 0; W ₂(1) = 0.85+2.54 = 2.39;

s =2: u ₂(2) = 2; W ₂(2) = 0.93+2.48 = 3.41;

u ₂(2) = 1; W ₂(2) = 0.90+2.54 = 3.44;

u ₂(2) = 0; W ₂(2) = 0.85+2.58 = 3.43;

s =3: u ₂(3) = 3; W ₂(3) = 0.94+2.48 = 3.42;

u ₂(3) = 2; W ₂(3) = 0.93+2.54 = 3.47;

u ₂(3) = 1; W ₂(3) = 0.90+2.58 = 3.48;

u ₂(3) = 0; W ₂(3) = 0.85+2.63 = 3.48;

s =4: u ₂(4) = 4; W ₂(4) = 0.95+2.48 = 3.43;

u ₂(4) = 3; W ₂(4) = 0.94+2.54 = 3.48;

u ₂(4) = 2; W ₂(4) = 0.93+2.58 = 3.51;

u ₂(4) = 1; W ₂(4) = 0.90+2.63 = 3.53;

u ₂(4) = 0; W ₂(4) = 0.85+2.66 = 3.51;

s =5: u ₂(5) = 5; W ₂(5) = 0.96+2.48 = 3.44;

u ₂(5) = 4; W ₂(5) = 0.95+2.54 = 3.49;

u ₂(5) = 3; W ₂(5) = 0.94+2.58 = 3.52;

u ₂(5) = 2; W ₂(5) = 0.93+2.63 = 3.56;

u ₂(5) = 1; W ₂(5) = 0.90+2.66 = 3.56;

u ₂(5) = 0; W ₂(5) = 0.85+2.69 = 3.54;

s =6: u ₂(6) = 6; W ₂(6) = 0.97+2.48 = 3.45;

u ₂(6) = 5; W ₂(6) = 0.96+2.54 = 3.50;

u ₂(6) = 4; W ₂(6) = 0.95+2.58 = 3.53;

u ₂(6) = 3; W ₂(6) = 0.94+2.63 = 3.57;

u ₂(6) = 2; W ₂(6) = 0.93+2.66 = 3.57;

u ₂(6) = 1; W ₂(6) = 0.90+2.69 = 3.59;

u ₂(6) = 0; W ₂(6) = 0.85+2.72 = 3.57;

s =7: u ₂(7) = 7; W ₂(7) = 0.97+2.48 = 3.45;

u ₂(7) = 6; W ₂(7) = 0.97+2.54 = 3.51;

u ₂(7) = 5; W ₂(7) = 0.96+2.58 = 3.54;

u ₂(7) = 4; W ₂(7) = 0.95+2.63 = 3.58;

u ₂(7) = 3; W ₂(7) = 0.94+2.66 = 3.58;

u ₂(7) = 2; W ₂(7) = 0.93+2.69 = 3.62;

u ₂(7) = 1; W ₂(7) = 0.90+2.72 = 3.62;

u ₂(7) = 0; W ₂(7) = 0.85+2.74 = 3.59.

Продовжуючи, дійдемо до 1-ї частини. Тут нам не треба змінювати значення s, оскільки число автомобілів перед першим кроком дорівнює 7:

W * = W ₁(7) = max{ f ₁(u)+ W ₂(7- u)}

Таким чином, максимальне підвищення технічної готовності по всьому управлінні знайдено. Тепер виберемо рекомендації. Максимум технічної готовності управління досягається при відправці 3 автомобілів в 1 частину. Після першого кроку залишається 4 автомобілі. Згідно з таблицею, виділяємо другій частині оптимальну кількість автомобілів - 1, третьому - 0, четвертому - 0 і п’ятому - 3.

Задача вибору найкоротшого маршруту

Іншою задачею динамічного програмування є задача вибору найкоротшого (найшвидшого) маршруту. Ця задача формулюється наступним чином:

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

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

Для розв'язування задачі методом динамічного програмування розіб'ємо всі пункти мережі на групи. До першої групи віднесемо пункт 1; до другої - пункти, в які можна по­пасти безпосередньо з пункту 1; до третьої - пункти, в які можна попасти без­посередньо з будь-якого пункту другої групи і т.д. Внаслідок такого розбиття рух транспорту з пункту 1 в пункт N набуде поетапного характеру: на першому етапі транспорт рухається з пункту 1 в деякий пункт другої групи, на другому ета­пі - з пункту другої групи в пункт третьої групи і т.д. Таким чином, процес зна­ходження найкоротшого маршруту з пункту 1 в пункт N розкладається на етапи. На кожному з етапів потрібно так вибрати маршрут, щоб час слідування був мінімальним.

Для цієї задачі принцип оптимальності можна сформулю­вати так: оптимальний маршрут слідування з пункту 1 в пункт N має властивість: яким би не був маршрут досягнення проміжного пункту мережі, подальший маршрут руху повинен співпадати з оптимальним маршрутом для тієї частини маршруту, яка починається з цього пункту.

Приклад. Задано мережу доріг з вказуванням відстаней (Рис. 2.29). Знайти найкоротший шлях слідування з пункту 1 в пункт 7.

Рис. 2.29.

Позначимо через d_ij відстань між суміжними вузлами i та j, а U_j – найкоротшу відстань між першим та j -им вузлами. За методом Беллмана запишемо формулу (2.21) у такому вигляді:

U_j =min{ U_i + d_ij: i =1,…, j –1}, j =1, …, 7.

Знайдемо поетапно U_j.

1. U ₁=0

2. U ₂= U ₁+ d ₁₂=0+2=2, U ₃= U ₁+ d ₁₃=0+4=4.

3. U ₄=min{ U ₁+ d ₁₄, U ₂+ d ₂₄, U ₃+ d ₃₄}=min{0+10,2+11,4+3}=7.

4. U ₅=min{ U ₂+ d ₂₅, U ₄+ d ₄₅}=min{2+5,7+8}=7

U ₆=min{ U ₃+ d ₃₆, U ₄+ d ₄₆}=min{4+1,7+7}=5

5. U ₇=min{ U ₅+ d ₅₇, U ₆+ d ₆₇}=min{7+6,5+9}=13

Одержали мінімальну відстань між вузлами 1 і 7, яка дорівнює 13, а найкоротший маршрут буде таким: 1®2®5®7.

? Контрольні запитання