Формальная постановка задачи
Введем обозначения:
n - число этапов, на которых принимаются решения о вложении денег в тот или иной проект. В нашем примере такие решения принимаются каждый месяц и потому n= 6. m - число проектов. В примере m =4.Pi - проекты, где i = 1 …m.Ri - величина риска проекта Pi.qi - число этапов проекта Pi.Si j - сумма денег, вкладываемая в проект Pi на j -м этапе. Si j - это и есть наши искомые переменные, значения которых предстоит найти в ходе решения задачи. Заметьте, что здесь i = 1 ... m, j = 1 ... qi N - общее число искомых переменных, которое определяется формулой N =
Перейдем теперь к формулировке оптимизационной задачи:
Необходимо минимизировать первоначальный капитал фонда
K => min
при выполнении четырех групп ограничений:
Ограничения баланса: Bi = 0 i = 1…n
Ограничения среднего риска: Ri <= Rc i = 1…n
Ограничения средней длительности проекта: Ti <= Tc i = 1…n
Ограничения на положительность значений: Si j >= 0 i = 1 ... n, j = 1 ... qi
Первую группу ограничений составляют ежемесячные ограничения баланса. Все имеющиеся к началу месяца сбережения следует вложить в те или иные проекты. Деньги " в чулке" хранить нельзя. Поэтому сумма денег, полученных в конце месяца с учетом дивидендов и выплаты долговых обязательств, равна сумме денег, вкладываемых в инвестиционные проекты на следующем месяце. Конечно, чтобы такая возможность всегда существовала, необходимо, чтобы среди проектов был "безопасный" проект с наименьшим риском и минимальным сроком вложения. Параметры такого проекта должны быть заведомо меньше задаваемых значений среднего риска и средней продолжительности. Существование такого проекта гарантирует существование решения задачи для любых исходных данных. В нашем примере это первый проект. Понятно, что таким проектом может считаться вложение денег в Сбербанк.
Отметим еще краевые балансовые ограничения. В начале первого месяца сумма вложений в инвестиционные проекты равна начальному капиталу фонда. В конце последнего месяца сумма полученных денег равна сумме, которую следует выплатить для погашения долга. Эти ограничения вытекают из предназначения временного целевого фонда.
Я не стану выписать балансовые ограничения в явном виде, поскольку, с одной стороны, они достаточно понятны, с другой стороны их формальная запись для общего случая довольно громоздка из-за динамического характера решаемой задачи. Ограничусь тем, что приведу краевые уравнения баланса и уравнение для одного из месяцев. Вот как выглядит уравнение баланса на начальном этапе:
K = S1 1 + S2 1 + S3 1 + S4 1
Это уравнение задает целевую функцию - начальный капитал K, значение которого предстоит определить. Уравнение баланса говорит о том, что весь начальный капитал должен быть вложен в инвестиционные проекты.
Баланс по завершении работы фонда имеет вид:
1.015* S1 6 + 1.035* S2 3 + 1.06* S3 2 + 1.11* S4 1 = Capital
Это уравнение говорит, что деньги, полученные в конце шестого месяца от всех проектов, должны давать сумму, равную требуемому капиталу.
Баланс после истечения двух месяцев с учетом выплаты аванса имеет вид:
1.015* S1 2 + 1.035* S2 1 - D1 = S1 3 + S2 2
Вторую группу составляют ежемесячные ограничения среднего риска. Если обозначить через Li k сумму инвестиций i -го проекта в k - м месяце, то эти ограничения в общем случае имеют вид:
m m
i i
Исходя из этой общей формулы, можно выписать ограничения этой группы в конкретной ситуации. Приведу только одно ограничение для четвертого месяца нашего примера:
R1* S1 4 + R2* S2 2 + R3* S3 2 + R4* S4 1 <= Rc*(S1 4 + S2 2 + S3 2 + S4 1)
Третью группу составляют ежемесячные ограничения средней длительности проектов. Общая формула имеет вид:
m m
i i
В построении ограничений участвует опять таки средневзвешенная, но теперь уже с учетом длительности проектов сумма инвестиций i -го проекта в k - м месяце. Формулы становятся чуть более сложными, поскольку в текущем месяце используются не постоянные коэффициенты, как в случае с подсчетом рисков, а динамически пересчитываемые коэффициенты, задающие время до окончания этапа проекта. Опять таки, ограничимся тем, что приведем только одно ограничение для того же четвертого месяца нашего примера:
T1 4* S1 4 + T2 4* S2 2 + T3 4* S3 2 + T4 4* S4 1 <= Tc*(S1 4 + S2 2 + S3 2 + S4 1)
В нашем примере: T1 4 = 1; T2 4 =1; T3 4 = 3; T4 4 = 3.
С точки зрения математика полученная задача является довольно простой задачей линейного программирования. Ее решение может быть получено в Excel вручную, используя возможности мощного инструментального средства, встроенного в Excel, - решателя Solver. Однако понятно, что даже опытный пользователь, вряд ли сумеет без ошибок выписать все ограничения задачи, особенно при увеличении числа инвестиционных проектов.
Оптимизация инвестиций
Нажатие этой кнопки запускает основной процесс. Здесь MasterF поможет пользователю поставить оптимизационную задачу по выбору инвестиционных проектов и получить ее решение в форме, удобной для анализа. По сути, перед пользователем открывается страница, позволяющая достаточно просто поставить задачу, к рассмотрению которой сейчас и перейдем.
Планирование инвестиций с учетом риска
Приведу содержательную постановку задачи, которая была предложена моим коллегой - доцентом экономического факультета - Шукурьяном С. И.
АОЗТ "Риск" заключило контракт на покупку оборудования на общую сумму 750000$. В соответствии с условиями контракта аванс в размере 150000$ необходимо заплатить через 2 месяца, а оставшуюся сумму через 6 месяцев после заключения контракта. Для обеспечения выплат руководитель "Риска" создал временный целевой фонд и назначил его руководителя. Начальный капитал фонда составляет сумму, меньшую, чем та, которую предстояло заплатить в конце контракта. Остальные деньги руководитель фонда должен был обеспечить за счет грамотной инвестиционной политики и получения соответствующих дивидендов. Кроме того, руководитель "Риска" поставил жесткие ограничения на среднюю величину допустимого ежемесячного риска и среднюю ежемесячную длительность вложения денег. Задать величину требуемого начального капитала должен был руководитель фонда, но, естественно, руководство хотело, как можно меньше денег вложить в начальный капитал фонда.
Руководитель фонда после предварительных консультаций с экспертами отобрал 4 возможных проекта, которые разумно было инвестировать. И хотя число инвестиционных проектов сравнительно невелико, подобрать наилучшее или даже просто приемлемое решение "вручную" оказалось совсем не просто. И тогда руководитель фонда обратился к программистам с целью помочь ему в решении задачи. Так появился помощник MasterF.
Программист начал с формализации постановки задачи, стараясь сделать ее на начальном этапе как можно более простой. Начнем с инвестиционных проектов. Каждый из них имеет следующие характеристики:
Дату начала и длительность.Число этапов, на каждом из которых производится выплата денег. Для этапа указана его длительность и сумма, выплачиваемая в конце этапа.Минимальная и максимальная сумма, которую можно вложить в проект.Степень риска проекта, заданная независимыми экспертами.
Данные о четырех отобранных инвестиционных проектах представлены в таблице:
| A | 1.015 | 1.015 | 1.015 | 1.015 | 1.015 | 1.015 | 1 |
| B | 1.035 | 1.035 | 1.035 | 4 | |||
| C | 1.06 | 1.06 | 9 | ||||
| D | 1.11 | 7 | |||||
Как следует из этой таблицы, проект B, например, состоит из трех этапов, длительность каждого - 2 месяца. В конце этапа прибыль составляет 3,5% от суммы, вложенной на начало этапа. Аналогичный смысл имеют данные и для других проектов. Никаких ограничений на суммы, вкладываемые в проекты, в данном случае не накладывается. Последний столбец таблицы задает риски каждого проекта.
Проект MasterF. Реализация
Проект получился достаточно большим. Я решил не приводить в тексте главы соответствующий программный код и его описание. Расскажу только о том, что делается в проекте, но не о том, как это делается, оставляя реализацию для самостоятельной работы. Надеюсь, что проект будет размещен на сервере и будет доступен, так, что желающие, смогут не только поэкспериментировать с проектом, но и изучить код всего проекта или отдельных его частей.
Проект представляет собой документ Excel, состоящий из четырех рабочих страниц, носящих имена: Титул, ПостановкаЗадачи, Ограничения, Решения.
Работа с проектами
Предполагается, что в организации ведется база данных по инвестиционным проектам. При нажатии первой из командных кнопок пользователь получает возможность работы с этой базой данных. В частности он может просматривать, хранимые там проекты и добавлять новые. В моей реализации для хранения данных о проектах используется Access. Для просмотра и добавления новых записей в базу данных я использовал формы Access. Замечу, что эта часть помощника дана в упрощенном виде и достаточно проста в реализации. Я не уделял ей серьезного внимания.
Справка
И эта функция помощника лишь обозначена. При нажатии командной кнопки открывается обычный текстовый файл, в который можно поместить всю информацию, которая может понадобиться пользователю, работающему с помощником.
Страница "Ограничения"
В начальный момент эта страница почти пуста. Вот как она выглядит:
увеличить изображение
Рис. 9.5. Страница формирования оптимизационной задачи в начальный момент работы
Как видите на странице две надписи и, соответственно, две командные кнопки - "Нажми меня" и "Решатель". По нажатию первой из этих кнопок автоматически создаются переменные задачи, формируется целевая функция и ограничения задачи. Все эти данные размещаются на странице в полном соответствии с требованиями решателя Solver, и в таком виде, чтобы пользователь сумел понять и оценить правильность работы своего помощника. Конечно же, это наиболее серьезная часть той работы, которую выполняет MasterF. Чтобы дать некоторое представление о том, как решаются задачи, возникающие на этом этапе, я приведу лишь одну процедуру, задающую первое балансное ограничение:
Public Sub FormFirstBalance() 'Формирование краевого балансного ограничения первого этапа Dim Myr As Range, i As Byte Dim Bound As String, NameVar As String Set Myr = Worksheets("Ограничения").Range("Bounds").Offset(1, 0) 'Формирование формулы, задающей краевое ограничение Bound = "=" For i = 1 To ProjectsNumber If ProjectStages(i) > 0 Then NameVar = "Sum_" & i & "_1" Bound = Bound & NameVar & "+"
End If Next i Bound = Left(Bound, Len(Bound) - 1) 'Формирование трех ячеек рабочего листа, содержащих 'имя ограничения, левую и правую часть. Myr.Offset(0, 1).Value = Bound Myr.Offset(0, 1).Name = "Bal0" If MaxMin = 1 Then 'Краевое условие задает ограничение Myr.Value = "Balance0" Myr.Offset(0, 2).Value = Capital Myr.Offset(0, 2).Name = "Bar0" Else 'Краевое условие задает целевую функцию Myr.Value = "Goal" 'Переменная Goal - содержит имя ячейки, задающей цель или ограничение. 'Используется при вызове Решателя Goal = "Bal0" End If End Sub
Вот несколько моментов, на которые следует обратить внимание:
Имена переменных я строю по определенным правилам, - в них используется имя проекта и имя этапа. Это позволяет мне динамически строить формулу, задающую краевое ограничение. Для размещения ограничения на рабочем листе, я использую три ячейки. В первой из них помещаю имя ограничения. Заметьте, все ограничения именованы, что позволяет пользователю проанализировать работу, которую выполнил MasterF. Во второй и третьей ячейках размещаются левая и правая часть ограничения. В зависимости от постановки задачи формируемое уравнение может задавать цель или быть первым балансным ограничением.
Всем, кого решение оптимизационных задач на Excel интересует в большей степени, рекомендую обратиться к полному коду проекта. А сейчас давайте взглянем на результаты работы, которую выполнил MasterF по формированию переменных и полной системы ограничений:
увеличить изображение
Рис. 9.6. Автоматическое формирование переменных и ограничений задачи
Как видите, наш помощник сформировал и разместил на странице множество переменных, целевую функцию и три группы ограничений. При желании можно остановиться на этом этапе, и далее вручную вызывать Solver и анализировать результаты полученного решения. Но можно и эту работу поручить помощнику. Нажав командную кнопку "Решатель", можно перейти к следующему шагу работы помощника. На этом шаге программно запускается решатель Solver, который и находит решение задачи, если оно, конечно, существует. После того, как решение получено, помощник выполняет важную работу по формированию отчета о решении в форме, понятной пользователю. Для отчета используется следующая страница нашего документа.
Страница "ПостановкаЗадачи"
Вот внешний вид этой страницы в тот момент, когда пользователь начинает с ней работать:
увеличить изображение
Рис. 9.2. Страница MasterF, позволяющая задать постановку задачи
На странице можно выделить три раздела - выбор проектов, выбор целевой функции и ограничений, задание промежуточных выплат. В разделе выбора проектов имеется кнопка "Выбрать проекты", по нажатию которой появляется список проектов, содержащихся в базе данных. Пользователь может выбрать интересующие его проекты, глядя на их характеристики. Вот как выглядит этот этап работы:
Рис. 9.3. Форма выбора проектов
Этот этап работы, где из базы данных выбираются нужные данные, и формируется список, в котором пользователь делает свой выбор, достаточно подробно описан в главе 7.
В разделе выбора цели у пользователя появляется две возможности, - он может либо максимизировать конечный капитал, обладая фиксированным начальным капиталом, либо минимизировать требуемый начальный капитал, зная ожидаемый капитал в конце инвестиционного процесса. Выбор пользователя соответствующего переключателя влияет на внешний вид страницы. В одном случае появится окошко для задания начального капитала, в другом - ожидаемого капитала. В одном из этих окошек и следует задать значение капитала. Замечу, что в рассматриваемой нами содержательной задаче, возникшей в АОЗТ "Риск", необходимо минимизировать начальный капитал.
Следующие два флажка позволяют включать при необходимости ограничения на средний риск и среднюю длительность проектов. При включенных флажках появляется окошко, где можно задать соответственно требуемый средний риск и среднюю длительность проекта. Замечу, что балансные ограничения всегда будут формироваться при постановке оптимизационной задачи.
Еще одно окошко в этом разделе позволяет задать продолжительность нашего процесса.
При включенном флажке "Выплаты" становится доступным список этапов, на каждом из которых можно задать выплаты или дополнительные взносы.
Взгляните, как выглядит постановка, полностью соответствующая задаче фирмы "Риск":
увеличить изображение
Рис. 9.4. Постановка задачи, возникшей в АОЗТ "Риск"
Как видите, пользователю не пришлось много трудиться, чтобы задать всю необходимую информацию. Чтобы перейти к следующему этапу работы остается нажать командную кнопку с надписью "Нажми по завершении Постановки". В результате перед ним откроется следующая страница "Ограничения", где будет создаваться и решаться оптимизационная задача.
Страница "Решение"
На этой странице формируется подробный отчет о полученном решении. Здесь наглядно показано, какие проекты нужно выбирать на каждом этапе, сколько средств нужно вкладывать в тот или иной проект, какие дивиденды приносит каждый проект. Взгляните, как выглядит отчет о решении нашей конкретной задачи:
увеличить изображение
Рис. 9.7. Отчет о решении
Как следует из отчета, чтобы уплатить на втором месяце 150000, и получить по окончании шести месяцев сумму в 600000, необходимо иметь начальный капитал в размере 684628$. В первый месяц этот капитал следует поровну распределить между двумя проектами - A и C. На третьем и пятом месяце деньги следует вкладывать в проект B. Проект D в решении не используется - у него слишком большая длительность, так что ограничения на среднюю длительность не позволяют использовать этот проект.
Я надеюсь, что при желании Вы сумеете самостоятельно реализовать подобный проект, и уж, по крайней мере, разобраться в программном коде моей реализации проекта. Хочу отметить, что проект был написан мной довольно давно, так что при работе с базой данных я использовал объекты DAO, а не ADO. Но, может быть, в этом есть свое достоинство.
Страница "Титул"
Вот как выглядит титульная страница нашего документа:
увеличить изображение
Рис. 9.1. Титульная страница MasterF
Три командные кнопки - Работа с проектами, Оптимизация инвестиций и Справка - осуществляют переход к соответствующей службе помощника.
