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

Московсий Государственный инженерно-физический институт (технический университет)

Го С Д

На правах рукописи

! <ОСГ

АЛФИМОВ РОМАН ВАЛЕРЬЕВИЧ

СИСТЕМА АВТОМАТИЗИРОВАННОЙ ПОДДЕРЖКИ

ПРИНЯТИЯ РЕШЕНИЯ ПРИ ПРОВЕДЕНИИ ВАЛЮТНЫХ ОПЕРАЦИЙ В РЕАЛЬНОМ МАСШТАБЕ ВРЕМЕНИ

05.13.06 - Автоматизированные системы управления

диссертации на соискание ученой степени кандидата технических наук

АВТОРЕФЕРАТ

Научный руководитель: кандидат технических наук, доцент Петухов Михаил Николаевич

МОСКВА 1997

Работа выполнена в Московском Государственном инженерно-физическом институте (техническом университете)

Научный руководитель: кандидат технических наук, доцент

Петухов Михаил Николаевич

Официальные оппоненты:

доктор технических паук Долгов Александр Михайлович кандидат технических наук Ворошин Алексей Павлович

Ведущая организация: АКБ "Автобанк"

Защита состоится " "/О" ^Си^гСе^Л 1997г. в/[/часов OQmm. на заседании диссертационного : совета Д053.03.04 в МИФИ по адресу: 115409, Москва, Каширское шоссе д. 31, тел. 324-84-9S, 323-91-67.

С диссертацией можно ознакомится в библиотеке МИФИ. Автореферат разослан "0G " Н^^ЛА 1997г.

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

Ученый секретарь диссертационного света доктор технических наук,

профессор В.Э. Вольфенгаген

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Под управлением рисками понимают выбор стратегий движения капитала, которые позволяют:

- обеспечить высокую доходность средств;

- уменьшить зависимость от изменения внешних факторов, влияющих на состояние "рынка в последующие моменты времени.

Значительную роль в управлении рисками играет анализ и управление собственными средствами, тесно связанный с понятием от-крытой'позиции. Открытая позиция (ОП) представляет собой совокупность средств банка и средств привлеченных с рынка в некоторый момент времени.

Проблема управления рисками в различной мере охватывается широким набором прикладных математических дисциплин, таких как математическая теория инвестиций, технический анализ и т.п. Фундаментальные основы управления рисками сформулированы зарубежными авторами: Р. Н. Элиотом, В. Блау, Р. Марковитцем, В.Д. Ганиом.

Основные положения классических теорий, с учетом изменившейся структуры финансовых рынков и методов управления капиталом, развиты современными авторами: Дж. Мерфи, Р. Бала ном, Дж. Берштсйном, В. Виллисом, Т. Майерсом.

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

Необходимо отмстить следующее:

- проблема управления рисками на нескольких сегментах рынка, как правило, представляет собой задачу высокой размерности, что обуславливает насущную необходимость использования методов, в той или иной степени преодолевают!« "проклятие размерности";

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

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

Цели работы. Целями работы являются:

- исследование применимости существующих моделей рынка к задачам управления рисками в РМВ;

- построение математической модели многосегментного рынка для управления рисками;

- постановка оптимизационной задачи поддержки принятия решения в РМВ на базе предложенной модели;

- разработка методов, улучшающих характеристики известных методов оптимизации с учетом специфики сформулированной задачи и допускающих использование и РМВ;

- реализация предложенных алгоритмов и исследование их поведения;

- разработка автоматизированной системы, функционирующей на базе построенной модели поддержки принятия решения в РМВ.

Методы исследовании. Основу исследовании, выполненных в работе, составляют методы теории множеств п комбинаторной оптимизации.

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

Научную новизну диссертации и основные положения, которые выносится на защиту, составляют следующие основные результаты:

1. Обосновано и выполнено построение моденI поддержки принятия решения при управлении рисками в РМВ на основе анализа ОП.

2. Предложена и обоснована оптимизационная постановка задачи изменения ОП в рамках построенной модели. Обоснована предпочтительность целочисленных решений.

3. Исследована структура оптимизационной задачи изменения позиций, сформулирован и обоснован критерии качества решения в

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

4. Исследованы характеристики существующих алгоритмов оптимизации в контексте задачи изменения позиции. С учетом специфики предметной области и требований РМВ определены пути их улучшения.

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

6. Разработана автоматизированная система поддержки принятия решения на базе предложенной модели и с учетом специфических требований к реализации.

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

Разработаны и внедрены системы управления рисками на основе модели анализа ОП в РМВ.

Реализация результатов работы. Модели и методы, предложенные в работе были использованы при разработке автоматизированных систем управлений корреспондентских счетов и валютных операций АБ "Империал". В настоящее время указанные системы находятся в промышленной эксплуатации.

