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

Известно, что проблема замены старого парка машин новыми, устаревших орудий — современными — одна из основных проблем индустрии.

Оборудование со временем изнашивается, стареет физически и «морально»; в процессе эксплуатации либо падает производительность оборудования, либо растут эксплуатационные расходы, либо и то и другое.

Формулировка задачи: рассматривается плановый период из нескольких лет, в начале которого имеется одна машина фиксированного возраста. В процессе работы машина дает ежегодно доход, требует эксплуатационных затрат и имеет остаточную стоимость, причем все перечисленные характеристики зависят от возраста ма- шины. В любой год машину можно сохранить или продать по остаточной стоимости и купить новую по известной цене (которая может меняться со временем). Задача состоит в следующем: для каждого года в плановом периоде надо решить — сохранять имеющуюся в этот момент машину или продать ее и купить новую с тем, чтобы суммарная прибыль за весь плановый период была макси-мальной.

Переход системы S из одного состояния в другое за 1 год в за-висимости от принятого решения можно изобразить графически (рис. 11.1).

Введем в рассмотрение функцию fn(t) — величину суммарного дохода (прибыли) за последние п лет планового периода при условии, что в начале этого периода из п лет имеется машина возраста /.

Функции f\(t)yfi(t), ...,/,(/), учитывающие вклад последующих шагов в общий эффект, называются функциями Беллмана — по фамилии американского математика Р. Беллмана, создателя метода динамического программирования.

Предположим, что к началу последнего года планового периода п = 1 у нас имеется машина возраста /. В нашем распоряжении две возможности. Рассмотрим их.

Возможность 1-я: сохранить машину и, следовательно, получить за последний год доход

(11.1)

ДО - U(t).

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

t — возраст машины: / = 0, 1,2,..., (/ = 0 — соответствует использованию новой машины, t = 1 — соответствует использованию машины возраста 1 год и т.д.);

Z(t) — стоимость продукции, производимой за 1 год на машине возраста /;

U(t) — эксплуатационные затраты за 1 год на машину возраста

S(t) — остаточная стоимость машины возраста /;

Т — текущее время в плановом периоде;

Р(Т) — цена новой машины в году Г (может меняться со временем от изменения цен; для простоты будем считать, что Р(Т) = Р, т. е. не зависит от времени);

ґ0 — начальный возраст машины;

N — длина планового периода.

Мы сделали ряд упрощений, чтобы не осложнять анализа задачи. Так, например, мы считаем, что функции Z(t), U(t), S(t) не зависят от текущего времени.

В нашей задаче в качестве системы S рассматривается машина, набор параметров, характеризующих ее состояние, состоит из единственного параметра — возраста машины. В качестве возможных управлений рассматриваются два решения — о сохранении имеющейся машины и о ее замене на новую. Условимся считать, что решения принимаются в моменты п = N; N — 1:... 1. Таким образом, плановый период разбит на шаги длиной в 1 год и в каждый из них решается — сохранить или заменить машину.

Возможность 2-я: продать имеющуюся машину и купить новую, что обеспечит в последний год доход

(П.2)

S(t) - Р + Z(0) - U(0).

Для принятия решения необходимо вычислить функцию Белл- мана /і (/), которая для нашего случая имеет вид:

(П.З)

Задача будет решена, если мы определим прибыль за весь плановый период, т.е.

Л + і и/„. (11.4)

Если связь между ними будет найдена, то последовательно, двигаясь с конца, где п = 1, и зная fx(t), сможем найти/2(/), —> /лКО и тем самым решить задачу.

Итак, предположим, что с конца планового периода остается п + 1 год; в нашем распоряжении имеется машина возраста t и мы ищем оптимальную политику для периода длиной п + 1 год. Этот период разбивается на две части (рис. 11.2).

1 п лет

