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

07-2 3746

ч

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

"■у.

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

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

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

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

Уфа 2007

дореформенного уровня 1990-го года. Несмотря на то, что в 2005 году РФ стала крупнейшим получателем иностранных инвестиций в Юго-Восточной Европе и СНГ, получив 26 млрд. долл. из 50 млрд. долл., вложенных в регион (по данным ЮНКСТАД), она по-прежнему значительно отстаёт от мировых лидеров -Китая (60,3 млрд. долл. инвестиций в 2005 г.), США (106 млрд. долл.) и Великобритании (219 млрд. долл.).

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

Всё больше различных научных коллективов в России и за рубежом занимаются вопросами повышения эффективности инвестиционной деятельности, управления проектами и теорией календарного планирования (C.B. Севастьянов, И.В. Буркова, В-Н. Бурков, В.Н. Лившиц, П.Л. Виленский, С.А. Смоляк, Э.Х. Гимади, C.N. Potts, D.B. Shmoys, К. Jansen, J.K. Lenstra).

Актуальность данной темы исследования подтверждается также тем, что в «Приоритетные направления развития науки, технологий и техники в Российской Федерации», утверждённым Президиумом РАН РФ, включены темы: «1.1.7. Математическое моделирование», «7.2.6. Анализ нестационарных динамических макроэкономических процессов. Теория и методы экономико-математического моделирования».

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

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

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

2. Произвести сравнение и выбор критериев оценки эффективности инвестиционного проекта.

3. Разработать алгоритмы решения поставленной задачи.

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

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

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

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

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

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

3. Обоснование NP-трудности поставленной задачи, основанное на интерпретации задачи с точки зрения теории графов, и двухэтапный алгоритм её решения, сочетающий численные методы «первого подходящего» и «ветвей и границ».

4. Программное обеспечение, реализующее предлагаемый алгоритм.

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

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

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

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

3. Предложен алгоритм решения поставленной задачи, который совмещает два наиболее распространённых подхода к решению NP-полных задач. При этом с помощью метода «первого подходящего» (First Fit), удаётся получить эффективную оценку сверху в качестве входящих данных метода «ветвей и границ» (Branch-Bound). Особенностью поставленной задачи является то, что алгоритмы типа «первый подходящий» не обеспечивают оптимума ни при каком исходном упорядочивании проектов.

4. Вычислительный эксперимент позволил выделить наилучший приоритетный список из трёх рассмотренных. Показано, что ранжирование по убыванию модифицированного показателя рентабельности (Rent) является лучшим для алгоритма «первого подходящего» (First Fit).

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

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

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

Исследования проводились в рамках гранта РФФИ 04-06-80009 «Математическое моделирование инвестиционных проектов в реальных экономических условиях» (2004-2006 гг.).

Разработанные алгоритм и программное обеспечение внедрены в компании «Бисот».

Апробация работы. Основные положения и результаты работы докладывались на: Всероссийской молодёжной научно-технической конференции «Интеллектуальные системы управления и обработки информации» (УГАТУ, 2003); V Всероссийском симпозиуме по прикладной и промышленной математике (Санкт-Петербург, 2-8 мая 2005); Зимней школе-семинаре аспирантов УГАТУ, (Уфа, 2006); VII Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2-8 мая 2006); 18-ой международной конференции по системным исследованиям, информатике и кибернетике (Баден-Баден, 2006); 8-я Международной конференции "Компьютерные науки и информационные технологии" С81Т2006 (Карлсруэ, Германия); Башкирско-Германском форуме молодых экономистов (Уфа-2006); Международной школе-семинаре имени академика С.Шаталина «Системное моделирование социально-экономических процессов» (Воронеж, 9-13 октября 2006); Международной научно-практической конференции «Разработка оценки эффективности и реализация инвестиционных и инновационных проектов» (Ташкент, 14—16 ноября 2006).

Публикации. Основные материалы диссертационной работы опубликованы в 11 научных трудах, в том числе 4 статьи в изданиях, рекомендованных ВАК, и статьи в 4 международных и 4 российских научных изданиях.

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

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

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

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

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

■ задача мастера - задана для одного обслуживающего прибора;

■ задача Джонсона - класс задач с двумя обслуживающими приборами;

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

■ задачи ресурсного планирования комплексов работ;

■ общая модель многостадийной обслуживающей системы (C.B. Севастьянов):

- система открытого типа (общий случай задачи open shop);

- задача job shop;

- задача flow shop.

Анализ перечисленных моделей выявил три наиболее существенных отличия задач оптимизации сроков инвестирования от традиционных задач календарного планирования:

1. Отсутствие составляющей, аналогичной понятию «машины». Количество проектов, которые одновременно может профинансировать инвестор, определяется не неким фиксированным числом «машин», а сочетанием средств, которыми располагает инвестор, и средств, которые требуются для финансирования рассматриваемых проектов. Это сочетание не является статичным и принимает свои значения для каждого сочетания располагаемых в данный момент средств инвестора и финансируемых проектов.

2. Изменяемость «работ». Инфляция оказывает важное влияние на экономическую ситуацию в стране, поэтому необходимо делать пересчёт проектов в соответствии с неким инфляционным коэффициентом. Традиционная же модель теории расписаний не предусматривает изменения ресурсной составляющей рассматриваемых работ.

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

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

Во второй главе предлагается новый подход к моделированию инвестиционного процесса, описываются интегральные характеристики инвестиционного проекта, приводится постановка задачи календарного планирования, её

интерпретация с точки зрения теории графоЕ, также сделан анализ сложности поставленной задачи.

Основные понятия

В предлагаемой модели время принимает дискретные значения 0,1,2,.... Предусматривается возможность вложения в банк как альтернативного использования средств, через /' обозначена банковская процентная ставка.

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

Значения i, г могут меняться от года к году; в данной работе эти параметры предполагаются постоянными, в то же время, описанные алгоритмы применимы и в общем случае.

Под инвестиционным проектом (потоком платежей) понимается вектор C=(cq,C|,произвольной размерности, обладающий следующими свойствами: первая ненулевая компонента С отрицательная, последняя ненулевая ком-

i

понента С и сумма компонент ^с, положительные, здесь / — длительность про-

i=0

екта. Значение с, есть размер выплаты в момент i (далее считаем, что это начало года). Если с,>0, то средства поступают инвестору, если с,<0, то инвестор средства в проект вкладывает.

Характеристики проектов

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

В работе используются следующие характеристики проектов:

/

- NPV(C,i) = * (1 + i)~* - «чистый приведенный доход» проекта (Net

к-0

Present Value), то есть дисконтированная суммарная прибыль по проекту;

ч

- MM(C,i) = -minУ\ск *(1 +0 * - минимум средств, необходимых для

' ts

финансирования проекта;

- R{C,i)= _ модлфщдлровадщдй индекс рентабельности,

MM(C,i)

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

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

Проекты могут иметь ограничения по сроку начала финансирования: С/„ V,- натуральные числа, характеризующие соответственно минимально и максимально возможную даты начала финансирования.

Предполагается, что отобрано несколько проектов (портфель) Cj=(cjx), Cj\,...), где j= 1,..., т - номер проекта в портфеле, а с,- г'-ая выплата по j-ому проекту.

Пусть связь между сроками начал финансирования двух проектов выражается так - «финансирование проекта А может быть начато не ранее, чем через к лет после начала финансирования проекта В». Обозначим через кЬа - временной лат, связывающий указанные проекты.

Пусть tj - время начала финансирования проекта С,. Из ограничений задачи следует, что

£/,</, (1)

Связи между проектами С, и С, будут выражены следующим образом

l,+ktj<tr (2)

Общее время финансирования всего портфеля равно

Г = шах{г +lj). (3)

Через F. 1 обозначен начальный капитал инвестора, F.t>Q.

В каждый момент времени средства инвестора складываются из накопленного в банке остатка от предшествующего инвестиционного процесса и текущих выплат по проектам. Если Fh - средства на счете инвестора в момент времени h, то до платежей по проектам капитал инвестора равен (1 +i)*F),.l.

