Розв’язок. Для опису задачі у вигляді моделі динамічного програмування будемо розглядати процес виділення автомобілів підприємствам як n-кроковий процес

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

Система характеризується чотирма управляючими змінними x ₁ , x ₂ , x ₃ , x ₄ (за кількістю кроків) та п’ятьма параметрами стану S ₀, S ₁ , S ₂ , S _3, S _4.

Рівняння стану системи на кожному кроці виражають залишок автомобілів S_k після k -го кроку і можуть бути записані у вигляді

; ; ; .

Показник ефективності процесу – загальний прибуток від виконання перевезень

.

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

крок 4: ;

крок 3: ;

крок 2: ;

крок 1: .

Розрахунок показників умовної оптимізації 4-1-го кроків згідно з даними рівняннями наведений в таблиці 7.2. Побудову таблиці та відповідні розрахунки виконують у такій послідовності.

1. У першому стовпчику таблиці перелічуються можливі стани системи (кількість невиділених автомобілів S_k ) на початку k -го кроку; у другому – управління (всі можливі кількості виділених автомобілів x_k від їх наявного залишку) на k -му кроці; у третьому – стан системи (залишок автомобілів S_k після їх виділення) наприкінці k -го кроку.

2. Виконується умовна оптимізація на 4-ому кроці (стовпчик 4) за максимальним прибутком від виділення автомобілів x підприємству П ₄. Значення виграшу чисельно дорівнює значенням таблиці вихідних даних.

3. Виконуємо умовну оптимізацію на третьому кроці (k= 3). Спочатку розраховуємо умовні виграші в залежності від стану системи S_k , S_{k -1} та змінних управління x_k за формулою

