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

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

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

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

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

Введем обозначения: r(t) - стоимость продукции, производимой за один год на единице оборудования возраста t лет;

u(t) - ежегодные затраты на обслуживание оборудования возраста t лет;

s(t) - остаточная стоимость оборудования возраста t лет;

Р - покупная цена оборудования.

Рассмотрим период N лет, в пределах которого требуется определить оптимальный цикл замены оборудования.

Обозначим через fN(t) максимальный доход, получаемый от оборудования возраста t лет за оставшиеся N лет цикла использования оборудования при условии оптимальной стратегии.

Возраст оборудования отсчитывается в направлении течения процесса. Так, t = 0 соответствует случаю использования нового оборудования. Временные же стадии процесса нумеруются в обратном направлении по отношению к ходу процесса. Так, N = 1 относится к одной временной стадии, остающейся до завершения процесса, а N = N - к началу процесса.

На каждом этапе N–стадийного процесса должно быть принято решение о сохранении или замене оборудования. Выбранный вариант должен обеспечивать получение максимальной прибыли.

Функциональные уравнения, основанные на принципе оптимальности, имеют вид:

Первое уравнение описывает N–стадийный процесс, а второе- одностадийный. Оба уравнения состоят из двух частей: верхняя строка определяет доход, получаемый при сохранении оборудования; нижняя - доход, получаемый при замене оборудования и продолжении процесса работы на новом оборудовании.

В первом уравнении функция r(t) - u(t) есть разность между стоимостью произведенной продукции и эксплуатационными издержками на N–й стадии процесса.

Функция fN–1 (t + 1) характеризует суммарную прибыль от (N - 1) оставшихся стадий для оборудования, возраст которого в начале осуществления этих стадий составляет (t + 1) лет.

Нижняя строка в первом уравнении характеризуется следующим образом: функция s(t) - Р представляет чистые издержки по замене оборудования, возраст которого t лет.

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

Последняя функция fN–1 представляет собой доход от оставшихся N - 1 стадий, до начала осуществления которых возраст оборудования составляет один год.

Аналогичная интерпретация может быть дана уравнению для одностадийного процесса. Здесь нет слагаемого вида f0(t + 1), так как N принимает значение 1, 2,..., N. Равенство f0(t) = 0 следует из определения функции fN(t).

Уравнения являются рекуррентными соотношениями, которые позволяют определить величину fN(t) в зависимости от fN–1(t + 1). Структура этих уравнений показывает, что при переходе от одной стадии процесса к следующей возраст оборудования увеличивается с t до (t + 1) лет, а число оставшихся стадий уменьшается с N до (N - 1).

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

Пример. Определить оптимальный цикл замены оборудования при следующих исходных данных: Р = 10, S(t) = 0, f(t) = r(t) - u(t), представленных в таблице.

Решение. Уравнения запишем в следующем виде:

Вычисления продолжаем до тех пор, пока не будет выполнено условие f1(1) > f2(2), т.е. в данный момент оборудование необходимо заменить, так как величина прибыли, получаемая в результате замены оборудования, больше, чем в случае использования старого. Результаты расчетов помещаем в таблицу, момент замены отмечаем звездочкой, после чего дальнейшие вычисления по строчке прекращаем.

Можно не решать каждый раз уравнение, а вычисления проводить в таблице. Например, вычислим f4(t):

Дальнейшие расчеты для f4(t) прекращаем, так как f4(4) = 23 По результатам вычислений и по линии, разграничивающей области решений сохранения и замены оборудования, находим оптимальный цикл замены оборудования. Для данной задачи он составляет 4 года.

Ответ. Для получения максимальной прибыли от использования оборудования в двенадцатиэтапном процессе оптимальный цикл состоит в замене оборудования через каждые 4 года.

Оптимальное распределение ресурсов

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

Введем обозначения: xi - количество ресурсов, выделенных i–му предприятию (i = );

gi(xi) - функция полезности, в данном случае это величина дохода от использования ресурса xi, полученного i–м предприятием;

fk(x) - наибольший доход, который можно получить при использовании ресурсов х от первых k различных предприятий.

Сформулированную задачу можно записать в математической форме:

при ограничениях:

Для решения задачи необходимо получить рекуррентное соотношение, связывающее fk(x) и fk–1(x).

Обозначим через хk количество ресурса, используемого k–м способом (0 ≤ xk ≤ х), тогда для (k - 1) способов остается величина ресурсов, равная (x - xk). Наибольший доход, который получается при использовании ресурса (x - xk) от первых (k - 1) способов, составит fk–1(x - xk).

Для максимизации суммарного дохода от k–гo и первых (k - 1) способов необходимо выбрать xk таким образом, чтобы выполнялись соотношения

Рассмотрим конкретную задачу по распределению капиталовложений между предприятиями.

Распределение инвестиций для эффективного использования потенциала предприятия

Совет директоров фирмы рассматривает предложения по наращиванию производственных мощностей для увеличения выпуска однородной продукции на четырех предприятиях, принадлежащих фирме.

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

Найти распределение средств между предприятиями, обеспечивающее максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить не более одной инвестиции.

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

Рекуррентные соотношения будут иметь вид:

для предприятия № 1

для всех остальных предприятий

Решение будем проводить согласно рекуррентным соотношениям в четыре этапа.

1–й этап. Инвестиции производим только первому предприятию. Тогда

