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

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

005005365

МУСЛИМОВА Галия Рамилевна

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

-■8 ДЕК 2011

Уфа-2011

005005365

Работа выполнена в ФГБОУ ВПО «Уфимский государственный авиационный технический университет» на кафедре вычислительной математики и кибернетики

Научный руководитель

д-р физ.-мат. наук, проф. БРОНШТЕЙН Ефим Михайлович

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

д-р физ.-мат. наук, проф. СПИВАК Семен Израилевич

Башкирский государственный университет, каф. мат. моделирования

Ведущая организация

канд. техн. наук

ОЛЕЙНИК Татьяна Николаевна

ЗАО "Аптека-Холдинг", филиал в г. Уфа

Башкирский государственный педагогический университет им. М. Акмуллы

Защита диссертации состоится 22 декабря 2011 года в 10 часов на заседании диссертационного совета Д-212.288.03 при Уфимском государственном авиационном техническом университете по адресу: 450000, г. Уфа, ул. К. Маркса, д. 12

С диссертацией можно ознакомиться в библиотеке университета

Автореферат разослан 18 ноября 2011 года

Ученый секретарь ^

диссертационного совета // / \л 'С

д-р техн. наук, проф. // { У^Р В.В.Миронов

Общая характеристика работы

Актуальность темы

Управление проектами различной природы в силу важности привлекает исследователей, представляющих различные области знаний. Международным институтом Управления Проектами (PMI) разработана база знаний по эффективному управлению проектами (Project Management Body of Knowledge) которая интегрирует профессиональные знания по управлению проектами и является международно-признанным стандартом (IEEE, ANSI).

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

Рациональное инвестирование средств является важной задачей, стоящей перед инвесторами. Она важна как для инвесторов, так и для народного хозяйства в целом. Исследование инвестиционных проектов начато в работах И. Фишера, Д. Кейнса. Задачи формирования оптимальных (в том или ином смысле) портфелей из инвестиционных проектов рассматривались Дж. Лори, Л. Сэведж, М. Вейнгартнером, Дж. Хиршлейфером, П. Л. Виленским, В. Н. Лившицем, С. А. Смоляком, В. 3. Беленьким, С. И. Спиваком, Е. М. Бронштейном и рядом других исследователей. В работах М. Балинского, А. Шогана, Дж. Мамера рассмотрены задачи формирования портфелей инвестиционных проектов, если по некоторым семействам проектов предусмотрены групповые выплата,/, подобные задачи возникают на практике довольно часто (приобретение спецтранспорта, офисных помещений в местах реализации проектов и др.). При этом не рассматривались ситуации, когда по семействам проектов возможны не только платежи инвестора, но и поступления средств (например, сдача помещений в аренду), не учитывались также возможность заимствования средств (на начальном этапе это может оказаться целесообразно) и возможная взаимозависимость проектов. Подобные ситуации возникают на практике, в то же время, подобные задачи исследованы недостаточно. Эти обстоятельства являются обоснованием актуальности темы диссертации.

Цель работы и задачи исследования

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

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

2. Разработка эвристических алгоритмов решения поставленной оптимизационной задачи.

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

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

Основные результаты, выносимые на защиту:

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

2. Проблемно ориентированные эвристические численные методы и алгоритмы решения задачи формирования оптимальных инвестиционных портфелей с учетом групповых выплат и взаимосвязи проектов (модифицированный метод ветвей и границ и эволюционный алгоритм (1+1)-ЕЛ), (п. 3 Паспорта специальности 05.13.18).

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

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

Научная новизна

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

2. Разработаны эвристические алгоритмы решения сформулированной оптимизационной задачи, учитывающие ее специальную структуру (модифицированный метод ветвей и границ, эволюционный алгоритм класса (1+1) - ЕА).

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

провести сравнение эффективности модифицированного метода ветвей и границ и эволюционного алгоритма (1+1) - ЕА и точных алгоритмов оптимизации.

4. Установлено, что эффективность предложенных эвристических алгоритмов близка к эффективности точных алгоритмов, при этом для задач малой размерности при сравнении точных алгоритмов выигрывает метод Гомори, для задач большей размерности - метод ветвей и границ. Также установлено, что значение целевой функции нечувствительно к изменению процентных ставок (эластичность является малой), т.е при формировании портфелей из инвестиционных проектов риском процентной ставки можно пренебречь. Это установлено на основе вычислительного эксперимента.

