Задачи динамического программирования в экономике

 «Задачи динамического программирования в экономике»

Разделы лекции:

 

1. Модели динамического программирования. Принцип оптимальности Р. Беллмана. Уравнение Беллмана.

2. Задача оптимального распределения инвестиций. Выбор оптимальной стратегии обновления оборудования.

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

 

РАЗДЕЛ 1. МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ. ПРИНЦИП ОПТИМАЛЬНОСТИ Р. БЕЛЛМАНА. УРАВНЕНИЕ БЕЛЛМАНА.

 

ЧТО ТАКОЕ ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ?

 

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

 

КАКИЕ ЗАДАЧИ РЕШАЮТСЯ МЕТОДАМИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ?

 

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

 

- распределе­ния дефицитных капитальных вложений между новыми направ­лениями их использования;

 

- разработки правил управления спро­сом или запасами, устанавливающими момент пополнения запаса и размер пополняющего заказа;

 

-  разработки принципов ка­лендарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию;

 

- составле­ния календарных планов текущего и капитального ремонтов обо­рудования и его замены;

 

- поиска кратчайших расстояний на транспортной сети;

 

- формирование последовательности развития коммерческой операции и т.д.

 

В це­лом, математический аппарат ДП  можно представить как пошаговое или поэтапное программирование. Однако, если в задачах линейного программирования зависи­мости между критериальной функцией и переменными обяза­тельно линейны, то в задачах ДП эти зависимости могут иметь еще и нелинейный характер. ДП можно использовать как для ре­шения задач, связанных с динамикой процесса или системы, так и для статических задач, связанных, например, с распределением ресурсов. Для процессов с непрерывным временем ДП рассматривает­ся как предельный вариант дискретной схемы решения. Получа­емые при этом результаты практически совпадают с теми, кото­рые получаются методами максимума Л.С. Понтрягина или Га­мильтона — Якоби — Беллмана. Это значительно расширяет область применения ДП для решения задач управления. Следует заметить, что методы динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. А возможность упрощения про­цесса решения, которая достигается за счет ограничения области и количества исследуемых при переходе к очередному этапу ва­риантов, усиливает достоинства этого метода.

 

НА ЧЕМ ОСНОВАНО РЕШЕНИЕ ЗАДАЧ МЕТОДАМИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ?

 

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

 

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

 

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

 

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

 

ПОСТАНОВКА ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

 

Постановку задачи динамического программирования рас­смотрим на примере инвестирования, связанного с распределе­нием средств между несколькими предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния S0 в конечное состояние Sn.  Предположим, что уп­равление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необхо­димо определить два типа переменных — переменную состояния системы Sk  и переменную управления xk. Переменная Sk опреде­ляет, в каких состояниях может оказаться система на рассматри­ваемом k-м шаге. В зависимости от состояния Sk  на этом шаге можно применить некоторые управления, которые характеризу­ются переменной xk, удовлетворяющей определенным ограничениям, и называются допустимыми.

 

Допустим, X = (x1, x2, …, xk, …, xn) – арифметический вектор (X – управление), переводящий систему из состояния S0 в состояние Sn,  а Sk — промежуточное состояние системы на k-м шаге управ­ления. Тогда последовательность состояний системы можно представить в виде графа (рисунок 1).

 

 

Рисунок 1. Граф состояний системы.

 

Применение управляющего воздействия xk  на каждом шаге переводит систему в новое состояние Sk  и приносит некоторый результат: φ_k(S_k-1, x_k). Для каждого возможного состояния на каж­дом шаге среди всех возможных управлений выбирается опти­мальное управление х*_k  такое, чтобы результат, который дости­гается за шаги с k-го по последний n-й, оказался бы оптималь­ным. Числовая характеристика этого результата называется функцией Беллмана F_k(S_k) и зависит от номера шага k и состоя­ния системы S_k-1.

 

КАК ФОРМУЛИРУЕТСЯ ЗАДАЧА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ?

 