2–й этап. Инвестиции выделяем первому и второму предприятиям. Рекуррентное соотношение для 2–го этапа имеет вид

при х = 20 f2(20) = max (8 + 0,0 + 10) = max (8, 10) = 10,

при x = 40 f2(40) = max (16,8 + 10,20) = max (16, 18, 20) =20,

при х = 60 f2(60) = max (25,16 + 10, 8 + 20,28) = max (25,26, 28,28) =28,

при х = 80 f2(80) = max (36,25 + 10,16 + 20,8 + 28,40) = max (36, 35, 36, 36, 40) = 40,

при х = 100 f2(100) = max (44,36 + 10,25 + 20,16 + 28,8 + 40,48) = max (44, 46, 45, 44, 48, 48) = 48,

при х = 120 f2(120) = max (62,44 + 10,36 +20,25 + 28,16 + 40,8 + 48,62) = max (62, 54, 56, 53, 56, 56, 62) = 62.

3–й этап. Финансируем 2–й этап и третье предприятие. Расчеты проводим по формуле

при х = 20 f3(20) = mах (10, 12) = 12,

при x = 40 f3(40) = max (20,10 + 12,21) = max (20, 22, 21) = 22,

при х = 60 f3(60) = max (28,20 + 12,10 + 21,27) = max (28, 32, 31, 27) = 32,

при х = 80 f3(80) = max (40,28 + 12,20 + 21,10 + 27,38) = max (40, 40, 41, 37, 38) = 41,

при x = 100 f3(100) = max (48,40 + 12,28 + 21,20 + 27,10 + 38,50) = max (48, 52, 49, 47, 48, 50) = 52,

при х = 120 f3(120) = max (62,48 + 12,40 + 21,28 + 27,20 + 38,10 + 50,63) = max (62, 60, 61, 55, 58, 60, 63) = 63.

4–й этап. Инвестиции в объеме 120 млн р. распределяем между 3–м этапом и четвертым предприятием.

При х = 120 f4(120) = max (63,52 + 11,41 + 23,32 + 30,22 + 37,12 + 51,63) = max (63, 63, 64, 62, 59, 63, 63) = 64.

Получены условия управления от 1–го до 4–го этапа. Вернемся от 4–го к 1–му этапу. Максимальный прирост выпуска продукции в 64 млн р. получен на 4–м этапе как 41 + 23, т.е. 23 млн р. соответствуют выделению 40 млн р. четвертому предприятию (см. табл. 29.3). Согласно 3–му этапу 41 млн р. получен как 20 + 21, т.е. 21 млн р. соответствует выделеник 40 млн р. третьему предприятию. Согласно 2–этапу 20 млн р. получено при выделении 40 млн р. второму предприятию.

Таким образом, инвестиции в объеме 120 млн р. целесообразно выделить второму, третьему и четвертому предприятиям по 40 млн р. каждому, при этом прирост продукции будет максимальным и составит 64 млн р.

Минимизация затрат на строительство и эксплуатацию предприятий

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

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

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

Введем обозначения:

х - количество распределяемого ресурса, которое можно использовать п различными способами,

xi - количество ресурса, используемого по i–му способу (i = );

gi(xi) - функция расходов, равная, например, величине затрат на производство при использовании ресурса xi по i–му способу;

φk(x) - наименьшие затраты, которые нужно произвести при использовании ресурса х первыми k способами.

Необходимо минимизировать общую величину затрат при освоении ресурса x всеми способами:

при ограничениях

Экономический смысл переменных xi состоит в нахождении количества предприятий, рекомендуемого для строительства в i–м пункте. Для удобства расчетов будем считать, что планируется строительство предприятий одинаковой мощности.

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

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

Необходимо разместить предприятия таким образом, чтобы обеспечить минимальные суммарные затраты на их строительство и эксплуатацию. Значения функции затрат gi(x) приведены в таблице.

В данном примере gi(х) - функция расходов в млн р., характеризующая величину затрат на строительство и эксплуатацию в зависимости от количества размещаемых предприятий в i–м районе;

φk(x) - наименьшая величина затрат в млн. р., которые нужно произвести при строительстве и эксплуатации предприятий в первых k районах.

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

для остальных районов

Задачу будем решать в три этапа.

1–й этап. Если все предприятия построить только в первом районе, то

минимально возможные затраты при х = 5 составляют 76 млн р.

2–й этап. Определим оптимальную стратегию при размещении предприятий только в первых двух районах по формуле

Найдем φ2(l):

g2(1) + φ1(0) = 10 + 0 = 10,

g2(0) + φ1(l)= 0 +11 = 11,

φ2(l) = min (10, 11) = 10.

Вычислим φ2(2):

g2(2) + φ1(0) = 19 + 0 = 19,

g2(l) + φ1(l) = 10 + 11 = 21,

g2(0) + φ1 (2) = 0 + 18 = 18,

φ2(2) = min (19, 21, 18) = 18.

Найдем φ2(3):

g2(3) + φ1 (0) = 34 + 0 = 34,

g2(2) + φ1(l) = 19 + 11 = 30,

g2(1) + φ1(2) = 10 + 18 = 28,

g2(0) + φ1(3) = 0 + 35 = 35,

φ2(3) = min (34, 30, 28, 35) = 28.

Определим φ2(4):

g2(4) + φ1(0) = 53 + 0 = 53,

g2(3) + φ1(l) = 34 + 11 = 45,

g2(2) + φ1(2) = 19 + 18 = 37,