Практическая значимость и внедрение результатов

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

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

- моделирование исходных данных при различных условиях;

Исследования проводились при поддержке РФФИ «Интегрированная

портфельная теория» (проект 07-06-00021) и «Асимметричные и комплексные меры риска и их применение при формировании портфелей ценных бумаг» (проект 10-06-00001).

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

Апробация работы

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

• на второй, третьей и пятой всероссийских зимних школах-семинарах аспирантов и молодых ученых (Уфа, 2007, 2008, 2010);

• на Международной научной школе-семинаре имени академика С. С. Шаталина (Воронеж, 2008);

• на шестой Всероссийской открытой научно - практической конференции «Актуальные задачи математического моделирования и информационных технологий» (Сочи, 2010),

• на VI Московской международной конференции по исследованию операций (ОЮИ2010) (Москва, 2010).

Публикации

Основные материалы диссертационной работы опубликованы в 13 научных трудах, в том числе 4 статьи в изданиях, рекомендованных ВАК РФ, 8 в других изданиях и 1 свидетельство о регистрации программного продукта.

Структура работы

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

Основное содержание работы

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

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

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

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

Рассмотрим две содержательные задачи финансового анализа.

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

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

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

Эти процессы можно описать следующей единой математической

моделью.

Заданы следующие объекты:

- подмножество АсЛп+1 (в соответствии с терминологией первой задачи элементы этого множества именуем инвестиционными проектами), требуется выбрать некоторое подмножество А'.

- множества и,УсВ(А), где В(А) - булеан (множество всех подмножеств),

- отображение g:U—> й.1*1 (содержательный смысл этого отображения состоит в необходимости включения вектора в рассмотрение, если выбирается хотя бы один элемент из и - подробности далее),

- бинарное отношение БсА2 (его смысл: если (а^^Б, то вектор а\ можно выбирать только если выбран вектор а2),

- числа г^>1 (содержательный смысл этих величин это соответственно ставка заимствования и банковская ставка) и Р.]>0 '(содержательный смысл -начальный капитал).

Для каждого подмножества А'сА формируем вектор = Еве<1' а + Еавожм'« $'(")>

при следующих ограничениях.

- VI' е V: 1ь< С; а'\ < 1 (элементы V являются семействами альтернативных проектов),

- если (аьа2)е8, то из того, что а^А' следует, что а2еА'.

Определена последовательность К], РС(А'),..., РХ(Л') следующим

рекуррентным соотношением.

Необходимо выбрать множество А' таким образом, что рЛ.а') - тах. Смысл - максимизация итогового эффекта.

Приведем модель к задаче кусочно-линейного булева программирования. Для этого введем булевы переменные х, и у/.

д-. = 1 тогда и только тогда, когда а^Ау/=1 тогда и только тогда, когда Uj-nA '*<Z> Тогда yjtXi при а,-ей,-,

v. < £„.s v., (два последних неравенства в совокупности означают, что

yj= 1 тогда и только тогда, когда хотя бы для одного i е С^) если (a0aj)eS, то (содержательный смысл в том, что проект хс может быть включен в портфель только в том случае если в портфель включается проект xd),

h(A') = Q;.Vj

F'XA) \гРк_,(Л')+Ьк{А') при Fk_,{A')<0[k .....П)>