Пусть Рк = {_/: tJ < h < tj, + lj | - множество проектов, финансируемых в

момент времени h Платеж по проекту j, осуществляемый в момент И, равен Cj h_4 . Поскольку стоимость денег (а, соответственно, и проектов) меняется со

временем, то осуществляется коррекция проектов в соответствии с темпом инфляции. Платеж, с учетом влияния инфляции, будет равен * (1 + г)'1.

Задача выглядит следующим образом: требуется каждому проекту С, поставить в соответствие такое время его начала tj, удовлетворяющее ограничениям (1) и (2), чтобы в любой момент времени выполнялось условие неразорения : Fh=(l + i)Fh_l + J]cjA_,:(\ + r)''>0 (4)

№i

при А=0,1,...,Г, а время финансирования всего портфеля было минимально, т.е.

Г-)-min. (5)

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

Интерпретация задачи с точки зрения теории графов

Совокупность проектов может быть удобно представлена в виде взвешенного ориентированного ациклического графа, вершинами которого являются проекты, наличие дуги (Q.C,) означает, что проект С, должен начинаться после проекта С., вес дуги равен соответствующем}' временному лагу ку. Назовём

истоком вершину, имеющую только исходящие дуги. Будем считать, что вершины занумерованы таким образом, что наличие дуги (С„ Су) означает, что ;</. Такая нумерация вершин в подобных графах всегда существует.

В случае, если все проекты в портфеле связаны друг с другом, можно этот портфель представить в виду мульти-проекта (рисунок 2). Если начало финансирования проекта С„ не зависит от срока начала проекта С,, то будем говорить,

Рисунок 2. Мульти-проект, представленный в виде графа

Каждая вершина С, имеет пометку Р1 - минимально возможное время начала его финансирования. Для проекта (вершины), принятого к финансированию, Пометка вершины (проекта) Р, обладает следующими свойствами:

1)/}>0; 2) Р, е[£/,.,

3 )/>>/>+*,,/<;

При изменении пометки любой вершины производится пересчёт пометок всех вершин-наследников.

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

тах {/; + /,} ->тш (6)

при выполнении условия (4).

Анализ сложности

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

Пусть в рассматриваемой экономике нулевая инфляция, все проекты состоят из одного, единичного платежа, инвестор располагает средствами, достаточными для финансирования всех проектов, и нет ограничений на срок начала финансирования проекта, то есть г=0, , >т, С,=(- \), £/, = 0, К —» а>, г=1,2

