§5. Задача замены оборудования.

Постановка задачи. На некотором производстве рассматривается вопрос эксплуатации оборудования в период времени длительностью n лет. Этот период условно разбивается на этапы (например, один этап – один год). В начале каждого этапа относительно оборудования принимается решение: продолжать эксплуатировать старое или заменить его новым оборудованием. Решение зависит от следующих четырех характеристик оборудования: производительности, величины эксплуатационных расходов, остаточной стоимости старого и стоимости нового оборудования. Отметим, что первые три характеристики старого оборудования определяются его возрастом. Эти характеристики определяют прибыль, получаемую от эксплуатации оборудования. Требуется определить цикл замены оборудования в заданный период времени длительностью n лет, чтобы суммарная прибыль от его использования была максимальной.

Решение задачи. Введем обозначения. Пусть

t – возраст оборудования , t = 0, 1, …, n, где n – длина планового периода,

c(t) – стоимость продукции, производимой за год на единице оборудования, возраст которого t лет (производительность),

u(t) – ежегодные затраты на обслуживание этого оборудования (эксплуатационные расходы),

s(t) – остаточная стоимость оборудования,

p – стоимость нового оборудования.

Задачу решим методом динамического программирования. Первый этап метода – погружение задачи в семейство аналогичных задач. Рассмотрим при всех выше сформулированных условиях плановый период, включающий последние лет. Будем считать, что возраст оборудования на начало года равен t лет. Ясно, что . Если k = 0 , то получим исходную задачу.

0	1		…		k	k+1		…		n

Введем функцию Беллмана – максимальное значение прибыли за последние лет планового периода от использования оборудования, возраст которого на начало года равен t лет. Обозначим ее через Заметим, что это функция двух аргументов k и t. В принятых обозначениях возраст соответствует эксплуатации нового оборудования.

Перейдем ко второму этапу метода динамического программирования – составлению уравнения Беллмана. Для этого рассмотрим две возможные ситуации на начало .

Если на году оборудование, возраст которого t лет, сохранить, то прибыль предприятия от его использования равна –стоимостью произведенной продукции минус стоимостью эксплуатационных издержек. Следуя принципу оптимальности, считаем, что все последующие годы решение о замене оборудования принималось оптимально. Поэтому общая прибыль за последние лет в этом случае равна

+ B_n-(k+1)(t+1). (5.1)

Пусть на году оборудование, возраст которого t лет, заменяется новым. Тогда прибыль предприятия за этот год состоит из выручки от продажи старого плюс стоимость произведенной продукции на новом оборудовании минус эксплуатационные издержки нового оборудования и минус затраты на его покупку, т.е. равна  (). Согласно принципу оптимальности за последние лет в этом случае равна

 () + B_n-(k+1)(1). (5.2)

Таким образом, если величина прибыли (5.1) больше или равна величине прибыли (5.2), то нужно работать на старом оборудовании, в противном случае оборудование следует заменить. Объединяя (5.1) и (5.2), запишем уравнение Беллмана

B_n-k(t) = max, (5.3)

где первое выражение определяет прибыль, которая может быть получена за последние лет на старом оборудовании, второе – при его замене. При этом предполагается, что переход к работе на новом оборудовании происходит за один этап.

Полагая в (5.3) k = n1, получаем начальное условие для этого рекуррентного относительно аргумента k уравнения. Оно имеет вид уравнения одноэтапного процесса, для которого слагаемые B_n-(k+1)(t+1) и B_n-(k+1)(1) не имеют экономического смысла, и поэтому исключается, таким образом, прибыль от использования оборудования, возраст которого t лет, в последний год планового периода равна

B₁(t) = max. (5.4)

Третий этап метода динамического программирования – поиск решения уравнения (5.3) с начальными условиями (5.4) и построение по нему решения исходной задачи.

В уравнении (5.3) положим k = n2:

B₂(t) = max – (5.5)

это оптимальная прибыль за последние два года планового периода.

Далее полагаем в уравнении (5.3) k = n3, n4, … , 0. После процесса оптимизации получим последовательность B₃(t), B₄(t),…, B_n(t).

Алгоритм решения. Исходные данные заносим в таблицу 5.1.

Таблица 5.1.

t	0	1	2	…	n
r(t)	r(0)	r(1)	r(2)	…	r(n)
u(t)	u(0)	u(1)	u(2)	…	u(n)
s(t)	s(0)	s(1)	s(2)	…	s(n)

Далее составляем таблицу 5.2, заполняя ее значениями функции . Каждое значение функции Беллмана соответствует либо политике сохранения оборудования, либо политике его замены. В каждой строке таблицы будем отделять такие значения разграничивать жирной линией границы клетки.

Таблица 5.2.

t	0	1	2	…	n
B1 (t) - прибыль за последний год	B1 (0)	B1 (1)	B1 (2)	…	B1 (n)
B2 (t) - прибыль за последние два года	B2 (0)	B2 (1)	B2 (2)	…	B2 (n)
…	…	…	…	…
Bn(t) - прибыль за весь плановый период	Bn (0)	Bn (1)	Bn (2)	…	Bn (n)

Пример 1. Пусть рассматривается вопрос эксплуатации оборудования в период времени длительностью 10 лет. Этот период условно разбиваем на этапы: один этап – один год. В таблице 3 приведены исходные данные по производительности, по величине эксплуатационных расходов и остаточной стоимости старого оборудования. Стоимость нового оборудования равна 25 ден. ед. Требуется определить цикл замены оборудования в заданный период времени длительностью 10 лет, чтобы суммарная прибыль от его использования была максимальной.

Таблица 5.3.