Fr_(A') max (содержательный смысл -NFV проектов)

Наконец, преобразуем модель к задаче частично булева линейного программирования, что позволит использовать для решения некоторые стандартные методы (в работе использовался алгоритм отсечения Гомори). Для этого заметим, что поскольку r>q, то F^A') = max{qFk., 4. hk(A'),rFk^ -4- fi-,(4')}.

Задача принимает следующий вид.

Пусть кит- мощности соответственно множеств А и U. Найти булевы переменные .т, (¡'=1,2,.,.,к), yj (/-1,2,...,т) и вещественные числа Fn такие, что

yj>X/ при a, £Mj,

если {ac,ad)^S, то

h = ot.*i -г £(%)>}> Fk £ qFk~i - h.k, г* £ rF,., -ft»,

Методы решения задач целочисленного ЛП (классификация)

Для решения поставленной оптимизационной задачи были использованы точные и эвристические численные методы, представленные на рис. 1.

Точные метода.

Численные метода репения задач •

де,"очнсяоц1К1ГО вдиейноги .. . — •••<11ро1раммировиаьгая.....--.=

¡а »¡Эвристические: % _ метода

• метод отсеяешш ■. Гомори-

"ветвей п. гранпц"

модифицирован ¿1 ветвей п граппц

Рисунок 1 - Классификация методов решения задач целочисленного

линейного программирования Точные методы решения рассматривались в стандартном виде. Были разработаны эвристические алгоритмы модифицированный метод ветвей и

Рисунок 2 - Блок-схема модифицированного метода «ветвей и границ»

Основные обозначения (рис.2): С - множество исходных инвестиционных проектов; и - подмножества проектов, Р - множество платежей по группам проектов; я, г - банковские ставки дисконтирования и

заимствования; Бп - начальный капитал инвестора; т - длительность проектов; п - количество проектов; б - количество проектов и; Рот^ -формируемый инвестиционный портфель; БВеэ! - итоговый капитал инвестора; gruppгoject(C,U) - пользовательская процедура, создающая из всех проектов, не входящих ни в одно подмножество и, дополнительное подмножество и; туе1у(С,и,Р^,г,Рп) - пользовательская процедура, рассчитывающая портфель стандартным методом «ветвей и границ» для каждого подмножества проектов и в отдельности, но с учетом включенных с портфель проектов.

Рисунок 3 - Блок-схема эволюционного алгоритма (1+1)-ЕА

Основные обозначения (рис.3): Zmax - максимальное заданное число неудачных включений проектов в портфель (неудача заключается в том, что при включении проекта в портфель результирующий капитал инвестора ие увеличивается); Port - текущий портфель проектов; FCurr - текущее значение

капитала инвестора; БВез! - итоговый капитал инвестора; Ъ - текущее число неудачных включений проектов в портфель; пр\рго]еЫ{С,Р^,1) -пользовательская функция, рассчитывающая значение чистого приведенного дохода (ИРУ) проектов по формуле +К(ЕГ=о7~;У «)>

где к - момент времени, в который выполняются платежи по проектам; прурБ(НРУ,С) - пользовательская процедура формирующая из исходных проектов приоритетный список РЭ в порядке убывания их значений КРУ; пех1й1(С,Р,Рп,и)д,гД,8) - пользовательская процедура, которая помещает по порядку проекты из приоритетного списка РБ в текущий портфель (при этом из списка РБ он удаляется), а также рассчитывается БСшт для этого портфеля

по формуле: = тах д^ + |>,с/(1+1) + г^ +2>,с,(,ы) + £ .

I '=1 ы .И ]

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

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

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

л Перемени« банка ей открытки счетов и гаоэдке гоедостаа пения кредитов

Формирование икаестш+ю^ь* данных, Ммнвеспмкхньа данные группирование проектов иолределет зависимостей иекду ними

Данные об хна естм^емн порфелях

Начальньи «йгмгал инеестсра

Ставки

днаокшроаэиия и

Расчет итогового капитала инвестора с учеюм вложения всех средств в банк

Итоговый капитал инвестора при условии вложения ^•средств в банк

Имвестицанньй портфель и итоговый капитал инвестора

Показатели аф^ективностх проектов

Оптималеньй |*чеестж^онньй тръхвгь и итогов ьй капитал инвестора

Рисунок 4 - Функциональная модель процесса формирования оптимального инвестиционного портфеля проектов (1-ый уровень)

На рисунке 5 представлена архитектура разработанного прототипа комплекса программ :

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

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

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

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

четыре модуля решения задачи - производят решение оптимизационной задачи соответствующими методами;

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

- блок вывода результатов - выводит результаты вычислений на экран и сохраняет их во внешних файлах;

Рисунок 5 - Архитектура прототипа комплекса программ «Формирование инвестиционного портфеля»