Если начало финансирования проекта С(, не зависит от срока начала проекта Су, то будем говорить, что к^=ку=0.

В этом случае, задача (4), (6) может быть сформулирована в виде следующей задачи распознавания.

Задача 1

Условие: Дан граф G=(C, К), в котором С - множество вершин (проектов), К- множество дуг, соединяющих эти вершины, и Q - некая оценка длительности финансирования портфеля.

Вопрос: Верно ли, что G содержит гамильтонов путь такой, что шах{^+/,}<£?

Задача 1 является NP-полной. Поскольку она является частным случаем поставленной задачи, то вся массовая задача (4), (6) является NP-трудной.

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

Практическая необходимость решения NP-трудных задач привела к возникновению и развитию таких направлений исследования как:

— методы сокращения перебора вариантов при отыскании точного решения задачи (методы типа «ветви и границы»);

— нетрудоёмкие алгоритмы нахождения приближённого решения (куда, например, относятся различные «жадные» алгоритмы), - без каких-либо гарантий качества получаемых решений;

— алгоритмы полиномиальной трудоёмкости для нахождения приближённого решения с гарантированными оценками качества.

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

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

Можно привести наглядный пример. Пусть даны два проекта (-10;-10;20;-10;23) и (-10; 10;-20; 10;20). Процентная ставка 10%, темп инфляции 5%, начальный капитал 18. При упорядочении (1,2) время начала первого проекта равно 1, а время начала второго проекта 4, а при упорядочении (2,1) -время начала второго проекта равно 0, а первого 4. Т.е. в обоих случаях время реализации портфеля равно 9 годам. В то же время, оба проекта можно начать в момент 3, тогда общее время реализации портфеля составит 8 лет.

Поэтому для решения задачи (1)-(5) был разработан подход, сочетающий в себе два популярных направления исследования практических решений NP-

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

1. Проекты упорядочиваются по одной из характеристик: NPV, ММ, R, далее к ним применяется принцип «первый подходящий» (First Fit);

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

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

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

11 вычислительный эксперимент І'ЇМ ■Е mm Оэй§

Ввод данных Промежуточные результаты | Статистика 1

Проекты: Начальный капитал: i81 Характеристики: 1

Плотеж\Гад 0 1 I2 |Э |4 |Б , NPV jRent

1 -36 -25 18 16 74 49 м В 118.73 24.1

г ;-4Э -11 18 -3 -37 45 17.61 65.65 26.83

3 -29 -77 -A3 95 16 62 36.06 139.5 25.85

4 -42 -62 15 93 21 -76 11.86 116,55 10.18

5 -26 27 84 -10D -66 34 7.25 52.24 13.88

6 -90 51 -20 55 -26 82 18.83 90 20,92

І7 1 < -Я1 кк як -47 -41 Расписания: -R У. > 12.87 81 15.88

Плате*ЛАлг. nn(NFV) |ПП(ММ) |nn(Rent) |ВиГр -

Длина йШшІШ §¡¡¡21 22 20 —

1 13 14 13 7

г 0 2 0 13

3 9 9 9 12

4 15 7 1В 10

5 2 0 2 12

6 Є 13 6 2

7 4 1 4 8

Рисунок 3. Экранная форма программы

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

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

• длина проектов — 8 лет;

• количество проектов в портфеле - 8;

• процентная ставка -0,1;

• темп инфляции - 0,08;

• начальный капитал - 200;

• границы выплат-(-100; 100).

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

Таблица 1.

Первоначальная Первоначальная Первоначальная

сортировка по сортировка по сортировка по R

NPV ММ

1 этап

(алгоритм первого

подходящего) 1.14 1,10 1,08

2 этап (алгоритм

ветвей и границ) 1,04 1,04 1,04

Точное решение 1 1 1

За единицу в этой таблице принято оптимальное значение целевой функции.

Таблица 2.

Среднее время работы алгоритма

1 этап 0,03 сек.

2 этап 45 сек.

Точное решение 14 мин.

Видно, что предлагаемый алгоритм даёт решение, близкое к оптимальному, при значительной экономии вычислительных ресурсов.

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

В частности рассматривались портфели из 5-20 случайных проектов с длительностью 10 лет каждый и портфели из 10 проектов с длительностью от 5 до 20 года. В каждом случае проводилось 250 экспериментов. Сравнивались как значения целевой функции, так и время вычислений. Приведем соответствующие результаты.

Результаты исследования зависимости качества решения, предлагаемого алгоритмом «первый подходящий», от исходной сортировки сведены в график 1. Число проектов в портфеле фиксировано - 10, длительность проекта меняет-

График 1.

Зависимость от исходной сортировки

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Длительность проекта

На графике 2 приведено исследования для фиксированной длительности проекта. Все проекты длятся 10 лет. Количество проектов в портфеле меняется.

График 2.

Зависимость от исходной сортировки

5 6 7 Є 9 10 11 12 13 14 15 16 17 18 19 20 Количество проектов в поріфепе

На графике 3 приведена зависимость времени решения задачи методом «первый подходящий» при начальной сортировке rio Rent от её начальной размерности. По очереди фиксировались длительность проекта и количество проектов в портфеле на уровне 10. Значение второго параметра менялось соответственно от 5 до 20.

График 3.

Влияние начальной размерности на время решения

140

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Значение аргумента

В таблицах 3 и 4 приведены время и результаты решения задачи методом «первый подходящий» (при разных начальных сортировках) и методом ветвей и границ.

Таблица 3. Результат, получаемый при фиксированной длительности проекта (5 лет). _______

Количество проектов в портфеле Результат решения (NPV) Результат решения L(MM)__ Результат решения (Rent) Результат решения (метод ветвей и границ)

5 проектов 13,644 14,376 13,76 10,832

6 проектов 16,044 16,732 16,188 13,324

7 проектов 17,188 17,724 17,208 15,14

8 проектов 18,344 19,308 18,536 15,444

9 проектов 20,8 21,6 20,6 18,6

Под результатом решения здесь понимается средняя длина получаемого портфеля.

Таблица 4. Время работы алгоритма, получаемое при фиксированной длительности проекта (5 лет), мс.___________

Время ре-

Количество шения (ме-

проектов в Время реше- Время реше- Время реше- тод ветвей и

портфеле ния (ЫРУ) ния (ММ) ния (Яет) границ)

5 проектов 1,6 2,86 1,736 35,068

6 проектов 2,336 3,624 3,144 268,388

7 проектов 4,372 4,168 3,944 1801,344

8 проектов 6,248 6,08 6,516 5950,612

9 проектов 9 5,8 9,6 37083,6

На основе проведённых вычислительных экспериментов были сделаны следующие выводы:

1. Как правило, предпочтительнее использовать первоначальную сортировку по модифицированному индексу рентабельности (таблица 1).

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

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

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

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

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

3. Проведен анализ сложности поставленной задачи. С помощью интерпретации задачи с точки зрения теории графов, установлена её МР- груд-

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

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

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

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

Публикации в изданиях, рекомендуемых ВАК

1. Одна задача календарного планирования процесса инвестиций / Е.М. Бронштейн, Т.Н. Олейник // Обозрение прикладной и промышленной математики. 2005. Т. 12, № 1. С. 112.

2. Оптимизация графика финансирования инвестиционных проектов / Т.Н. Олейник // Обозрение прикладной и промышленной математики. 2006. Т. 13, № 4. С. 693-694.

3. Об одной задаче календарного планирования / Т.Н. Олейник // Вестник УГАТУ : науч. журн. Уфимск. гос. авиац. техн. ун-та. 2006. Т.8, №2(18). С. 64-66.

4. Задача календарного планирования портфеля инвестиционных проектов / Е.М. Бронштейн, Т.Н. Олейник // Информационные технологии. 2007. №3. С. 70-73.

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

5. Задача финансирования ряда проектов с нефиксированным сроком их начала за минимальное время / Т.Н. Олейник // Интеллектуальные системы управления и обработки информации : матер, всерос. молодёжи, науч.-техн. конф. Уфа : УГАТУ, 2003. С. 119.

6. Некоторые оптимизационные задачи теории инвестиций / Е.М. Бронштейн, Т.Н. Олейник, Г.З. Латыпова // 18-я междунар. конф. по сис-

темным исследованиям, информатике и кибернетике : матер, конф. Загреб, 2006. С. 18-21. Статья на англ. яз.

7. Задача календарного планирования портфеля инвестиционных проектов / Т.Н. Олейник // Интеллектуальные системы обработки информации и управления : сб. статей per. зимн. шк.-сем. аспирантов и молодых учёных. Уфа, 2006. Т. 1.С. 131-135.

8. Дискретная задача формирования оптимального расписания финансирования портфеля инвестиционных проектов / Т.Н. Олейник // CSIT'2006. 8-я междунар. конф. по информатике и информационным технологиям : сб. статей. Карлсруэ, Германия, 2006. Т. 2. С. 35-37. Статья на англ. яз.

9. Оптимальное календарное планирование финансирования инвестиционных проектов / Т.Н. Олейник // «Круглый стол» по информационным технологиям и математическим методам исследований в экономике : сб. статей. Уфа, 2006. С. 129-135. Статья на англ. яз.

10. Задача календарного планирования портфеля инвестиционных проектов / Т.Н. Олейник // Системное моделирование социально-экономических процессов : матер, междунар. шк.-сем. им. акад. С. Шаталина. ЦЭМИ РАН, 2006. С. 63-69.

11. Оптимальные календарные графики инвестиций / Е.М. Бронштейн, Т.Н. Олейник // Разработка оценки эффективности и реализация инвестиционных и инновационных проектов : матер, междунар. науч.-пракг. конф. Ташкент, 2006. С. 99-100.

Диссертант

Т.Н. Олейник

Олейник Татьяна Николаевна

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

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

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

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

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

1 -79 84

2006394958

2006394958

Введение.

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

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

1 глава.

1.1 Задачи теории расписаний.

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

1.1.2. Задачи теории расписаний в общей постановке.

1.1.3 Задача Джонсона и графики Ганта.

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

1.1.5 Общая модель обслуживающих систем.

1.1.6 Анализ соответствия приведённых моделей и описанной проблемы.

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

1.3 Методы решения задач дискретной оптимизации.

1.3.1. Перестановочный прием в задачах теории расписаний.

1.3.2. Приближенные и эвристические методы.

1.3.3 Метод ветвей и границ.

1.3.4 Сетевые модели. Расчет временных характеристик сетевых моделей

1.3.5 Потоки в сетях. Теорема Форда-Фалкерсона о максимальном потокебЗ

2 глава.

2.1.1. Определение инвестиционного проекта.

2.1.2 Методы оценки эффективности инвестиционных проектов.

2.2 Постановка задачи.

2.2.1 Общая постановка задачи.

2.2.2 Интерпретация задачи с точки зрения теории графов.

2.3 Анализ поставленной задачи.

3 глава.

3.1 Предлагаемый алгоритм решения.

3.2 Реализация алгоритма.

3.3 Вычислительный эксперимент.

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

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

В декабре 1999 г., В.Путин заявил, что при реализации стратегии экономического роста «на первое место . следует поставить повышение инвестиционной активности» [107]. За прошедшие 6 лет, многое было сделано для выполнения задачи, обозначенной как государственный приоритет.

В сентябре 2006 г., международное рейтинговое агентство Standard & Poor's, которое считается самым консервативным в вопросе повышения рейтингов, повысило инвестиционный рейтинг России, отреагировав таким образом на выплату Россией долга Парижскому клубу кредиторов, а также на растущие показатели золотовалютных резервов и улучшение показателей бюджета [85].

S&P было последним из «тройки» (Moody's, Fitch и Standard & Poor's) рейтинговым агентством, присвоившим России первую рейтинговую ступень в инвестиционной зоне. Произошло это 31 января 2005 г. и стало мощным толчком к росту фондового рынка во 2-й половине 2005 и начале 2006 гг [87]. После этого было несколько повышений рейтингов уже в инвестиционной зоне всеми тремя агентствами [84].

Теперь Российская Федерация входит в перечень стран, перспективных с точки зрения инвестиций, по типу того, что предоставляет международный инвестиционный банк «Lehman Brothers Aggregate», документация которого используется инвестирующими организациями в качестве основания для принятия решения [51].

Инвестиции в экономику РФ (по данным ГосКомСтатРФ)

140

120

100

60

80 Инв. в осн. кап (в % к пред. году)

-■—Инв. в осн. кап (в % к 1990 г.)

Иностр. Инв. ($ млрд.)

40

20 0

CNrOTj-iniDt^COCOOT-CNICOTf 0)0>£Т>00)00)0)0)00000 ОЭООСЭООЭОЭООЭООООО т-ч-^-т-т-т-т-т-т-С^СЧСМСМСМ