Публикации. По результатам диссертационной работы опубликовано 4 работы.

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, содержит 93 страницы, в том числе 7 таблиц, 6 рисунков, библиография включает 50 наименований. .

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

К таковым следует отнести:

- анализ состояния рынка;

- анализ состояния собственных средств;

- оценка условий сделок, предложенных участниками рынка;

- представление своих условий сделок другим банкам;

- определение условий, при которых требуется реакция на изменения состояния рынка;

- определение моментов времени и конкретного вида сделок, которые необходимо провести в данный момент; . .

- заключение сделки;

- исполнение условий сделки;

- контроль и учет проведенных операций. , * . .

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

Основываясь на проведенном анализе, сделан вывод о том, что наибольший эффект в управлении рисками в РМВ достигается при. использовании некоторой комбинации формальных и неформальных методов (основанных на эвристических знаниях лица принимающего решение (ЛПР), относительно анализа состояния рынка). Определен круг задач управления рисками, качество решения которых можно повысить за счет использования математических методов. На основе полученных результатов выполнено разделение функции управления рисками на функции реализуемые непосредственно ЛПР и функции, поддержки принятия решения. К функциям поддержки принятия решения отнесено:

- осуществление регистрации и фильтрации информации о состоянии рынка;

- выполнение анализа состояния собственных средств;

-оценка условий сделок других участников рынка;

- предоставление собственных условий сделок участникам рынка;

- определение условий, при которых требуется реакция на изменения рынка;

- определение моментов времени заключения сделок и конкретного вида сделок.

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

Далее в работе построена формальная модель поддержки принятия решения при управлении рисками.

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

- предложения на рынке в течение торгов имеют неизменную структуру (в течение торгов не может добавится новый тип сделки или новые параметры);

- конкретное предложение определяется фиксированным набором значений параметров, таких как объем сделки, курс, дата расчетов и т.д.;

- изменение значений параметров происходит в РМВ;

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

- предпочтительными являются "круглые" значения объема сделки.

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

Для описания предметной области введен формализм.

Определены следующие множества:

- типов средств;

- типов сделок;

- состояние рынка в момент времени I;

- сделок каждого типа;

- сделок покупки;

- сделок продажи.

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

Характеристиками ¡-ой ОП в момент времени I далее будем называть множество функций:

РС,( I )={ РСи( ОР( ¡, I), I, I ))},] = 1 где: '

ОР ¡( I)-ОП по ¡-.му средству; '

I)- состояние рынка в момент времени I; № - количество характеристик ОП.

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

Введем ограничения для РСу следующим образом: РС""пи <= РСи <= РО'м (1)

Будем считать, что собственные средства находятся в состоянии, соответствующем рынку, если выполнены условия (1):

Пусть [1о, и] непрерывный промежуток времени в течение которого проводятся торги. Минимальный шаг дискретности с которым могут совершатся сделки - с!1. Будем предполагать, что в течение времени <11 рынок не претерпевает существенных изменений и его оценка, сделанная в момент времени 1к верна на интервале [ (к, 1к + сН ).

На основе введенного формализма предлагается следующая модель поддержки принятия решения при управлении рисками. До начала торгов:

1) Определение структуры множеств ОТ - типов сделок и ОР -открытых позиций.

2) На основе анализа ЛПР рынка и собственных средств определение характеристик ОП и задание для них верхних и нижних границ (неизменных в течение торговой сессии).

Во время торгов:

3) Для каждого момента времени tt, в который возможно заключение сделки, определение FCi.j. Если все ограничения (1) выполнены, то сделки не совершаются. В противном случае 4.

4) Определение списка сделок покупки и продажи из множества сделок в момент времени tk, приводящих состояние собственных средств в соответствие с состоянием рынка. В случае, если такое невозможно - ЛПР неверно заданы ограничения на характеристики и требуется их пересмотр.

Далее задачу 4 будем называть задачей изменения ОП (ЗИОП).

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

Анализ часто используемых на практике характеристик ОП позволил разделить их на две группы:

- характеристики прибыли;

- характеристики риска.

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

Для s-ofi сделки покупки в ОП можно указать коэффициент

as( tk):

FC,.¡(tk) = 2 а,( tk) s

Коэффициент as( t*) характеризует влияние s-ой сделки покупки в открытой позиции на значение характеристики FC¡.¡ в момент времени tk. ЗИОП может быть сформулирована как оптимизационная задача с ограничениями задачи линейного программирования в действительных числах следующего вида.

FCmin,. j <= FC¡(tk) + S b¡. ¡,s * v, - 2 Cíj.s * ws <= РСта\ ¡ s= 1 • = 1

0 <= vs <= v"1",

0 <= ws <=wmaxs (2)

где:

X ь,.* - сумма по всем сделкам покупки множества МВ( и);.

Ь,,|.5- коэффициент определяемый из характеристики ОП для бой сделки покупки;