Задача динамического программирования формулируется следующим образом: требуется определить такое управление X*, переводящее систему из начального состояния S0  в конечное со­стояние Sn, при котором целевая функция принимает наиболь­шее (наименьшее) значение F(S0, X*) → extr.

 

В ЧЕМ ЗАКЛЮЧАЮТСЯ ОСОБЕННОСТИ МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ?

 

Особенности математической модели динамического про­граммирования заключаются в следующем:

 

1) задача оптимизации формулируется как конечный много­шаговый процесс управления;

 

2) показатель эффективности или критерий оптимальности операции определяется целевой функцией, которая является ад­дитивной функцией от каждого шага оптимизации. То есть

 

           n

F(X) = ∑ φ_k(S_k-1, x_k);

          k=1        

 

3) выбор управления х_k на каждом шаге зависит только от состояния системы к этому шагу S_k-1 и не влияет на предшествую­щие шаги (нет обратной связи);

 

4) состояние системы S_k после каждого шага управления за­висит только от предшествующего состояния системы S_k-1 и уп­равляющего воздействия х_k (отсутствие последействия) и может быть записано в виде уравнения состояния системы:

 

Sk =f_k(S_k-1, x_k), k=1, …, n;

 

5) на каждом шаге управление x_k  зависит от конечного числа управляющих переменных, а состояние системы S_k  зависит от ко­нечного числа параметров;

 

6) оптимальное управление представляет собой арифметичес­кий вектор X*, определяемый последовательностью оптималь­ных пошаговых управлений: X* = (x*1, х*2, ..., х*k, ..., х*n), число которых и определяет количество шагов задачи.

 

ПРИНЦИП ОПТИМАЛЬНОСТИ И МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ ДИНАМИЧЕСКОГО ПРОЦЕССА УПРАВЛЕНИЯ.

 

В основе метода ДП лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р.Э. Беллманом.

 

КАКОВО БЫ НИ БЫЛО СОСТОЯНИЕ СИСТЕМЫ В РЕЗУЛЬТАТЕ КАКОГО-ЛИБО ЧИСЛА ШАГОВ, НА БЛИЖАЙШЕМ ШАГЕ НУЖНО ВЫБИРАТЬ УПРАВЛЕНИЕ ТАК, ЧТОБЫ ОНО В СОВОКУПНОСТИ С ОПТИМАЛЬНЫМ УПРАВЛЕНИЕМ НА ВСЕХ ПОСЛЕДУЮЩИХ ШАГАХ ПРИВОДИЛО К ОПТИМАЛЬНОМУ ВЫИГРЫШУ НА ВСЕХ ОСТАВШИХСЯ ШАГАХ, ВКЛЮЧАЯ ВЫИГРЫШ НА ДАННОМ ШАГЕ.

 

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

 

ПРИМЕР 1.

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

 

Кроме того, при выборе управления на данном шаге следует учитывать возможные варианты состояния предыдущего шага.

 

ПРИМЕР 2.

Например, при определении количества средств, вкладываемых в предприятие в i-м году, необходимо знать, сколько средств осталось в наличии к этому году,  и какой доход получен в предыдущем (i – 1)-м году.

 

КАКИЕ ТРЕБОВАНИЯ НЕОБХОДИМО УЧИТЫВАТЬ ПРИ ВЫБОРЕ ШАГОВОГО УПРАВЛЕНИЯ?

 

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

 

1) возможные исходы предыдущего шага S_k-1;

 

2) влияние управления xk на все оставшиеся до конца процес­са шаги  (n – k).

 

В задачах динамического программирования первое требова­ние учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и проводя для каждого из вариантов УСЛОВНУЮ ОПТИМИЗАЦИЮ. Выполнение второго требования обеспечивается проведением БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ в обратном порядке.

 

В ЧЕМ ЗАКЛЮЧАЕТСЯ УСЛОВНАЯ ОПТИМИЗАЦИЯ?

 

