Динамическое программирование. Задача о замене оборудования

1. Разбиение задачи на подзадачи меньшего размера.
2. Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
3. Использование полученного решения подзадач для конструирования решения исходной задачи.

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).³

 

 

Типовой алгоритм решения задач методом динамического программирования:

1. Описать строение оптимальных решений.
2. Выписать рекуррентное соотношение, связывающие оптимальные значения параметра для подзадач.
3. Двигаясь снизу вверх, вычислить оптимальное значение параметра для подзадач.
4. Пользуясь полученной информацией, построить оптимальное решение.

Для решения задач  оптимизации существует специальная  теория, большая заслуга в ее создании принадлежит Р. Беллману, в общем виде она достаточна сложна.⁴ 

Метод динамического программирования может применяться только для определенного класса задач. Эти задачи должны удовлетворять таким требованиям:

1. Задача оптимизации интерпретируется как n-шаговый процесс управления.
2. Целевая функция равна сумме целевых функций каждого шага.
3. Выбор управления на i-м шаге зависит только о состояния системы к этому шаге, не влияет на предшествующие шаги (нет обратной связи).
4. Состояние после i-го шага управления зависит только от предшествующего состояния   управления (отсутствие последействия).
5. На каждом шаге управление зависит от конечного числа управляющих переменных, а состояние от конечного числа параметров.

В основе решения всех задач динамического программирования лежит "принцип оптимальности" Беллмана, который выглядит следующим образом:  
Каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.  
Этот принцип впервые был сформулирован Р. Беллманом в 1953 г. Им же четко были сформулированы и условия, при которых принцип верен. Основное требование - процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.

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

 

       2.3. Достоинства  динамического   программирования:

 

1. Идея и метод динамического программирования наиболее приспособлены к дискретным задачам, каковыми являются задачи из экономики.

2. Метод динамического программирования применим при любом способе задания и любом допустимом множестве состояний и управлений. Этого преимущества лишены классические методы оптимизации и другие вычислительные методы математического программирования.

3. Вычислительные схемы метода динамического программирования в дискретном случае связаны с перебором оптимальных значений показателя эффективности и управления на i-м шаге для всех возможных значений переменной состояния, но объем расчетов по этому методу значительно меньше, чем при прямом переборе вариантов. Это связано с тем, что на этапе условной оптимизации неудачные варианты сразу отбрасываются, а сохраняются лишь условно оптимальные на данном шаге.

4. Метод динамического программирования дает возможность анализа чувствительности к изменению исходных данных S_i и n. Фактически здесь решается не одна задача, а множество однотипных задач для различных состояний S_i и различных на каждом шаге. Поэтому при изменении исходных данных можно не решать задачу заново, а сделать лишь несложные добавления к уже выполненным расчетам, т.е. продолжить уже решенную задачу за счет увеличения числа шагов n или числа значений S_i.⁶

 

4. Задача о замене оборудования. Постановка задачи в общем виде.

Чем дольше механизм эксплуатируется, тем выше затраты на его обслуживание и ниже его производительность. Когда  срок эксплуатации механизма достигает определенного уровня, может оказаться более выгодной его замена. Задача о замене оборудования, таким образом, сводиться к определению оптимального срока эксплуатации механизма.

Предположим, что мы занимаемся заменой механизмов на протяжении n лет. В начал каждого года принимается решение либо об эксплуатации механизма еще год, либо о его замене новым.

Обозначим через r(t) и c(t) прибыль от эксплуатации t–летнего механизма на протяжении года и затраты на его обслуживание за тот же период. Далее пусть  s(t) - стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна I.

Элементы модели динамического  программирования таковы :