V, - объем б-ой сделки покупки;

2 С|.(,$ * - сумма по всем сделкам продажи множества МВ( 1к). - коэффициент определяемый из характеристики ОП для бой сделки продажи;

ws - объем я-ой сделки продажи;

Переменными являются и \\ч.

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

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

Однако, в работе показано, что более существенным моментом при выборе критерия является предпочтительность сделок с стандартным объемом (лот), поскольку только при таком условии возможно обеспечить реализацию сделок в РМВ.

При решении ЗИОП как задачи ЛП целочисленное решение может быть не найдено. По этой причине, предложен подход, основанный на решении ЗИОП, как задачи нелинейного программирования в действительных числах с линейными ограничениями (2) и критериальной функцией, оптимальное значение которой достигается в целочисленной точке.

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

РСтпи<=РС,.)( Ц) +ИЬЦ5*у5 - ГСта\,

5=1 5=1

V, е{0,у'.......у™",},

ws e {0, w'.......w^s), (3)

где:

{ v's,...., vmaxs } - стандартные объемы s-ой сделки покупки; { w's,...., wmaxs} - стандартные объемы s-ой сделки продажи. При критериальной функции вида: К = const

(3) - задача целочисленного линейного программирования (ЦЛП).

Проведенная оценка размерности практической ЗИОП, показывает, что для многосегментного рынка количество сделок покупки/продажи, возможных в некоторый момент времени, может составлять около сотни. При такой размерности решение задачи ЦЛП в общем виде при использовании известных методов представляется затруднительным. ,

Для исследования ЗИОП определена верхняя оценка вычислительной сложности ЗИОП как функции C(N), где N - ¡ ;ерность задачи. Показано, что значение N ~= 50 - 100. Время реакции системы при ЭТОМ Не ДОЛЖНО превышать lmax- Реальное значение 1тзх оценивается как примерно 5с (при изменяющейся структуре рынка принятие решения ЛПР о заключении сделки за меньшее время представляется затруднительным). При сделанных предположениях С( N ) не может представлять собой функцию, сложности более высокой чем' полином.

Для подхода, основанного на решении задачи нелинейного программирования с ограничениями (2) выполнены преобразования ограничении исходной задачи к виду:

А2*х=Ь (4)

х >= 0 х <= Г

Отсюда, путем введения переменных недостатка: А * х = b (5)

х >= О

Выражение (5) - каноническая форма ограничений задачи ЛП. Введена критериальную функция К( А, b, х ), характеризующая отличие решения задачи в действительных числах от целочисленного, где:

А - матрица задачи в формулировке (5); Ь - вектор свободных членов; х - вектор - результат.

Условимся, что : К( А, Ь, х ) >= 0, причем К( А, Ь, х ) = О тогда и только тогда, когда все компоненты х целые числа.

Решение (х11, х! 2, хЫ ) более предпочтительно чем (х2|, х2:,..., x2N ) если выполнено условие: К( А,Ь, х1) <К( А,Ь,х2). . ; •

Сложность алгоритма ЗИОП не должна превышать С(Ь1) = 0( № ), где р - степень полинома, зависящая от используемых аппаратных средств. Поскольку расчет критериальной функции выполняется на каждом шаге алгоритма:

С( N ) = С1( N ) * С2( N ), (6) "

где: ■'.•'.;'

С( N )- сложность алгоритма; • .

С1(Ы) - сложность процедуры вычисления критерия; С2( N ) - сложность процедуры поиска в пространстве состояний. . .

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

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

- N ' •• ' •

К =N/4 - 2 (1/2 - х 11 , , (7) ¡=1

Действительно:

- сложность процедуры вычисления (7) - 0( N );

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

- (7) является квадратичной.

Для функции вида (7) построен алгоритм численной оптимизации, приведенный на рис. 1.

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

рис. 1 - Алгоритм численной оптимизации для 3110П

Для альтернативного подхода, основанного на решении задачи ЦЛП установлены специальные свойства матрицы задачи, позволяющие решать ЗИОП как задачу ЦЛП специального вида.

Свойство 1

Выберем характеристику ОП и представим ее в виде:

Р(Б,рЛ) = 2р'( МО* Ук+ £ Е а,л * V ы -

к I Я

- 2 2 а^г * ^ (8)

\ 52 ...

где: б - тип средств ОП;

р - номер характеристики ОП;

1 - момент времени расчета характеристики;

£ Р'( МО* V* -

к

сумма переоценки в момент времени г по всем сделкам в ОП, заключенным в момент времени 1к < Г,

Р'( 1,1к) - переоценка к-ой сделки в ОП;

2 2 аы * \'ы -

I 51 ,

сумма по всем сделкам покупки, заключенным в момент времени 1;

- объем б! - ой сделки ¡-го типа;

а;,5| - весовой коэффициент для 51-ой сделки покупки, совершенной в момент времени I;

2 2 а^г * -

1 52

сумма по всем сделкам продажи, заключенным в момент времени I;

\j.s2 - объем э2 - ой сделки .¡-го типа;

- весовой коэффициент для сделки продажи уР2, совершенной в момент времени I.

Одновременная покупка и продажа средств одного типа не приводит к изменению характеристики ОП (8).

о

lu v

Отсюда, (8) в каждый момент времени имеет одну из следующих

форм:

F(s, р, t) = S F'( t, tk ) * vt + Z E ai.si * v ы (9)

к i si

либо:

F(s, p, t) = S F'( t. tk ) * Vk - £ S aj.s: * vJ S2 (10)

k j s2

Выражение (9) соответствует моменту времени когда выполняется покупка средств ОП, выражение (10) соответствует продаже.

Заметим, что если хотя бы одна из характеристик ОП для средств определенного типа имеет вид (9) тогда все характеристики ОП данного типа имеют вид (9). Аналогичное утверждение верно и для выражения (10).

Свойство 2

В каждый момент времени заключается не более одной сделки каждого типа.

Пусть:

Z £аы*\'Ы (11)

i si

часть выражения (8) определяющая сделки покупки, совершенные в момент времени t.

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

Отсюда, (11) приобретает вид:

S а, * v i (12)

i

После выполнения аналогичных преобразований для выражения (12) выражения (9) и (10) можно заменить выражениями (13) и (14) следующего вида:

F(s, p, t) = S F'( t, tk ) * vk + Е a, * v i (13)

k i

либо:

ю

Р^.р.О = ЕР'( 1,Ц)* ^ (14)

к )

Свойство 3

Каждая сделка покупки/продажи увеличивает ОП в одном средстве и уменьшает в другом. Таким образом, в случае, когда средства б 1-го типа привлекаются - средства б2-го типа размещаются и наоборот.

Таким образом, если характеристики для -го типа средств имеют вид:

Fisl.pl, о = £р/,|( МО* + Е а,и* V,!.! . (15)

к I

то для б2 - го средства, проданного за - ое они имеют вид:

Р(82,р2Д) = £р'52( МО + у.и -Е а$2д*у,2.У (16)

к 1 . • •

Выделенные нами свойства ! - 3 являются существенным сужением класса задач ЦЛП.

Важно отметить, что каждое из свойств непосредственно следует из семантики предметной области и не накладывает дополнительных ограничений на ЗИОП.

Для построения алгоритма, основанного на использовании свойств 1 - 3, введен формализм графа ЗИОП. Обозначим граф ЗИОП как в.

Каждой вершине графа в соответствует некоторый элемент матрицы ЗИОП. Пометим вершину четверкой вида . { ТР, БВ, УОЬ, ТБ }, где:

ТР - тип сделки;

БВ - покупка/продажа;

УОЬ - объем сделки ;

ТБ - тип средств;

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

г(ТР, БВ, УОЦТБ).

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

Так, если для сделки типа ТР определены объемы

{О, УОЬ|,..., УОЬя }, то граф в включает Я + 1 вершину, которые соответствуют единственному элементу матрицы ЗИОП.

Нулевым элементам матрицы ЗИОП не соответствует ни одной вершины.

Согласно свойству .1 каждой пок\ пке средств типа ТЯI соответствует продажа средств типа ТБ:. Отсюда, каждой вершине /,(ТР, 8В|, УОЬ|, ТБ] ) взаимно однозначно соответствует вершина '¿¡(ТР, 813:, УОи.ТБг).

Соединим вершины п и г\ дугой.

Согласно свойству 2, может быть совершено не более одной сделки каждого типа. Согласно свойству I каждый типа средств может либо привлекаться либо размещаться.

Отразим эти свойства в графе в следующим образом. Вершину г,(ТР|, БВк У01л, Т51 ) соединил дугой со всеми вершинами х^ТР:, БВз, У01.2, ТБ2), для которых:

ТР, <> ТР2;

БВ| = БВ:;

ТБ| = ТБз.

Полученный граф далее будем называть графом ЗИОП.

Пусть М - общее число характеристик в ОП (число строк матрицы А).

В дополнение к графу О определим матрицу В размерности

М*4.

Элемент Ь/.| есть текущее значение:

£р'( МО* V»;

к- •

для ¡-ой характеристики, т.е. значение характеристики без добавления сделок в момент времени

Элемент Ь,.2 - ограничение снизу Р/™1 на текущее значение характеристики.

Элемент Ьи - ограничение сверху Р,п,ах на текущее значение характеристики.

Элемент Ьи - значение характеристики, полученное после включения в характеристику сделок, совершенных в момент времени I.

В случае, если не заключено ни одной сделки Ь,.з = Ьы-

Если выполнено:

= 1..М: Ь,.з >= Ь,.< и Ьи<= Ь,.2 , (17)

то проведение сделок в момент времени г не требуется.

Каждому набору сделок, соответствует некоторый подграф графа й.

Заметим, что если подграф С графа в связный, то он удовлетворят свойствам 1 - 3 матрицы ЗИОП. Это следует непосредственно из определения графа в.

По подграфу С с использованием матрицы ЗИОП можно однозначно определить значение всех характеристик.

Если имеется целочисленное решение ЗИОП, то найдется подграф О* графа в, однозначно соответствующий данному решению. При этом:

V ¡=*1..М:Ь,4>=Ь,,| иЬ,4<=Ьи (18)

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

Предложен следующий алгоритм для построения допустимого подграфа.

1) По матрице ЗИОП построение исходного графа О и матрицы В. .

