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

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

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

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

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

Введем обозначения: 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) - стоимость продукции, производимой за год на единице оборудования возраста t лет; u(t) - расходы, связанные с эксплуатацией этого оборудования; s(t) - остаточная стоимость оборудования возраста t лет; р - покупная цена оборудования; Т - продолжительность плано­вого периода; t = 0,1, 2,... , Т - номер текущего года.

Решение. Чтобы решить задачу, применим принцип оптимально­сти Р. Беллмана. Рассмотрим интервалы (годы) планового периода в по­следовательности от конца к началу. Введем функцию условно-опти­мальных значений функции цели Fk(t). Эта функция показывает мак­симальную прибыль, получаемую от оборудования возраста t лет за по­следние к лет планового периода. Здесь возраст оборудования рассмат­ривается в направлении естественного хода времени. Например, t = 0 соответствует использованию совершенно нового оборудования. Временные же шаги процесса нумеруются в обратном порядке. Напри­мер, при к = 1 рассматривается последний год планового периода, при к = 2 - последние два года и т. д., при к = Т - последние Т лет, т. е. весь плановый период. Направления изменения t и к показаны на рисунке.

В этой задаче систему составляет оборудование. Ее состояние ха­рактеризуется возрастом. Вектор управления - это решение в момент t = = 0,1, 2,... , Т о сохранении или замене оборудования. Для нахождения оптимальной политики замен следует проанализировать, согласно прин­ципу оптимальности, процесс от конца к началу. Для этого сделаем пред­положение о состоянии оборудования на начало последнего года (k = 1). Пусть оборудование имеет возраст t лет. В начале Т-го года имеются две возможности: 1) сохранить оборудование на Т-й год, тогда прибыль за последний год составит r(t) - u(t); 2) продать оборудование по остаточ­ной стоимости и купить новое, тогда прибыль за последний год будет равна s(t) - р + г(0) - u(0), где г(0) - стоимость продукции, выпущенной на новом оборудовании за первый год его ввода; u(0) - эксплуатацион­ные расходы в этом году. Здесь целесообразно разворачивать процесс от конца к началу. Для последнего года (к = 1) оптималь­ной политикой с точки зрения всего процесса будет политика, обеспе­чивающая максимальную прибыль только за последний год. Учитывая значение прибыли при различном образе действия (замена - сохране­ние), приходим к выводу, что решение о замене оборудования возраста t лет следует принять в случае, когда прибыль от нового оборудования на последнем периоде больше, чем от старого, т.е. при условии

Итак, для последнего, года оптимальная политика и максимальная прибыль F 1 {t) находятся из условия

Пусть к = 2, т. е. рассмотрим прибыль за два последних года. Де­лаем предположение о возможном состоянии t оборудования на начало предпоследнего года. Если в начале этого года принять решение о сохранении оборудования, то к концу года будет получена прибыль r(t) - u(t). На начало последнего года оборудование перейдет в состояние t + 1, и при оптимальной политике в последнем году оно принесет прибыль, равную F 1 (t + 1). Таким образом, общая прибыль за два года составит r(t) - u(t) + F 1 (t + 1). Если же в начале предпоследнего года будет при­нято решение о замене оборудования, то прибыль за предпоследний год составит s(t)-p+r(0)-u(0). Поскольку приобретено новое оборудование, на начало последнего года оно будет в состоянии t = 1. Следовательно, общая прибыль за последние два года при оптимальной политике в по­следнем году составит

Условно-оптимальной в последние два года будет политика, достав­ляющая максимальную прибыль:

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

Таким образом, разворачивая весь процесс от конца к началу, получаем, что максимальная прибыль за плановый период Т составит F T (t 0). Так как начальное состояние to известно, из выражения для F T (t 0) находим оптимальное решение в начале первого года, потом вытекающее оптимальное решение для второго года и т.д. Обратимся к чи­словому примеру.

Разработать оптимальную политику замены оборудования при усло­виях:

1) стоимость r(t) продукции, производимой с использованием обо­рудования за год, и расходы u(t), связанные с эксплуатацией оборудова­ния, заданы таблицей;

2) ликвидационная стоимость машины не зависит от ее возраста и равна 2;

3) цена нового оборудования со временем не меняется и равна 15;

4) продолжительность планового периода 12 лет.

Итак, s(t) = 2, р = 15, Т = 12.

Запишем функциональные уравнения для F 1 (t) и F к (t) при числовых значениях нашего примера:

Пользуясь выражениями (8.9), (8.10), будем последовательно вычис­лять значения максимальной прибыли F к (t) и записывать их в специаль­ную таблицу (табл. 8.4). Первую строку получим, придавая параметру t в равенстве (8.9) значения 0,1,... ,12 и используя исходные данные табл. 8.3. Например, при t = 0

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