Рисунок 1. Инвестиции в экономику Российской Федерации (по данным ГосКомСтата РФ).

Однако, несмотря на явные улучшения инвестиционного климата России, из рисунка 1 видно, что инвестиции в основной капитал ещё далеко не достигли дореформенного уровня 1990-ого года. И несмотря на то, что в 2005 году РФ стала крупнейшим получателем иностранных инвестиций в Юго-Восточной Европе и СНГ, получив $ 26 млрд. из $ 50 млрд., вложенных в регион (по данным ЮНКСТАД), она по-прежнему значительно отстаёт от мировых лидеров - Китая ($ 60,3 млрд. инвестиций в 2005 г.), США ($ 106 млрд.) и Великобритании ($219 млрд.).

Поэтому всё больше различных научных коллективов в России и за рубежом занимаются вопросами повышения эффективности инвестиционной деятельности, управления проектами и, к тому же, теорией календарного планирования (Севастьянов С.В., Буркова И.В, Бурков В.Н., Лившиц В.Н., Виленский П.Л., Смоляк С.А., Гимади Э.Х., Potts C.N., Shmoys D.B., Jansen К, Lenstra J.К.).

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

Всё больше различных научных коллективов в России и за рубежом занимаются вопросами повышения эффективности инвестиционной деятельности, управления проектами и теорией календарного планирования (С.В. Севастьянов, И.В. Буркова, В.Н. Бурков, В.Н. Лившиц, П.Л. Виленский, С.А. Смоляк, Э.Х. Гимади, C.N. Potts, D.B. Shmoys, К. Jansen, J.K. Lenstra).

Актуальность данной темы исследования подтверждается также тем, что в «Приоритетные направления развития науки, технологий и техники в Российской Федерации», утверждённым Президиумом РАН РФ, включены темы: «1.1.7. Математическое моделирование», «7.2.6. Анализ нестационарных динамических макроэкономических процессов. Теория и методы экономико-математического моделирования».

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

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

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

2. Произвести сравнение и выбор критериев оценки эффективности инвестиционного проекта.

3. Разработать алгоритмы решения поставленной задачи.

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

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

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

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

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

3. Обоснование NP-трудности поставленной задачи, основанное на интерпретации задачи с точки зрения теории графов, и двухэтапный алгоритм её решения, сочетающий численные методы «первого подходящего» и «ветвей и границ».

4. Программное обеспечение, реализующее предлагаемый алгоритм.

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

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

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

Исследования проводились в рамках гранта РФФИ 04-06-80009 «Математическое моделирование инвестиционных проектов в реальных экономических условиях» (2004-2006 гг.).

Разработанные алгоритм и программное обеспечение внедрены в компании «Бисот».

Апробация работы. Основные положения и результаты работы докладывались на: Всероссийской молодёжной научно-технической конференции «Интеллектуальные системы управления и обработки информации» (УГАТУ, 2003); V Всероссийском симпозиуме по прикладной и промышленной математике (Санкт-Петербург, 2-8 мая 2005); Зимней школе-семинаре аспирантов УГАТУ, (Уфа, 2006); VII Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2-8 мая 2006); 18-ой международной конференции по системным исследованиям, информатике и кибернетике (Баден-Баден, 2006); 8-я Международной конференции "Компьютерные науки и информационные технологии" CSIT'2006 (Карлсруэ, Германия); Башкирско-Германском форуме молодых экономистов (Уфа-2006); Международной школе-семинаре имени академика С.Шаталина «Системное моделирование социально-экономических процессов» (Воронеж, 9-13 октября 2006); Международной научно-практической конференции «Разработка оценки эффективности и реализация инвестиционных и инновационных проектов» (Ташкент, 14-16 ноября 2006).

Публикации. Основные материалы диссертационной работы опубликованы в 11 научных трудах, в том числе 4 статьи в изданиях, рекомендованных ВАК, и статьи в 4 международных и 4 российских научных изданиях.

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

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

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

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

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

- система открытого типа (общий случай задачи open shop);

- задача job shop;

- задача flow shop.

Анализ перечисленных моделей выявил три наиболее существенных отличия задач оптимизации сроков инвестирования от традиционных задач календарного планирования:

1. Отсутствие составляющей, аналогичной понятию «машины». Количество проектов, которые одновременно может профинансировать инвестор, определяется не неким фиксированным числом «машин», а сочетанием средств, которыми располагает инвестор, и средств, которые требуются для финансирования рассматриваемых проектов. Это сочетание не является статичным и принимает свои значения для каждого сочетания располагаемых в данный момент средств инвестора и финансируемых проектов.

2. Изменяемость «работ». Инфляция оказывает важное влияние на экономическую ситуацию в стране, поэтому необходимо делать пересчёт проектов в соответствии с неким инфляционным коэффициентом. Традиционная же модель теории расписаний не предусматривает изменения ресурсной составляющей рассматриваемых работ.

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

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

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

Основные понятия

В предлагаемой модели время принимает дискретные значения 0,1,2,.

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

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

Значения /, г могут меняться от года к году; в данной работе эти параметры предполагаются постоянными, в то же время, описанные алгоритмы применимы и в общем случае.

Под инвестиционным проектом (потоком платежей) понимается вектор

С=(с0,с|,.,с/) произвольной размерности, обладающий следующими свойствами: первая ненулевая компонента С отрицательная, последняя ненулевая компонента С и сумма компонент ^^положительные, здесь / о длительность проекта. Значение с,- есть размер выплаты в момент i (далее считаем, что это начало года). Если cf>0, то средства поступают инвестору, если Cj<0, то инвестор средства в проект вкладывает.

Характеристики проектов

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

В работе используются следующие характеристики проектов: /

- NPV(C,i) = *(1 + i)~k - «чистый приведенный доход» проекта (Net к=0

Present Value), то есть дисконтированная суммарная прибыль по проекту;

- MM(C,i) = -m'm'YJck *(\ + i)~k - минимум средств, необходимых для q к-о финансирования проекта;

- R(C,i)= МОдИфИцИрованный индекс рентабельности, смысл

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

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

Проекты могут иметь ограничения по сроку начала финансирования: £/,-, V,-натуральные числа, характеризующие соответственно минимально и максимально возможную даты начала финансирования.