УСЛОВНАЯ ОПТИМИЗАЦИЯ. На первом этапе решения задачи, на­зываемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгорит­мом обратной прогонки. На последнем, n-м, шаге оптимальное управление х*n определяется функцией Беллмана: F(S) = max{φ_n(S,x_n)}, в соответствии с которой максимум выбирается из всех возможных значений х_n,  причем хn принадлежит управлению X (x_nÎX). Дальнейшие вычисления проводятся согласно рекуррентно­му соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге. В общем виде это соотношение имеет вид:

 

F_n(S) = max{φ_n(S_n-1, x_n) +F_k+1(f_k(S_k-1, x_k))}, х_k ÎХ.

 

Этот максимум (или минимум) определяется по всем возмож­ным для k и S значениям переменной управления х_n ÎХ.

 

В ЧЕМ ЗАКЛЮЧАЕТСЯ БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ?

 

БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ. После того как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го  по первый, осуществляется второй этап решения за­дачи, называемый безусловной оптимизацией, проводимой в об­ратном порядке.

 

Пользуясь тем, что на первом шаге (k=1) состояние системы известно - это ее начальное состояние S0, можно  найти опти­мальный результат за все n шагов и оптимальное управление на первом шаге x*1, которое этот результат доставляет. После приме­нения этого управления система перейдет в другое состояние S₁=f₁(S₀, x*₁), зная которое, можно, пользуясь результатами ус­ловной оптимизации, найти оптимальное управление на втором шаге x*₂ и так далее до последнего n-го шага.

 

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

 

РАЗДЕЛ 2. ЗАДАЧА ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ ИНВЕСТИЦИЙ. ВЫБОР ОПТИМАЛЬНОЙ СТРАТЕГИИ ОБНОВЛЕНИЯ ОБОРУДОВАНИЯ.

 

Требуется распределить имеющиеся B единиц средств среди n предприятий, доход g_i(x_i) от которых в зависимости от количест­ва вложенных средств xi  определяется матрицей размера (n x n) (таблица 1), так, чтобы суммарный доход со всех пред­приятий был бы максимальным. Состояние системы перед каж­дым шагом определяется числом еще не вложенных средств.

 

Таблица 1.

gi xi	g1	g2	…	gi	…	gn
x1	G1(x1)	G2(x1)	…	Gi(x1)	…	Gn(x1)
x2	G1(x2)	G2(x2)	…	Gi(x2)	…	Gn(x2)
…	…	…	…	…	…	…
xi	G1(xi)	G2(xi)	…	Gi(xi)	…	Gn(xi)
…	…	…	…	…	…	…
xn	G1(xn)	G2(xn)	…	Gi(xn)	…	Gn(xn)

 

Запишем математическую модель задачи.

 

Определить вектор X* = (x*₁, x*₂,..., х*_k, ..., х*_n), удовлетворяющий ус­ловиям:

 

n

∑ x_i = B; (1)

i=1 

 

x_i≥0, i =1, …, n; (2)

 

и обеспечивающий максимум целевой функции

 

          n

F(X)=∑g_i(x_i) →max. (3)

        i=1

 

Теперь необходимо записать рекуррентное соотношение свя­зи между шагами управления: F_k(x)  и F_k+1(x).

 

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

 