(к

її і

Рис. 11.2.

Рассмотрим все возможные решения в «первом году» для машины возраста t и для каждого состояния системы найдем оптимальную политику в оставшейся части из п последних лет. Так мы получим политики на весь период из п + 1 последних лет, лучшая из которых и будет условно оптимальной для всего периода.

В случае сохранения машины доход за рассматриваемый период определяется выражением:

ДО-М»+/„('+ 1). (П.5)

В случае замены машины аналогичной имеем:

S(0-/>+Z(0)- ?/(0)+/„(1). (11.6)

Для принятия окончательного решения вычислим функцию Беллмана вида

\Z(t)-U(t) +fn(t + \) сохранение машины;

n+l ~m[S(t)-P + Z(0)-U(0) + fn(l) замена машины. (1L7)

Рекуррентные формулы (11.3.; 11.7) позволяют реализовать концепцию динамического программирования и развернуть процесс нахождения оптимальной политики с конца, последовательно находя /і(/),/2(0, 0> ...,/МО Д™ различных значений /.

Пример 11.1. Пусть функции Z(0, U(t) и значения А = Z(/) — — U(t) заданы табл. 11.1.

Мы ограничились машиной возраста t < 10 лет, так как из табл. 11.1 видно, что машина возраста t > 10 лет невыгодна. Будем считать условно (для простоты вычислений), что:

остаточная стоимость машины равна 0;

цена новой машины со временем не меняется и равна 10 условным единицам;

длина планового периода N равна 10 годам, т. е. S(t) = 0; Р = 10.

Таблица 11.1

Исходные данные t 0 1 2 3 4 5 6 7 8 9 10 Z(t) 20 20 20 19 19 18 18 17 17 16 15 U(t) 10 11 12 12 13 13 14 14 15 15 15 А 10 9 8 7 6 5 4 3 2 1 0

Тогда формулы (11.3 и 11.6) принимают вид

fx(t) = Z(t) - U(t) сохранение машины. (11.8)

\Z(t)-U(t) + fn(t +1) сохранение машины; /„+1(0 = max (11.9)

[y^(l) замена машины.

Используя полученные формулы, вычислим значения функций Беллмана^(/) при различных ли/.

Таблица 11.2

Решение задачи о замене оборудования с использованием метода динамического программирования 0 1 2 3 4 5 6 7 8 9 10 /і(0 10 9 8 7 6 5 4 3 2 1 0 fi(t) 19 17 15 13 11 9 9 9 9 9 9 т 27 24 21 18 17 17 17 17 17 17 17 т 34 30 26 24 24 24 24 24 24 24 24 № 40 35 32 31 30 30 30 30 30 30 30 № 45 41 39 37 36 35 35 35 35 35 35 МО 51 48 45 43 41 41 41 41 41 41 41 № 58 54 51 48 48 48 48 48 48 48 48 /9(0 64 60 56 55 54 54 54 54 54 54 54 /юЮ 70 65 63 61 60 60 60 60 60 60 60

Заполнение таблицы будем производить по строкам: сначала заполним первую строку, потом вторую и т. д. Заметим, что согласно формуле (11.8.) первая строка табл. 11.2 совпадает с последней строкой табл. 11.1.

Теперь перейдем к заполнению второй строки таблицы:

fz<0>-tf<°> + /i JlO + 9 1Q сохранение /2 (0) = max|^ ф = max|9 = 19 машины,

Г Z(l)-J7(l) + /1(2) /9 + 8 сохранение /2(l) = maxj^(i) =max|9 =17 машинЫ)

j Z(5) — ?/ (5) -ь /J (6) {5 + 4 сохранение

/2(5) = шахі = max і =9

машины.

2 l/i(l) [9

Здесь обе политики - сохранения и замены - обеспечивают одинаковую прибыль — 9 единиц, выбираем в этом случае «старую» машину, к которой «привыкли». Далее

' ч fZ(6)-tf(6) + ./i(7) [4 + 3 Л

/2(6) = тах^ 1 =тах\ =9 замена машины.

2 [ЛО) [9

Для того чтобы в таблице различать, в результате какой политики получается оптимальный доход (т. е. в данном случае /2(6)), мы будем величину оптимального дохода, соответствующую политике замены, записывать особым цветом, например, красным. Итак, значение /2(6) в таблице будет записано красным цветом.

Можно показать, что /2(7) = /2(8) = /2(9) = /2(10) = 9 и соответствует замене машины.

После заполнения второй строки таблицы (11.2) заполняем третью, четвертую и т.д. В итоге черный цвет в таблице соответствует политике сохранения машины, а красный — политике ее замены (в табл. 11.2 жирная черта отделяет черные и красные числа).

Построенная табл.

Допустим, вначале имеется машина возраста 7 лет. Посмотрим, какова будет оптимальная политика действий для получения максимальной прибыли за 10 лет планового периода.

Величина максимальной прибыли (согласно табл. 11.2) определяется функцией Беллмана/ю(7) = 60. Теперь найдем оптимальную политику, обеспечивающую эту прибыль.

Так как/10(7) вписано в таблицу красным цветом, то для достижения максимальной прибыли необходимо в первом году рассматриваемого периода заменить машину на новую. По истечении одного года мы за 9 лет до конца планового периода будем иметь машину возраста один год. Теперь надо действовать оптимально в ос-тавшийся период, располагая машиной возраста один год, т. е. найти ./9(1) из девяти лет. Из табл. 11.2 видно, что — черное, следовательно, во втором году надо сохранить машину. Рассматривая процесс по годам, замечаем: /8(2) — черное, /7(3) — черное, /6(4) — черное,/5(5) — красное. Последнее выражение (f$(5) — красное) указывает на то, что по истечении пяти лет планового периода машину надо менять на новую. Действуя далее оптимально, найдем последовательно: Д(\) — черное,/3(2) — черное,/2(3) — черное, /і(4) — черное. Итак, используя табл. 11.2, мы найдем оптимальную политику, которую можно представить схемой

/ЮС?)" замена сохранение ¦М2У сохранение /7(3) сохранение./*^) сохранение

замена /4(1)' сохранение /з(2) сохранение У2(з)' сохранение

В рассмотренной задаче число возможных решений, принимаемых ежегодно, равно двум (сохранить машину или заменить). На практике часто применяют решение о покупке неновой машины; в этом случае необходимо включить в число возможных решений (управлений) решение: заменить имеющуюся машину возраста t на машину возраста ^ < 5 (на старую заменять невыгодно).

В этом случае рекуррентные формулы (11.3 и 11.7) существенно усложняются. Динамическое программирование позволяет учесть все решения (управления), которые вызывают практический интерес.

Эффективность динамического программирования обусловлена использованием рекуррентных формул (11.3; 11.7), позволяющих осуществить рациональный процесс поиска оптимальных вариантов, чем полный перебор вариантов. Это делается при помощи функций Беллмана, несущих информацию об оптимальном про-должении процесса.