2) Проверка условия (17) для матрицы В. Если условие (17) выполнено, то завершение работы алгоритма сообщением, о том, что не требуется совершение сделок в момент времени I. В противном случае -шаг 3.

3) На основе матрицы В построение векторов у1 и у2.

Элементы вектора у1 - номера тех строк матрицы В для которых выполнено Ь),4 < Ьи-

Элементы вектора у2 - номера тех строк матрицы В для которых выполнено Ь.,4 > Ьи.

4) Построение подграфа С следующим образом.

Для каждого типа средств, соответствующего некоторой характеристике с номерами из вектора у1 удаление всех сделок продажи.

Для каждого типа средств, соответствующего некоторой характеристике с номерами из вектора у2 удаление всех сделок покупки.

I ¿г

Если построенным граф С не связный (не выполнены свойства 1-3) - завершение работы алгоритма сообщением об отсутствии целочисленного решения, в противном случае - шаг 5.

5) Генерация допустимого набора сделок покупки. Из графа С построение графа С', соответствующего набору.

6) Пока есть допустимые наборы сделок покупки выполнить

шаг 7.

7) Если граф С связный - вычислить значение для всех ¡=]..М. Если для В выполнено (17) завершить работу алгоритма. Построенный граф С является оптимальным. В противном случае - следующая итерация шага 5.

