11.2. Задача о замене оборудования
Известно, что проблема замены старого парка машин новыми, устаревших орудий — современными — одна из основных проблем индустрии.
Оборудование со временем изнашивается, стареет физически и «морально»; в процессе эксплуатации либо падает производительность оборудования, либо растут эксплуатационные расходы, либо и то и другое.
Поэтому задача о замене оборудования весьма актуальна.Формулировка задачи: рассматривается плановый период из нескольких лет, в начале которого имеется одна машина фиксированного возраста. В процессе работы машина дает ежегодно доход, требует эксплуатационных затрат и имеет остаточную стоимость, причем все перечисленные характеристики зависят от возраста ма- шины. В любой год машину можно сохранить или продать по остаточной стоимости и купить новую по известной цене (которая может меняться со временем). Задача состоит в следующем: для каждого года в плановом периоде надо решить — сохранять имеющуюся в этот момент машину или продать ее и купить новую с тем, чтобы суммарная прибыль за весь плановый период была макси-мальной.
Переход системы S из одного состояния в другое за 1 год в за-висимости от принятого решения можно изобразить графически (рис. 11.1).
Введем в рассмотрение функцию fn(t) — величину суммарного дохода (прибыли) за последние п лет планового периода при условии, что в начале этого периода из п лет имеется машина возраста /.
Функции f\(t)yfi(t), ...,/,(/), учитывающие вклад последующих шагов в общий эффект, называются функциями Беллмана — по фамилии американского математика Р. Беллмана, создателя метода динамического программирования.
С помощью этих функций ведется анализ задач динамического программирования. Очевидно, если мы сумеем вычислить fn(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.Таблица 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 Г 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), позволяющих осуществить рациональный процесс поиска оптимальных вариантов, чем полный перебор вариантов. Это делается при помощи функций Беллмана, несущих информацию об оптимальном про-должении процесса.