Динамическое программирование. Задача о замене оборудования

 

Переходим к анализу  процесса эксплуатации оборудования на четвертом этапе.

Этап 4:

			Оптимальное решение
				решение
1	8-1+5=12	9-1-6+7=9	12	с
2	7-2+4=9	9-1-6+7=9	9	с,н
3	6-2+2=6	9-1-6+7=9	9	н
4	5-3+2=4	9-1-6+7=9	9	н

 

Теперь приступим к  этапу 3. На этом этапе возраст оборудования может принимать значения 1,2 и 3.

 

Этап 3:

    

           

			Оптимальное решение
1	8-1+6=16	9-1-6+12=14	16	с
2	7-2+9=14	9-1-6+12=14	14	с, н
3	6-2+9=13	9-1-6+12=14	14	н

 

Этап 2:

 

			Оптимальное решение
				Решение
1	8-1+14=21	9-1-6+16=18	21	с
2	7-2+14=19	9-1-6+16=18	19	с

 

Этап 1:

			Оптимальное решение
				Решение
1	8-1+19=26	9-1-6+21=23	26	с

 

Оптимальное решение: 

              
Лучше учесть и доходы от нового оборудования. Они равны r(0) − c(0) = 8.

Окончательно получаем оптимальное решение в более  привычном виде:

  ⁹

Значение     — наибольшая прибыль, которую можно получить при эксплуатации оборудования в данном примере.

По результатам рассмотренного примера можно сделать следующий  вывод. Оборудование нужно заменить один раз по истечении трех лет  эксплуатации. Максимальная прибыль  при этом составит 34 млн. руб.¹⁰

 

3.2. Задача 2.

   Компания планирует определить оптимальную политику замены используемого в настоящее время трехлетнего механизма на протяжении следующих 4 лет (n = 4), т.е. вплоть до начала пятого года. Таблица 1 содержит относящиеся к задаче данные. Компания требует обязательной замены механизма, который находится в эксплуатации 6 лет. Стоимость нового механизма равна 100 000 долл.

 

 

 

 

 

 

Таблица 1.

Возраст t без учета первых 3-х лет (года)	Возраст t* с учетом 3-х лет (года)	Прибыль r(t) (долл.)	Стоимость обслуживания c(t) (долл.)	Остаточная стоимость s(t) (долл.)
0		20000	200	-
1	3	19000	600	80000
2	4	18500	1200	60000
3	5	17200	1500	50000
4	6	15500	1700	30000
5	7	14000	1800	10000
6	8	12200	2200	5000

Определение допустимых значений возраста механизма на каждом этапе является нетривиальной задачей. На рис. 1 представлена рассматриваемая задача замены оборудования в виде сети. В начале первого года имеется механизм, эксплуатирующийся 3 года (на графике рис. 1 по оси Y откладывается возраст механизма). Мы можем либо заменить его, купить новое (З) или  (Н),   либо эксплуатировать старое (С) на протяжении следующего года. Если механизм заменили, то в начале второго года его возраст будет равен одному году, в противном случае его возраст будет 4 года. Такой же подход используется в начале каждого года, начиная со

второго по четвертый.

 

Рисунок 1. Схема возможной  замены механизма.

 

Если однолетний механизм заменяется в начале второго или  третьего года, то заменивший его механизм к началу следующего года также будет однолетним. К тому же, в начале 4-го года 6-летний механизм обязательно должен быть заменен, если он еще эксплуатируется; в конце 4-го года все механизмы продаются (П) в обязательном порядке. На схеме сети также видно, что в начале второго года возможны только механизмы со сроком эксплуатации 1 или 4 года. В начале третьего года механизм может иметь возраст 1, 2 или 5 лет, а в начале четвертого — 1, 2, 3 или 6 лет.

Решение данной задачи эквивалентно поиску маршрута максимальной длины (т.е. приносящего максимальную прибыль) от начала первого года к концу четвертого в сети, показанной на рис. 1. При решении таких задач часто используют табличную форму записи. (Числовые данные в таблице кратны тысячам долларов.)

Этап 4.