g2(l) + φ1(3) = 10 + 35 = 45,

g2(0) +φ1(4) = 0 + 51 = 51,

φ2(4) = min (53, 45, 37, 45, 51) = 37.

Вычислим φ2(5):

g2(5) + φ1(0) = 75 + 0 = 75,

g2(4) + φ1(l) = 53 + 11 = 64,

g2(3) + φ1(2) = 34 + 18 = 52,

g2(2) + φ1(3) = 19 + 35 = 54,

g2(1) + φ1(4) = 10 + 51 = 61,

g2(0) + φ1(5) = 0 + 76 = 76,

φ2(5) = min (75, 64, 52, 54, 61, 76) = 52.

3–й этап. Определим оптимальную стратегию при размещении пяти предприятий в трех районах по формуле

φ3(x) = min{g3(x3) + φ2(x – х3)}.

Найдем φ3(5):

g3(5) + φ2(0) = 74 + 0 = 74,

g3(4) + φ2(1) = 54 + 10 = 64,

g3(3) + φ2(2) = 36 + 18 = 54,

g3(2) +φ2(3) = 20 + 28 = 48,

g3(1) + φ2(4) = 9 + 37 = 46,

g3(0) + φ2(5) = 0 + 52 = 52,

φ3(5) = min (74, 64, 54, 48, 46, 52) = 46.

Минимально возможные затраты при х = 5 составляют 46 млн р.

Определены затраты на строительство предприятий от 1–го до 3–го этапа. Вернемся 3–го к 1–му этапу. Минимальные затраты в 46 млн р. на 3–м этапе получены как 9 + 37, т.е. 9 млн р. соответствуют строительству одного предприятия в третьем районе (см. табл. 29.4). Согласно 2–му этапу 37 млн р. получены как 19 + 18, т.е. 19 млн р. соответствуют строительству двух предприятий во втором районе. Согласно 1–му этапу 18 млн р. соответствуют строительству двух предприятий в первом районе.

Ответ. Оптимальная стратегия состоит в строительстве одного предприятия в третьем районе, по два предприятия во втором и первом районах, при этом минимальная стоимость строительства и эксплуатации составит 46 ден. ед.

Нахождение рациональных затрат при строительстве трубопроводов и транспортных артерий

Требуется проложить путь (трубопровод, шоссе) между двумя пунктами А и В таким образом, чтобы суммарные затраты на его сооружение были минимальные.

Решение. Разделим расстояние между пунктами А и В на шаги (отрезки). На каждом шаге можем двигаться либо строго на восток (по оси X), либо строго на север (по оси Y). Тогда путь от А в В представляет ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей. Затраты на сооружение каждого из отрезков известны (рис. 29.2) в млн р.

Разделим расстояние от А до В в восточном направлении на 4 части, в северном – на 3 части. Путь можно рассматривать как управляемую систему, перемещающуюся под влиянием управления из начального состояния А в конечное В. Состояние этой системы перед началом каждого шага будет характеризоваться двумя целочисленными координатами х и у. Для каждого из состояний системы (узловой точки) найдем условное оптимальное управление. Оно выбирается так, чтобы стоимость всех оставшихся шагов до конца процесса была минимальна. Процедуру условной оптимизации проводим в обратном направлении, т.е. от точки В к точке А.

Найдем условную оптимизацию последнего шага.

Данный сервис предназначен для онлайн решения задачи оптимальной стратегии обновления оборудования . Обычно в исходных данных задаются следующие параметры:

• r(t) - стоимость продукции, произведенной в течение каждого года планового периода с помощью этого оборудования;
• u(t) - ежегодные затраты, связанные с эксплуатацией оборудования;
• s(t) - остаточная стоимость оборудования;
• р - стоимость нового оборудования, включающая расходы, связанные с установкой, наладкой, запуском оборудования и не меняющаяся в данном плановом периоде.

Если стоимость оборудования не указана, будет решаться задача с функциями затрат и замены (задача планирования капитальных вложений).

Планирование капитальных вложений.

Пример №1 . Найти оптимальную стратегию эксплуатации оборудования на период продолжительностью 6 лет, если годовой доход r(t) и остаточная стоимость S(t) в зависимости от возраста заданы в таблице, стоимость нового оборудования равна P = 13 , а возраст оборудования к началу эксплуатационного периода составлял 1 год.

t	0	1	2	3	4	5	6
r(t)	8	7	7	6	6	5	5
s(t)	12	10	8	8	7	6	4

