Теоретичні відомості:

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

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

Методичні рекомендації до виконання завдань:

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

Для п’ятого року (після 4-х років) маємо табл. 15.2.

Таблиця 15.2 – Визначення прибутку після 4 років експлуатації

Кількість років експлуатації
І		ІІ		ІІІ		ІV
u5=0	u5=1	u5=0	u5=1	u5=0	u5=1	u5=0	u5=1
r1=75-25=50	r0-∆= =80-20- -40=20	r2=65-30=35	r0-∆= =80-20- -40=20	r3=60-35=25	r0-∆= =80-20- -40=20	r4=60-45=15	r0-∆= =80-20- -40=20

. Це максимальний за рік прибуток.

Для четвертого року (тобто після 3-х) маємо три можливі для віку обладнання І, ІІ, ІІІ років. Значення прибутку за четвертий та п’ятий роки занесемо в таблицю15.3.

Таблиця 15.3 – Визначення прибутку після 3 років експлуатації

Кількість років експлуатації
І		ІІ		ІІІ
u4=0	u4=1	u4=0	u4=1	u4=0	u4=1
r1 + =75-25 + +=50+35=85	r0–∆ + = = 80–20–40+ +=20+50=70	r2+=65-30+=35+25=60	r0–∆+= =80–20– –40+= =20+50=70	r3+=60––35+= =25+20=45	r0-∆+= =80-20- -40+=70

. Це максимально можливий прибуток за 2 останні роки.

Для третього року (тобто після 2-х) є дві можливості: для віку обладнання І, ІІ років. Значення прибутку занесене в табл. 15.4.

Таблиця 15.4 – Визначення прибутку після 2 років експлуатації

Кількість років експлуатації
І		ІІ
u3=0	u3=1	u3=0	u3=1
r1 + =75-25 + +=50+70=120	r0–∆+=80–20– –40+=20+85= =105	r2+=65–30+70=105	r0–∆+= =20+85=105

. Це максимально можливий прибуток за три останні (3, 4, 5) роки.

Для другого року маємо можливість, що викладено в таблиці 15.5.

Таблиця 15.5 – Визначення прибутку після 1 років експлуатації

Кількість років експлуатації
І
u2=0	u2=1
r1 + =50+105=155	r0–∆+=20+120=140

Маємо: . Це максимально можливий прибуток за останні чотири, а отже, і за п’ять років, оскільки на першому році вибору не було.

Таким чином, максимальний прибуток підприємства складає 155 тис. грн. Цей розв’язок забезпечують два оптимальні керування прита(в першому – заміна обладнання на третьому році, а в другому – на четвертому).

Питання для самоконтролю:

1. Які задачи відносять до задач динамічного програмування?

2. У чому полягають особливості розвязування задач динамічного програмування?

3. У чому зміст принципу оптимальності Белмана?