Оптимальная политика замены оборудования (динамическое программирование)
Выбери формат для чтения
Статья: Оптимальная политика замены оборудования (динамическое программирование)
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Лекция 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-й год, сохранение.