Предполагается, что отобрано несколько проектов (портфель) Cj=(cjQ, cj\,.), где j= 1,., т - номер проекта в портфеле, a cjr i-ая выплата по j-ому проекту.

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

Пусть tj - время начала финансирования проекта С,-. Из ограничений задачи следует, что и<^<Уг (1)

Связи между проектами С,- и Cj будут выражены следующим образом У

Общее время финансирования всего портфеля равно

Г = шах{Г.+/у}. (3) j

Через F.\ обозначен начальный капитал инвестора, F.\>0.

В каждый момент времени средства инвестора складываются из накопленного в банке остатка от предшествующего инвестиционного процесса и текущих выплат по проектам. Если Fh - средства на счете инвестора в момент времени h, то до платежей по проектам капитал инвестора равен (\+i)*Fh.\-Пусть Ph = |у :tj <h<tj + /,.} - множество проектов, финансируемых в момент времени /г. Платеж по проекту /, осуществляемый в момент h, равен сj h4 . Поскольку стоимость денег (а, соответственно, и проектов) меняется со временем, то осуществляется коррекция проектов в соответствии с темпом инфляции. Платеж, с учетом влияния инфляции, будет равен cJh * (1 + r)'J.

Задача выглядит следующим образом: требуется каждому проекту С, поставить в соответствие такое время его начала (,, удовлетворяющее ограничениям (1) и (2), чтобы в любой момент времени выполнялось условие неразорения :

0 + 0^ + 1^0 + 0^0 (4) при h-0,l,.,T, а время финансирования всего портфеля было минимально, т.е.

Г-» mi п. (5)

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

Интерпретация задачи с точки зрения теории графов

Совокупность проектов может быть удобно представлена в виде взвешенного ориентированного ациклического графа, вершинами которого являются проекты, наличие дуги (С,-,С7) означает, что проект С,- должен начинаться после проекта Q, вес дуги равен соответствующему временному лагу ку. Назовём истоком вершину, имеющую только исходящие дуги. Будем считать, что вершины занумерованы таким образом, что наличие дуги (С„Су) означает, что /</. Такая нумерация вершин в подобных графах всегда существует.

В случае, если все проекты в портфеле связаны друг с другом, можно этот портфель представить в виду мульти-проекта (рисунок 2). Если начало финансирования проекта Ch не зависит от срока начала проекта Су, то будем говорить, что kjt~kij= 0.

Рисунок 2. Мульти-проект, представленный в виде графа

Каждая вершина С, имеет пометку Pt - минимально возможное время начала его финансирования. Для проекта (вершины), принятого к финансированию, Prti. Пометка вершины (проекта) Pj обладает следующими свойствами: 1)/>>0; 2)Pie[Ui,Vi]-, 3 )Pj>Pl+k9,iZj

При изменении пометки любой вершины производится пересчёт пометок всех вершин-наследников.