Значення f ₃(x ₃) беремо з таблиці вихідних даних (стовпчик f ₃(x ₃), значення – зі стовпчика 4 розрахункової таблиці і заносимо відповідно в стовпчики 5 та 6. Із одержаних значень умовних виграшів (стовпчик 7) вибираємо оптимальний на даному кроці

.

Для цього порівнюємо величини при одному і тому ж значенні S ₂ , та вибираємо найбільше число, яке і буде дорівнювати . В таблиці 7.2 ці значення позначені зірочкою.

4. Аналогічним чином виконуємо умовну оптимізацію 2-го та 1-го кроків, після чого переходимо до другого етапу розрахунків –безумовної оптимізації. Для зручності розрахунків перенесемо по всіх кроках з таблиці 7.2 в основну таблицю (таблиця 7.3) підсумки умовної оптимізації, тобто послідовність значень функцій та відповідні їм оптимальні значення параметрів управління .

Таблиця 7.2 – Умовна оптимізація процесу
k = 4, 3, 2, 1	k = 4 Z *4(S 3)	k = 3; Z *3(S 2)	k = 2; Z *2(S 1)	k = 1; Z *1(S 0)
S k –1	хk	S k = S k –1– xk	f 4(x 4)	f 3(x 3)	Z *4(S 3)	Z *3 = f 3(x 3) + Z *4(S 3)	f 2(x 2)	Z *3(S 2)	Z *2 = f 2(x 2) + Z *3(S 2)	f 1(x 1)	Z *2(S 1)	Z *1= f 1(x 1) + Z *2(S1)
				1, 6		1, 6	0+1, 6=1, 6		1, 8	0+1, 8=1, 8		1, 9	0+1, 9=1, 9
			0, 3	1, 3	0, 3+1, 3=1, 6	0, 6	1, 3	0, 6+1, 3= 1, 9*	0, 8	1, 6	0, 8+1, 6= 2, 4*
			0, 4	0, 8	0, 4+0, 8=1, 2	0, 9	0, 9	0, 9+0, 9=1, 8	1, 0	1, 3	1, 0+1, 3=2, 3
			0, 7	0, 6	0, 7+0, 6=1, 3	1, 1	0, 7	1, 1+0, 7=1, 8	1, 1	1, 0	1, 1+1, 0=2, 1
			1, 1	0, 4	1, 1+0, 4=1, 5	1, 3	0, 4	1, 3+0, 4=1, 7	1, 2	0, 6	1, 2+0, 6=1, 8
			1, 8		1, 8+0= 1, 8*	1, 5		1, 5+0=1, 5	1, 8		1, 8+0=1, 8
				1, 3		1, 3	0+1, 3= 1, 3*		1, 3	0+1, 3=1, 3		1, 6	0+1, 6=1, 6
			0, 3	0, 8	0, 3+0, 8=1, 1	0, 6	0, 9	0, 6+0, 9=1, 5	0, 8	1, 3	0, 8+1, 3= 2, 1*
			0, 4	0, 6	0, 4+0, 6=1, 0	0, 9	0, 7	0, 9+0, 7= 1, 6*	1, 0	1, 0	1, 0+1, 0=2, 0
			0, 7	0, 4	0, 7+0, 4=1, 1	1, 1	0, 4	1, 1+0, 4=1, 5	1, 1	0, 6	1, 1+0, 6=1, 7
			1, 1		1, 1+0=1, 1	1, 3		1, 3+0=1, 3	1, 2		1, 2+0=1, 2
				0, 8		0, 8	0+0, 8=0, 8		0, 9	0+0, 9=0, 9		1, 3	0+1, 3=1, 3
			0, 3	0, 6	0, 3+0, 6= 0, 9*	0, 6	0, 7	0, 6+0, 7= 1, 3*	0, 8	1, 0	0, 8+1, 0= 1, 8*
			0, 4	0, 4	0, 4+0, 4=0, 8	0, 9	0, 4	0, 4+0, 9=1, 3	1, 0	0, 6	1, 0+0, 6=1, 6
			0, 7		0, 7+0=0, 7	1, 1		1, 1+0=1, 1	1, 1		1, 1+0=1, 1
				0, 6		0, 6	0+0, 6=0, 6		0, 7	0+0, 7=0, 7		1, 0	0+1, 0=1, 0
			0, 3	0, 4	0, 3+0, 4= 0, 7*	0, 6	0, 4	0, 6+0, 4= 1, 0*	0, 8	0, 6	0, 8+0, 6= 1, 4*
			0, 4		0, 4+0=0, 4	0, 9		0, 9+0=0, 9	1, 0		1, 0+0=1, 0
				0, 4		0, 4	0+0, 4= 0, 4*		0, 4	0+0, 4=0, 4		0, 6	0+0, 6=0, 6
			0, 3		0, 3+0=0, 3	0, 6		0, 6+0= 0, 6*	0, 8		0, 8+0= 0, 8*

Таблиця 7.3 – Підсумки умовної оптимізації

Визначення оптимального варіанту виділення автомобілів (безумовну оптимізацію) провадимо у такому порядку.

1. Визначаємо максимальний прибуток, котрий може бути досягнутий при виділенні початкових S ₀ = 20 автомобілів. Цей прибуток дорівнює 2, 4 тис. грн. (стовпчик 8). За стовпчиком 9 визначаємо кількість виділених автомобілів першому підприємству (П ₁)

автомобіля.

2. Знаходимо залишок автомобілів перед виділенням другому підприємству (П ₂)

автомобілів.

У стовпчику 7 для одержуємо автомобілів.

3. Знаходимо залишок автомобілів перед виділенням третьому підприємству (П ₃)

автомобілів.

У стовпчику 5 таблиці 7.3 одержуємо автомобіля.

5. Знаходимо залишок автомобілів перед виділенням четвертому підприємству (П ₄)

автомобіля.

Із стовпчика 3 таблиці 7.3 одержуємо автомобіля.

Отже, максимальний прибуток автотранспортного підприємства, який дорівнює 2, 4 тис. грн. буде отриманий, якщо розподілити автомобілі між підприємствами таким чином: П ₁ = 4автомобіля; П ₂ = 8 автомобілів; П ₃ = 4 автомобіля; П ₄ = 4 автомобіля.

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

1. Сформулюйте принцип оптимальності Беллмана.

2. За яких умов задачу можна представити у вигляді моделі динамічного програмування?

3. Дайте визначення адитивної та мультиплікативної цільової функції.

4. Дайте визначення параметру стану, змінної управління, умовно оптимальному рішенню в динамічному програмуванні.

5. У чому полягає умовна та безумовна оптимізація процесу?