8) Ни для одного допустимого набора сделок не выполнено (17) (не существует корректирующего набора сделок). Завершение работы алгоритма сообщением об отсутствии целочисленного решения ЗИОП.

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

С11<г1'2>

где:

г1 - число типов сделок;

с11 число типов средств.

Такая оценка, несмотря на то, что является экспоненциальной, позволяет реализовать поиск целочисленного решения ЗИОП в РМВ с указанными ограничениями на время реакции системы.

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

В работе приведено описание реализации автоматизированной системы. К ее функциям следует отнести:

1) Получение информации о состоянии рынка, поступающей в РМВ из коммуникационных систем.

2) Фильтрация информации, поступившей из коммуникационных систем и ее сохранение в БД.

3) Ввод и коррекция ЛПР информации о семантике предметной области и стратегии управления рисками.

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

5) На основе данных о состоянии рынка, хранящихся в БД, -расчет текущих значений характеристик ОП. Выполнение процедуры для определения перечня сделок, которые требуется провести в конкретный момент времени. . ;

6) Обеспечение ЛПР, заключающего сделки, информацией о значениях характеристик и параметрах сделок, которые необходимо провести.

7) Обеспечение хранения в БД информации о проведенных сделках. Формирование справочно-аналнтических отчетов по проведенным операциям.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

- ограничения на время реакции системы.

Основные результаты работы заключаются в следующем:

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

2) Сформулирована задача поддержки принятия решения в операциях на финансовых рынках и обоснована необходимость ее решения в рамках предложенной модели.

3) Выделены факторы, влияющие на принятие решения ЛПР при управлении рисками.

4) Построена -математическая модель поддержки принятия решения при управлении рисками на основе понятия ОП.

о

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

6) Рассмотрены особенности решения 'ШОП при формулировке п виде задачи с линейными ограничениями и нелинейной критериальной функцией (ЛОНК).

7) Исследована ЗИОП п формулировке Л ОIIK. Iпредложена критериальная функция специальною вида, обладающая требуемыми .свойствами. Разработан численный метод для решения задачи минимизации построенной критериальной функции при линейных ограничениях.

8) Исследована ЗИОП в формулировке ЦЛП. Выделены специфические свойства матрицы задачи, позволяющие рассматривать ее как задачу ЦЛП специального вцца. Введен формализм графа задачи ЗИОП. Граф построен таким образом, что его связность гарантирует сохранение специальных свойств матрицы задачи.

9) На основе графа ЗИОП построем алгоритм поиска оптимального подграфа, которому однозначно соответствуют целочисленное решение. Доказана корректность алгоритма, проведена оценка вычислительной сложност и. Показано, что при определенной в исследовании размерности практической задачи, временные характеристики предложенного алгоритма позволяют его использовать для решения ЗИОП в РМВ.