Целевая функция задачи будет выглядеть следующим образом: max{/>+/J-»min (6) при выполнении условия (4).

Анализ сложности

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

Пусть в рассматриваемой экономике нулевая инфляция, все проекты состоят из одного, единичного платежа, инвестор располагает средствами, достаточными для финансирования всех проектов, и нет ограничений на срок начала финансирования проекта, то есть г= О, Fx>m, С/=(-1), (/, = 0, V.->co, /=1,2,.,/и.

Если начало финансирования проекта С„ не зависит от срока начала проекта С,, то будем говорить, что kji=kij=0.

В этом случае, задача (4), (6) может быть сформулирована в виде следующей задачи распознавания.

Задача 1

Условие: Дан граф G=(C, К), в котором С - множество вершин (проектов), К- множество дуг, соединяющих эти вершины, и Q - некая оценка длительности финансирования портфеля.

Вопрос: Верно ли, что G содержит гамильтонов путь такой, что ma x{Pi+li}<Q?

Задача 1 является NP-полной. Поскольку она является частным случаем поставленной задачи, то вся массовая задача (4), (6) является NP-трудной.

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

Практическая необходимость решения NP-трудных задач привела к возникновению и развитию таких направлений исследования как:

- методы сокращения перебора вариантов при отыскании точного решения задачи (методы типа «ветви и границы»);

- нетрудоёмкие алгоритмы нахождения приближённого решения (куда, например, относятся различные «жадные» алгоритмы), - без каких-либо гарантий качества получаемых решений;

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

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

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

Можно привести наглядный пример. Пусть даны два проекта (-10;-10; 20;-10; 23) и (-10; 10;-20; 10; 20). Процентная ставка 10%, темп инфляции 5%, начальный капитал 18. При упорядочении (1,2) время начала первого проекта равно 1, а время начала второго проекта 4, а при упорядочении (2,1) - время начала второго проекта равно 0, а первого 4. Т.е. в обоих случаях время реализации портфеля равно 9 годам. В то же время, оба проекта можно начать в момент 3, тогда общее время реализации портфеля составит 8 лет.

Поэтому для решения задачи (1)-(5) был разработан подход, сочетающий в себе два популярных направления исследования практических решений NP-полных задач - методов сокращения перебора вариантов при отыскании точного решения задачи и нетрудоёмких алгоритмов нахождения приближённого решения. Был предложен следующий порядок их применения:

0. Проекты упорядочиваются по одной из характеристик: NPV, MM, R, далее к ним применяется принцип «первый подходящий» (First Fit);

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

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

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

W Вычисли гельный эксперимент

Ввод данных

Проекты:

Промежуточные результаты

Начальный капитал. 81

Статистика Характеристики:

Платежу од 0 |l * I' 4 5 А NFV [мм |Rent

1 -96 |-25 48 16 74 49 1118.73 24,1

-43 -11 18 -3 -37 45 17,61 65.65 26.83

3 -29 -77 -49 95 16 62 36.06 139.5 25.85

4 -42 -82 45 93 21 -76 11,86 116.55 10,18

5 -26 27 84 -100 -66 34 7.25 52.24 13,88

6 -90 51 -20 55 -26 82 18.83 90 20.92

7 j < -81 fifc ЯК -17 -47 -Я v > 12.87 81 15.88

Расписания

Платеж\Алг. nri(NFV) |ПП(ММ) |пп((4ем) |ВиГр I А

Длина шЯЯШШШ [21 22 20

1 13 14 13 7 г 0 2 0 13

3 9 9 9 12

4 15 7 15 10

5 2 0 2 12

6 6 13 6 2

7 А 1 А 0 V

Рисунок 3. Экранная форма программы

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

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

• длина проектов - 8 лет;

• количество проектов в портфеле - 8;

• процентная ставка - 0,1;

• темп инфляции - 0,08;

• начальный капитал - 200;

• границы выплат - (-100; 100).

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

Таблица 1.

Первоначальная сортировка по NPV Первоначальная сортировка по ММ Первоначальная сортировка по R

1 этап (алгоритм первого подходящего) 1,14 1,10 1,08

2 этап (алгоритм ветвей и границ) 1,04 1,04 1,04

Точное решение 1 1 1

За единицу в этой таблице принято оптимальное значение целевой функции.

Среднее время работы алгоритма

1 этап 0,03 сек.

2 этап 45 сек.

Точное решение 14 мин.

Видно, что предлагаемый алгоритм даёт решение, близкое к оптимальному, при значительной экономии вычислительных ресурсов.

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

В частности рассматривались портфели из 5-20 случайных проектов с длительностью 10 лет каждый и портфели из 10 проектов с длительностью от 5 до 20 года. В каждом случае проводилось 250 экспериментов. Сравнивались как значения целевой функции, так и время вычислений. Приведем соответствующие результаты.

Результаты исследования зависимости качества решения, предлагаемого алгоритмом «первый подходящий», от исходной сортировки сведены в график 1. Число проектов в портфеле фиксировано - 10, длительность проекта меняется.

График 1.

Зависимость от исходной сортировки

-NFV -ММ Rent

9 10 11 12 13 14 15 16 17 18 19 20 Длительность проекта

На графике 2 приведено исследования для фиксированной длительности проекта. Все проекты длятся 10 лет. Количество проектов в портфеле меняется.

График 2.

Зависимость от исходной сортировки

5 25

-NPV -ММ Rent

10 11 12 13 14 15 Количество проектов в портфеле

На графике 3 приведена зависимость времени решения задачи методом «первый подходящий» при начальной сортировке по Rent от её начальной размерности. По очереди фиксировались длительность проекта и количество проектов в портфеле на уровне 10. Значение второго параметра менялось соответственно от 5 до 20.

График 3.

Влияние начальной размерности на время решения

140

120

10 проектов *—10 лет 0

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Значение аргумента

В таблицах 3 и 4 приведены время и результаты решения задачи методом «первый подходящий» (при разных начальных сортировках) и методом ветвей и границ.

Таблица 3. Результат, получаемый при фиксированной длительности проекта (5 лет).

Результат решения

Количество Результат Результат Результат (метод проектов в решения решения решения ветвей и портфеле (NPV) (ММ) (Rent) границ)

5 проектов 13,644 14,376 13,76 10,832

6 проектов 16,044 16,732 16,188 13,324

7 проектов 17,188 17,724 17,208 15,14

8 проектов 18,344 19,308 18,536 15,444

9 проектов 20,8 21,6 20,6 18,6

Под результатом решения здесь понимается средняя длина получаемого портфеля.

Таблица 4. Время работы алгоритма, получаемое при фиксированной длительности проекта (5 лет), мс.

Время решения

Количество Время Время Время (метод проектов в решения решения решения ветвей и портфеле (NPV) (ММ) (Rent) границ)

5 проектов 1,6 2,86 1,736 35,068

6 проектов 2,336 3,624 3,144 268,388

7 проектов 4,372 4,168 3,944 1801,344

8 проектов 6,248 6,08 6,516 5950,612

9 проектов 9 5,8 9,6 37083,6

На основе проведённых вычислительных экспериментов были сделаны следующие выводы:

1. Как правило, предпочтительнее использовать первоначальную сортировку по модифицированному индексу рентабельности (таблица 1).

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

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

1 глава

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

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

Приведём содержательное описание проблемы.

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

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

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

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

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

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

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

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

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

3. Проведен анализ сложности поставленной задачи. С помощью интерпретации задачи с точки зрения теории графов, установлена её NP-трудность и на этой основе предложен двухэтапный алгоритм решения, сочетающий метод «первого подходящего» и метод «ветвей и границ». Особенностью поставленной задачи является то, что алгоритмы типа первого подходящего не обеспечивают оптимума ни при каком исходном упорядочивании проектов.

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

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

Заключение

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

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

1. Approximation Algorithms for NP-Hard Problems, Ed. by D.S. Hochbaum, PWS, 1997. P.157-178.

2. Baker B.S., Goffman Jr. E.G., Riverst R.L. Orthogonal packing in two dimensions // SIAM J. Comput. 9 (1980). P. 846-855.

3. Baker B.S., Riverst R.L. Orthogonal packing in three dimensions // SIAM J. Comput. 11 (1980). P. 541-559.

4. Berkey J.O., Wang P.Y. Two dimensional finite bin packing algorithms.// J. Oper. Res. Soc. 38 (1987). P. 423-429.

5. Bronshtein E., Oleynick Т., Latypova G. Some optimization problems of investment theory. Pre-conference proc. 18-th Intern. Conf. on System Research, Informatics and Cybernetics, Baden- Baden, 2006. Zagreb, 2006. P. 18-21.

6. Bronshtein E., Spivak S. Convex structures and investments. // Proc. of 4-th investments conference. Cambridge, 1998. P.325-339.

7. Brucker P. Scheduling Algorithms. Berlin: Springer, 1995. P. 215-218.

8. Carlier J. And Pinson E. An algorithm for solving the job-shop problem // Management Science. 1989. V.35.P.164-176.

9. Chazelle B. The bottom-left bin packing heuristic: An efficient implementation // IEEE Trans, on Comput. 2 (1983). P. 697-707.

10. O.Chen B. and Strusevich V.A. Approximation algorithms for three-machine open shop scheduling// ORSA Journal on Computing. 1993. V. 5. P. 321-326.

11. Chen B. Scheduling Multiprocessor Flow Shops // D.-Z. Du and J. Sun (Eds.). New Advances in Optimization and Approximation. Kluwer, 1994. P. 1-8.

12. Chen В., Potts C.N. and Woeginger G.J. A review of machine scheduling: complexity, algorithms and approximability // Handbook of Combinatorial Optimization. D.-Z. Du and P.M.Pardalos (Eds.). Kluwer Academic Publishers, 1998. P.21-169.

13. Chung F.K.R., Garey M.R., Johnson D.S. On packing two-dimensional bins // SIAM J. Algebraic Discrete Meth. 3 (1982). P. 66-76.

14. Coffman E., Garey M., Johnson D. Approximation algorithms for bin packing an updated survey // Algorithm Design for Computer System Design (Ausiello G., Lucertini M., Serafini P.eds) Berlin etal. N1. 984 p.

15. Coffman E.G. Jr., Garey M.R., Johnson D.S., Tarjan R.E. Performance bounds for level-oriented two-dimensional packing algorithms // SIAM J. Comput. 9(1980). P. 801-826.

16. Fiala T. An algorithm for the open-shop problem // Math. Oper. Res. 1983.

17. Gabow H.N. and Kariv 0. Algorithms for Edge Coloring Bipartite Graphs and Multigraphs // SIAM J.Comput. 1982. V. 11. P. 117-129.

18. Garey M.R. and Johnson D.S. Complexity Results for Multiprocessor Scheduling under Resource Constraints // SIAM J.Comput. 1975. V. 4. P. 397411.

19. Gonzalez T. and Sahni S. Open Shop Scheduling to Minimize Finish Time // J. ACM. 1976. V. 23, N. 4. P. 665-679.

20. Hall L.A. Approximability of flow shop scheduling // in: Proceedings of the 36lh IEEE Symposium on Foundations of Computer Science. 1995. P. 82-91.

21. Husson В., Jordan H. Le choix des investissement. J.Delmas et Cie, 1998. P.68-75.

22. Jansen, K., Solis-Oba, R., and Sviridenko, M. Makespan minimization in job shops: a polynomial time approximation scheme // Proceedings of the 31st Annual ACM Symp. on Theory of Computing. 1999. P. 394-399.

23. Johnson D.S. Near-optimal bin packing algorithms // PhD Thesis. MIT: Cambridge. 1973.246 р.

24. Johnson, S.M. Optimal Two and Three-Stage Production Schedules with Setup Times Included // Nav. Res. Log. Quart. 1954. V. 1, N. 1. P. 61-68.

25. Keller H., Kotov V. An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing // Operations Research Letters. V. 31. N 1. 2003. P. 68-89.

26. Kononov A., Sevastianov S., and Tchernykh I. When difference in machine loads leads to efficient scheduling in open shops II Annals of Oper. Res. 1999. V. 92. P. 211-239.

27. Land A.H., and Doig A.G. An automatic method of solving discrete programming problems. Econometrica. v28 (1960). P 497-520.

28. Lawler E.L., Lenstra J.K., Rinnooy Kan, A.H.D., and Shmoys D.B. Sequencing and scheduling: algorithms and complexity // Handbooks in Operations Research and Management Science. V. 4. Amsterdam: North Holland, 1993. P. 445-522.

29. Lee, C.-Y. and Vairaktarakis G.L. Minimizing Makespan in Hybrid Flow-shops// Opns. Res. Letters. 1994. V. 16. P. 149-158.

30. Little J.D.C., Murty K.G., Sweeney D.W., and Karel C. An algorithm for the traveling salesman problem. Operations Research, vl 1 (1963). P. 972-989.

31. Little J.D.C., Sweeney D.W., and Karel C. A discrete algorithm for the traveling salesman problem. Operations Research, vl (1964). P. 343-357.

32. Lodi A., Martello S., Vigo D. Heuristic algorithms for the three-dimensional bin packing problem // European Journal of Operational Research. 2002. N 141. P. 410-420.

33. Mas-Colell A. The theory of general economic equilibrium. A differentiable approach//Cambridge: University-press, 1985. P.37-95.

34. Oleynick T.N. Optimum scheduling of investment projects financing. // Proceedings of the Round-Table Discussion on Information Technologies and Mathematical Methods of Investigation in Economics. Ufa. September 8,2006. P. 129-135.

35. Potts C.N., Sevast'janov S.V., Strusevich V.A., Van Wassenhove L.N. and Zvaneveld C.M. The two-stage assembly scheduling problem: complexity and approximation // Operations Research. 1995. V.43, N.2. P. 346-355.

36. Potts, C.N. Analysis of heuristics for two-machine flow-shop sequencing subject to release dates // Math. Oper. Res. 1985. V. 10, N. 4. P. 576-584.

37. Schuurman P. and Woeginger G.J. Approximation Algorithms for the Multiprocessor Open Shop Problem // Report Woe-13, October 1997. TU Graz, Austria. P. 45-51.

38. Sevastianov, S.V. Multi-parameter complexity analysis of discrete problems // Proc. International Workshop Discrete Optimization Methods in Scheduling and Computer-Aided Design, Minsk, September 56, 2000. Minsk, 2000. P. 172-174.

39. Shmoys D.B., Stein C., and Wein J. Improved Approximation Algorithms for Shop Scheduling Problems // Proceedings of the 2nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 1991. P. 148-157.

40. Williamson D.P., Hall L.A., Hoogeveen J.A., Hurkens C.A.J., Lenstra J.K., Sevastianov S.V., and Shmaoys D.B. Short shop schedules // Oper. Res. 1997. V.45, N.2. P.288-294.

41. Андреев А.Ф., Дунаев В.Ф. и др. Основы проектного анализа в нефтяной и газовой промышленности. М., 1997. С.113.

42. Андронникова Н.Г., Баркалов С.А., Бурков В.Н., Котенко A.M. Модели и методы оптимизации региональных программ развития. (Препринт) М.: Институт проблем управления им. В.А. Трапезникова РАН, 2001. С Л 3-21.

43. Андронникова Н.Г., Бурков В.Н., Леонтьев С.В. Комплексное оценивание в задачах регионального развития (Научное издание /

44. Институт проблем управления им. В.А. Трапезникова РАН) М.: 2002. С. 79-93.

45. Аркин В.И., Сластников А.Д. Ожидание инвестиций и налоговые льготы / Препринт № WP/97/033. М.: ЦЭМИРАН, 1997. С168-187.

46. Арсланова 3., Лившиц В. Принципы оценки эффективности инвестиционных проектов в разных системах хозяйствования // Инвестиции в России. 1995. № 2. С.52-57.

47. Баркалов П.С., Буркова И.В., Глаголев А.В., Колпачев В.Н. Задачи распределения ресурсов в управлении проектами. М.: 2002 (Научное издание / Институт проблем управления им. В.А. Трапезникова РАН), 63 с.

48. Баркалов С.А. Теория и практика календарного планирования в строительстве. Воронеж: ВГАСА, 1999. С. 63-115.

49. Баркалов С.А., Бурков В.Н. и др. Прикладные модели в управлении организационными системами. ИПУ РАН, ВГАСУ, ТГУ, Тула. 2002. С. 215-221.

50. Беленькая О. Изменение инвестиционного рейтинга России -последствия для финансовых рынков. Мнение эксперта opec.ru. http://usb.corri.Ua/ru/finances/worldfinance/markets/2003/10/l/ Электронный ресурс.

51. Беренс В., Хавранек П.М. Руководство по подготовке промышленных технико-экономических исследований. М.: АОЗТ «Интерэксперт», 1995. С.89.

52. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск. Наука, 1978. С.61-79.

53. Бирман Г., Шмидт С. Экономический анализ инвестиционных проектов. М.: ЮНИТИ, Банки и биржи, 1997. С.264-273.

54. Брейли Р., Майерс С. Принципы корпоративных финансов. М.: Тройка-Диалог, 1997. С.49-59.

55. Бронштейн Е.М., Олейник Т.Н. Одна задача календарного планирования процесса инвестиций. Обозрение прикладной и промышленной математики. Т. 12, № 1,2005, С. 112.

56. Бронштейн Е.М., Спивак С.И. О применении выпуклых структур в теории инвестиций // Труды Средневолжского математического общества.-1999.- № 1 .-С. 121-130.

57. Бронштейн Е.М., Черняк Д.А. Сравнительный анализ показателей эффективности инвестиционных проектов. Экономика и математические методы. Т. 41, №2, 2005, С. 21-28.

58. Бурков В.Н., Буркова И.В. Задачи дихотомической оптимизации. -Материалы международной научно-технической конференции «Системные проблемы качества, математического моделирования, информационных и электронных технологий», Радио и связь, 2003. С. 2328.

59. Бурков В.Н., Горгидзе И.А., Ловецкий С.Е. Прикладные задачи теории графов. Тбилиси: Мецниереба, 1974. С.131-145.

60. Бурков В.Н., Грацианский Е.В., Еналеев А.К., Умрихина Е.В. Организационные механизмы управления научно-техническими программами. М.: ИПУ РАН, 1993. С. 44-48.

61. Бурков В.Н., Ловецкий С.Е. Методы решения экстремальных задач комбинаторного типа (обзор). Автоматика и телемеханика - 1968, №11. С. 23-35.

62. Бурков В.Н., Ловецкий С.Е. Эвристический подход к решению динамических задач распределения ресурсов. Автоматика и телемеханика - 1966, № 5. С. 69-73.

63. Бурков В.Н., Новиков Д.А. Как управлять проектами. М.: СИНТЕГ ГЕО, 1997. С. 159-164.

64. Буркова И.В. Метод дихотомического программирования в задачах управления проектами // Диссертация на соискание учёной степени кандидата технических наук. На правах рукописи. Москва 2004.С. 100.

65. Валдайцев С.В. Оценка бизнеса и инноваций. М.: Филинъ, 1997. С. 246.

66. Виленский П.Л., Лившиц В.Н. Оценка эффективности инвестиционных проектов с учётом реальных характеристик экономической среды. Аудит и финансовый анализ. №3. М.: Изд. Дом «Компьютерный аудит», 2000. С.544.

67. Виленский П.Л., Лившиц В.Н., Орлова Е.Р., Смоляк С.А. Оценка эффективности инвестиционных проектов АНХ при Правительстве РФ. М.: Дело, 1998. С. 312-328.

68. Виленский П.Л., Лившиц В.Н., Смоляк С.А. Оценка эффективности инвестиционных проектов: Теория и практика: Учеб. пособие. 2-е изд., перераб. и доп. -М.: Дело, 2002. - 888 с.

69. Виленский П.Л., Смоляк С.А. Показатель внутренней нормы доходности проекта и его модификации / Препринт № WP/98/060. М.: ЦЭМИ РАН, 1998. С. 123-127.

70. Виленский П.Л., Смоляк С.А. Расчёты оборотного капитала в инвестиционном проектировании // Моделирование механизмов функционирования экономики России на современном этапе. Вып. 3. М.: ЦЭМИ РАН, 1999. С.41-46.

71. Воропаев В.И. Управление проектами в России. -М.: Алане. 1995. С. 8594.

72. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Исследования по теории расписаний // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1974. С. 3-10. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 12.)

73. Гимади Э.Х., Залюбовский В.В. Задача упаковки в контейнеры: асимптотически точный подход // Известия вузов. Математика. 1997. № 12. С. 25-33.

74. Гимади Э.Х., Залюбовский В.В., Шарыгин П.И. Задачи упаковки в полосу: асимптотически точный подход // Известия высших учебных заведений. Математика. №12(427). 1997. С. 34-44.

75. Гимади Э.Х., Перепелица В.А. Статистически эффективный алгоритм выделения гамильтонова контура (цикла) // Методы дискретного анализа. Новосибирск: Изд-во Ин-та математики, 1973. С. 15-28. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 22.)

76. Гитман Л.Дж., Джонк М.Д. Основы инвестирования. М.: Дело, 1997. С. 33-41.

77. Голенко Д.И., Тарнопольский Ю.Я. Оптимизация календарных планов методами направленного поиска. Кибернетика - 1970. № 6. С. 32-41.

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

79. Душин Б.И. Алгоритм для 2-маршрутной задачи Джонсона // Кибернетика. 1998. N 3. С. 53-58.

80. Емеличев В.А. Дискретная оптимизация. Последовательностные схемы решения. I, II. Кибернетика - 1971. № 6; - 1972, № 2. С. 74-86.

81. Запад повысил инвестиционный рейтинг России. // Российская газета. 01.02.2005. №3687.

82. Инвестиционный рейтинг России повышен агентством S&P. http://www.dohodnoemesto.ru/new 17.asp Электронный ресурс.

83. Интриллигатор М. Реформа российской экономики. Роль институтов // Экономика и математические методы. Т. 33. Вып. 3. 1997. С. 15-33.

84. Каплин A. Moody's подтверждает инвестиционный рейтинг России. -Новости агенства Aton-line. http://www.aton-line.ru/analvtics/cornrnent/moody39spodtverzhdaet investicionnyjreitingr ossii/ Электронный ресурс.

85. Каплин А. Последствия повышения инвестиционного рейтинга Российской Федерации. http://www.aton-line.ru/analytics/comment/posledstviya povivisheniya investicionnogo reiting a rossii/ Электронный ресурс.

86. Клейнер Г.Б., Тамбовцев B.JL, Качалов P.M. Предприятие в нестабильной экономической среде: риски, стратегия, безопасность. М.: Экономика, 1997. С. 386.

87. Комплексная оценка эффективности мероприятий, направленных на ускорение научно-технического прогресса. Методические рекомендации и комментарий по их применению. М.: Информэлектро, 1988. С. 241.

88. Корбут А.А., Финкелыитейн Ю.Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969. С. 487.

89. Курош А.Г. Курс высшей алгебры. М.: Наука, 1968. С. 524.

90. Методические рекомендации по оценке эффективности инвестиционных проектов (Вторая редакция). М-во экон. РФ, М-во фин. РФ, ГК РФ по стр-ву, архит. и жил. политике. М.: ОАО «НПО Изд-во "Экономика"», 2000. С.387.

91. Методические рекомендации по оценке эффективности инвестиционных проектов. М.: Экономика, 2000. С.354.

92. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. I, II. Кибернетика - 1965. № 1; Т. 2. С. 41-48.

93. Олейник Т.Н. Об одной задаче календарного планирования. -Вестник УГАТУ. // Научный журнал Уфимского государственного авиационного технического университета. Т.8, №2(18), 2006. С. 64-66.

94. Олейник Т.Н. Об одной задаче календарного планирования. -Вестник УГАТУ. // Научный журнал Уфимского государственного авиационного технического университета. Т.8, №2(18), 2006. С. 64-66.

95. Олейник Т.Н. Оптимизация графика финансирования инвестиционных проектов. Обозрение прикладной и промышленной математики. Т. 13, № 4, 2006, С. 693-694.

96. Орлов А.И. Менеджмент. М.: Знание, 1999. С.223.

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

98. Путин В. Россия на рубеже тысячелетия // Экономика и жизнь. 2000. №2.

99. Севастьянов С.В. Геометрические методы и эффективные алгоритмы в теории расписаний // Диссертация на соискание учёной степени доктора наук. На правах рукописи. Новосибирск 2000 - 280 с.

100. Севастьянов С.В. Некоторые обобщения задачи Джонсона // Управляемые системы. Новосибирск: Изд-во Ин-та математики, 1981. С. 45-61. (Тр./ АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 21.)

101. Севастьянов С.В. Применение геометрических методов в многостадийных задачах теории расписаний // Тез. докл. на 11 Международной конф. по проблемам теоретической кибернетики. Ульяновск, 10-14 июня 1996. Ульяновск: Изд-во СВНЦ, 1996. С. 180-181.

102. Севастьянов С.В. Эффективное построение расписаний в системах открытого типа // Сибирский журнал исследования операций. 1994. Т. 1, N 1. С 20-42.

103. Севастьянов С.В. Эффективное построение расписаний, близких к оптимальным, для случаев произвольных и альтернативных маршрутов деталей II Докл. АН СССР. 1984. Т.276, N 1. С.46-48.

104. Севастьянов С.В. Эффективное построение расписаний, близких к оптимальным, для случаев произвольных и альтернативных маршрутов деталей II Докл. АН СССР. 1984. Т. 276, N 1. С. 46-48.

105. Севастьянов С.В., Черных И.Д. Достаточное условие эффективной разрешимости задачи open shop // Дискретный анализ и исследование операций. 1996. Т. 3, N. 1. С. 57-74.

106. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. М.: ФИЗМАТЛИТ. 2002. 240 с.

107. Танаев B.C., Сотсков Ю.И., Струсевич В.А., Теория расписания. Многостадийные системы // М.: Наука, 1989. С. 670.

108. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975. С. 724.

109. Теория расписаний и вычислительные машины. Под ред. Э.Г. Коффмана. -М.: Наука, 1984. 620 с.

110. Уздемир А.П. Динамические целочисленные задачи оптимизации в экономике. -М.: Физматлит, 1995. 540 с.

111. Управление проектами. Под общей редакцией В.Д. Шапиро. -СПб.: Два три, 1996. 486 с.

112. Харари Ф. Теория графов, М.: Мир, 1973. 413 с.