Международные фондовые биржи: опыт и проблемы функционирования

2. Постановка  задачи динамического  программирования

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

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

               x₁             x₂      x_k-1             x_k            x_k+1      x_n

    …             … 

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

     Применение  управляющего воздействия хk на каждом шаге переводит систему в новое  состояние S1(S, хk) и приносит некоторый результат Wk(S, хk). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление х*k, такое, чтобы результат, который достигается за шаги с k-го по последний n-й, оказался бы оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk(S) и зависит от номера шага k и состояния системы S.

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

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

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

     2) целевая функция (выигрыш) является  аддитивной и равна сумме целевых функций каждого шага:

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

     4) состояние системы Sk после каждого  шага управления зависит

только  от предшествующего состояния системы Sk-1 и этого управляющего воздействия  хk (отсутствие последействия) и может  быть записано в виде уравнения состояния: Sk = f(Sk-1, хk), k = 1, n;

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

     6) оптимальное управление представляет  собой вектор X*, определяемый последовательностью оптимальных пошаговых управлений:

X^* = (х^*₁, х^*₂, …, х^*_k, …, х^*_n), число которых и определяет количество шагов задачи. 

3. Принцип оптимальности и  математическое                                                    описание динамического программирования

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

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

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

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

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

     Условная  оптимизация. На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге, оптимальное управление х^*_n определяется функцией Беллмана: F(S) = max{Wn(S,xn)}, в соответствии с которой максимум выбирается из всех возможных значений х_n, причем х_n€ Х.

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

F_n(S) = max{W_n(S, x_n) + F_k+1(S¹(S, x_k))}, x_k€Х.

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

     Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по

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

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

II ВЫБОР И СОСТАВЛЕНИЕ МОДЕЛЕЙ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ ИНВЕСТИЦИЙ

     2.1 Общая постановка  классической задачи распределения инвестиций 

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

     Для развития выделены капитальные вложения в размере S. Имеется n объектов вложений, по каждому из которых известна ожидаемая прибыль fi(x), получаемая от вложения определенной суммы средств. Необходимо распределить капитальные вложения между n объектами (предприятиями, проектами) таким образом, чтобы получить максимально возможную суммарную прибыль.  

   Для составления математической модели исходим из предположений:

1. прибыль от каждого предприятия (проекта) не зависит от вложения средств в другие предприятия;
2. прибыль от каждого предприятия (проекта) выражается в одних условных единицах;
3. суммарная прибыль равна сумме прибылей, полученных от каждого предприятия (проекта).

 

   Данная  постановка является упрощенной моделью  реального процесса распределения  инвестиций, и в "чистом" виде не встречается, так как не учитывает  некоторые факторы, а именно:

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

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

   Пусть рассматривается задача, распадающаяся  на m шагов или этапов, например планирование инвестиций, управление производственными мощностями в течение длительного срока. Показатель эффективности задачи в целом обозначим через W, а показатели эффективности на отдельных шагах–через φi, i=1..m. Если W обладает свойством аддитивности, т.е.

                                                                 _m

W=∑ φ_i

                                                                 ⁱ⁼¹

то можно  найти оптимальное решение задачи методом динамического программирования.

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

Определение 1.

Переменная  х_i, от которой зависят выигрыши на i-м шаге и, следовательно, выигрыш в целом, называется шаговым управлением, i=1..m. 

Определение 2.

Управлением процесса в целом (x) называется последовательность шаговых управлений x=(x₁, x₂,…, x_i,…, x_m).  

Определение 3.

Оптимальное управление x–это значение управления x, при котором значение W(x^*) является максимальным (или минимальным, если требуется уменьшить проигрыш).

W^*=W(x^*)=max{W(x)}, x € X, 

где X–область допустимых управлений.

     Оптимальное управление x^* определяется последовательностью оптимальных шаговых управлений 

x*=(x₂^*, x₂^*,…, x_i^*,…, x_m^*). 

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

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