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

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

1. возможные исходы предыдущего шага;
2. влияние управления на все оставшиеся до конца процесса шаги.

     В задачах динамического программирования первый пункт учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и приводя для каждого из вариантов условную оптимизацию. Выполнение второго пункта обеспечивается тем, что в задачах динамического программирования условная оптимизация проводится от конца процесса к началу. Сперва оптимизируется последний m-й шаг, на котором не надо учитывать возможные воздействия выбранного управления xm на все последующие шаги, так как эти шаги просто отсутствуют. Делая предположения об условиях окончания (m-1)-го шага, делая предположения об исходах окончания (m-2)-го шага и определяя условное оптимальное управление на (m-1)-м шаге, приносящее оптимальный выигрыш на двух последних шагах–(m-1)-м и m-м. Так же действуют на всех остальных шагах до первого. На первом шаге, как правило, не надо делать условных предположений, так как состояние системы перед первым шагом обычно известно.

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

2.2Составление  математической модели  динамического программирования                  и этапы решения задачи

Дополнительно введем следующие условные обозначения:

s–состояние процесса;

S_i–множество возможных состояний процесса перед i-м шагом;

W_i–выигрыш с i-го шага до конца процесса, i=1..m.

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

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

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

     3. Определение множества  шаговых управлений xi, i=1..m и налагаемых на них ограничений, т.е. области допустимых управлений X. 

     4. Определение выигрыша

φ(s, x_i), 

который принесет на i-м шаге управление x_i, если система перед этим находилась в состоянии s. 

     5. Определение состояния s’, в которое переходит система из состояния s под  влиянием управления x_i:   

s’=f_i(s, x_i,), 

где f_i–функция перехода на i-м шаге из состояния s в состояние s’.  

        6. Составление уравнения, определяющего условный оптимальный выигрыш                                                                                    

на последнем  шаге, для состояния s моделируемого  процесса 

                                                       W_m(S)=max{φ_m(s, xm)}.                                    

                                                                  x_m€X 

                 

     7. Составление основного функционального уравнения динамического программирования, определяющего условный оптимальный выигрыш для  данного состояния s с i-го шага и до конца процесса через уже известный оптимальный выигрыш с (i+1)-го шага и до конца: 

                                                W_i(S)=max{φ_i(s, x_i)+W_i=1(f_i(s, x_i))}.                    

                                                                      x_m€X  

     В уравнении в уже известную  функцию W_i+1(s), характеризующую условный оптимальный выигрыш с (i+1)-го шага до конца процесса, вместо состояния s подставлено новое состояние s’=f_i(s, x_i), в которое система переходит на i-м шаге под влиянием управления  xi.

     Заметим, что в динамических моделей, в  отличии от линейных моделей, отдельно вводятся переменные управления xi, и  переменные, характеризующие изменение  состояния s под влиянием управления. Таким образом, структура динамических моделей более сложная, что естественно, так как в этих моделях учитывается фактор времени.  

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

     После того как вы полнены пункты 1–7, изложенные выше, и математическая модель составлена, приступают к ее расчету. Укажем основные этапы решения задачи динамического программирования.

     1. Определение множества возможных состояний Sm для последнего шага.

     2. Проведение условной оптимизации для каждого состояния s, принадлежащей Sm на последнем m-м шаге по формуле (5) и определение условного оптимального управления x(s), s принадлежит Sm.

     3. Определение множества возможных состояний Si для i-го шага, i=2, 3,…m-1.

     4. Проведение условной оптимизации для i-го шага, i=2, 3,…m-1 для каждого состояния  s, принадлежащей Si,, по формуле и определение условного оптимального управления xi(s), s принадлежит Si, i=2, 3,…m-1.

     5. Определение начального состояния системы s1, оптимального выигрыша W₁(S₁) и оптимального управления x₁(S₁) по формуле при i=1. Это есть оптимальный выигрыш для всей задачи W^*=W₁(x₁^*).

     6. Проведение безусловной оптимизации управления. Для проведения безусловной оптимизации необходимо найденное на первом шаге оптимальное управление x₁^*=x₁(s₁) подставить в формулу и определить следующее состояние системы s₂=f₂(s₁, x₁). Для измененного состояния найти оптимальное управление x₂^*=x₂(s₂), подставить в формулу (4) и т.д. Для i-го состояния si найти s_i+1=f_i+1(s_i,x_i^*) и x^*_i+1(s_i+1) и т.д.

2.3 Распределение инвестиций как задача динамического программирования

     Инвестор  выделяет средства в размере D условных единиц, которые должны быть распределены между m-предприятиями. Каждое i-е предприятие  при инвестировании в него средств x приносит прибыль qi(x) условных единиц, i=1..m. Нужно выбрать оптимальное распределение инвестиций между предприятиями, обеспечивающее максимальную прибыль.

     Выигрышем W в данной задаче является прибыль, приносимая  m-предприятиями.

Построение  математической модели.

     1. Определение числа шагов.  Число  шагов m равно числу предприятий, в которые осуществляется инвестирование.

     2. Определение состояний системы.  Состояние системы на каждом  шаге характеризуется  количеством  средств si, имеющихся в наличии   перед данным шагом,  s ≤ D.

     3. Выбор шаговых управлений. Управление на i-м шаге x_i, x=1..m   является количество средств, инвестируемых в i-е предприятие.

     4. Функция выигрыша на i-м шаге:

q_i(x_i)

–это прибыль, которую приносит i-е предприятие при инвестировании в него средств  xi.                                                        

                                                                _m

W=∑q_ix_i,

                                                                                                   ⁱ⁼¹

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

     5. Определение функции перехода  в новое состояние.

                                                             f_i(s, x)=s-x                                           

     Таким образом, если на i-м шаге система находилась в состоянии s, а выбрано управление x, то на i+1-м шаге система будет находиться в состоянии s- x.  Другими словами, если в наличии имеются средства в размере s у.е., и в i-е предприятие инвестируется x у.е., то для дальнейшего инвестирования остается   s-x у.е.

     6. Составление функционального уравнения для i=m.                                  

                                                              W_m(s)=q_m(s)                                        

                                                               x_m(s)=s                                              

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

     7. Составление основного функционального уравнения. Подставив в формулу

W_i(S)=max{φ_i(s, x_i)+W_i=1(f_i(s, x_i))}.

x_m€X 

выражения q_i(x_i) и f_i(s, x)=s-x, получим следующее функциональное уравнение

 

W_i(s)=max{q_i(x)+W_i+1(s-x)} 

     Поясним данное уравнение. Пусть перед i-м  шагом у инвестора остались средства в размере s  у.е. Тогда х у.е. он может вложить в i-е предприятие, при этом оно принесет доход q_i(x), а оставшиеся s-x  у.е.—в остальные предприятия с i+1-го до m-го. Условный оптимальный выигрыш от такого вложения  W_i+1(s-x). Оптимальным будет то условное управление x, при котором сумма q_i(x) и  W_i+1(s-x) максимальна.  

Пример 1.  

D=5000

m=3

Значения q_i(x), i=1..3 заданы в таблице 1 

Таблица 1. 

  

Для x₁>x₂  q_i(x₁)≥q_i(x₂),  i=1..5. 

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

Проведем  условную оптимизацию. По ее результатам  заполняется таблица 2.