Решение .
I этап. Условная оптимизация (k = 6,5,4,3,2,1).
Переменной управления на k-м шаге является логическая переменная, которая может принимать одно из двух значений: сохранить (С) или заменить (З) оборудование в начале k-го года.
1-й шаг: k = 6. Для 1-го шага возможные состояния системы t = 1,2,3,4,5,6, а функциональные уравнения имеют вид:
F 6 (t) = max(r(t), (C); S(t) - P + r(0), (З))
F 6 (1) = max(7 ; 10 - 13 + 8) = 7 (C)
F 6 (2) = max(7 ; 8 - 13 + 8) = 7 (C)
F 6 (3) = max(6 ; 8 - 13 + 8) = 6 (C)
F 6 (4) = max(6 ; 7 - 13 + 8) = 6 (C)
F 6 (5) = max(5 ; 6 - 13 + 8) = 5 (C)
F 6 (6) = max(5 ; 4 - 13 + 8) = 5 (C)
2-й шаг: k = 5. Для 2-го шага возможные состояния системы t = 1,2,3,4,5, а функциональные уравнения имеют вид:
F 5 (t) = max(r(t) + F 6 (t+1) ; S(t) - P + r(0) + F 6 (1))
F 5 (1) = max(7 + 7 ; 10 - 13 + 8 + 7) = 14 (C)
F 5 (2) = max(7 + 6 ; 8 - 13 + 8 + 7) = 13 (C)
F 5 (3) = max(6 + 6 ; 8 - 13 + 8 + 7) = 12 (C)
F 5 (4) = max(6 + 5 ; 7 - 13 + 8 + 7) = 11 (C)
F 5 (5) = max(5 + 5 ; 6 - 13 + 8 + 7) = 10 (C)
F 5 (6) = max(5 + ; 4 - 13 + 8 + 7) = 6 (З)
3-й шаг: k = 4. Для 3-го шага возможные состояния системы t = 1,2,3,4, а функциональные уравнения имеют вид:
F 4 (t) = max(r(t) + F 5 (t+1) ; S(t) - P + r(0) + F 5 (1))
F 4 (1) = max(7 + 13 ; 10 - 13 + 8 + 14) = 20 (C)
F 4 (2) = max(7 + 12 ; 8 - 13 + 8 + 14) = 19 (C)
F 4 (3) = max(6 + 11 ; 8 - 13 + 8 + 14) = 17 (C/З)
F 4 (4) = max(6 + 10 ; 7 - 13 + 8 + 14) = 16 (C/З)
F 4 (5) = max(5 + 6 ; 6 - 13 + 8 + 14) = 15 (З)
F 4 (6) = max(5 + ; 4 - 13 + 8 + 14) = 13 (З)
4-й шаг: k = 3. Для 4-го шага возможные состояния системы t = 1,2,3, а функциональные уравнения имеют вид:
F 3 (t) = max(r(t) + F 4 (t+1) ; S(t) - P + r(0) + F 4 (1))
F 3 (1) = max(7 + 19 ; 10 - 13 + 8 + 20) = 26 (C)
F 3 (2) = max(7 + 17 ; 8 - 13 + 8 + 20) = 24 (C)
F 3 (3) = max(6 + 16 ; 8 - 13 + 8 + 20) = 23 (З)
F 3 (4) = max(6 + 15 ; 7 - 13 + 8 + 20) = 22 (З)
F 3 (5) = max(5 + 13 ; 6 - 13 + 8 + 20) = 21 (З)
F 3 (6) = max(5 + ; 4 - 13 + 8 + 20) = 19 (З)
5-й шаг: k = 2. Для 5-го шага возможные состояния системы t = 1,2, а функциональные уравнения имеют вид:
F 2 (t) = max(r(t) + F 3 (t+1) ; S(t) - P + r(0) + F 3 (1))
F 2 (1) = max(7 + 24 ; 10 - 13 + 8 + 26) = 31 (C/З)
F 2 (2) = max(7 + 23 ; 8 - 13 + 8 + 26) = 30 (C)
F 2 (3) = max(6 + 22 ; 8 - 13 + 8 + 26) = 29 (З)
F 2 (4) = max(6 + 21 ; 7 - 13 + 8 + 26) = 28 (З)
F 2 (5) = max(5 + 19 ; 6 - 13 + 8 + 26) = 27 (З)
F 2 (6) = max(5 + ; 4 - 13 + 8 + 26) = 25 (З)
6-й шаг: k = 1. Для 6-го шага возможные состояния системы t = 1, а функциональные уравнения имеют вид:
F 1 (t) = max(r(t) + F 2 (t+1) ; S(t) - P + r(0) + F 2 (1))
F 1 (1) = max(7 + 30 ; 10 - 13 + 8 + 31) = 37 (C)
F 1 (2) = max(7 + 29 ; 8 - 13 + 8 + 31) = 36 (C)
F 1 (3) = max(6 + 28 ; 8 - 13 + 8 + 31) = 34 (C/З)
F 1 (4) = max(6 + 27 ; 7 - 13 + 8 + 31) = 33 (C/З)
F 1 (5) = max(5 + 25 ; 6 - 13 + 8 + 31) = 32 (З)
F 1 (6) = max(5 + ; 4 - 13 + 8 + 31) = 30 (З)
Результаты вычислений по уравнениям Беллмана F k (t) приведены в таблице, в которой k - год эксплуатации, а t - возраст оборудования.
Таблица – Матрица максимальных прибылей

k / t	1	2	3	4	5	6
1	37	36	34	33	32	30
2	31	30	29	28	27	25
3	26	24	23	22	21	19
4	20	19	17	16	15	13
5	14	13	12	11	10	6
6	7	7	6	6	5	5