Ю) Па базе предложенных методов разработана автомат изированная система по;|держки принятия решения при управлении рисками в операциях па финансовых рынках. Эффективность пре;ито-жднных в диссертации методов подтверждена решением на их основе ряда практических задач.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Киселев Б.Е., Аверина A.B. Петухов. М.Н., Золотухина Е.Б., Алфимов Р.В. Разработка систем поддержки валютных операций. // "Банковские системы", М.:1995. CI7-19.

2. Р.В. Алфимов. Полиномиальный алгоритм ;пя задачи выполнимости булевой формулы. - М., Препринт. МИФИ, 1995.

3. Свидетельство об официальной регистрации программ для ЭВМ N 940341. Автоматизированная система контроля и учета валютных операций. -М., РОСАПО, 1994.

4. Разработка модели экспертной контрольно-диагностической системы. Научно-технический отчет, тема 92-3-029-732, итоговый, - М., МИФИ, 1992, N гос. per. 0291.0019927.

Подписано в печать $ Ю 9? Заказ -7С-Ч Тираж '(ОС PkJ

Типография МИФИ, Каширское шоссе, 31 1

о

ВВЕДЕНИЕ.-.

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

1.1. Функции банков - участников финансовых рынков.—.

1.2. Обеспечение операций на финансовых рынках.-.

1.3. Задачи банка в операциях на финансовых рынках.

1.4. Задача поддержки принятия решения, как составная часть управления рисками.

1.5. Сравнительный анализ методов управления рисками.

1.6. Функции принятия решения, допускающие реализацию в рамках формальной модели.

Выводы по первой главе.

ГЛАВА 2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ДЛЯ ЗАДАЧИ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЯ.

2.1. Определения основных понятий предметной области -—.-.

2.2. Функция переоценки портфеля как критерий качества принятия решения при проведении операций на финансовых рынках.-.

2.3. Модель поддержки принятия решения на основе понятия открытой позиции.

2.4. Математическая постановка ЗИОП.

Выводы по второй главе.-.

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

3.1. Оценка вычислительной сложности алгоритмов для ЗИОП исходя из требования реального масштаба времени.-.

3.2. Общие свойства ЗИОП

3.3. Сравнительный анализ методов решения задач ЛП и ЦЛП в применении к ЗИОП.-.

3.4. Метод решения ЗИОП при формулировке с линейными ограничениями.-.

3.5. Метод решения ЗИОП при формулировке в виде задачи ЦЛП.

3.6 Граф ЗИОП.-.-.

3.7. Алгоритм построения оптимального подграфа графа ЗИОП.

3.8. Анализ алгоритма, доказательство корректности, оценка вычислительной сложности.-.-.

Выводы по третьей главе.

ГЛАВА 4. АВТОМАТИЗИРОВАННАЯ СИСТЕМА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЯ НА ОСНОВЕ МОДЕЛИ ОТКРЫТЫХ ПОЗИЦИЙ.-.

4.1. Описание функций автоматизированной системы.

4.2. Ввод характеристик ОП.-.

4.3. Модульная структура системы.

4.4. Пример функционирования системы.—.

Выводы по четвертой главе.

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

Под управлением рисками понимают выбор стратегий движения капитала, которые позволяют:

- обеспечить высокую доходность средств;

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

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

Проблема управления рисками в различной мере охватывается широким набором прикладных математических дисциплин, таких как математическая теория инвестиций, технический анализ и т.п. Фундаментальные основы управления рисками сформулированы зарубежными авторами: Л. Вильямсом, Р.Марковитцем, В.Д. Ганном [21,10,17].

Основные положения классических теорий, с учетом изменившейся структуры финансовых рынков и методов управления капиталом, развиты современными авторами: Дж. Мерфи, Р. Баланом, Дж. Берштейном, Д. Джобманом, В. Блау [18, 23,20,16,24 ].

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

Необходимо отметить следующее:

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

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

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

Цели работы. Целями работы являются:

- исследование применимости существующих моделей рынка к задачам управления рисками в РМВ;

- построение математической модели многосегментного рынка для управления рисками;

- постановка оптимизационной задачи поддержки принятия решения (ЗППР) в РМВ на базе предложенной модели;

- разработка методов, улучшающих характеристики известных методов оптимизации с учетом специфики сформулированной задачи и допускающих использование в РМВ;

- реализация предложенных алгоритмов и исследование их поведения;

- разработка автоматизированной системы, функционирующей на базе построенной модели поддержки принятия решения в РМВ.

Методы исследования. Основу исследований, выполненных в работе, составляют методы теории множеств и комбинаторной оптимизации.

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

Научную новизну диссертации и основные положения, которые выносятся на защиту, составляют следующие основные результаты:

1. Обосновано и выполнено построение модели поддержки принятия решения при управлении рисками в РМВ на основе анализа ОП.