.	C	Н			Оптимальное решение
t	r(t) + s(t + 1) - c(t)	r(0) + s(t) + s(1) - c(0) - I	f4(t)			Решение
1	19,0 + 60 - 0,6 = 78,4	20 + 80 + 80 - 0,2 - 100 = 79,8	79,8			Н
2	18,5 + 50 - 1,2 = 67,3	20 + 60 + 80 - 0,2 - 100 = 59,8	67,3			С
3	17,2 + 30 - 1,5 = 45,7	20 + 50 + 80 - 0,2 - 100 = 49,8	49,8			Н
4	Необходима замена	20 + 5 + 80 - 0,2 - 100 = 4,8	4,8			Н

 

 

 Этап 3.

.	C	Н	Оптимальное решение
t	r(t) - c(t) + f4(t + 1)	r(0) + s(t) - c(0) - I + f4(1)	f3(t)	Решение
1	19,0 - 0,6 + 67,3 = 85,7	20 + 80 - 0,2 - 100 + 79,8 = 79,6	85,7	С
2	18,5 - 1,2 + 49,8 = 67,1	20 + 60 - 0,2 - 100 + 79,8 = 59,6	67,1	С
5	14,0 - 1,8 + 4,8 = 17,0	20 + 10 - 0,2 - 100 + 79,8 = 9,6	17,0	Н

 

  

Этап 2.

.	C	Н	Оптимальное решение
t	r(t) - c(t) + f3(t + 1)	r(0) + s(t) - c(0) - I + f3(1)	f2(t)	Решение
1	19,0 - 0,6 + 67,1 = 85,5	20 + 80 - 0,2 - 100 + 85,7 = 85,5	85,5	С или Н
4	15,5 - 1,7 + 19,6 = 33,4	20 + 30 - 0,2 - 100 + 85,7 = 35,5	35,5	Н

 

 Этап 1.

.	C	Н	Оптимум
t	r(t) - c(t) + f2(t + 1)	r(0) + s(t) - c(0) - I + f2(1)	f1(t)	Решение
1	17,2 - 1,5 + 35,5 = 51,2	20 + 50 - 0,2 - 100 + 85,5 = 55,3	55,3	Н

 

На рис. 2 показана последовательность получения оптимального решения. В  начале первого года оптимальным  решением при t = 1 является замена механизма. Следовательно, новый механизм к началу второго года будет находиться в эксплуатации 1 год. При t = 1 в начале второго года оптимальным решением будет либо использование, либо замена механизма. Если он заменяется, то новый к началу третьего года будет находиться в эксплуатации 1 год, иначе механизм будет иметь возраст 2 года. Описанный процесс продолжается до тех пор, пока не будет определено оптимальное решение для четвертого года.

 
Рисунок 2. Решение примера 

Следовательно, начиная  с первого года эксплуатации механизма, альтернативными оптимальными стратегиями  относительно замены механизма будут (Н, С, С, Н) и (Н, Н, С, С). Общая прибыль составит 55 300 долл. ¹¹

 

3. Задача 3.

 

К началу текущей пятилетки  на предприятии установлено новое  оборудование. Производительность этого  оборудования и затраты на содержание и ремонт зависят от времени. В таблице 1 показаны эти зависимости. Затраты на приобретение и установку нового оборудования составляют 40 тысяч рублей, старое оборудование списывается. Составить план замены оборудования на пять лет, максимизирующий общую прибыль.

Таблица 1.

	Время, в течение которого используется оборудование (лет)
t	0	1	2	3	4
Годовой выпуск продукции r(t)	80	75	65	60	60
Ежегодные затраты c( ) на содержание и ремонт оборудования (тысяч руб.)	20	25	30	35	45

 

 Введем следующие обозначения.

(t) – максимальный доход на временном отрезке i, . . . , n, при возрасте оборудования    лет в начале i−го года.

  – начальные затраты на приобретение и установку нового оборудования (цена нового оборудования) = 40 тысяч рублей и остается неизменной на протяжении всех лет

Составим уравнение  Беллмана:

Решение начинается с  последнего 5 года пятилетки. Пусть  это будет 1975 год. Так как в 1971 году оборудование было новым, то к  началу 1975 года при t=5 могут быть значения 1, 2, 3 или 4.

 

Этап 5:

 

			Оптимальное решение
				решение
1	75-25=50	80-20-40-20	50	c
2	65-30=35	80-20-40=20	35	c
3	60-35=25	80-20-40=20	25	с
4	60-45-15	80-20-40=20	20	н