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

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

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

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

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

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

Введем обозначения: 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 части. Путь можно рассматривать как управляемую систему, перемещающуюся под влиянием управления из начального состояния А в конечное В. Состояние этой системы перед началом каждого шага будет характеризоваться двумя целочисленными координатами х и у. Для каждого из состояний системы (узловой точки) найдем условное оптимальное управление. Оно выбирается так, чтобы стоимость всех оставшихся шагов до конца процесса была минимальна. Процедуру условной оптимизации проводим в обратном направлении, т.е. от точки В к точке А.

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

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

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

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

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

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

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

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

Обозначим через Л*(/) - оптимальные затраты, получаемые от

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

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

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

Пример 4.2

Оборудование эксплуатируется в течение пяти лет и после этого продается. В начале каждого года можно принять решение о сохранении оборудования или его замене новым. Стоимость нового оборудования Р 0 = 4000 руб. После t лет эксплуатации (1 g(t) = Р 0 2~‘ руб. (ликвидная стоимость). Затраты на содержание в течение года зависят от возраста оборудования t и равны r(t) = 600(/ + 1).

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

Решение. Способ деления управления на шаги естественный - но годам, п = 5. Параметр состояния - возраст машины лу= t, ,v 0 = 0 - машина новая в начале первого года эксплуатации. Управление на каждом шаге зависит от двух переменных If и If.

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

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

(при If затраты только на эксплуатацию машины возраста t, при If машина продается (-4000 2~"), покупается новая (4000) и эксплуатируется в течение первого года (600), общие затраты равны (-4000 2 " + 4000 + 600)).

Пусть л’ (?) - условные оптимальные затраты на эксплуатацию машины, начиная с А"-го шага до конца, при условии, что к началу А"-го шага машина имеет возраст / лег. Запишем для функций Л"(г) уравнения Веллмана, заменив задачу максимизации задачей минимизации:

Величина 4000 2 0+11 - стоимость машины возраста t лет (по условию машина после пяти лет эксплуатации продается):

Из определения функций Л* (/) следует A min = Л*(0).

Представим геометрическое решение этой задачи. Отложим по оси абсцисс номер шага к, а по оси ординат - возраст машины /. Точка (к - 1, /) на плоскости соответствует началу А - -го года эксплуатации машины возраста / лет. Перемещение на графике в зависимости от принятого управления на /о-м шаге показано на рис. 4.3.

Рис. 4.3

Состояние начала эксплуатации машины соответствует точке,v‘(0, 0), конец - точкам.5(5,/). Любая траектория, переводящая точку ДА-1, /) из в.5, состоит из отрезков - шагов, соответствующих годам эксплуатации. Необходимо выбрать такую траекторию, при которой затраты на эксплуатацию машины окажутся минимальными.

Над каждым отрезком, соединяющим точки (А’ - 1, /) и (А, / + 1), записываются соответствующие управлению If затраты (600(/ + 1)), а над отрезком, соединяющим точки (к - 1, /) и (к , /), - затраты, соответствующие управлению If (4600 - 4000 2 "). Таким образом размещаются все отрезки, соединяющие точки на 1рафикс, соответствующие переходам из любого состояния лд_| в состояние s k (см. рис. 4.3).

Далее на размеченном фафе производится условная оптимизация. В состояниях (5, /) машина продается, условный оптимальный доход от продажи равен 4000 2~‘, но поскольку целевая функция связана с затратами, то в кружках точек (5, /) ставится величина дохода со знаком минус. Далее на последующих этапах выбираются минимальные затраты среди двух возможных переходов, записываются в кружок данной точки, а соответствующие управления на этом шаге помечаются пунктирной стрелкой. При этом на каждом шаге трафически решаются уравнения Веллмана (рис. 4.4).

После проведения условной оптимизации получим в точке (0, 0) минимальные затраты на эксплуатацию машины в тсченШ пяти лет с последующей продажей: A min = 11 900. Далее строится оптимальная траектория, перемещаясь из точки So(0, 0) по пунктирным стрелкам в.?. Получаем набор точек: {(0, 0), (1, 1), (2, 2), (3, 1), (4, 2), (5, 3)}, который соответствует оптимальному управлению U"(u c , U‘, U U c , U c). Оптимальный режим

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

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

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

Определить оптимальную стратегию использования оборудования в период времени длительностью т лет, причем прибыль за каждые 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.

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

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

Условная оптимизация начинается с последнего 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.

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

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

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

Таблица 9.2.

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

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

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

1. Максимум дохода от машины за определенный промежуток времени.

2. Минимум затрат на ремонтно-эксплуатационный нужды, если доход подсчитать не удается.

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

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

t - возраст оборудования;

d(t) - чистый годовой доход от оборудования возраста t;

U(t) - издержки на ремонтно-эксплуатационные нужды машины возраста t;

С - цена нового оборудования.

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

Алгоритм решения задачи следующий:

1) f1(t) = max d(0) - С

) fn(t) = max fn-1(t+1) + d(t)

fn-1(1) + d(0) - С

Увеличение издержек приведет к снижению чистого дохода, который рассчитывается так:

d(t) = r(t) - u(t)

r(t) - годовой объем дохода от оборудования возраста t;

u(t) - годовые затраты на ремонтно - эксплуатационные нужды

оборудования возраста t.

Подход максимизации дохода

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

Если до конца периода остался 1 год

Если до конца периода осталось n лет

(t) = max

где t - возраст оборудования;

d (t) - чистый годовой доход от оборудования возраста t;

C - цена нового оборудования.

Увеличение издержек приведет к снижению чистого дохода, который рассчитывается так

(t) = r(t) - u(t)

где r (t) - годовой объем дохода от оборудования возраста t;

u(t) - годовые затраты на ремонтно-экплуатационные нужды оборудования возраста t.

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

Таблица 2. Чистый доход от оборудования по годам