С этой целью разобьем процесс оптимизации на n шагов и бу­дем на каждом k-м шаге оптимизировать инвестирование не всех предприятий, а только предприятий с k-го по n-е. При этом есте­ственно считать, что в остальные предприятия (с первого по (k–1)-е тоже вкладываются средства, и поэтому на инвестирова­ние предприятий с k-го по n-е остаются не все средства, а неко­торая меньшая сумма с_k≤В. Эта величина и будет являться пере­менной состояния системы. Переменной управления на k-м шаге назовем величину хk средств, вкладываемых в k-е предприятие. В качестве функции Беллмана F_k(c_k)  на k-м шаге можно выбрать максимально возможный доход, который можно получить с пред­приятий с k-го  по n-е при условии, что на их инвестирование ос­талось с_k средств. Очевидно, что при вложении в k-е предприятие хk средств будет получена прибыль gk(xk), а система к (k+1)-му шагу перейдет в состояние S_k+1,  и, следовательно, на инвестиро­вание предприятий с  (k+1)-го до n-го останется средств: c_k+1=(c_k – x_k).

 

Таким образом, на первом шаге условной оптимизации при k=n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может ос­таться количество средств сn, где 0≤c_n≤B. Чтобы получить макси­мум прибыли с этого предприятия, можно, например, вложить в него все эти средства, т.е. F_n(c_n)=g_n(c_n), и х_n=с_n.

 

На каждом последующем шаге для вычисления функции Беллмана необходимо использовать результаты предыдущего ша­га. Пусть на k–м шаге для инвестирования предприятий с k-го по n-е осталось с_k средств (0≤c_k≤B) . Тогда от вложения в k-е пред­приятие xk средств будет получена прибыль gk(xk), а на инвести­рование остальных предприятий (с (k+1)-го по n-е) останется:  c_k+1=(ck – хk) средств. Максимально возможный доход, который мо­жет быть получен с предприятий (с k-го по n-е), будет равен:

 

F_k(c_k) = max{g_k(x_k) +F_k+1(c_k–x_k)}, по всем х_k≤ck, k=1, …, n. (4)

 

Максимум выражения (4) достигается на некотором зна­чении x*k, которое является оптимальным управлением на k-м шаге для состояния системы Sk. Действуя так, мы можем определить функцию Беллмана и оптимальные управления по­следовательно вплоть до шага k=1.

 

Значение функции Беллмана F1(c1) представляет собой мак­симально возможный доход со всех предприятий, а значение х*1, на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие. Затем на этапе безусловной оптимизации для всех последующих шагов вычисляется величина c_k=(c_k-1–x_k-1),  и оптимальным управле­нием на k-м  шаге является то значение хk, которое обеспечивает максимум дохода при соответствующем состоянии системы Sk.

 

ПРИМЕР 3 (ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ИНВЕСТИЦИЙ).

 

На развитие трех предприятий g1, g2, g3 выделено 5 млн. руб. Известна эффективность капитальных вложений в каждое предприятие, заданная значением нелинейной функции gi(xi), и представленная в таблице 2. Необходимо распределить выделенные средства между предприятиями таким образом, чтобы получить максимальный суммарный доход. Для упрощения расчетов предполагаем, что распределение средств осуществляется в целых числах: xi={0, 1, 2, 3, 4, 5} млн. руб.

 

Таблица 2.

xi	g1	g2	g3
0	0	0	0
1	2,2	2	2,8
2	3	3,2	5,4
3	4,1	4,8	6,4
4	5,2	6,2	6,6
5	5,9	6,4	6,9

 

РЕШЕНИЕ.

 

ЭТАП 1. УСЛОВНАЯ ОПТИМИЗАЦИЯ (k=3,2,1).

 

1-й шаг: k=3. Предположим, что все средства в количестве x3=5 млн. руб. отданы третьему предприятию. В этом случае мак­симальный доход, как это видно из таблицы 3, составит g3(x3)=6,9 млн. руб., следовательно: F3(c3)=g3(x3).

 

2-й шаг: k=2. Определяем оптимальную стратегию при рас­пределении денежных средств между вторым и третьим предпри­ятиями. При этом рекуррентное соотношение Беллмана имеет вид: F2(c2)=max {g2(x2) – F3(c2–x2)}, по всем x2≤c2.  На основе полученного рекуррентного соотношения составлена по данным таблицы 2.

 

3-й шаг: k=1. Определяем оптимальную стратегию при рас­пределении денежных средств между первым и двумя другими предприятиями, используя следующую формулу для расчета сум­марного дохода:

 

F1(c1)=max {g1(x1) – F2(c1–x1)}, по всем x1≤c1.

 

ЭТАП 2. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ (k=1,2,3).

 

Определяем компоненты оптимальной стратегии.

 

1-й шаг: k=1. По данным из таблицы 5 максимальный доход при распределении 5 млн. руб. между тремя предприятиями со­ставляет: с1=5, F1(5)=10,8 млн. руб. При этом первому предприятию нужно выделить х*1 = 1 млн. руб.

 

2-й шаг: k=2. Определяем величину оставшихся денежных средств, приходящуюся на долю второго и третьего предприятий.

 

C2=c1 – x*1=5–1=4 млн. руб.

 

По данным таблицы 4 находим, что оптимальный вариант распределения денежных средств размером 4 млн. руб. между вто­рым и третьим предприятиями составляет: F2(4)=8,6 млн. руб., при выделении второму предприятию x*2=2 млн. руб.

 

3-й шаг: k=3. Определяем величину оставшихся денежных средств, приходящуюся на долю третьего предприятия:

c3=c2 – x*2=4 – 2=2 млн. руб.

 

По данным таблицы 5 находим:

 

F3(2) = 5,4 млн. руб., и x*3=2 млн.  руб.

 

Таким образом, оптимальный план инвестирования предпри­ятий: x*1 = 1 млн. руб.,x*2=2 млн.  руб., x*3=2 млн.  руб.

 

X* = (1,2,2), который обеспечит максимальный доход, равный

 

F(5) = g1(l) + g2(2)+g3(2) = 2,2 + 3,2 + 5,4 = 10,8 млн.  руб.

 

ВЫБОР ОПТИМАЛЬНОЙ СТРАТЕГИИ ОБНОВЛЕНИЯ ОБОРУДОВАНИЯ.

 

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

 

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

 

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

 

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

 

Таблица 6.

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

 

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

 

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

 

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

 

1≤t≤t₀+k – 1. (5)

 

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

 

Таким образом, переменная t в данной задаче является пере­менной состояния системы на k-м шаге.

 

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

 

x_k(t) = (C), если оборудование сохраняется;

 

x_k(t)=(З), если оборудование заменяется.

 

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

 

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

 

Если в начале каждого года сохраняется оборудование, возраст которого t лет, то доход за этот год составит r(t). К началу (k+1)-го года возраст оборудования достигнет (t+1),  и макси­мально возможный доход за оставшиеся годы (с (k+1)-го по n-й) составит F_k+1(t+1).

 

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

 

F_k(t)  = max{r(t)+ F_k+1(t+1)} в случае (С);

 

F_k(t)  = max{S(t) – P +r(0)+F_k+1(1)} в случае (З).

 

Функция Fk(t) вычисляется на каждом шаге управления для всех t удовлетворяющих условию: 1≤t≤t0+k – 1. (5)  Управление, при котором достигается мак­симум дохода, является оптимальным.

 

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

 

F_n(t)  = max{r(t)} в случае (С);  F_n(t)  = max{S(t) – P +r(0)} в случае (З). (6)

 

Значения функции Fn(t), определяемые Fn-1(t) Fn-2(t), …,  вплоть до F1(t), F0(t), представляют собой возможные доходы за все годы. Максимум дохода достигается при некотором управлении, применяя которое на первом году, мы определяем возраст оборудования к началу второго года. Для этого возраста оборудования выбирается управление, при котором достигается максимум дохода за годы со второго по n-й и т д. В результате чего на этапе бе­зусловной оптимизации определяются те годы, в начале которых следует произвести замену оборудования.

 

ПРИМЕР 4 (ВЫБОР ОПТИМАЛЬНОЙ СТРАТЕГИИ ЗАМЕНЫ ОБОРУДОВАНИЯ).

 

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

 

Таблица 7.

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

 

РЕШЕНИЕ.

 

ЭТАП 1. УСЛОВНАЯ ОПТИМИЗАЦИЯ (k= 6, 5, 4, 3, 2, 1).

 

1-й шаг: k=6. Для первого шага возможные состояния систе­мы t=1, 2, 3, 4, 5, 6, а функциональные уравнения (6) имеют вид:

 

 

2-й шаг: k=5. Для второго шага возможные состояния систе­мы  t=1, 2, 3,4, 5;  а функциональное уравнение (6) имеет вид:

 

в соответствии с которым вычисляем:

 

3-й шаг: k=4; Для третьего шага возможные состояния систе­мы  t=1,2, 3,4;  а функциональное уравнение (6) имеет вид:

 

в соответствии с которым вычисляем:

 

4-й шаг: k=3; t= 1, 2, 3.

Тогда

 

 

 

5-й шаг: k=2; t=1,2. Из функционального уравнения (6) получим:

 

 

6-й шаг: k= 1; t =1. Тогда из (6) имеем:

 

 

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

 

ЭТАП 2. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ (k=1, 2, 3, 4, 5, 6).

 

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

 

К началу третьего года при k=3 возраст оборудования станет t₃=t₂+1=2+1=3. Безусловное оптимальное управление: x₃(3)=(З), т.е. для получения максимума прибыли за оставшиеся годы необхо­димо в этом году провести замену оборудования.

 

К началу четвертого года при k=4 возраст оборудования ста­нет равен t₄=1. Безусловное оптимальное управление x₄(1) = (С).

 

Далее соответственно для оставшихся шагов k=5 и k=6 получим:

 

k=5,  t5=t4+1=1+1=2; x5(2)=(C);

 

k=6,  t6=t5+1=2+1=3; x6(3)=(C).

 

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

 

РАЗДЕЛ 3. ВЫБОР ОПТИМАЛЬНОГО МАРШРУТА ПЕРЕВОЗКИ ГРУЗОВ.  ПОСТРОЕНИЕ ОПТИМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАЦИЙ В КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ.

 

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

 

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

 

В задаче имеется ограничение — двигаться по изображенным на схеме маршрутам можно только слева направо, то есть, попав, например, в пункт 7, мы имеем право переместиться только в пункт 10 и не можем возвратиться обратно в 5-й или 6-й. Эта особен­ность транспортной сети дает право отнести каждый из десяти пунктов к одному из поясов. Будем считать, что пункт принадлежит к k-му поясу, если из него можно попасть в конечный пункт ровно за k шагов, т.е. с заездом ровно в (k–1)-й промежуточный пункт. Таким образом, пункты 7, 8 и 9 принадлежат к первому поясу, 5 и 6 — ко второму, 2, 3 и 4 — к третьему и 1 — к четвертому. Тогда на k -м шаге будем находить оптимальные маршруты перевозки гру­за из пунктов k-го пояса до конечного пункта. Оптимизацию бу­дем производить с конца процесса, и потому, дойдя до k-то шага, неизвестно, в каком из пунктов k-го пояса окажется груз, перево­зимый из первого пункта.

 

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

 

k – номер шага (k=1, 2, 3, 4);

 

i – пункт, из которого осуществляются перевозки (i=1,2,..., 9);

 

j - пункт, в который доставляется груз (j=2, 3,..., 10);

 

cij –  стоимость перевозки груза из пункта i в пункт j.

 

Fk(i) - минимальные затраты на перевозку груза на k-м шаге решения задачи из пункта i до конечного пункта.

 

Очевидно, что минимум затрат на перевозку груза из пунктов k-то пояса до пункта 10 будет зависеть от того, в каком пункте этого пояса мы оказались. Номер i пункта, узел, принадлежащий k-му  поясу, будет являться переменной состояния системы на k-м шаге. Поскольку оптимизация осуществляется с конца процесса, то, находясь в некотором пункте i k-то пояса, принимается реше­ние о перемещении груза в один из пунктов (k – 1)-го пояса, а на­правление дальнейшего движения известно из предыдущих ша­гов. Номер j пункта (k – 1)-го пояса будет переменной управле­ния на k-м шаге.

 

Для первого шага управления (k=1) функция Беллмана пред­ставляет собой минимальные затраты на перевозку груза из пунк­тов 1-го пояса в конечный пункт, т.е. F1(i) =ci10. Для последую­щих шагов затраты складываются из двух слагаемых  – стоимости перевозки груза cij из пункта i k-го пояса в пункт j (k – 1)-го по­яса и минимально возможных затрат на перевозку из пункта j до конечного пункта, т.е. F_k-1(j), Таким образом, функциональное уравнение Беллмана будет иметь вид:

 

F_k(i) = min{c_ij + F_k-1(j)} по всем j (j=2, 3,..., 10).  (7)

 

Минимум затрат достигается на некотором значении j*, кото­рое является оптимальным направлением движения из пункта i в конечный пункт.

 

На четвертом шаге попадаем на 4-й пояс; состояние системы становится определенным i=1. Функция F4(1) представляет со­бой минимально возможные затраты по перемещению груза из 1-го пункта в 10-й. Оптимальный маршрут определяется в ре­зультате анализа всех шагов в обратном порядке, а выбор некото­рого управления j на k-м шаге приводит к тому, что состояние си­стемы на (k – 1)-м шаге становится определенным.

 

ПРИМЕР 5 (ВЫБОР ОПТИМАЛЬНОГО МАРШРУТА ПЕРЕВОЗКИ ГРУЗОВ).

 

ЭТАП 1. УСЛОВНАЯ ОПТИМИЗАЦИЯ.

 

1-й шаг: k=1. Функциональное уравнение Беллмана (7) на первом шаге имеет вид: F₁(i)=C_i,10. Все возможные перемещения груза на первом шаге и резуль­таты расчета приведены в таблице 9. На первом шаге в пункт 10 груз может быть доставлен из пунктов 7, 8 или 9.

 

2-й шаг: k=2. Функциональное уравнение (7) на втором шаге принимает вид:

 

F₂(i) = min{C_ij + F₁(j)} по всем j.

 

3-й шаг: k=3. Функциональное уравнение Беллмана (7) на третьем шаге имеет вид:

 

F3(i) = min{Cij + F2(j)} по всем j.

 

4-й шаг: k=4.  Функциональное уравнение Беллмана (7) на четвертом  шаге имеет вид:

 

F4(i) = min{Cij + F3(j)} по всем j.

 

 

ЭТАП 2. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ.

 

На этапе условной оптимизации получено, что минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют F4(1) = 20. Данный результат достигается при движении груза из 1-го пункта в 3-й. По данным таблицы 11, из пункта 3 необходимо двигаться в пункт 6, затем — в пункт 7 (см. таблица 10) и из него - в конечный пункт (см. таблица 9). Таким образом, оптимальный маршрут доставки груза: 1→3→6→7→10.

 

ПОСТРОЕНИЕ ОПТИМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАЦИЙ В КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ.

 

Пусть на оптовую базу прибыло n машин с товаром для раз­грузки и m машин для загрузки товаров, направляемых в магазины. Материально ответственное лицо оптовой базы осуществля­ет оформление документов по операциям разгрузки или загрузки для одной машины, а затем переходит к обслуживанию другой машины. Издержки от операций обусловлены простоем транспорта, типом операции (прием или отправка товара) и не зависят от конкретной машины. Необходимо спланировать последова­тельность операций обоих видов таким образом, чтобы, суммарные издержки по приему и отправке товаров для всех машин были минимальными.

 

Из условия следует, что состояние экономической системы характеризуется двумя параметрами: количеством принятых и  оформленных машин по разгрузке товара и количеством машин, отправленных с товаром в магазины. Поэтому решение будем искать на плоскости XOY, в прямоугольнике, который является областью допустимых состояний системы. Если по оси OX отложить число n разгруженных машин, а по оси OY— число m загруженных товаром машин, то можно построить на плоско­сти XOY граф состояний процесса, в котором каждая вершина харак­теризует состояние операции приема и отгрузки товара на опто­вой базе. Ребра этого графа означают выполнение работы по приему или отправке товара на очередной машине. Каждому ребру можно сопоставить издержки, связанные с выполнением опера­ции по разгрузке или загрузке машины.

 

ПРИМЕР 6 (ПОСТРОЕНИЕ ОПТИМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАЦИЙ В КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ).

 

Пусть на оптовую базу прибыло 6 машин с товаром для раз­грузки и 4 машины для загрузки товаров, направляемых в магазины (то есть n=6, m=4). Известны затраты по выполнению каждой операции, которые показаны на ребрах графа (рисунок 4). Точка S0 определяет начало процесса, а S1 – конечное состоя­ние, соответствующее приему и отправке всех машин. Оптимиза­цию процесса будем производить с конечного состояния — S1. Весь процесс разобьем на шаги, их количество k=n+m= 6+4=10. Каждый шаг представляет собой сечение графа состояний, про­ходящее через вершины. 

 

 

 ЭТАП 1. УСЛОВНАЯ ОПТИМИЗАЦИЯ.

 

1-й шаг: k=1. На первом шаге с задаваемым сечением А1, В1 из состояний A1 и B1 возможен только один вариант перехода в конечное состояние S1. Поэтому в вершинах A1 и B1 записываем соответственно издержки 8 и 11. Ребра A1S1 и B1S1 обозначаем стрелкой, направленной в вершину S1.

 

2-й шаг: k=2. Второй шаг оптимизации задается сечением по вершинам A2, В2, C1. Из состояний A2 и С1 возможен единствен­ный переход в вершины A1 и В1 соответственно, поэтому в вер­шинах A2 и C1 записываем суммарные издержки 17 и 22 на первых двух шагах перехода в конечное состояние S1.

 

Из вершины B2 возможны два варианта перехода: в вершину А1 или вершину В1. При переходе B2→A1 сумма издержек состав­ляет 10+8=18, на переходе B2→В1 сумма составляет 13+11=24. Из двух вариантов суммарных издержек выбираем наименьшую (18) и обозначаем стрелкой условно оптимальный переход B2→A1.

 

3-й шаг: k=3. На третьем шаге сечение проходит через вер­шины A3, B3, С2, D1. Из вершин А3 и D1 возможен единственный переход в вершины A2 и C1 соответственно. Суммарные издержки для состояния D1 равны 22+12=34. Из вершины B3 возможны два варианта перехода: в вершину A2 издержки равны 17+8=25; в вершину B2 издержки равны: 18+9=27.

 

Для вершины C2 возможен переход в вершину B2 (издержки: 18+10=28) и в вершину C1 (издержки: 22+12=34). Выбираем для вершин В3 и C2 наи­меньшие суммарные издержки и обозначаем стрелкой условно оптимальный переход.

 

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

Минимально возможные суммарные издержки по обслужи­ванию всех 10 машин на оптовой базе составляют 88 у. е.

 

ЭТАП 2. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ.

 

Определяем оптимальную траекторию на исходном сетевом графе, просматривая результаты всех шагов в обратном порядке, учитывая, что выбор некоторого управления на k-м шаге приво­дит к тому, что состояние на (k – 1)-м шаге становится опреде­ленным. В результате строим ориентированный граф перехода из со­стояния S0 в состояние S1; на каж­дом шаге безусловной оптимизации переход почти всегда единст­венный и совпадает с построенными условно оптимальными пе­реходами.

 

Минимальные издержки Fmin соответствуют следующему оп­тимальному пути на графе:

 

(S0→E6 →D6 →D5→D4→D3→C3→B3→A2→A1→S1);

 

и равны: Fmin=12+9+9+7+7+10+9+8+9+8=88 усл. ед.

 

ВЫВОД. В соответствии с решением, оптимальное уп­равление процессом разгрузки и загрузки машин товаром состо­ит в следующем: на первом шаге следует оформить документы по разгрузке одной машины, на втором  - по загрузке одной маши­ны, далее обслуживать три машины по разгрузке товара, три ма­шины по загрузке и на последних двух шагах оформить докумен­ты по разгрузке двух машин.