2. Предложена и обоснована оптимизационная постановка задачи изменения ОП в рамках построенной модели. Обоснована предпочтительность целочисленных решений.

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

4. Исследованы характеристики существующих алгоритмов оптимизации в контексте задачи изменения позиции. С учетом специфики предметной области и требований РМВ определены пути их улучшения.

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

6. Разработана автоматизированная система поддержки принятия решения на базе предложенной модели и с учетом специфических требований к реализации.

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

Разработаны и внедрены системы управления рисками на основе модели анализа ОП в РМВ.

Реализация результатов работы. Модели и методы, предложенные в работе были использованы при разработке автоматизированных систем управлений корреспондентских счетов и валютных операций АБ "Империал". В настоящее время указанные системы находятся в промышленной эксплуатации.

Публикации. По результатам диссертационной работы опубликовано 4 работы.

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, содержит 93 страницы, в том числе 7 таблиц, 6 рисунков, библиография включает 50 наименований.

Основные результаты работы заключаются в следующем:

1) На основе анализа литературных данных, определен круг задач управления рисками, качество решения которых можно повысить за счет использования формальных методов.

2) Выделены факторы, влияющие на принятие решения ЛПР при управлении рисками.

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

4) Построена математическая модель поддержки принятия решения при управлении рисками на основе понятия ОП.

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

6) Рассмотрены особенности решения ЗИОП при формулировке в виде задачи с линейными ограничениями и нелинейной критериальной функцией (ЛОНК). Показана необходимость разработки методов решения для обоих случаев.

7) Исследована ЗИОП в формулировке ЛОНК. Предложена критериальная функция специального вида, обладающая требуемыми свойствами. Разработан численный метод для решения задачи минимизации построенной критериальной функции при линейных ограничениях.

8) Исследована ЗИОП в формулировке ЦЛП. Выделены специфические свойства матрицы задачи, позволяющие рассматривать ее как задачу ЦЛП специального вида. Введен формализм графа задачи ЗИОП. Граф построен таким образом, что его связность гарантирует сохранение специальных свойств матрицы задачи.

9) На основе графа ЗИОП построен алгоритм поиска оптимального подграфа, которому однозначно соответствуют целочисленное решение. Доказана корректность алгоритма, проведена оценка вычислительной сложности. Показано, что при определенной в исследовании размерности практической задачи, временные характеристики предложенного алгоритма позволяют его использовать для решения ЗИОП в РМВ.

10) На базе предложенных методов разработана автоматизированная система поддержки принятия решения при управлении рисками в операциях на финансовых рынках. Эффективность предложенных в диссертации методов подтверждена решением на их основе ряда практических задач.

ЗАКЛЮЧЕНИЕ

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

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

- ограничения на время реакции системы.

1. Э. Рид, Р. Коттер, Э. Гилл, Р. Смит. Коммерческие банки. -М.: Прогресс, 1983.

2. Пономарев В.А. Анализ балансов капиталистических коммерческих банков. М.: Издательство МФТИ, 1982.

3. Миловидов В.Д. Совеременное банковское дело: Опыт США. -М.: Издательство МГУ, 1992.

4. Усоскин В.М. Соверменный коммерческий банк. М.: ИПЦ "ВАЗАР-ФЕРРО", 1994.

5. Sheldon Н.Р. The Practice and Low Of Banking. London, 1972.

6. Walker S., David A. Retail EFT Activity of Commercial Banks: A Comparative Analysis. Journal of Contemporary Business, Summer 1977, p. 31-44.

7. Edmister. R. Financical Institutions, Markets and Management.-New York, 1986.

8. Киселев Б.Е., Аверина A.B. Петухов. M.H., Золотухина Е.Б., Алфимов Р.В. Разработка систем поддержки валютных операций. // "Банковские системы", М.:1995. С17-19.

9. J. F. Dalton, Е. Т. Jones, R. В. Dalton. Mind over markets New York, 1993.

10. Markovitz H.M. Portfolio Selection. Yele Press, 1959.

11. Tohin D. Liquidity preference as behaviour toward risk. //Rev. of Econ. Studies, 1958, v.25, N1, pp. 65-86.

12. Duff D. Security Marckets: Stockhastic models. Stenf. Univ. Press,1988.

13. Крянев A.B., Черный А.И. Численные методы решения некорректно поставленных задач математической теории инвестиций // Сборник тезисов докладов "Обратные и некорректно поставленные задачи". М.:1995. С.ЗО.

14. Alexander G., Francis J. Portfolio Analysis, N.-Y., 1985.

15. Elton E.J., Gruber M.J. Modern Portfolio Theory and Investment Analysis. N.-Y., 1981.

16. D.R. Jobman. The New Science of Technical Analysis N.-Y., 1993.

17. W.D. Gann. How To Make Proffits. N.Y., 1976.

