Оптимальная политика замены оборудования (динамическое программирование)

Лекция 2 (23.03.2020) Оптимальная политика замены оборудования (динамическое программирование) Проблема своевременной замены устаревшего (физически или морально) оборудования возникает в любой сфере производственной деятельности. Поэтому возникает задача определения наиболее подходящего момента замены. В качестве критерия выбирается минимум ожидаемых затрат или максимум ожидаемой прибыли. Рассмотрим задачу. Пусть в начале планового периода из N лет имеется некоторое оборудование возраста t. Ежегодно на этом оборудовании производится продукция стоимостью r(t). Оборудование требует эксплуатационных затрат u(t) и имеет остаточную стоимость s(t). В любой год оборудование можно сохранить или продать по остаточной стоимости и купить новое по цене p. Требуется разработать оптимальную политику замены оборудования исходя из условий максимизации ожидаемой прибыли за период N лет. Будем следовать подходу Р. Беллмана и начнем процесс оптимизации с конца планового периода – рассмотрим сначала последний год. Пусть к началу последнего года имеется оборудование возраста t. Если оборудование сохранить, то за последний год прибыль составит: ( ) ( ). Если оборудование продать по остаточной стоимости и купить новое, то прибыль к концу последнего года составит: ( ) ( ) ( ), где ( ) – стоимость продукции, произведенной новым оборудованием («нулевого» возраста) за год, ( ) – расходы, связанные с эксплуатацией нового оборудования в течение года. Мы должны действовать так, чтобы последний год принес максимальную прибыль. Заменять оборудование выгодно лишь в том случае, когда ( ) ( ) ( ) ( ) ( ) ( ) максимально возможную прибыль за последние n лет планового периода Обозначим при условии, что в начале периода имеется оборудование возраста t и мы придерживаемся оптимальной политики. Тогда ( ) ( ) ( ) { ( ) ( ) ( ) Пусть n=2 – рассмотрим два последних года. Если оборудование сохраняет, то прибыль к концу первого года: ( ) ( ) За год оборудование постареет и к началу последнего года будет иметь возраст t+1 лет. Если придерживаться оптимальной политики на последнем году, то дополнительно будет ) , а общая прибыль за два года составит получена прибыль ( ( ) ( ) ( ) Если в начале второго года принято решение о замене оборудования, то затраты и ( ) ( ) К концу года прибыль от нового оборудования составят ( ) оборудование будет иметь возраст 1 год, поэтому прибыль за два года составит: ( ) ( ) ( ) ( ) Оптимальную политику за два последних года определяет функция: ( ) ( ) ( ) ( ) { ( ) ( ) ( ) ( ) Рассуждая аналогично, можно получить выражения для ( ) …. и т.д. Рекуррентные уравнения Беллмана имеют вид: ( ) ( ) ( ) ( ) { ( ) ( ) ( ) ( ) Рекуррентные уравнения Беллмана позволяют формировать оптимальную политику замен с конца планируемого периода последовательно находя: ( ), ( ), …., ( ) для любых значений t. Рассмотрим пример. Пусть N=10, а ( ) ( ) задаются таблицей: T 0 1 2 3 4 5 6 7 8 9 10 ( ) 27 26 26 25 24 23 23 22 21 21 20 ( ) 15 15 16 16 16 17 18 18 19 20 20 ( ) Сначала запишем функциональные уравнения для числовых данных примера: ( ) { ( ) ( ) ( ) { { ( ) Теперь начнем вычислять, начнем с Пусть t=0, тогда ( ) ( ) ( ) { ( ) ( ( ) ( ) ) ( ) ( ) , придавая t значения 0,1,2, …..,10 { ( ) { ( ) При t=1 ( ) { ( ) ( ) ( ) ( ) ( ) ( ) При t=7 ( ) { { ( { ( ) При t=8 ( ) { ) Видим, что с ростом t разность ( ) ( ) убывает, поэтому при t=8 и больших t оптимальной будет политика замены оборудования. Вычислим теперь ( ) ( ) { Последовательно находим При t=4 получаем ( ) ( ) { ( ) ( ) ( ) ( ) ( ) , ( ) ( ) , .. ( ) { Здесь обе политики обеспечивают одинаковую прибыль, лучше тогда выбрать политику сохранения т.к. имеющееся оборудование нам хорошо известно. При t=5 ( ) { Видим, что ( ) ( ) ( ) { , это обеспечивается при политике замены. ( ) И при t>5 оптимальной будет политика замены. Запишем ( ) ( ) { ( ) { ( ) ( ) ( ) ( ) ( ) Продолжая вычисления, заполним следующую таблицу: t 1 2 3 4 5 6 7 8 9 10 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 12 23 33 42 50 57 66 75 83 91 11 21 30 38 45 54 63 71 79 87 10 19 27 34 43 52 60 68 76 85 9 17 !! 24 33 42 50 58 66 75 83 8 14 24 !! 33 41 49 !!57 !! 66 74 82 6 !! 14 24 33 !! 41 !!48 57 66 !! 74 82 5 14 24 33 41 48 57 66 74 82 4 14 24 33 41 48 57 66 74 82 !! 3 14 24 33 41 48 57 66 74 82 3 14 24 33 41 48 57 66 74 82 3 14 24 33 41 48 57 66 74 82 Знаком !! для каждой строки отмечено значение t, начиная с которого надо выполнять политику замены оборудования. Разберем теперь, как с использованием таблицы и полученных результатов строить политику сохранения и замены оборудования. Предположим, например, что в начале десятилетнего периода имеется оборудование четырехлетнего возраста. Требуется разработать политику в отношении этого оборудования. Этот процесс формирования оптимальной можно изобразить символически : ( ) 1-й год, сохранение, ( ) 2-й год, замена , ( ) 3-й год, сохранение, ( ) ( ) 5-год, сохранение, ( ) 6-год, сохранение, 4-й год, сохранение, ( ) ( ) 8-й год, сохранение, ( ) 9-й год сохранение, 7-ой год, замена, ( ) 10-й год, сохранение.