1. Этап і представляется порядковым номером года і, і=1,2,...n
2. Вариантами решения на i–м этапе ( т. е. для i–го года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале i–го года.
3. Состоянием на i–ом этапе является срок эксплуатации (возраст) механизма к началу i–го года.

Пусть f_i(t)– максимальная прибыль, получаемая за годы от i до n  при условии, что в начале i–го года имеется механизм t– летнего возраста.

Рекуррентное уравнение  имеет следующий вид:

 

1. – если эксплуатировать механизм
2. – если заменить механизм.⁷

Постановка  задачи в общем виде.

Рассмотрим задачу  в общей  постановке.

Пусть в течение периода, состоящего из n этапов, предприятие использует оборудование, которое вместе с установкой имеет стоимость I. Со временем оборудование изнашивается. При этом:

1. суммарная производительность оборудования  r(t) снижается, так как увеличивается время, необходимое для его профилактики и ремонта;

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

по остаточной стоимости не учитывается. Это допущение не является принципиальным и введено для упрощения анализа.

Обозначим моменты начала каждого  этапа через  ; 

момент завершения всего периода  — через  . Тогда на каждом этапе мы можем выбрать одно из двух возможных управлений:

  — сохранить установленное  оборудование и продолжать его  эксплуатацию;

   — приобрести новое оборудование  и заменить старое.

Здесь следует подчеркнуть, что  управленческие решения могут применяться только в моменты

Оптимальной инвестиционной политикой (стратегией управления) U* называется совокупность таких решений    , в результате реализации которых рассматриваемое производство за n шагов переходит из начального     состояния в конечное        и при этом суммарная прибыль от эксплуатации оборудования достигает максимального значения. Состояние процесса на i-ом      этапе характеризуется возрастом оборудования. Максимально возможный возраст оборудования в момент     равен i, а минимальный равен 1, если на предыдущем этапе произошла замена оборудования.

Прибыль    ,получаемая на i-м этапе, зависит от состояния оборудования  и сделанного нами выбора (управления) :

    

где r(0) — стоимость продукции, выпускаемой на новом оборудовании;

s(t) – стоимость продажи оборудования, который эксплуатировался t лет;

I — полная стоимость нового оборудования.

Очевидно, что суммарная  прибыль F, которую требуется максимизировать  для разработки оптимальной инвестиционной политики, равна сумме прибылей на каждом из этапов производства. Таким образом, суммарная прибыль будет определяться по формуле:

В выражении (2) критерий является аддитивным. Для оптимизации  подобных критериев возможно использование методов динамического программирования.

Таким образом, суть разработки оптимальной инвестиционной политики — это получение максимального  значения суммарной прибыли F. Она  зависит от результатов управления процессом эксплуатации оборудования на каждом шаге. Особенностью динамического программирования является рассмотрение процесса от конца к началу, то есть сначала анализируется n-1 этап, ищется здесь оптимальное решение, затем то же делается на n-2 этапе и т.д.  Таким образом, основой математического аппарата для нахождения оптимального решения является принцип оптимальности Беллмана:

           (3)

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

Управление    выбирают следующим образом:

1) для всех возможных  управлений    определяются значения сумм

        (4),

которые сравниваются между  собой;

2) в качестве условно  оптимального управления выбирается  то управление, которое соответствует  наибольшему значению      (при решении задачи максимизации).

Если наибольшее значение     получается при применении нескольких различных управлений, то все они являются условно оптимальными. В этом случае   не единственный.

При выборе управления на предпоследнем этапе (при i = n-1) никаких дальнейших шагов по эксплуатации оборудования не планируется, так что естественно считать . Тогда в сумме (4) остается лишь первое слагаемое. Таким образом, процесс продвигается от конечного этапа к начальному и на всех промежуточных шагах находятся значения:

– условно оптимальных  управлений   для каждого из возможных состояний ;

– оптимальное значение    .

Вектор оптимального управления U* всего процесса будет  получен при объединении найденных  в ходе вычислений условно оптимальных управлений U*:

   

⁸

 

1. Задача 1.

Пусть требуется выработать оптимальную стратегию для эксплуатации оборудования на 6-ти летнем периоде (табл. 1).

Таблица 1.

Возраст оборудования – t(лет)	0	1	2	3	4	5
Производительность оборудования – r(t) (млн. руб.)	9	8	7	6	5	5
Затраты на ремонт – c(t) (млн. руб.)	1	1	2	2	3	4

 

Стоимость нового комплекта  оборудования I=6 млн. руб. Будем предполагать, что за пределами срока, представленного в таблице, эксплуатация оборудования нас не интересует.

Обозначения:

(t) – максимальный доход на временном отрезке i, . . . , n, при возрасте оборудования    лет в начале i−го года.

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

Составляем уравнение  Беллмана.

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

 

Этап 5:

			Оптимальное решение
				решение
1	8-1=7	9-6-1=2	7	c
2	7-2=5	9-6-1=2	5	c
3	6-2=4	9-6-1=2	4	с
4	5-3=2	9-6-1=2	2	с,н
5	5-4=1	9-1-6=2	2	н