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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Уравнение (29.1) описывает N-стадийный процесс, а (29.2) — одностадийный. Оба уравнения состоят из двух час­тей: верхняя строка определяет доход, получаемый при сохра­нении оборудования; нижняя — доход, получаемый при замене оборудования и продолжении процесса работы на новом обору­довании.

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

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

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

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

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

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

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

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

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

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

Для N = 1

Для N = 2

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

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

Дальнейшие расчеты для f₄(t) прекращаем, так как f₄(4) = 23 < f₃(1) = 24.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогда

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

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

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

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

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

при х = 120 f₂(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 f₃(20) = mах (10, 12) = 12,

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

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

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

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

при х = 120 f₃(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 f₄(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 млн р.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

g₂(1) + φ₁(0) = 10 + 0 = 10,

g₂(0) + φ₁(l)= 0 +11 = 11,

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

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

g₂(2) + φ₁(0) = 19 + 0 = 19,

g₂(l) + φ₁(l) = 10 + 11 = 21,

g₂(0) + φ₁ (2) = 0 + 18 = 18,

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

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

g₂(3) + φ₁ (0) = 34 + 0 = 34,

g₂(2) + φ₁(l) = 19 + 11 = 30,

g₂(1) + φ₁(2) = 10 + 18 = 28,

g₂(0) + φ₁(3) = 0 + 35 = 35,

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

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

g₂(4) + φ₁(0) = 53 + 0 = 53,

g₂(3) + φ₁(l) = 34 + 11 = 45,

g₂(2) + φ₁(2) = 19 + 18 = 37,

g₂(l) + φ₁(3) = 10 + 35 = 45,

g₂(0) +φ₁(4) = 0 + 51 = 51,

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

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

g₂(5) + φ₁(0) = 75 + 0 = 75,

g₂(4) + φ₁(l) = 53 + 11 = 64,

g₂(3) + φ₁(2) = 34 + 18 = 52,

g₂(2) + φ₁(3) = 19 + 35 = 54,

g₂(1) + φ₁(4) = 10 + 51 = 61,

g₂(0) + φ₁(5) = 0 + 76 = 76,

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

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

φ₃(x) = min{g₃(x₃) + φ₂(x – х₃)}.

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

g₃(5) + φ₂(0) = 74 + 0 = 74,

g₃(4) + φ₂(1) = 54 + 10 = 64,

g₃(3) + φ₂(2) = 36 + 18 = 54,

g₃(2) +φ₂(3) = 20 + 28 = 48,

g₃(1) + φ₂(4) = 9 + 37 = 46,

g₃(0) + φ₂(5) = 0 + 52 = 52,

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

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

В точку В можно попасть из B₁ или В₂. В узлах запишем стоимость пути. Стрелкой покажем минимальный путь.

Рассмотрим предпоследний шаг (рис. 29.4).

Для точки В₃ условное управление — по оси X, а для точки B₅ — по оси Y. Управление для точки В₄ выбираем как

т.е. по оси Y.

Условную оптимизацию проводим для всех остальных уз­ловых точек (рис. 29.5).

Получим

где с — север, в —восток.

Минимальные затраты составляют

Если решать задачу исходя из оптимальности на каждом этапе, то решение будет следующим:

Затраты составят 10 +12 + 11 + 10 + 9 + 13 +10 = 75 > 71.

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