Из табл. 8.3 видно, что r(t) – u(t) с ростом t убывает. Поэтому при t > 9 оптимальной будет политика замены оборудования. Чтобы раз­личать, в результате какой политики получается условно-оптимальное значение прибыли, будем эти значения (до t = 9 включительно опти­мальной является политика сохранения) разграничивать жирной лини­ей. Для заполнения второй строки табл. 8.4 используем формулу (8.10). Для к = 2 получаем

Придадим параметру t значения 0,1,2,... ,12, значения r(t) и u(t) возьмем из табл. 8.3, а значения F 1 (t + 1) - из первой строки табл. 8.4. Для третьей строки расчетную формулу получим из равенства (8.10) при к = 3:

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

Пусть, например, в начале планового периода имеем оборудование возраста 6 лет. Разработаем "политику замен" на двенадцатилетний пе­риод, доставляющую максимальную прибыль. Информация для этого имеется в табл. 8.4. Максимальная прибыль, которую можно получить за 12 лет при условии, что вначале имелось оборудование возраста 6 лет, находится в табл. 8.4 на пересечении столбца t = 6 и строки F12(t); она составляет 180 единиц.

Значение максимальной прибыли F12(6) = 180 записано справа от ломаной линии, т.е. в области "политики замены". Это значит, что для достижения в течение 12 лет максимальной прибыли в начале первого года оборудование надо заменить. В течение первого года новое обору­дование постареет на год, т.е., заменив оборудование и проработав на нем 1 год, мы за 11 лет до конца планового периода будем иметь обо­рудование возраста 1 год. Из табл. 8.4 берем F11(l) = 173. Это значе­ние располагается в области "политики сохранения", т. е. во втором году планового периода надо сохранить оборудование возраста 1 год, и, про­работав на нем год, за 10 лет до конца планового периода будем иметь оборудование возраста 2 года.

Выясняем, что значение F10(2) = 153 помещено в области сохра­нения. Работаем на оборудовании еще год. Теперь до конца планового периода осталось 9 лет, а возраст оборудования составляет 3 года. Нахо­дим F9(3) = 136. Это область сохранения. Работаем на оборудовании еще год. Его возраст становится равным 4 годам. До конца планового перио­да остается 8 лет. Определяем F8(4) = 120. Это область замен. Заменяем оборудование на новое. Проработаем на нем в течение четвертого года. Оно постареет на год. До конца планового периода останется 7 лет. На­ходим F7(l) = 113. Это область сохранения. Продолжив подобные рассу­ждения, установим, что F6(2) = 93, F5(3) = 76 расположены в области сохранения, F4(4)=60 - в области замен, F3(l) = 53, F2(2) = 33, F1(3) = 16 - в области сохранения. Разработанную политику изобразим следующей цепочкой:

Таким образом, вместо поиска оптимальной "политики замен" на плановый период в 12 лет мы погрузили исходную задачу в семейство подобных, когда период меняется от 1 до 12. Решение ведется по прин­ципу оптимальности для любого состояния системы, независимо от ее предыстории. Оптимальная "политика замен" является оптимальной на оставшееся число лет. Табл. 8.4 содержит информацию для решения и других задач. Из нее можно найти оптимальную стратегию замены оборудования с лю­бым начальным состоянием от 0 до 12 лет и на любой плановый период, не превосходящий 12 лет. Например, найдем "политику замен" на пла­новый период в 10 лет, если вначале имелось оборудование пятилетнего возраста:

Задачу о замене оборудования мы упростили. На практике же дета­лями не пренебрегают. Легко учесть, например, случай, когда остаточная стоимость оборудования s(t) зависит от времени. Может быть принято решение о замене оборудования не новым, а уже проработавшим некото­рое время. Не составляет также труда учесть возможность капитального ремонта старого оборудования. При этом в понятие "состояние" системы необходимо включить время последнего ремонта оборудования. Функция Fk(ti,t2) выражает прибыль за последние к лет планового периода при условии, что вначале имелось оборудование возраста t1, прошедшее ка­питальный ремонт после t2 лет службы. Характеристики г, s и и также будут функциями двух переменных t1 и t2.

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

Найти оптимальные сроки замены оборудования. Первоначальная стоимость оборудования q 0 =6000 усл. ед., ликвидационная стоимость L(t)=q 0 2 -i , стоимость содержания оборудования возраста i лет в течение 1 года S(t)=0,1q 0 (t+1), срок эксплуатации оборудования 5 лет. В конце срока эксплуатации оборудование продается. Задачу решить графически.

Для построения графика в ПП Wolfram Mathematica 6.0 вводим