В таблице выделено значение функции, соответствующее состоянию (З) - замена оборудования.
При решении данной задачи в некоторых таблицах при оценке выбора нужного управления мы получали одинаковые значения F для обоих вариантов управления. В этом случае, в соответствии с алгоритмом решения подобных задач необходимо выбирать управление сохранения оборудования.
II этап. Безусловная оптимизация (k = 6,5,4,3,2,1).
По условию задачи возраст оборудования равен t 1 =1 годам. Плановый период N=6 лет.
К началу 1-го года эксплуатации возраст оборудования увеличится на единицу и составит: t 1 = t 0 + 1 = 0 + 1 = 1. Прибыль составит F 1 (1)=37.
Оптимальное управление при k = 1, x 1 (1) = (C), т.е. максимум дохода за годы с 1-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
К началу 2-го года эксплуатации возраст оборудования увеличится на единицу и составит: t 2 = t 1 + 1 = 1 + 1 = 2. Прибыль составит F 2 (2)=30.
Оптимальное управление при k = 2, x 2 (2) = (C), т.е. максимум дохода за годы с 2-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
К началу 3-го года эксплуатации возраст оборудования увеличится на единицу и составит: t 3 = t 2 + 1 = 2 + 1 = 3. Прибыль составит F 3 (3)=23.
Безусловное оптимальное управление при k = 3, x 3 (3)=(З), т.е. для получения максимума прибыли за оставшиеся годы необходимо в этом году провести замену оборудования.
К началу 4-го года эксплуатации возраст оборудования увеличится на единицу и составит: t 4 = t 3 + 1 = 0 + 1 = 1. Прибыль составит F 4 (1)=20.
Оптимальное управление при k = 4, x 4 (1) = (C), т.е. максимум дохода за годы с 1-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
К началу 5-го года эксплуатации возраст оборудования увеличится на единицу и составит: t 5 = t 4 + 1 = 1 + 1 = 2. Прибыль составит F 5 (2)=13.
Оптимальное управление при k = 5, x 5 (2) = (C), т.е. максимум дохода за годы с 2-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
К началу 6-го года эксплуатации возраст оборудования увеличится на единицу и составит: t 6 = t 5 + 1 = 2 + 1 = 3. Прибыль составит F 6 (3)=6.
Оптимальное управление при k = 6, x 6 (3) = (C), т.е. максимум дохода за годы с 3-го по 6-й достигается, если оборудование сохраняется, т.е. не заменяется.
F 1 (1) → (C) → F 2 (2) → (C) → F 3 (3) → (З) → F 4 (1) → (C) → F 5 (2) → (C) → F 6 (3) → (C) →
Таким образом, за 6 лет эксплуатации оборудования замену надо произвести в начале 3-го года эксплуатации

Пример №2 . Задача планирования капитальных вложений. Интервал планирования Т=5 лет. Функция затрат на ремонт и дальнейшую эксплуатацию K(t)=t+2t 2 (р.); функция замены P(t)=10+0.05t 2 (р.). Определить оптимальную стратегию замены и ремонта для нового оборудования (t=0) и оборудования возраста t=1, t=2, t=3.
Определить оптимальные планируемые затраты по годам пятилетки, если количество оборудования по возрастным группам следующие: n(t=0)=10, n(t=1)=12, n(t=2)=8, n(t=3)=5

После того как выполнены пункты 1-7, и математическая модель составлена, приступают к ее расчету.

Основные этапы решения задачи динамического программирования:

• 1. Определение множества возможных состояний Sm для последнего шага.
• 2. Проведение условной оптимизации для каждого состояния s€ Sm на последнем m-м шаге по формуле (1.3) и определение условного оптимального управления x(s), s€ Sm
• 3. Определение множества возможных состояний Si для i-го шага, i=2,3…,m-1.
• 4. Проведение условной оптимизации i-го шага, i=2,3…,m-1 для каждого состояния s€ S m по формуле (1.4) и определение условного оптимального управления x i (s), s€ S m , i=2,3…,m-1.
• 5. Определение начального состояния системы s 1 , оптимального выигрыша W1(S1) и оптимального управления x1(S1) по формуле (1.4) при i=1. Это есть оптимальный выигрыш для всей задачи W* =W 1 (x 1 *).
• 6. Проведение безусловной оптимизации управления. Для проведения безусловной оптимизации необходимо найденное на первом шаге оптимальное управление x 1 *=x 1 (s 1) подставить в формулу (1.2) и определить следующее состояние системы s 1 =f 1 (s 1 ,x 1). Для измененного состояния найти оптимальное управление x 2 *=x 2 (s 2), подставить в формулу (1.2) и т.д. Для i-го состояния s 1 найти s i+1 =f i+1 (s i ,x i *) и x* i+1 (s i+1) и т.д.

Динамическое программирование обычно придерживается двух подходов к решению задач:

• · нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач;
• · восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи.

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

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

Принцип оптимальности Беллмана -- важнейшее положение динамического программирования, которое гласит: оптимальное поведение в задачах динамического программирования обладает тем свойством, что каковы бы ни были первоначальное состояние и решение (т. е. “управление”), последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения. Этот принцип можно выразить и рассуждая от противного: если не использовать наилучшим образом то, чем мы располагаем сейчас, то и в дальнейшем не удастся наилучшим образом распорядиться тем, что мы могли бы иметь.

Следовательно, если имеется оптимальная траектория, то и любой ее участок представляет собой оптимальную траекторию.

Этот принцип позволяет сформулировать эффективный метод решения широкого класса многошаговых задач.

Под функцией Беллмана в текущий момент времени понимаем минимальное значение критерия качества в текущий момент времени: Если t=0, то

Таким образом, значение функции Беллмана S(x,t) определяет минимальную величину функционала для любого начального состояния x(t) в любой момент времени t . С другой стороны, значение функции Беллмана совпадает со значением, так называемых текущих потерь на управление:

Эксплуатация оборудования планируется в течение n лет, но оборудование имеет тенденцию с течением времени стареть и приносить все меньшую годовую прибыль r(t) , где t - возраст оборудования. При этом есть выбор: либо в начале любого года продать устаревшее оборудование за цену S(t) , которая также зависит от возраста, и купить новое оборудование за цену P , либо оставить оборудование в эксплуатации. Требуется найти оптимальный план замены оборудования с тем, чтобы суммарная прибыль за все n лет была максимальной, учитывая, что к началу эксплуатационного периода возраст оборудования составляет t 0 лет.

Входными данными к этой задаче являются:

r(t) - доход от эксплуатации в течение одного года оборудования возраста t лет;

S(t) - остаточная стоимость оборудования;

P - цена нового оборудования;

t 0 - начальный возраст оборудования.

Переменной управления на k -м шаге является логическая переменная, которая может принимать два значения: С - сохранить , З - заменить оборудование в начале k -го года. Переменной состояния системы на k -м шаге является переменная t .

Функцию Беллмана F k (t) определим как максимально возможную прибыль от эксплуатации оборудования за годы с k -го по n -й, если к началу k -го года возраст оборудования составлял t лет. Применяя то или иное управление, мы переводим систему в некоторое новое состояние, а именно, если в начале k -го года мы оборудование сохраняем, то к началу следующего (k+1) -го года его возраст увеличится на 1 (состояние системы станет равно t +1), за год оно принесет прибыль r(t) , и максимально возможная прибыль за оставшиеся годы (с (k+1) -го по n -й) составит F k+1 (t+1) . Если же в начале k -го года принимаем решение на замену оборудования, то мы продаем старое оборудование возраста t лет за цену S(t) , покупаем новое оборудование за цену P и эксплуатируем его в течение k -го года, что приносит за этот год прибыль r(0) . К началу следующего года возраст оборудования составит 1 год, и за все годы с (k+1) -го по n -й максимально возможная прибыль будет F k+1 (1) .

Из этих двух вариантов управления выбираем тот, который приносит большую прибыль. Уравнение Беллмана на каждом шаге имеет вид:

Функцию Беллмана для первого шага (k=n ) легко вычислить - это максимально возможная прибыль только за последний n -й год:

Вычислив значение функции F n (t) по формуле (2), далее можно посчитать F n-1 (t) , затем F n-2 (t) и так далее до F 1 (t 0 ) . Функция F 1 (t 0 ) представляет собой максимально возможную прибыль за все годы (с 1-го по n -й). Этот максимум достигается при некотором управлении, применяя которое в течение первого года, мы определяем возраст оборудования к началу второго года (в зависимости от того, какое управление является для первого года оптимальным, это будет 1 или t 0 +1). Для данного возраста оборудования по результатам, полученным на этапе условной оптимизации , мы смотрим, при каком управлении достигается максимум прибыли за годы со 2-го по n -й и так далее. На этапе безусловной оптимизации отыскиваются годы, в начале которых следует произвести замену оборудования.

Определить оптимальную стратегию использования оборудования в период времени длительностью т лет, причем прибыль за каждые i лет, i = от использования оборудования возраста t лет должна быть максимальной.

Известны

r (t ) – выручка от реализации продукции, произведенной за год на оборудовании возраста t лет;

l (t ) – годовые затраты, зависящие от возраста оборудования t;

с (t ) – остаточная стоимость оборудования возраста t лет;

Р – стоимость нового оборудования.

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

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

1. Определение числа шагов. Число шагов равно числу лет, в течение которого эксплуатировалось это оборудование.

2. Определние состояний системы. Состояние системы характеризуется возрастом оборудования t , t= .

3. Определение уравнений. В начале i -го шага, i = может быть выбрано одно из двух управлений: заменять или не заменять оборудование. Каждому варианту управления приписывается число

4. Определение функции выигрыша на i -ом шаге. Функция выигрыша на i -ом шаге – это прибыль от использования оборудования к концу i -го года эксплуатации, t= , i = . Таким образом, если оборудование не продается, то прибыль от его использования – это разность между стоимостью произведенной продукции и эксплуатационными издержками. При замене оборудования прибыль составляет разность между остаточной стоимостью оборудования и стоимостью нового оборудования, к которой прибавляется разность между стоимостью продукции и эксплуатационными издержками для нового оборудования, возраст которого в начале i -го шага составляет 0 лет.

5. Определение функции изменения состояния

(9.7)

Таким образом, если оборудование не меняется х i =0, то возраст оборудования увеличивается на один год t +1, если же оборудование меняется х i =1, то оборудование будет годовалым.

6. Составление функционального уравнения для i =т

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

7. Составление основного функционального уравнения

где W i (t t лет с i -го шага (с конца i -го года) до конца периода эксплуатации;

W i + 1 (t ) – прибыль от использования оборудования возраста t+ 1год с (i +1)-го шага до конца периода эксплуатации.

Математическая модель задачи построена.

Пример

т =12, р= 10, с (t )=0, r (t ) – l (t )=φ (t ).

Значения φ (t ) даны в таблице 9.1.

Таблица 9.1.

t

φ (t )

Для данного примера функциональные уравнения будут иметь вид

Рассмотрим заполнение таблицы для нескольких шагов.

Условная оптимизация начинается с последнего 12-го шага. Для i =12 рассматриваются возможные состояния системы t= 0, 1, 2, …, 12. Функциональное уравнение на 12-ом шаге имеет вид

1) t= 0 х 12 (0)=0.

2) t= 1 х 12 (1)=0.