18. J. J. Murphy. Intermarket Techical Analysis. N.Y.,1991.

19. S. Nison. Beyond Candlesticks. London, 1991.

20. J. Benstein. Cyclic Analysis in Futures Trading: Systems, Methods and Procedures. N.Y.,1988.

21. L. R. Williams. How I Made $ 1,000,000 Trading Commodities Last Year.-N.Y., 1979.

22. A. Cardwell. Relative Strangth Index. N.Y.,1995

23. R.Balan. Elliot Wave Principle Applied to the Foreign Exchange Markets. -N.Y.,1989.

24. W. Blau. Momentum, Direction and Divergence. N.Y.,1985.

25. T. J. Jersey. Point and Figure Cahrting. N.Y.,1993.

26. J. W. Wilder. New Concepts in Technical Trading Systems. N.Y.,1978.

27. Инструкция пользователя торгового терминала БЕФТ SOFT.

28. Reuters Dealing 2000, Technical Reference.

29. X. Папандимитру, К. Стайглиц. Комбинаторная оптимизация. Алгоритмы и сложность. -М.: Мир, 1985.

30. Ху. Т. Целочисленное программиирование и потоки в сетях. -М.: Мир, 1976.

31. Рейнгольд Э. Нивергельт Ю., Део. Н. Комбинаторные алгоритмы, теория и практика. М.: Мир, 1980.

32. Гэрри М., Джонсон Д. Вычислительные машины и трудноре-шаемые задачи М.: Мир, 1982.

33. Юдин. Д.Б., Голыптейн Е.Г. Линейное программирование. -М.: Наука, 1969.

34. L. Tuncel, "Constant Potential Primal-Dual Algorithms: A Framework". Mathematical Programming 66 (1994), 145-159

35. M.J. Todd, 'The Affine-Scaling Direction for Linear Programming is a Limit of Projective-Scaling Directions". Linear Algebra and its Applications 152 (1991) 93-105.

36. S. Mizuno, M.J. Todd, and Y. Ye, "On adaptive-step primal-dual interior-point algorithms for linear programming" (Oct. 90). Mathematics of Operations Research 18 (1993) 964-981.

37. J. Renegar, "On the Computational Complexity and Geometry of the First-Order Theory of the Reals". Journal of Symbolic Computation 13 (1992) 255-352.

38. Bland R.G. New Finite Pivoting Rules, Discussion Paper 7612, Center for Operation Research and Econometrics (CORE). June 1976.

39. Хачиян JI.Г. Полиномиальный алгоритм в линейном программировании. ДАНН СССР, 1979, т. 244, N 5, с. 1093 - 1096.

40. Aspvall В., Stone R. Е. Khachiyan's linear programming algoritm, Journal of Algoritms, 1, No. 1,1980.

41. Шор. H. 3. Метод отсечения с растяженим пространства для решения задач выпуклого программирования. Кибернетика, 1977, N 1, с. 94-95.

42. M.J. Todd, "The Effects of Degeneracy and Null and Unbounded Variables on Variants of Karmarkar's Linear Programming Algorithm". In Large-Scale Numerical Optimization (T.F. Coleman and Y. Li, eds.), SIAM, Philadelphia, 1990, 81-91.

43. R. Urbaniak, R. Weismantel and G. Ziegler, A variant of Buchberger's algorithm for integer programming, preprint SC 94-29, ZIB Berlin.

44. S.A. Plotkin, D. Shmoys, and E. Tardos, "Fast approximation algorithms for fractional packing and covering problems". Proc. of the Thirty-second IEEE Symp. on Foundations of Computer Science (1991), 495-504.

45. F. Hsieh and B. Turnbull, "A Note on the Local Asymptotically Minimax Rate for Estimating a Crossing Point in a Diagnostic Marker Problem". Mathematics of Operations Research 19 (1993) 522-527.

46. M.J. Todd and Y. Ye, "A Lower Bound on the Number of Iterations of Long-Step and Polynomial Interior-Point Linear Programming Algorithms" (1/94). Annals of Operations Research 62 (1996), 233-252

47. P.B. Алфимов. Полиномиальный алгоритм для задачи выполнимости булевой формулы. М., Препринт, МИФИ, 1995.

48. В. Sturmfels and R.R. Thomas, Variation of cost functions in integer programming (1994), Technical Report, School of Operations Research, Cornell University.

49. Разработка модели экспертной контрольно-диагностической системы. Научно-технический отчет, тема 92-3-029-732, итоговый, М., МИФИ, 1992, N гос. per. 0291.0019927.

50. Аверина А.В., Петухов. М.Н., Золотухина Е.Б., Алифимов Р.В., Неплохов В.Ю., Угринович Н.В. Свидетельство об официальной регистрации программ для ЭВМ N 940341. Автоматизированная система контроля и учета валютных операций. -М., РОСАПО, 1994.