g = Plot[{6000*2^-x, 600*(x + 1)}, {x, 0, 5}]

В итоге получаем график:

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

Динамическое программирование. Оптимальное распределение средств между предприятиями

Найти оптимальное распределение средств в размере 9 усл. ед. между четырьмя предприятиями. Прибыль от каждого предприятия является функцией от вложенных в него средств и представлена таблицей:

Вложенные средства
I предприятие
II предприятие
III предприятие
IV предприятие

Вложения в каждое предприятия кратны 1 усл. ед.

Разобьем процесс выделения средств предприятиям на 4 этапа: на первом этапе выделяется y 1 средств предприятию П 1 , на втором -y 2 средств предприятию П 2 , на третьем - y 3 средств предприятию П 3 , на четвертом третьем - y 4 средств предприятию П 4

x n = x n - 1 - y n , n = 1,2,3, 4.

Заметим, что на четвертом этапе выделения средств весь остаток x 3 вкладывается в предприятие П 4 , поэтому y 3 = x 4 .

Воспользуемся уравнениями Беллмана для N = 4.

В результате получим следующие таблицы:

Таблица 1

Таблица 2

Таблица 3

Таблица 4

Из Таблицы 4 вытекает, что оптимальным управлением будет y 1 * =3, при этом оптимальная прибыль равна 42. Далее получаем

х 1 =х 0 -у 1 *=9-3=6, 2 (х 1)= 2 (6)=30, y 2 * =1

х 2 =х 1 -у 2 *=6-1=5, 3 (х 2)= 3 (5)=23, y 3 * =1

х 3 =х 2 -у 3 *=5-1=4, 4 (х 3)= 4 (4)=15, y 3 * =4

Таким образом, наиболее оптимальным является вложение в предприятия П1, П2, П3 и П4 денежных средств в размере 4, 1,1 и 3 усл.ед., соответственно. В этом случае прибыль будет максимальной и составит 42 усл. ед.

После того как выполнены пункты 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 -й и так далее. На этапе безусловной оптимизации отыскиваются годы, в начале которых следует произвести замену оборудования.

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

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

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

Основная характеристика оборудования – параметр состояния – его возраст .

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

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

–период планирования;

–ликвидная стоимость оборудования (
);

–стоимость содержания оборудования (
);

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

Уравнения состояний системы зависят от управления:

В самом деле, если к -ому шагу
, то при сохранении оборудования
через год возраст оборудования увеличится на 1. Если оборудование заменяется новым
, то это означает, что к началу-ого шага её возраст=0, а после года эксплуатации=1, т.е.
.

Показатель эффективности -ого шага:

.

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

Тогда уравнения Беллмана будут иметь вид:

Геометрическое решение задачи замены оборудования. Схема расчетов при решении задачи замены оборудования может быть представлена в виде двухкоординатной диаграммы (графа). На оси абсцисс будем откладывать номер шага , на оси ординат – возраст оборудования. Точка
на плоскости соответствует началу-го года эксплуатации оборудования возрасталет. Перемещение на графике в зависимости от принятого управления на-м шаге показано на рисунке.

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

Решение типового примера

Задание 4

На производственном предприятии «ТИТАН» оборудование эксплуатируется в течение
лет, после чего продается (считается, что послелет оборудование в результате морального износа не способно обеспечить выпуск конкурентоспособной продукции). В начале каждого года руководство предприятия принимает решение сохранить оборудование или заменить его новым аналогичным (при этом старое оборудование продается, а вырученные средства направляются на покрытие части стоимости нового оборудования). Первоначальная стоимость нового оборудования составляет
тыс. руб., затраты на содержание оборудования –
тыс. руб., и ликвидная стоимость оборудования –
тыс. руб. приведены в табл. 11.

Таблица 11

Исходные данные задачи замены оборудования

Необходимо:

1. Определить минимальные суммарные затраты производственного предприятия «ТИТАН» на эксплуатацию оборудования в течение рассматриваемого периода .

2. Определить оптимальную стратегию (план-график) эксплуатации оборудования, обеспечивающую минимальные суммарные затраты производственного предприятия «ТИТАН» на эксплуатацию в течение рассматриваемого периода в условиях текущих цен.

3. Дать экономическую интерпретацию полученного решения.

1. Определим минимальные суммарные затраты производственного предприятия «ТИТАН» на эксплуатацию оборудования в течение 5 лет. Проведем на размеченном графе (рис. 28) условную оптимизацию.

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

Состояние (4,1).

Таким образом, если система к последнему шагу находилась в точке (4,1), то следует идти в точку (5,2) (укажем это направление пунктирной линией).

Состояние (4,2).