10) t= 9 х 12 (9)=0.

11) t= 10 х 12 (10)=0; х 12 (10)=1.

13) t= 12 х 12 (12)=0; х 12 (12)=1.

Таким образом, на 12-ом шаге оборудование возраста 0 – 9 лет заменять не надо. Оборудование возраста 10 – 12 лет можно заменить или продолжить его эксплуатировать, так как для t= 10, 11, 12 имеется два условных оптимизационных управления 1 и 0.

По результатам расчетов заполняются два столбца таблицы 9.2, соответствующие i= 12.

Условная оптимизация 11-го шага.

Для i =11 рассматриваются все возможные состояния системы t =0, 1, 2, …, 12. Функциональное уравнение на 11-м шаге имеет вид

1) t= 0 х 11 (0)=0.

2) t= 1 х 11 (1)=0.

6) t= 5 х 11 (5)=0; х 11 (5)=1.

7) t= 6 х 11 (6)=1.

13) t= 12 х 11 (12)=1.

Таким образом на 11-ом шаге не следует заменять оборудование возраста 0 – 4 года. Для оборудования возраста 5 лет возможны две стратегии использования: заменить или продолжать эксплуатировать.

Начиная с 6-го года оборудование следует заменять. По результатам расчетов заполняются два столбца таблицы 9.2, соответствующие i =11.

1) t= 0 х 10 (0)=0.

2) t= 1 х 10 (1)=0.

3) t= 2 х 10 (2)=0.

4) t= 3 х 10 (3)=0.

5) t= 4 х 10 (4)=1.

13) t= 12 х 10 (12)=1.

На 10-ом шаге не следует заменять оборудование возраста 0 – 3 года. Начиная с 4-го года, оборудование следует заменять, так как новое оборудование приносит бóльшую прибыль.

По результатам расчетов заполняются два столбца в 9.2, соответствующие i =10.

Аналогичным образом заполняются остальные девять столбцов таблицы 9.2. При расчетах W i + 1 (t ) на каждом шаге значения φ (t ) для каждого t =0, 1, 2, …, 12 берутся из таблицы 9.1 исходных данных, приведенной в условии задачи, а значения W i (t ) – из последнего, заполненного на предыдущем шаге столбца в 9.2.

Этап условной оптимизации заканчивается после заполнения таблицы 9.2.

Безусловная оптимизация начинается с первого шага.

Предположим, что на первом шаге i =1 имеется новое оборудование, возраст которого 0 лет.

Для t=t 1 =0 оптимальный выигрыш составляет W 1 (0)=82. Это значение соответствует максимальной прибыли от использования нового оборудования в течение 12 лет.

W*=W 1 (0)=82.

Выигрышу W 1 (0)=82 соответствует х 1 (0)=0.

Для i =2 по формуле (9.7) t 2 =t 1 +1=1.

Безусловное оптимальное управление х 2 (1)=0.

Для i =3 по формуле (9.7) t 3 =t 2 +1=2.

Безусловное оптимальное управление х 3 (2)=0.

i =4	t 4 =t 3 +1=3	х 4 (3)=0
i =5	t 5 =t 4 +1=4	х 5 (4)=1
i =6	t 6 = 1	х 6 (1)=0
i =7	t 7 =t 6 +1=2	х 7 (2)=0
i =8	t 8 =t 7 +1=3	х 8 (3)=0
i =9	t 9 =t 8 +1=4	x 9 (4)=1
i =10	t 10 = 1	х 10 (1)=0
i =11	t 11 =t 10 +1=2	х 11 (2)=0
i =12	t 12 =t 11 +1=3	х 12 (3)=0

В рамках данной задачи оптимальная стратегия заключается в замене оборудования при достижении им возраста 4-х лет. Аналогичным образом можно определить оптимальную стратегию использования оборудования любого возраста.

В левой колонке таблицы 9.2 записываются возможные случаи системы t = , в верхней строке – номера шагов i = . Для каждого шага определяются условные оптимальные управления х i (t ) и условный оптимальный выигрыш W i (t ) c i -го шага и до конца для оборудования возраста t лет.

Управления, составляющие оптимальную стратегию использования оборудования, выделены в таблице 9.2 жирным шрифтом.

Таблица 9.2.

t

i =12

i =11

i =10

i =9

i =8

i =7

i =6

i =5

i =4

i =3

i =2

i =1

x 12

W 12

x 11

W 11

x 10

W 10

x 9

W 9

x 8

W 8

x 7

W 7

x 6

W 6

x 5

W 5

x 4

W 4

x 3

W 3

x 2

W 2

x 1

W 1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

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

Предположим, что планируется эксплуатация оборудования в течение некоторого периода времени продолжительностью n лет. Оборудование имеет тенденцию с течением времени стареть и приносить все меньший доход r (t ) (t – возраст оборудования). При этом есть возможность в начале любого года продать устаревшее оборудование за цену S (t ), которая также зависит от возраста t , и купить новое оборудование за цену P .

Под возрастом оборудования понимается период эксплуатации оборудования после последней замены, определенный в годах. Требуется найти оптимальный план замены оборудования с тем, чтобы суммарный доход за все n лет был бы максимальным, учитывая, что к началу эксплуатации возраст оборудования составлял t 0 лет.

Исходными данными в задаче являются доход r (t ) от эксплуатации в течение одного года оборудования возраста t лет, остаточная стоимость S (t ), цена нового оборудования P и начальный возраст оборудования t 0 .