В комплекс программ ((Формирование инвестиционного портфеля» входят четыре программных модуля Vetv, Gomori, VetvModif, Evolut, Generat, реализованных на языке Object Pascal в среде программирования Borland Delpfi 7.0.

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

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

При этом были заданы следующие параметры:

• Ki =100 - начальный капитал инвестора;

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

• число подмножеств Ц задавалось в зависимости от количества проектов ог 3 до 8 (Здля 5 проектов, 4 для 10 проектов, 5 для 15 и т. д.), их состав генерировался случайно по равномерному закону с помощью генератора псевдослучайных чисел языка Pascal, при условии, что каждый проект входит хотя бы в одно из подмножеств;

• ставка банковского вклада 4%;

• ставка банковского кредита 7%;

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

• для эволюционной стратегии условием останова было достижение 50 неулучшений популяции;

• для каждого значения временного горизонта и=4,...,9 генерировалось по 100 задач при размерности задач 5,10,15,20,25 и 30 проектов.

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

Также был поставлен вычислительный эксперимент, цель которого -анализ чувствительности решения задачи к изменениям параметров (банковская процентная ставка, ставка заимствования), а также влияние на результат числа подмножеств Ц,. Применялся точный метод ветвей и границ, при этом, проекты упорядочивались по убыванию чистой приведенной стоимости с учетом групповых платежей. Показателем чувствительности была эластичность, которая приближенно равна выраженному в процентах изменению зависимого параметра при увеличении аргумента на 1%. Эластичность рассчитывалась по формуле: wrm-wro.^,. где

NFV{ 1) - NFV портфеля при базовых ставках гид, NFV{2) -М-Упортфеля при гид, увеличенных на 1%.

——— Эволюционная стратегия

—*— Ветвей и границ

—Упрощенный метод ветвей и границ

—-— Метод Гомори

—Эволюционная стратегия

-------Ветвей «границ

—— Упрощенный метод ветвей и границ

......Метод Гомори

Рисунок 3 - Графики, отображающие эффективность и время работы

алгоритмов

Были заданы следующие общие параметры:

• F.i =100 - начальный капитал инвестора;

• С, и Pj - платежи по проектам и группам проектов генерировались случайно в диапазоне от -150 до 150;

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

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

• ставка банковского вклада 2%;

• ставка банковского кредита 2-7%;

• число проектов принималось равным 5,10,15;

• число подмножеств Ц задавалось в зависимости от количества проектов (Здля 5 проектов, 4 для 10 проектов, 5 для 15 ), их состав генерировался случайно, объединение множеств Ц совпадало с множеством проектов;

• длительность проектов 4—9 лет;

« учитывались по одному условия вида (3) и (4).

Результаты вычислений приведены на рис. 4.

Из рис. 4 видно, что

• эластичность накопленной стоимости оптимального портфеля к ставке заимствования является отрицательной (это естественно) и весьма мала по модулю;

• с ростом базовой ставки модуль эластичности в среднем возрастает;

Длительность проектов 4 года

10 15 20

Циспп nnri»irm*

• модуль эластичности также в среднем возрастает при увеличении временного горизонта;

• модуль эластичности в среднем убывает при возрастании числа проектов.

5 проектов, <р=2:

5 6 7 г,%

-0,035 -<

Рисунок 4 - Эластичность накопленной стоимости оптимального портфеля к ставке заимствования

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

• ставка банковского вклада 1 -4%;

• ставка банковского кредита 5%;

• значения других величин задавались как и в предыдущем случае. Результаты вычислений приведены на рис. 5.

5 проектов, г=5

12 3 4

4,34

Рисунок 5 - Эластичность накопленной стоимости оптимального портфеля к банковской процентной ставке

Из рис. 5 видно, что

• эластичность накопленной стоимости оптимального портфеля к банковской ставке весьма мала и является положительной (это также естественно);

• с ростом базовой ставки эластичность в среднем возрастает; эластичность также в среднем возрастает при увеличении временного горизонта;

• устойчивой тенденции изменения эластичности при возрастании числа проектов не выявлено.

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

• ставка банковского вклада 4%;

• ставка банковского кредита 7%;

• число ЩЦ) подмножеств Ц изменялось от 2 до 5, объединение множеств Ц совпадало с множеством проектов;

• длительность проектов 4-7 лет;

• число проектов равнялось 5,10,15.

Результаты вычислений приведены на рис. 6.

Из рис. 6 видно, что

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

10 проектов

1200 -

«

2 3 4 5

Рисунок 6 - Зависимость конечного капитала инвестора ^ от числа подмножеств Ц

Основные выводы и результаты работы

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

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

2. Разработаны проблемно ориентированные эвристические численные методы и алгоритмы решения сформулированной оптимизационной задачи (модифицированный метод ветвей и границ и эволюционный алгоритм (1+1) -ЕА) [2,8,10,13].

3. Разработан комплекс программ «Формирование инвестиционного портфеля», реализующий разработанные алгоритмы и точные алгоритмы (ветвей и границ и Гомори) в среде программирования Borland Delphi 7.0 в приложении к задаче формирования портфеля, состоящего из инвестиционных проектов [4,6,13].

4. Проведены экспериментальные расчеты (всего сгенерировано 3000 случайных примеров) для оценки эффективности предложенных алгоритмов, которые показали, что эффективность модифицированного метода ветвей и границ (отношение конечной стоимости полученного портфеля к стоимости оптимального) в среднем равна 0,97, эффективность эволюционной стратегии при принятых правилах останова в среднем равна 0,88. Также установлено, что при малой размерности (для задачи портфельного анализа) при длительности проектов от 6 до 9 лет метод ветвей и границ приводит к решению в среднем на 10% быстрее, чем метод Гомори. Для задачи портфельного анализа проведен численный эксперимент, в результате которого установлены тенденции изменения эластичности накопленной стоимости оптимального портфеля к процентным ставкам в зависимости от параметров задачи

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

Также исследовано влияние на результат числа подмножеств, на которые разбито множество проектов. С ростом числа подмнохсеств накопленная стоимость оптимального портфеля в среднем падает, причем темп падения уменьшается при увеличении числа проектов. [2,3].

Публикации по теме диссертации

Публикации в рецензируемых журналах из списка ВАК

1. Формирование оптимальных портфелей, состоящих из инвестиционных проектов, с учетом групповых выплат / Е. М. Бронштейн, Г. Р. Муслимова // Информационные технологии. 2010. № 6. С. 72-75.

2. Оптимальные инвестиционные портфели с учетом групповых выплат / Е. М. Бронштейн, Г. Р. Муслимова // Труды ИСА РАН. 2011. Т. 61. № 1.

С. 75-79.

3. Оптимальные портфели инвестиционных проектов с учетом групповых платежей и взаимосвязи проектов: оценка влияния изменения параметров

модели / Е.М. Бронштейн, Г.Р. Муслимова // Аудит и финансовый анализ, 2011. №2, С. 249-252.

4. Комплекс программ «Формирование инвестиционного портфеля» / Муслимова Г.Р. // Современные проблемы науки и образования, 2011. № 4. URL: www.science-education.ru/98-4721 (дата обращения: 20.09.20! 1).

Прочие публикации

5. Задача формирования оптимального инвестиционного портфеля / Г. Р. Галиханова (Муслимова) // Актуальные проблемы в науке и технике : сб. ст. 2-й per. зимн. шк.-сем. аспирантов и молодых ученых. Уфа: УГАТУ, 2007. Т. 2. С. 38-40.

6. Формирование оптимального инвестиционного портфеля с учетом групповых затрат на финансирование проектов / Г. Р. Муслимова // Экономика, социология и гуманитарные науки: сб. ст. 3-й всерос. зимн. шк.-сем. аспирантов и молодых ученых. Уфа: УГАТУ, 2008. Т. 3. С. 89-95.

7. Задача формирования оптимального инвестиционного портфеля из инвестиционных проектов с дополнительными условиями / Г. Р. Муслимова // Системное моделирование социально - экономических процессов : матер, междунар. научи, шк.-сем. им. академика С. С. Шаталина. Воронеж: ЦЭМИ РАН, 2008. С. 174-179.

8. Решение задачи формирования оптимальных портфелей, состоящих из инвестиционных проектов, с учетом групповых выплат / Г. Р. Муслимова // Информатика, управление и компьютерные науки: сб. тр. 5-й всерос. зимн. шк.-сем. аспирантов и молодых ученых. Уфа: УГАТУ, 2010. Т. 3. С.19-23.

9. Дополнительные условия при формировании оптимальных портфелей, состоящих из инвестиционных проектов / Г. Р. Муслимова // Молодой ученый. 2010. № 6. С. 56-58.

10. Методы решения задачи формирования оптимальных инвестиционных портфелей с учетом групповых выплат / Г. Р. Муслимова // Актуальные задачи математического моделирования и информационных технологий : матер. 6-й всерос. открытой науч.-практ. конф. Сочи: СГУТиКД, 2010. С. 108-110.

11. Некоторые эвристические алгоритмы для решения задачи формирования инвестиционного портфеля / Г .Р. Муслимова // Молодой ученый. 2010. №11. С. 101-103.

12. Формирование инвестиционных портфелей с учетом групповых выплат / Е. М. Бронштейн, Г. Р. Муслимова // VI Московская междунар. конф. по исследованию операций (ORM2010): Москва, 19-23 октября 2010 года: труды. М.: МАКС Пресс, 2010. С. 47-49.

13. Свид. о гос. per. программы для ЭВМ № 2010617172. Формирование инвестиционного портфеля / Г. Р. Муслимова. М.: Роспатент, 2010.

Диссертант

Г. Р. Муслимова

МУСЛИМОВА Галия Рамилевна

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано к печати 15.11.2011. Формат 60x84 1/16. Бумага офсетная. Печать плоская. Гарнитура Times New Roman Cyr. Усл. печ. л. 1,0. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ №373.

ФГБОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К.Маркса, 12

61 12-5/823

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

УНИВЕРСИТЕТ»

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

МУСЛИМОВА Галия Рамилевна

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

Научный руководитель доктор физико-математических наук, профессор Е.М. Бронштейн

Уфа-2011

Оглавление стр.

ВВЕДЕНИЕ............................................................................................................4

ГЛАВА 1. АНАЛИЗ ИНВЕСТИЦИОННЫХ ПРОЕКТОВ...............................9

1.1. Инвестиционные проекты. Основные понятия.............................................9

1.2 Виды отношений между инвестиционными проектами.............................22

1.3 Анализ известных подходов к задаче формирования инвестиционного портфеля.................................................................................................................33

1.4 Постановка задачи - цели и задачи исследования.......................................37

Выводы по главе 1.................................................................................................38

ГЛАВА 2. РЕШЕНИЕ ЗАДАЧИ ФОРМИРОВАНИЯ ПОРТФЕЛЯ НА ОСНОВЕ ЧИСЛЕННЫХ МЕТОДОВ...............................................................40

2.1 Математическая модель и постановка задачи..............................................40

2.2 Точные алгоритмы решения задачи формирования оптимального инвестиционного портфеля проектов..................................................................49

2.3 Модифицированный метод «ветвей и границ»............................................58

2.4 Эволюционный алгоритм (1+1)-ЕА...............................................................62

Выводы по главе 2.................................................................................................68

ГЛАВА 3. РАЗРАБОТКА ПРОТОТИПА КОМПЛЕКСА ПРОГРАММ ДЛЯ ФОРМИРОВАНИЯ ОПТИМАЛЬНОГО ИНВЕСТИЦИОННОГО ПОРТФЕЛЯ ПРОЕКТОВ....................................................................................70

3.1 Разработка архитектуры программного комплекса.....................................70

3.2 Разработка прототипа программного комплекса для формирования оптимального инвестиционного портфеля проектов.........................................79

3.3 Структура прототипа программного комплекса..........................................86

3.4 Описание пользовательского интерфейса комплекса программ................95

Выводы по главе 3...............................................................................................101

ГЛАВА 4. СРАВНИТЕЛЬНАЯ ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМОВ..................................................................................................103

4.1 Условия вычислительного эксперимента...................................................103

4.2 Сравнительный анализ эффективности алгоритмов..................................108

4.3 Анализ чувствительности накопленной стоимости оптимального портфеля...............................................................................................................113

4.4 Пример работы предложенных эвристических алгоритмов.....................119

Выводы по главе 4...............................................................................................132

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.........................................136

ВВЕДЕНИЕ

Актуальность темы

Управление проектами различной природы в силу важности привлекает исследователей, представляющих различные области знаний. Международным институтом Управления Проектами (PMI) разработана база знаний по эффективному управлению проектами (Project Management Body of Knowledge) которая интегрирует профессиональные знания по управлению проектами и является международно-признанным стандартом (IEEE, ANSI).

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

Рациональное инвестирование средств является важной задачей, стоящей перед инвесторами. Она важна как для инвесторов, так и для народного хозяйства в целом. Исследование инвестиционных проектов начато в работах И. Фишера, Д. Кейнса. Задачи формирования оптимальных (в том или ином смысле) портфелей из инвестиционных проектов рассматривались Дж. Лори, Л. Сэведж, М. Вейнгартнером, Дж. Хиршлейфером, П. Л. Виленским, В. Н. Лившицем, С. А. Смоляком, В. 3. Беленьким, С. И. Спиваком, Е. М. Бронштейном и рядом других исследователей. В работах М. Балинского, А. Шогана, Дж. Мамера рассмотрены задачи формирования портфелей инвестиционных проектов, если по некоторым семействам проектов предусмотрены групповые выплаты, подобные задачи возникают на практике довольно часто (приобретение спецтранспорта, офисных помещений в местах реализации проектов и др.). При этом не рассматривались ситуации, когда по семействам проектов возможны не только платежи инвестора, но и поступления средств (например, сдача помещений в аренду), не учитывались также возможность заимствования средств (на начальном этапе это может оказаться

целесообразно) и возможная взаимозависимость проектов. Подобные ситуации возникают на практике, в то же время, подобные задачи исследованы недостаточно. Эти обстоятельства являются обоснованием актуальности темы диссертации.

Цель работы и задачи исследования

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

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

2. Разработка эвристических алгоритмов решения поставленной оптимизационной задачи.

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

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

Основные результаты, выносимые на защиту:

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

соотношений, сведение задачи оптимального выбора к задаче частично целочисленного линейного программирования (п. 1 Паспорта специальности 05.13.18).

2. Проблемно ориентированные эвристические численные методы и алгоритмы решения задачи формирования оптимальных инвестиционных портфелей с учетом групповых выплат и взаимосвязи проектов (модифицированный метод ветвей и границ и эволюционный алгоритм (1+1)-ЕА), (п. 3 Паспорта специальности 05.13.18).

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

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

Научная новизна

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

2. Разработаны эвристические алгоритмы решения сформулированной оптимизационной задачи, учитывающие ее специальную структуру (модифицированный метод ветвей и границ, эволюционный алгоритм класса (1+1) - ЕА).

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

4. Установлено, что эффективность предложенных эвристических алгоритмов близка к эффективности точных алгоритмов, при этом для задач малой размерности при сравнении точных алгоритмов выигрывает метод Гомори, для задач большей размерности - метод ветвей и границ. Также установлено, что значение целевой функции нечувствительно к изменению процентных ставок (эластичность является малой), т.е при формировании портфелей из инвестиционных проектов риском процентной ставки можно пренебречь. Это установлено на основе вычислительного эксперимента.

Практическая значимость и внедрение результатов

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

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

- моделирование исходных данных при различных условиях;

Исследования проводились при поддержке РФФИ «Интегрированная

портфельная теория» (проект 07-06-00021) и «Асимметричные и комплексные меры риска и их применение при формировании портфелей ценных бумаг» (проект 10-06-00001).

Разработанные алгоритмы и прототип программного обеспечения используются в ОАО «Инвестиционное агентство», что зафиксировано в

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

Апробация работы

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

• на второй, третьей и пятой всероссийских зимних школах-семинарах аспирантов и молодых ученых (Уфа, 2007, 2008, 2010);

• на Международной научной школе-семинаре имени академика С. С. Шаталина (Воронеж, 2008);

_ V ТЧ ^ и и

• на шестой Всероссийской открытой научно - практической конференции «Актуальные задачи математического моделирования и информационных технологий» (Сочи, 2010),

• на VI Московской международной конференции по исследованию операций (ОЯМ2010) (Москва, 2010).

Публикации

Основные материалы диссертационной работы опубликованы в 13 научных трудах, в том числе 4 статьи в изданиях, рекомендованных ВАК РФ, 8 в других изданиях и 1 свидетельство о регистрации программного продукта.

Структура работы

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

ГЛАВА 1. АНАЛИЗ ИНВЕСТИЦИОННЫХ ПРОЕКТОВ.

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

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

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

1.1. Инвестиционные проекты. Основные понятия.

Потоки платежей

Инвестиционные проекты зачастую характеризуются не разовой выплатой, а целой цепочкой платежей. Описать эту ситуацию можно следующим образом. Пусть ^^ <...<!;„ - некоторые моменты времени, а Со, Сь...,Сп - суммы выплат или поступлений средств в соответствующие моменты времени. Таким образом, величины бывают как

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

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

привести их к одному моменту при некоторой процентной ставке I

Отнесение их к моменту времени Т дает значение ^С, [, Т) 3

м

1,-Т

, где

г дисконтныи множитель.

1 +1

Т -Т

Очевидна формула ^С, Т])= ^С, 1, Т2) у 1 2.

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

