Как решать задачи по динамическому программированию

Методы оптимальных решений

Лекция 5

Тема лекции 5: «Задачи динамического программирования в
экономике»

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

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 определяется матрицей размера (nxn)
(таблица 1), так, чтобы суммарный доход со всех пред­приятий был бы
максимальным. Состояние системы перед каж­дым шагом определяется числом еще не
вложенных средств.

Таблица 1.

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

Определить вектор 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.

РЕШЕНИЕ.

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

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

 Таблица 3.

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

Таблица 4.

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

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

На основе полученного рекуррентного
соотношения составлена таблица 5.

Таблица 5.

ЭТАП 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.

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

РЕШЕНИЕ.

ЭТАП 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 – возраст оборудования.

Таблица 8.

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

ЭТАП 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, обеспечивающий наименьшие
транспортные расходы.

Рисунок
2. Модель транспортной сети.

В задаче имеется ограничение —
двигаться по изображенным на схеме маршрутам можно только слева направо, то
есть, попав, например, в пункт 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-м
шаге. Поскольку оптимизация осуществляется с конца процесса, то, находясь в
некотором пункте ik-то
пояса, принимается реше­ние о перемещении груза в один из пунктов (k – 1)-го
пояса, а на­правление дальнейшего движения известно из предыдущих ша­гов. Номер
j
пункта (k
– 1)-го пояса будет переменной управле­ния на k-м шаге.

Для первого шага управления (k=1) функция
Беллмана пред­ставляет собой минимальные затраты на перевозку груза из пунк­тов
1-го пояса в конечный пункт, т.е. F1(i) =ci10. Для последую­щих шагов затраты
складываются из двух слагаемых  – стоимости
перевозки груза cijиз пункта ik-го пояса в пункт 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 (ВЫБОР ОПТИМАЛЬНОГО МАРШРУТА
ПЕРЕВОЗКИ ГРУЗОВ).

Решим сформулированную выше задачу,
исходные данные которой приведены на рисунке 2.

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

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

Таблица 9.

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

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

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

Таблица10.

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

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

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

Таблица 11.

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

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

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

Таблица 12.

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

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

Рисунок
3. Транспортная сеть с оптимальным маршрутом.

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

Пусть на оптовую базу прибыло 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. Каждый
шаг представляет собой сечение графа состояний, про­ходящее через вершины (на
рисунке 4 сечения показаны косыми линиями).

Рисунок
4. Графическая схема связи операций.

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

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

Рисунок 5. Фрагмент связи операции (шаг
1).

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, как
показано на рисунке 6.

Рисунок
6. Сетевая модель операции (шаг 2).

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 наи­меньшие суммарные издержки и обозначаем стрелкой условно оптимальный
переход, как показано на рисунке 7.

Рисунок
7. Сетевая модель операции (шаг 3).

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

Рисунок
8. Сетевая модель связи расходов операций.

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

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

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

Рисунок
9. Оптимальная последовательность операций.

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

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

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

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

СПИСОК  РЕКОМЕНДУЕМОЙ  ЛИТЕРАТУРЫ.

[1] Таха Х.А. Введение
в исследование операций. — 6-е изд. Пер. с англ. — М.: Издательский дом
«Вильямс», 2001. — 912 с: ил.

[2] Фомин Г. П.Математические
методы и модели в коммерческой деятельности: Учебник. — 2-е изд., перераб. и
доп. — М.: Финансы и статистика, 2005. — 616 с: ил.

 [3] Шелобаев С. И. Математические методы и модели в
экономике,  финансах, бизнесе: Учебное
пособие для вузов. — М.: ЮНИТИ – ДАНА, 2001. – 367 с.

[4] Шикин Е.
В., Чхартишвили А. Г. Математические методы и модели в управлении: Учебное
пособие. — 3-е изд. — М.: Дело, 2004. — 440 с. — (Серия «Классический
университетский учебник»).

[5]
Экономико-математические методы и прикладные модели: Учебное пособие для вузов/
В.В. Федосеев, А.Н. Гармаш,  Д.М.
Дайитбегов и др.; Под ред. В.В. Федосеева. — М.:  ЮНИТИ, 1999. – 391 с.