t	0	1	2	3	4	5	6	7	8	9	10
r(t)	55	53	50	48	45	42	40	36	32	28	25
u(t)	7	8	10	12	14	16	18	20	22	24	25
s(t)	12	12	10	10	10	8	8	8	6	6	6

Табл. 5.4 заполняется значениями B₁(t) согласно уравнению (5.4), которое имеет вид:

B₁(t) = max{r(t)  u(t), s(t)+55725} = max{r(t)  u(t), s(t) + 23}.

Например, при t = 0 получим

B₁(0) = max{r(0) u(0), s(0)+23)} = max{557,12+23} = max{48,35}=48,

что соответствует политике сохранения оборудования. Аналогичный результат имеет место и для t = 1. Далее для t = 4 получаем

B₁(4) = max {r(4)  u(4), s(4)+ 23} = max {4514, 10+23} = 33,

что соответствует политике замены оборудования. Нетрудно убедиться,

Таблица 5.4.

t	0	1	2	3	4	5	6	7	8	9	10
B1(t)	48	45	40	36	33	31	31	31	29	29	29

что при t = 5 также следует придерживаться политики замены оборудования. Разграничим значения, соответствующие политике сохранения оборудования и политике замены оборудования жирной линией границы.

Оптимальную прибыль за последние два года планового периода находим по уравнению (5.5), которое имеет вид

B₂(t)=max{r(t)u(t)+B₁(t+1), s(t)+23+45}=max{r(t)u(t)+B₁(t+1), s(t)+68}.

Результаты вычислений помещаем в таблицу 5.5. Например, для t = 0, 1 получаем

B₂(0) = max{r(0)u(0)+B₁(1), s(0)+68} = max{48+45,12+68} = 93,

B₂(1) = max{r(1)u(1)+B₁(2), s(1)+68} = max{538+40,12+68} = 85,

что соответствует политике сохранения оборудования. Далее при t = 2имеем

B₂(2) = max{r(2)u(2)+B₁(3), s(2)+68} = max{5010+36,10+68} = 78,

B₂(3) = max{r(3)u(3)+B₁(4), s(3)+68} = max{4812+33,10+68} = 78,

и т.д., что соответствует политике замены оборудования.

Таблица 5.5.

t	0	1	2	3	4	5	6	7	8	9	10
B2(t)	93	85	78	78	78	76	76	76	74	74	74

Для получения значений прибыли за последние три года планового периода в уравнении (5.3) положим k = 7

B₃(t) = max{r(t)  u(t) + B₂(t+1), s(t) + 23 + B₂(1)} =

= max{r(t)  u(t) + B₂(t+1), s(t) + 108}.

Вычисления для значений B₃(t) для всех t = 0 представлены в таблице 5.6.

Таблица 5.6.

t	0	1	2	3	4	5	6	7	8	9	10
B3(t)	133	123	118	118	118	116	116	116	114	114	114

Далее придадим параметру k значения последовательно 6, 5,…,0 и выполним вычисления значений функции Беллмана для всех t = 0. Все результаты вычислений помещаем в итоговую таблицу 5.7.

Таблица 5.7.

t		0	1	2	3	4	5	6	7	8	9	10
B1(t)	48		45	40	36	33	31	31	31	29	29	29
B2(t)		93	85	78	78	78	76	76	76	74	74	74
B3(t)	133		123	118	118	118	116	116	116	114	114	114
B4(t)		171	163	158	156	156	154	154	154	152	152	152
B5(t)		211	203	196	196	196	194	194	194	192	192	192
B6(t)		251	241	236	236	236	234	234	234	232	232	232
B7(t)		289	281	276	274	274	272	272	272	270	270	270
B8(t)		329	321	314	314	314	312	312	312	310	310	310
B9(t)		369	359	354	354	354	352	352	352	350	350	350
B10(t)		407	399	394	392	392	390	390	390	388	388	388

Таблица 5.7 содержит много ценной информации о поставленной задаче, с ее помощью можно найти ответ на поставленный вопрос для любой задачи семейства.

Рассмотрим вариант, когда надо при 10-летнем плановом периоде решить вопрос об оптимальной замене оборудования, возраст которого на начало планового периода составляет 5 лет. В таблице 5.7 находим значение B₁₀(5) = 390, это максимальная прибыль. Это значение в строке находится справа от жирной черты, т.е. соответствует политике замены оборудования. Итак, на начало планового периода следует заменить оборудование. На начало 2-го года оборудование имеет возраст 1 год. В таблице 5.7 находим значение B₉(1) = 359, оно находится слева от жирной черты, т.е. в области политики сохранения оборудования. На начало 3-го года оборудование имеет возраст 2 года. В таблице 5.7 находим значение B₈(2) = 314, оно также находится в области политики сохранения оборудования. На начало 4-го года оборудование имеет возраст 3 года. Значение B₇(3) = 274 оно находится в области политики замены оборудования, т.е. в начале 4-года оборудование следует заменить. Продолжая аналогичные рассуждения, выясняем, что в следующие два года оборудование менять не нужно, а на начало 7-года его меняем на новое. Проработав на нем год, на начало 9-го года снова меняем оборудование, сохранив его на десятый год планового периода.

По таблице 5.7 можно решать любую задачу семейства, в которое мы погрузили исходную задачу, т.е. задачу замены оборудования с произвольным начальным состоянием в промежутке от 0 до 10 лет на любой плановый период, не превышающий 10 лет. Например, пусть плановый период составляет 6 лет, а оборудование на начало периода имеет возраст 5 лет. Тогда Согласно таблице 5.7 (начинаем со строки B₆(t)) максимальная прибыль равна 234, если оборудование заменить только на начало 1-го года и 4-го года.