t			…	n
r	r(0)	r(1)	…	r(n)
S	S(0)	S(1)	…	S(n)

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

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

Поскольку процесс оптимизации ведется с последнего шага (k = n ), то на k -ом шаге неизвестно, в какие годы с первого по (k -1)-й должна осуществляться замена и, соответственно, неизвестен возраст оборудования к началу k -го года. Возраст оборудования, который определяет состояние системы, обозначим t . На величину t накладывается следующее ограничение:

1 ≤ t ≤ t 0 + k – 1 (19.5)

Выражение (9.5) свидетельствует о том, что t не может превышать возраст оборудования за (k –1)-й год его эксплуатации с учетом возраста к началу первого года, который составляет t 0 лет; и не может быть меньше единицы (этот возраст оборудование будет иметь к началу k -го года, если замена его произошла в начале предыдущего (k –1)-го года).

Таким образом, переменная t в данной задаче является переменной состояния системы на k -ом шаге. Переменной управления на k -ом шаге является логическая переменная, которая может принимать одно из двух значений: сохранить (С ) или заменить (З ) оборудование в начале k -го года:

Функцию Беллмана F k (t ) определяют как максимально возможный доход от эксплуатации оборудования за годы с k -го по n -ый, если к началу k -го возраст оборудования составлял t лет. Применяя то или иное управление, система переходит в новое состояние. Так, например, если в начале k -го года оборудование сохраняется, то к началу (k + 1)-го года его возраст увеличится на единицу (состояние системы станет t + 1), в случае замены старого оборудования новое достигнет к началу (k + 1)-го года возраста t = 1 год.

На этой основе можно записать уравнение, которое позволяет рекуррентно вычислить функции Беллмана, опираясь на результаты предыдущего шага. Для каждого варианта управления доход определяется как сумма двух слагаемых: непосредственного результата управления и его последствий.

Если в начале каждого года сохраняется оборудование, возраст которого t лет, то доход за этот год составит r (t ). К началу (k + 1)-го года возраст оборудования достигнет (t + 1) и максимально возможный доход за оставшиеся годы (с (k + 1)-го по n -й) составит F k +1 (t + 1). Если в начале k -го года принято решение о замене оборудования, то продается старое оборудование возраста t лет по цене S (t ), приобретается новое за P единиц, а эксплуатация его в течение k -го года нового оборудования принесет прибыль r (0). К началу следующего года возраст оборудования составит 1 год и за все оставшиеся годы с (k + 1)-го по n -й максимально возможный доход будет F k +1 (1). Из двух возможных вариантов управления выбирается тот, который приносит максимальный доход. Таким образом, уравнение Беллмана на каждом шаге управления имеет вид:

Функция F k (t ) вычисляется на каждом шаге управления для всех 1 ≤ t ≤ t 0 + k - 1. Управление при котором достигается максимум дохода, является оптимальным.

Для первого шага условной оптимизации при k = n функция представляет собой доход за последний n -ый год:

(19.7)

Значения функции F n (t ), определяемые F n-1 (t ), F n-2 (t ) вплоть до F 1 (t ).

F 1 (t 0) представляют собой возможные доходы за все годы. Максимум дохода достигается при некотором управлении, применяя которое на первом году, мы определяем возраст оборудования к началу второго года.

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

Пример 2. Найти оптимальную стратегию эксплуатации оборудования на период продолжительностью 6 лет, если годовой доход r (t ) и остаточная стоимость S (t ) в зависимости от возраста заданы в табл. 19.6, стоимость нового оборудования равна P = 13, а возраст оборудования к началу эксплуатационного периода составляет 1 год.

Таблица 19.6

t
r(t)
S(t)

I этап. Условная оптимизация.

1-й шаг: k = 6. Для него возможные состояния системы t = 1, 2, …, 6.

Функциональное уравнение имеет вид (19.7):

2-й шаг: k = 5. Для него шага возможные состояния системы t = 1, 2, …, 5.

Функциональное уравнение имеет вид:

3-й шаг: k = 4.

4-й шаг: k = 3.

5-й шаг: k = 2.

6-й шаг: k = 1.

Результаты вычислений Беллмана F k (t ) приведены в табл. 19.7, в которой k – год эксплуатации, t – возраст оборудования.

Таблица 19.7

k t

В табл. 19.7 выделено значение функции, соответствующее состоянию «З» – замена оборудования.

II этап. Безусловная оптимизация.

Безусловная оптимизация начинается с шага при k = 1. Максимально возможный доход от эксплуатации оборудования за годы с 1-го по 6-й составляет F 1 (1) = 37. Этот оптимальный выигрыш достигается, если на первом году не производить замены оборудования. Тогда к началу второго года возраст оборудования увеличится на единицу и составит: t 2 = t 1 + 1 = 2. Безусловное оптимальное управление при k = 2, х 2 (2) = С , т.е. максимум дохода за годы со 2-го по 6-й достигается, если оборудование не заменяется. К началу третьего года возраст оборудования увеличится на единицу и составит: t 3 = t 2 + 1 = 2. Безусловное оптимальное управление х 3 (3) = 3, т. е. для получения максимума прибыли за оставшиеся годы необходимо произвести замену оборудования. К началу четвертого года при k = 4 возраст оборудования станет равен t 4 = 1. Безусловное оптимальное управление х 4 (1) = С . Далее соответственно.