Чаще всего за значение момента Т принимается начальный момент времени. При Т=0 величина 1"(С, 0) будет называться дисконтированной или текущей стоимостью потока. Также применяется момент последней выплаты. Соответствующая величина называется накопленной стоимостью потока.

Выделяют три вида потоков платежей: инвестиционные проекты, аннуитеты, кредитные потоки.

В том случае, если моменты платежей ^ расположены очень часто, то поток платежей можно считать непрерывным. При этом допустим, что сила процента 8(1) зависит от времени.

Пусть поступление средств за промежуток [1,1+АЦ равно Б(1;)Л1;,

где Р(1:) - интенсивность поступления средств, аналог мгновенной

скорости. Дисконтированная сумма, поступившая за промежуток [Ц+Д1;]

!

приблизительно равна Р(1:)Л1>у(1:)= 0 ^ ■ Коэффициент

дисконтирования у(1)= 1/А. Отсюда следует, что дисконтированная сумма выплат за промежуток [0,п] равна

/=]>(*>• Л [30].

о

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

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

• первая ненулевая компонента С отрицательная. Это означает, что в начальный момент времени инвестор вкладывает средства в проект, т.е. осуществляет платеж по проекту.

• последняя ненулевая компонента С положительная. Это означает, что инвестору выплачиваются средства в конечный момент времени.

п

• >0 Суть данного неравенства заключается в том, что

1=0

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

Предположим, что инвестор вкладывает свободные средства в банк, эффективная процентная ставка 1 в котором предполагается постоянной за все время исполнения инвестиционного проекта.

п

Величина f(C, i, Т)= ^ СjVT J является доходом по проекту С,

7=1

причисленным к моменту Т.

Чаще всего рассматривается величина f(C, i, 0), т.е. проект дисконтируют к началу выплат. Для инвестиционных проектов величина f(C, i, 0) называется чистым приведенным доходом и обозначается NPV(C,i) (от английского Net Present Value). Заметим, что NPV(C,i) является многочленом от v=l/(l+i). Поскольку i>0, то ve(0,l]. Из непрерывности многочлена следует, что функцию NPV можно продолжить на отрезок [0,1], приняв за значение в 0 соответствующее предельное значение.

Из свойств инвестиционного проекта следует, что NPV(C,oo)<0 (при v=0) и NPV(C,1)>0 (при у =1). Из непрерывности многочлена следует, что при некоторой процентной ставке i* справедливо равенство

NVP(C, i>0. (1)

Уравнение (1) относительно переменной i называется характеристическим уравнением или уравнением доходности проекта С. Известно, что многочлен может иметь более одного корня. Если характеристическое уравнение имеет единственный корень, то он называется эффективной процентной ставкой или внутренней нормой доходности инвестиционного проекта. Эта величина обозначается IRR (от английского Internal Rate of Return). Смысл этой величины в том, что если банковская процентная ставка равна эффективной процентной ставке, то этот проект для инвестора не дает никакой прибыли. Если уравнение (1) имеет более одного корня, то значение IRR не определено. Вычисление эффективной процентной ста