3.3.4. Метод динамічного програмування за наявності двох обмежень

Метод динамічного програмування може бути поширений на випадок розподілу будь-якої кількості видів ресурсів, однак збільшення кількості видів ресурсів, які розподіляються, призводить до значних труднощів у застосуванні методу динамічного програмування. У випадку, коли кількість видів ресурсів , трудомісткість можна порівняти з методом простого перебору. Переваги методу динамічного програмування відносно більшої кількості ненульових значень змінних у випадку великого значення перестають бути вагомими.

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

за обмежень на використання першого та другого виду ресурсів

,

а також невід’ємності змінних

, ,

де - інтенсивність використання -го технологічного процесу, ;

та - кількість ресурсів відповідно першого та другого виду;

- ефективність використання -го технологічного процесу з інтенсивністю ;

— норми витрат ресурсів виду на -й процес, .

Для побудови рекурентних співвідношень введемо два параметри, які характеризують стан процесу, , - відповідно кількість першого та другого виду ресурсу на певному етапі..

Позначимо — максимальний прибуток у стані процесу та за умов, що

,
.

Тоді основне рекурентне співвідношення буде мати вигляд:

,

де

.

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

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

3.3.5. Задача про заміну обладнання

Розглянемо приклад задачі динамічного програмування, в якій змінні є булевими, і опишемо процедуру прийняття рішення на прикладі задачі про заміну обладнання.

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

Змінні моделі , будуть приймати значення тільки 1 або 0.

	1, якщо обладнання віку років слід замінити на початку року планування ;
	0, якщо обладнання віку років зберігається в році планування .

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

Якщо на початок -го року обладнання зберігається, то на початок -го року його вік збільшується на 1 рік. А якщо обладнання замінюється, тоді на початок наступного року воно досягає віку 1 рік.

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

Якщо на початку -го року приймається рішення про заміну обладнання, тоді виручка від реалізації обладнання віку років складе , витрати на нове обладнання дорівнюють , а експлуатація нового обладнання принесе прибуток . На початок наступного року вік обладнання буде 1 рік. Максимальний прибуток за всі роки, починаючи з -го по -ний рік складе .

З цих двох варіантів управління вибираємо той, який принесе найбільший прибуток:

	, якщо ;	(3.3.7)
	, якщо .

На кожному кроці необхідно обчислити для всіх . Для

	, якщо ;	(3.3.8)
	, якщо .

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

Приклад 3.5. Знайти оптимальний план заміни обладнання на період тривалістю 6 років, якщо річний прибуток та залишкова вартість в залежності від віку обладнання задані у таблиці 3.23.

Таблиця 3.23.

	0	1	2	3	4	5	6
Прибуток ( )	10	9	9	8	6	4	2
Залишкова вартість ( )	9	8	7	5	4	3	2

Вартість нового обладнання дорівнює 12 умовних одиниць, а вік обладнання на початок планового періоду складає 1 рік.

Розв’яжемо цю задачу методом динамічного програмування. Розіб’ємо весь період планування на 6 етапів (кожен рік – один етап). Для прийняття рішення на кожному наступному етапі необхідна інформація про вік обладнання на попередньому етапі. Тому стан досліджуваного процесу на кожному етапі визначається віком обладнання.

Максимальний прибуток від експлуатації обладнання за 6 років визначатиметься аналогічно (3.3.8):

	, якщо ;
	, якщо .

Обчислення , представимо у допоміжній таблиці 3.24.

Таблиця 3.24.

	1	9	8-12+10=6	9	0
	2	9	7-12+10=5	9	0
	3	8	5-12+10=3	8	0
	4	6	4-12+10=2	6	0
	5	4	3-12+10=1	4	0
	6	2	2-12+10=0	2	0

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

На наступних кроках максимальний прибуток визначається по формулі (3.3.7), тобто

	, якщо ;
	, якщо .

	, якщо ;
	, якщо .

	, якщо ;
	, якщо .

	, якщо ;
	, якщо .

	, якщо ;
	, якщо .

Заповнимо допоміжну таблицю 3.25.

Таблиця 3.25.

	1	9+9=18	8-12+10+9=15	18	0
	2	9+8=17	7-12+10+9=14	17	0
	3	8+6=14	5-12+10+9=12	14	0
	4	6+4=10	4-12+10+9=11	11	1
	5	4+2=6	3-12+10+9=10	10	1
	1	9+17=26	8-12+10+18=24	26	0
	2	9+14=23	7-12+10+18=23	23	0 або 1
	3	8+11=19	5-12+10+18=21	21	1
	4	6+10=16	4-12+10+18=20	20	1
	1	9+23=32	8-12+10+26=32	32	0 або 1
	2	9+21=30	7-12+10+26=31	31	1
	3	8+20=28	5-12+10+26=29	29	1
	1	9+31=40	8-12+10+32=38	40	0
	2	9+29=38	7-12+10+32=37	38	0
	1	9+38=47	8-12+10+40=46	47	0

Результати обчислень перенесемо до основної таблиці 3.26.

Таблиця 3.26.

1
2
3
4
5
6

Позначку „* ” у таблиці 3.26 мають елементи оптимальної стратегії.

Максимально можливий прибуток за 6 років складає 47 умовних одиниць. Оптимальна стратегія заміни обладнання полягає у збереженні обладнання на першому та другому роках. Тоді на початку третього року вік обладнання складе 3 роки і обладнання слід замінити. На початок четвертого року вік обладнання дорівнює 1 рік і заміну робити не треба. Тоді на початок п’ятого року обладнання матиме вік 2 роки і його слід зберегти. На початку шостого року обладнання матиме вік 3 роки і заміні не підлягатиме.