Содержание к диссертации
Введение
1 глава 23
1.1 Задачи теории расписаний 25
1.1.1 Задачи теории расписаний с одним обслуживающим прибором 26
1.1.2. Задачи теории расписаний в общей постановке 28
1.1.3 Задача Джонсона и графики Ганта 30
1.1.4 Постановка задачи теории расписаний как задачи частично-целочисленного линейного программирования 32
1.1.5 Общая модель обслуживающих систем 34
1.1.6 Анализ соответствия приведённых моделей и описанной проблемы. 37
1.2. Задачи ресурсного планирования комплексов работ 38
1.3 Методы решения задач дискретной оптимизации 48
1.3.1. Перестановочный прием в задачах теории расписаний 51
1.3.2. Приближенные и эвристические методы 52
1.3.3 Метод ветвей и границ 58
1.3.4 Сетевые модели. Расчет временных характеристик сетевых моделей 61
1.3.5 Потоки в сетях. Теорема Форда-Фалкерсона о максимальном потокебЗ
2 глава 67
2.1.1. Определение инвестиционного проекта 67
2.1.2 Методы оценки эффективности инвестиционных проектов 72
2.2 Постановка задачи 82
2.2.1 Общая постановка задачи 82
2.2.2 Интерпретация задачи с точки зрения теории графов 84
2.3 Анализ поставленной задачи 86
3 глава 88
3.1 Предлагаемый алгоритм решения 88
3.2 Реализация алгоритма 93
3.3 Вычислительный эксперимент 96
Заключение 106
Основные выводы и результаты работы 108
Список литературы
- Задачи теории расписаний с одним обслуживающим прибором
- Постановка задачи теории расписаний как задачи частично-целочисленного линейного программирования
- Сетевые модели. Расчет временных характеристик сетевых моделей
- Реализация алгоритма
Введение к работе
Общая характеристика работы
Актуальность темы.
В декабре 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].
Инвестиции в экономику РФ (поданным ГосКомСтатРФ)
Инв. в осн. кап (в % к 1990
г-)
Иностр. Инв. ($ млрд.)
Рисунок 1. Инвестиции в экономику Российской Федерации (по данным ГосКомСтата РФ).
Однако, несмотря на явные улучшения инвестиционного климата России, из рисунка 1 видно, что инвестиции в основной капитал ещё далеко не достигли дореформенного уровня 1990-ого года. И несмотря на то, что в 2005 году РФ стала крупнейшим получателем иностранных инвестиций в Юго-Восточной Европе и СНГ, получив $ 26 млрд. из $ 50 млрд., вложенных в регион (по данным ЮНКСТАД), она по-прежнему значительно отстаёт от мировых лидеров - Китая ($ 60,3 млрд. инвестиций в 2005 г.), США ($ 106 млрд.) и Великобритании ($219 млрд.).
Поэтому всё больше различных научных коллективов в России и за рубежом занимаются вопросами повышения эффективности инвестиционной деятельности, управления проектами и, к тому же, теорией календарного планирования (Севастьянов СВ., Буркова И.В, Бурков В.Н., Лившиц В.Н., Виленский П.Л., Смоляк С.А., Гимади Э.Х., Potts C.N., Shmoys D.B., Jansen К, Lenstra J.K.).
5 Многие исследователи полагают, что относительно низкая инвестиционная
привлекательность экономики Российской Федерации обусловлена
недостаточной эффективностью инвестиций. Поэтому повышение
эффективности инвестиций является актуальной задачей. Одним из
направлений повышения эффективности инвестиций является сокращение
общего срока финансирования инвестиционного портфеля.
Всё больше различных научных коллективов в России и за рубежом занимаются вопросами повышения эффективности инвестиционной деятельности, управления проектами и теорией календарного планирования (СВ. Севастьянов, И.В. Буркова, В.Н. Бурков, В.Н. Лившиц, П.Л. Виленский, С.А. Смоляк, Э.Х. Гимади, C.N. Potts, D.B. Shmoys, К. Jansen, J.K. Lenstra).
Актуальность данной темы исследования подтверждается также тем, что в «Приоритетные направления развития науки, технологий и техники в Российской Федерации», утверждённым Президиумом РАН РФ, включены темы: «1.1.7. Математическое моделирование», «7.2.6. Анализ нестационарных динамических макроэкономических процессов. Теория и методы экономико-математического моделирования».
Цель работы и задачи исследования.
Целью работы является построение математической модели, разработка численных методов и программного продукта для решения задачи оптимизации графика финансирования инвестиционного портфеля, обеспечивающей повышение эффективности деятельности инвестора за счёт сокращения общего срока финансирования портфеля проектов. Для достижения данной цели должны быть решены следующие задачи:
1. Построить модель формирования графика финансирования портфеля взаимосвязанных инвестиционных проектов, минимизирующего общий срок его финансирования и учитывающего инфляцию.
Произвести сравнение и выбор критериев оценки эффективности инвестиционного проекта.
Разработать алгоритмы решения поставленной задачи.
Разработать программное обеспечение для исследования сравнительной эффективности разработанных алгоритмов.
Провести вычислительный эксперимент для выбора наиболее эффективного алгоритма.
Научная новизна.
Математическая модель формирования графика финансирования портфеля взаимосвязанных инвестиционных проектов, учитывающая ресурсные ограничения и влияние инфляции, в которой минимизируется общий срок финансирования портфеля инвестиционных проектов.
Сравнительный анализ критериев оценки эффективности проектов для формирования приоритетного списка и статистические исследования качества решений, получаемых на их основе.
Обоснование NP-трудности поставленной задачи, основанное на интерпретации задачи с точки зрения теории графов, и двухэтапный алгоритм её решения, сочетающий численные методы «первого подходящего» и «ветвей и границ».
Программное обеспечение, реализующее предлагаемый алгоритм.
Результаты вычислительных экспериментов, показывающие, что для решения поставленной задачи предлагаемый алгоритм при небольшой размерности задачи даёт расписания, близкие к оптимальному, при существенной экономии вычислительных ресурсов пользователя. Также эксперименты показывают, что, как правило, предпочтительнее использовать первоначальную сортировку по модифицированному индексу рентабельности.
Практическая значимость и внедрение результатов.
Практическая значимость полученных результатов заключается в том, что предложенный алгоритм и реализованный на его основе программный продукт
7 построения расписания финансирования инвестиционного портфеля внедрен в виде надстройки к уже существующей системе информационной поддержки управления портфелем, используемой инвестором. Разработанное программное обеспечение позволяет пользователям строить близкое к оптимальному расписание финансирования портфеля при значительной экономии вычислительных ресурсов пользователя и проводить вычислительные эксперименты. Результаты проведенных экспериментов позволяют сделать выводы о влиянии различных параметров внешней финансовой среды и характеристик проектов на качество и время вычисления получаемого решения.
Исследования проводились в рамках гранта РФФИ 04-06-80009 «Математическое моделирование инвестиционных проектов в реальных экономических условиях» (2004-2006 гг.).
Разработанные алгоритм и программное обеспечение внедрены в компании «Бисот».
Апробация работы. Основные положения и результаты работы докладывались на: Всероссийской молодёжной научно-технической конференции «Интеллектуальные системы управления и обработки информации» (УГАТУ, 2003); V Всероссийском симпозиуме по прикладной и промышленной математике (Санкт-Петербург, 2-8 мая 2005); Зимней школе-семинаре аспирантов УГАТУ, (Уфа, 2006); VII Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2-8 мая 2006); 18-ой международной конференции по системным исследованиям, информатике и кибернетике (Баден-Баден, 2006); 8-я Международной конференции "Компьютерные науки и информационные технологии" CSIT'2006 (Карлсруэ, Германия); Башкирско-Германском форуме молодых экономистов (Уфа-2006); Международной школе-семинаре имени академика С.Шаталина «Системное моделирование социально-экономических процессов» (Воронеж, 9-13 октября 2006); Международной научно-практической конференции «Разработка оценки
8 эффективности и реализация инвестиционных и инновационных проектов» (Ташкент, 14-16 ноября 2006).
Публикации. Основные материалы диссертационной работы опубликованы в 11 научных трудах, в том числе 4 статьи в изданиях, рекомендованных ВАК, и статьи в 4 международных и 4 российских научных изданиях.
Структура работы. Диссертационная работа состоит из 124 страниц машинописного текста, включающего введение, три главы, заключение, рисунки, таблицы и список литературы из 123 наименований.
Основное содержание работы
Во введении обосновывается актуальность темы диссертационной работы, формулируется цель, научная новизна и практическая значимость полученных результатов.
В первой главе рассматриваются наиболее распространённые подходы к постановке и решению задач теории расписаний. Приводится содержательное описание задачи календарного планирования, возникающей в случае, если у инвестора не хватает средств для одновременного финансирования всех отобранных инвестиционных проектов. Проводится анализ существующих моделей задач теории расписаний и анализируется их соответствие описанной проблеме.
Были рассмотрены следующие задачи календарного планирования:
задача мастера - задана для одного обслуживающего прибора;
задача Джонсона - класс задач с двумя обслуживающими приборами;
задача теории расписаний как задача частично-целочисленного линейного программирования;
задачи ресурсного планирования комплексов работ;
9 общая модель многостадийной обслуживающей системы (СВ. Севастьянов):
система открытого типа (общий случай задачи open shop);
задача job shop;
задача flow shop.
Анализ перечисленных моделей выявил три наиболее существенных отличия задач оптимизации сроков инвестирования от традиционных задач календарного планирования:
Отсутствие составляющей, аналогичной понятию «машины». Количество проектов, которые одновременно может профинансировать инвестор, определяется не неким фиксированным числом «машин», а сочетанием средств, которыми располагает инвестор, и средств, которые требуются для финансирования рассматриваемых проектов. Это сочетание не является статичным и принимает свои значения для каждого сочетания располагаемых в данный момент средств инвестора и финансируемых проектов.
Изменяемость «работ». Инфляция оказывает важное влияние на экономическую ситуацию в стране, поэтому необходимо делать пересчёт проектов в соответствии с неким инфляционным коэффициентом. Традиционная же модель теории расписаний не предусматривает изменения ресурсной составляющей рассматриваемых работ.
Возможное сочетание одно- и многостадийных проектов. В один и тот же портфель инвестор может отобрать как моно-, так и мульти- проекты. Рассмотренные модели не учитывают возможности такого сочетания.
Приведённые отличия говорят о том, что для применения теории расписаний к инвестиционной практике необходимо внести существенные коррективы в описанную ранее модель.
Во второй главе предлагается новый подход к моделированию инвестиционного процесса, описываются интегральные характеристики инвестиционного проекта, приводится постановка задачи календарного
10 планирования, её интерпретация с точки зрения теории графов, также сделан анализ сложности поставленной задачи.
Основные понятия
В предлагаемой модели время принимает дискретные значения 0,1,2,.... Предусматривается возможность вложения в банк как альтернативного использования средств, через і обозначена банковская процентная ставка.
Также учитывается влияние инфляции. Реальная покупательная способность денег со временем падает. Темп инфляции г - доля, на которую ежегодно в среднем увеличиваются цены товаров и услуг.
Значения /, г могут меняться от года к году; в данной работе эти параметры предполагаются постоянными, в то же время, описанные алгоритмы применимы и в общем случае.
Под инвестиционным проектом (потоком платежей) понимается вектор C=(cq,C[,...,ci) произвольной размерности, обладающий следующими свойствами: первая ненулевая компонента С отрицательная, последняя
ненулевая компонента С и сумма компонент ^с(. положительные, здесь / -
/=0
длительность проекта. Значение с,- есть размер выплаты в момент / (далее считаем, что это начало года). Если с,>0, то средства поступают инвестору, если с,<0, то инвестор средства в проект вкладывает.
Характеристики проектов
Сравнение проектов осуществляется на основании интегральных числовых показателей, которые учитывают как сами потоки платежей, так и внешнюю финансовую ситуацию.
В работе используются следующие характеристики проектов:
- NPV(Cj) = ^ck*(\ + i)~k - «чистый приведенный доход» проекта (Net Present Value), то есть дисконтированная суммарная прибыль по проекту;
к=0
- MM (С, і) = -min^c^ *(\ + і)'к - минимум средств, необходимых для
финансирования проекта;
- R(C,i) = ' - модифицированный индекс рентабельности, смысл
ММ (С, і)
его заключается в дисконтированной отдаче на единицу средств, которые необходимо иметь для финансирования проекта.
Постановка задачи и математическая модель
Проекты могут иметь ограничения по сроку начала финансирования: /,-, V,-натуральные числа, характеризующие соответственно минимально и максимально возможную даты начала финансирования.
Предполагается, что отобрано несколько проектов (портфель) Cj=(cjo, Cj\,...), гдеу=1,..., т - номер проекта в портфеле, a cjr /-ая выплата потому проекту.
Пусть связь между сроками начал финансирования двух проектов выражается так - «финансирование проекта А может быть начато не ранее, чем через к лет после начала финансирования проекта В». Обозначим через кьа -временной лаг, связывающий указанные проекты.
Пусть tj - время начала финансирования проекта Су. Из ограничений задачи следует, что
U,ut,*Vr (1)
Связи между проектами С,- и С,- будут выражены следующим образом
t. + kyutj. (2)
Общее время финансирования всего портфеля равно
T = max{t.+/.}. (3)
j j j
Через F.\ обозначен начальный капитал инвестора, F.\>0. В каждый момент времени средства инвестора складываются из накопленного в банке остатка от предшествующего инвестиционного процесса
12 и текущих выплат по проектам. Если F/, - средства на счете инвестора в момент времени h, то до платежей по проектам капитал инвестора равен (\+i)*Fh.\-Пусть Ph = ij:tj
момент времени //. Платеж по проекту /, осуществляемый в момент h, равен с.Л_, . Поскольку стоимость денег (а, соответственно, и проектов) меняется со
временем, то осуществляется коррекция проектов в соответствии с темпом инфляции. Платеж, с учетом влияния инфляции, будет равен с.h_t * (1 + г)'.
J > j
Задача выглядит следующим образом: требуется каждому проекту Сопоставить в соответствие такое время его начала /,-, удовлетворяющее ограничениям (1) и (2), чтобы в любой момент времени выполнялось условие неразорения :
^ = 0+0^ + 1^,(1+^0 (4)
JePk
при h=0,I,...,T, а время финансирования всего портфеля было минимально, т.е.
Г->тіп. (5)
В случае, если ограничения (1) не заданы, поставленная задача всегда будет совместна, т.к. существует возможность накопления на банковском счёте инвестора суммы, достаточной для финансирования любого количества проектов.
Интерпретация задачи с точки зрения теории графов
Совокупность проектов может быть удобно представлена в виде взвешенного ориентированного ациклического графа, вершинами которого являются проекты, наличие дуги (Ci,Cj) означает, что проект С,- должен начинаться после проекта С,-, вес дуги равен соответствующему временному лагу kij. Назовём истоком вершину, имеющую только исходящие дуги. Будем считать, что вершины занумерованы таким образом, что наличие дуги {CitCj) означает, что /
13 В случае, если все проекты в портфеле связаны друг с другом, можно этот портфель представить в виду мульти-проекта (рисунок 2). Если начало финансирования проекта С/, не зависит от срока начала проекта С,-, то будем говорить, что kjrkij^Q.
Рисунок 2. Мульти-проект, представленный в виде графа
Каждая вершина С, имеет пометку Р{ - минимально возможное время начала его финансирования. Для проекта (вершины), принятого к финансированию, Pf=ti- Пометка вершины (проекта) Р, обладает следующими свойствами:
1)/>>0;
2)Pie[Ui,Vi];
3)Ру>/> + ^,/<;
При изменении пометки любой вершины производится пересчёт пометок всех вершин-наследников.
Целевая функция задачи будет выглядеть следующим образом:
max{/> + /,}-»min (6)
при выполнении условия (4).
Анализ сложности
Рассмотрим частный случай поставленной массовой задачи.
Пусть в рассматриваемой экономике нулевая инфляция, все проекты состоят
из одного, единичного платежа, инвестор располагает средствами,
достаточными для финансирования всех проектов, и нет ограничений на срок
начала финансирования проекта, то есть r=0, F_x>m, C/=(-l), Ut = 0, Vi ->оо,
i=l,2,...,т.
Если начало финансирования проекта С,, не зависит от срока начала проекта С,-, то будем говорить, что kjrkif=0.
В этом случае, задача (4), (6) может быть сформулирована в виде следующей задачи распознавания.
Задача 1
Условие: Дан граф G={C, К), в котором С - множество вершин (проектов), К- множество дуг, соединяющих эти вершины, и Q - некая оценка длительности финансирования портфеля.
Вопрос: Верно ли, что G содержит гамильтонов путь такой, что max{Pi+li}
Задача 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-полных задач - методов сокращения перебора вариантов при отыскании точного решения задачи и нетрудоёмких алгоритмов нахождения приближённого решения. Был предложен следующий порядок их применения:
Проекты упорядочиваются по одной из характеристик: NPV, MM, R, далее к ним применяется принцип «первый подходящий» (First Fit);
С помощью метода ветвей и границ находится квазиоптимальный вариант, т.е. наилучший среди тех, которые можно получить при всевозможных
упорядочиваниях проектов с условием их запуска в минимально возможный момент времени (также учитываются ограничения, наложенные на срок начала финансирования проекта).
Сложность предложенного алгоритма имеет порядок п\. Сложность точного решения имеет порядок к", где к- оценка сверху максимальной длительности финансирования портфеля, п - число проектов.
На основе этого алгоритма был создан программный продукт для случая, когда не заданы ограничения (1) и (2), то есть проекты не имеют никаких предустановленных ограничений на срок начала финансирования.
Рисунок 3. Экранная форма программы
На базе этого программного продукта был проведён ряд вычислительных экспериментов для исследования качества получаемого решения.
17 1. Был проведен вычислительный эксперимент для оценки качества решений, полученных эвристическим алгоритмом, в сравнении с оптимальным (методом полного перебора). Использовались следующие исходные данные:
длина проектов - 8 лет;
количество проектов в портфеле - 8;
процентная ставка - 0,1;
темп инфляции - 0,08;
начальный капитал - 200;
границы выплат -(-100; 100).
Было проведено 200 экспериментов, проекты генерировались случайно, в соответствии с равномерным законом распределения. Средние значения целевой функции приведены в таблице 1, среднее время работы алгоритма приведено в таблице 2.
Таблица 1.
За единицу в этой таблице принято оптимальное значение целевой функции.
Таблица 2.
Видно, что предлагаемый алгоритм даёт решение, близкое к оптимальному, при значительной экономии вычислительных ресурсов.
2. Был проведён эксперимент, в котором анализировалось влияние, как продолжительности исходных проектов, так и их числа на качество и время приближенного решения задачи, полученного эвристическим алгоритмом.
В частности рассматривались портфели из 5-20 случайных проектов с длительностью 10 лет каждый и портфели из 10 проектов с длительностью от 5 до 20 года. В каждом случае проводилось 250 экспериментов. Сравнивались как значения целевой функции, так и время вычислений. Приведем соответствующие результаты.
Результаты исследования зависимости качества решения, предлагаемого алгоритмом «первый подходящий», от исходной сортировки сведены в график 1. Число проектов в портфеле фиксировано - 10, длительность проекта меняется.
График 1
Зависимость от исходной сортировки
На графике 2 приведено исследования для фиксированной длительности проекта. Все проекты длятся 10 лет. Количество проектов в портфеле меняется.
График 2.
На графике 3 приведена зависимость времени решения задачи методом «первый подходящий» при начальной сортировке по Rent от её начальной размерности. По очереди фиксировались длительность проекта и количество проектов в портфеле на уровне 10. Значение второго параметра менялось соответственно от 5 до 20.
График 3.
размерности на время решения
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Значение аргумента
В таблицах 3 и 4 приведены время и результаты решения задачи методом «первый подходящий» (при разных начальных сортировках) и методом ветвей и границ.
21 Таблица 3. Результат, получаемый при фиксированной длительности
проекта (5 лет).
Под результатом решения здесь понимается средняя длина получаемого портфеля.
Таблица 4. Время работы алгоритма, получаемое при фиксированной
длительности проекта (5 лет), мс.
22 На основе проведённых вычислительных экспериментов были сделаны следующие выводы:
1. Как правило, предпочтительнее использовать первоначальную сортировку
по модифицированному индексу рентабельности (таблица 1).
2. Использование для решения поставленной задачи алгоритмов типа
первого подходящего даёт расписания, близкие к оптимальному при небольшой
размерности задачи, при существенной экономии вычислительных ресурсов
пользователя (таблица 2, 3).
3. Увеличение числа проектов в большей мере удлиняет процесс решения
задачи, нежели рост их продолжительности.
1 глава
Появление в российской экономической действительности различного рода паевых инвестиционных фондов, частным случаем которых являются пенсионные фонды, и стабилизация роста экономики привели к возникновению новых задач, требующих осмысления. В российской экономике появилась возможность вложения денег не только в спекуляции с ценными бумагами, но и в средне- и долгосрочные инвестиционные проекты, а значит, появилась необходимость выработки теоретических рекомендаций по управлению портфелями инвестиционных проектов. Эта проблема имеет множество сторон - это и проблема оценки эффективности инвестиционного проекта, и проблема оценки его общественной значимости, и многое другое. Подобные задачи только начинают рассматриваться российскими учёными.
Данная работа посвящена рассмотрению задачи оптимального календарного планирования финансирования портфеля инвестиционных проектов.
Приведём содержательное описание проблемы.
Прежде всего, мы предполагаем, что инвестор уже отобрал ряд проектов, которые отвечают его требованиям, обладают устраивающим его уровнем риска, и которые он хочет профинансировать в полном объёме.
В данной работе элиминировано влияние риска, поскольку мы полагаем, что инвестор может подобрать проекты либо с одинаковым, либо со сравнительно низким его уровнем.
Поскольку инвестор берёт на себя обязательство финансировать проекты в полном объёме, то предполагается, что у него есть возможность назначать срок начала его финансирования (далее - срок начала проекта). В случае, если у инвестора не хватает средств для финансирования всего портфеля сразу, возникает задача календарного планирования финансирования портфеля. Целью инвестора, в данном случае, является минимизация общего срока финансирования портфеля, поскольку его прибыль фиксирована и равна прибыли всего портфеля. Данный критерий оптимизации задачи является
24 новым для инвестиционной теории, т.к. для инвестиционных проектов, как правило, оптимизация проводится по критерию прибыльности.
Пусть инвестор располагает возможностью хранить деньги в банке, но не имеет возможности брать в банке ссуду. В таком случае, при планировании сроков проектов следует учитывать условие неразорения - средства инвестора в любой момент должны быть неотрицательными. Остаток средств, не используемых в текущем году для финансирования проектов, инвестора кладёт в банк, где они увеличиваются в соответствии с текущей банковской ставкой.
Сложность моделирования этой ситуации заключается в том, что стоимость денег изменяется со временем и в современной российской экономике влияние этого фактора настолько велико, что его необходимо учитывать при моделировании. Инвестиционный проект, реализация которого сегодня стоит п, через несколько лет будет стоить т. Кроме того, следует отметить, что проекты могут финансировать друг друга. То есть, расходы по одному проекту в текущем году, могут быть покрыты за счёт поступлений денежных средств по другому проекту в этом же году. Следовательно, каждое сочетание сроков начала проектов будет создавать новую затратную схему. Эта особенность значительно усложняет перебор вариантов финансирования портфеля и является важным отличием теории финансирования портфеля инвестиционных проектов от портфеля ценных бумаг.
В данной главе будут рассмотрены известные постановки задач дискретной оптимизации и методам их решения. Будет также рассмотрено их соответствие описанной проблеме.
1.1 Задачи теории расписаний
Изучением вопросов оптимального планирования и управления на сетевых структурах занимается теория расписаний - раздел дискретного программирования. Задачи теории расписаний, как правило, трудноразрешимы, хотя для некоторых из них существуют эффективные алгоритмы решения [118,113,12,36].
Предваряя формальный обзор основных задач теории расписаний, приведём краткое описание этой области оптимизационных задач.
Во всех моделях теории присутствует такой фактор, как время. Заранее известен набор заданий -работ, которые требуется выполнить, известен набор исполнителей этих работ, которых принято называть машинами (хотя в реальных задачах это могут быть, например, живые люди или группы людей) , и задан выбор технологических ограничений, описывающих множество допустимых способов выполнения исходного множества работ. В понятие «способ выполнения работ» могут входить различные аспекты: во-первых, определение набора используемых ресурсов и их количество (возможно, изменяющееся во времени); во-вторых, выбор исполнителя работы; и, в-третьих, определение расписания выполнения работ, т.е. моментов времени, когда начинает выполняться каждая работа или какая-то её часть (операция), в какие моменты происходят её прерывания и последующие возобновления. Зачастую определение способа выполнения работ сводится лишь к нахождению расписания. (Причём, если прерывания работ запрещены, то достаточно указать лишь момент начала каждой операции.) Для краткости, всякий способ выполнения работ будем называть «расписанием».
Наконец, в любой модели теории расписаний, как и вообще в моделях дискретной оптимизации, как правило, присутствует целевая функция, позволяющая оценивать качество того или иного допустимого расписания. В
1 Иногда вместо базисных понятий «работы» и «машины» используются термины «детали» и «станки». В монографии [118] для этой цели используются термины - «требования» и «приборы».
26 задаче теории расписаний требуется либо найти оптимальное расписание (на котором достигается минимум или максимум целевой функции - в зависимости от типа задачи), либо «построить» произвольное допустимое расписание, либо, наконец, доказать, что такого допустимого расписания не существует [28].
К задачам теории расписаний относятся:
-задачи упорядочения - минимизации функций на перестановках,
-задачи согласования - определение длительностей выполнения работ при конфликтующих потребностях работ в ресурсах,
-задачи распределения - при альтернативных технологиях выполнения работ.
Мы в дальнейшем будем рассматривать лишь задачи теории расписаний, связанные с упорядочением работ.
1.1.1 Задачи теории расписаний с одним обслуживающим прибором
Общая постановка.
Пусть имеется п заявок на обслуживание. Они обслуживаются одним прибором, соответственно, за /(1), t(2),...,t(n) единиц времени. Предполагается, что все заявки пришли в систему одновременно и ожидают обслуживания. Пусть/7,/) - функция штрафов за простой заявки с номером /, если её обработка завершится в момент времени /. Пусть r=(i( 1),/(2),...,/(«)) - перестановка из п натуральных чисел {\,2,...,п}, которая определяет порядок обработки заявок. Пусть Р - множество всех таких различных перестановок. Очевидно, что мощность этого множества есть п\. Обозначим через F(r) - суммарный штраф, получаемый за обработку заявок в порядке, определяемом перестановкой г. Тогда
F{r) = /(/(1),/(/(1))) + /(/(2),/(/(1) + /(/(2))) +
...+ /(/(/!), /(/(1)) + /(/(2)) +...+ /(/(11)))
27 При такой формализации задача одного обслуживающего прибора ставится как задача поиска такой перестановки из множества Р, на которой достигает минимальное значение критерий задачи F [112].
Примеры задач одного обслуживающего прибора.
Задача директора. Содержательное описание.
На прием к директору записалось несколько человек. Зная время на прием каждого, требуется в таком порядке принимать посетителей, чтобы суммарное время, проведенное посетителями в очереди на приём, было минимально.
Математическая модель.
Исходные параметры модели.
Пусть /=1,2,...,/и -номера посетителей, /(/) - время, необходимое на обслуживание посетителя с номером /, /=1,2,...,/77. Функции штрафов имеют вид Л/,/) = /, /=l,2,...,w.
Варьируемые параметры.
Обозначим через /=(/(1),/(2),...,/(/7)) - перестановку из п натуральных чисел, определяющую порядок приема посетителей. Через Р - обозначим множество всевозможных перестановок натуральных чисел {l,2,...,w}.
Ограничения математической модели.
геР (1.1.2)
Постановка оптимизационной задачи.
Критерий оптимальности для задачи директора имеет вид:
F(r) = //7/(/,1) + (т -1)/(/,2) +... + /(/,/77) -> min (1.1.3)
Задача мастера. Содержательное описание.
Мастер, придя на работу, обнаружил неисправными несколько станков. Имея в своем распоряжении одну ремонтную бригаду, требуется определить
28 такой порядок ремонта станков (потери от простоя станков различны и зависят от производительностей станков), чтобы суммарные потери от простоя станков были минимальны.
Математическая модель.
Исходные параметры модели.
Пусть /=1,2,...,т -номера станков, /(/) - время, необходимое на ремонт станка с номером /, /=1,2,...,/17. Функции штрафов имеют вид:
/(/,/) = c(l)t, /=1,2,...,/77.
Варьируемые параметры.
Обозначим через /=( /(1),/(2),...,/(/7)) - перестановку из п натуральных чисел, определяющую порядок ремонта станков. Через Р - обозначим множество всевозможных перестановок натуральных чисел {l,2,...,w}.
Ограничения математической модели.
гєР (J. 1.4)
Постановка оптимизационной задачи.
Критерий оптимальности для задачи мастера имеет вид:
F(r) = (/(1))/((0,1) + с(/(2))[/(/(1)) + /(/(2))] + ... + с(/(/77))[/(/(1))+ i
/(/(2)) + + t{i(m))] -> min
1.1.2. Задачи теории расписаний в общей постановке
Содержательное описание.
Есть несколько деталей, которые проходят обработку на станках. Задана матрица технологических маршрутов, определяющая порядок обработки деталей на станках, и матрица трудоемкостеи, определяющая времена обработки деталей на станках.
Допустимым расписанием обработки деталей на станках назовем порядок обработки деталей на станках, при котором одновременно на одном станке не может обрабатываться более одной детали, деталь может начинать обработку на очередном станке лишь после того, как её обработка закончилась на
29 предшествующем по технологии станке, и обработка деталей на станках происходит без перерывов до полного выполнения соответствующих операций.
Требуется найти такое допустимое расписание, время завершения выполнения всех операций для которого, - минимально.
Математическая модель.
Исходные параметры модели.
Пусть /-1,2,...,т, - номера станков,/=1,2,...,и - номера деталей.
Обозначим через R= ||r(i,j)| - тп матрицу технологических маршрутов,
элемент которой r(ij) - номер по порядку обработки детали с номером у на станке с номером / (элемент множества {1,2,...,т}).
Обозначим через Т = ||t(i,j)| - тп матрицу трудоемкостей, элемент
которой t(ij) - время выполнения работы с номером / на станке с номером /.
Варьируемые параметры.
Пусть X=|x(i,j) | - тп матрица неизвестных, элемент которой x{i,j) - время начала выполнения детали с номером/ на станке с номером /.
Пусть Y= |y(i,j)|| - тп матрица неизвестных, элемент которой y{i,j) - время окончания выполнения детали с номером/ на станке с номером /.
Пусть Z= ||z(i,j)|j - тп матрица неизвестных, элемент которой z{ij) - номер
по порядку (в расписании) обработки детали/ на станке /. Ограничения математической модели.
x(ij)>y(k,j), (1.1.6)
для всех к, для которых r(ij) > r(kj), i,kr=\,2,...,m,j=\,2,...,n.
y{i,j) = x(i,j) + /(/,/), (1.1.7)
/=I,2,...,m,/=l,2,...,«.
x(i,j)>y(i,k), (1.1.8)
если z(i,j) > z(i,k), i=l,2,...,m, j,k=l,2,...,n.
*(/,/) >0, y(i,j)>0, i = 1,2,...,m, / = l,2,...,w.
z(/,/)e{l,2,...,w}, / = 1,2,...,/и, / = 1,2,...,n. (1.1.9)
Здесь ограничения (1.1.6) означают, что начало обработки детали с номером j на станке с номером / может наступить не раньше, чем завершится обработка этой детали на всех станках, предшествующих для этой детали станку с номером /.
Ограничения (1.1.7) означают, что обработка деталей на станках происходит без перерывов.
Ограничения (1.1.8) означают, что начало обработки детали с номером у* на станке с номером / может наступить не раньше, чем на этом станке завершится обработка предшествующих по расписанию деталей.
Ограничения (1.1.9) являются естественными условиями на введенные переменные.
Постановка оптимизационной задачи.
В качестве критерия оптимальности для задачи теории расписаний в общей постановке выбирается функционал:
/7(Jf,7,Z) = max2(/,7')->min, /=1,2,...,w, j = l,2,...,n (1.1.10)
'J
Критерий (1.1.10) означает минимизацию времени завершения обработки деталей на станках.
1.1.3 Задача Джонсона и графики Ганта
Если порядок обработки деталей на станках одинаков, то такие задачи называются задачами Джонсона (по имени американского математика СМ. Джонсона, изучавшего такие задачи). В этих задачах, не уменьшая общности, предполагается, что порядок обработки каждой детали совпадает с естественной нумерацией станков. Среди задач Джонсона особая роль принадлежит задачам с двумя обслуживающими приборами (двумя станками), для которых Джонсон разработал эффективный алгоритм решения [24, 109].
Пусть у-1,2,...,« - номера деталей, A(j) и B(j) , соответственно, времена обработок детали с номерому на первом и втором станках,у=1,2,...,и.
Обозначим через x(j) - время простоя второго станка непосредственно перед началом обработки детали с номерому',у'=1,2,...,я.
Тогда критерием оптимальности задачи Джонсона с двумя станками станет функционал
Пх) = 2>(y)->min (1.1.11)
7=1
Нетрудно показать, расписание обработки деталей на станках задается перестановкой г натуральных чисел из множества {1,2,...,п). Если г=(1,2,...,л), то х(\)=А(1), х(2)= max {А{\)Щ2) - ВД - *(1), 0}, -,
^х(У) = max {A(l)+...+A(n) - 5(1)-...-5(«-1),...Д1)+...+Л(/) - 5(1)-...-5(/-1),...,
7=1
Д1)}.
Пусть г nq две перестановки г=(1,2,...,я), #=(1,2,. ..J-IJ+IJ,...,«). Пусть F{r)
тах{А(1)+А(2)+...+А0) - B(l)-B(2)-...-B(j-l), А(1)+А(2)+...+А(/+1) -
B(l)-B(2)-...-B(j)}
Вычтем из левой и правой частей неравенства (1.1.12) величину A(\)+A(2)+...A(j+l) - 5(1)-5(2)-...-5(/4).
Получим, после несложных преобразований,
mm{A(j +1), ВЦ)} > mm{A(j), B(j +1)} (1.1.13)
Отсюда работа/ выполняется раньше работыу'+1, если выполняется условие (1.1.13).
Вышедоказанное позволяет сформулировать алгоритм Джонсона построения оптимального расписания выполнения работ на двух станках [82]: Шаг 1. Найти минимальную величину среди AQ) и 5(j),y'=l,2,...,/?. Шаг 2. Если минимум достигается на A(j), то деталь с номером/ ставится на обработку самой первой, если на 5(/), то деталь с номером j ставится на
32 обработку последней, деталь с номером у исключается из рассмотрения, и процесс построения расписания продолжается с шага 1.
Построенные расписания наглядно отображаются с помощью так называемых графиков Ганта или Гант-карт.
График Ганта - это графическое отображения расписания, в котором каждому станку соответствует своя ось времени.
1.1.4 Постановка задачи теории расписаний как задачи частично-целочисленного линейного программирования
Как и в разделе 1.1.2, пусть /=1,2,...,т, - номера станков, j=\,2,...,n - номера деталей, R= |r(i,j)| - тп матрица технологических маршрутов, элемент
которой r(ij) - есть номер по порядку обработки детали с номером/ на станке с номером / (элемент множества {l,2,...,m}), Т= |t(i,j)| - тп матрица
трудоемкостей, элемент которой t(ij) - означает время выполнения работы с
номером у на станке с номером /.
В качестве варьируемых параметров математической модели выберем:
Х= |x(i,j)| - тп матрицу неизвестных, элемент которой x(ij) означает
время начала обработки детали с номером у на станке с номером /, /=1,2,...,т, 7=1,2,...,«;
y(i,j,k)=\, если на станке с номером / деталь с номером/ обрабатывается раньше детали с номером к,
y(i,j,k)=0, если на станке с номером / деталь с номером к обрабатывается раньше детали с номером у;
/ - вспомогательная переменная, определяющая время завершения выполнения всех работ.
Ограничения математической модели.
x(i,j)-x(i,k)>t(i,k) umk(i,k)-x(i,j)>t(i,j), /=l,2,...,m,y=1,2,...,я (1.1.14)
Одновременно на станке / не могут выполняться работы с номерами/ и к:
33 x(i,j)-x(k,j)>t(k,j), еслиr(k,j)
Деталь с номером j переходит на обработку следующий станок лишь после того, как она пройдет полную обработку на предшествующем по технологии станке.
x(i,j) + t(i,j)
Общее время завершения выполнения всех работ не превышает величины t,
x(i,j)>0, / = l,2,...,m,;'= 1,2,...,/7 (1.1.17)
Естественные ограничения на введенные переменные. В построенной модели не формализованными являются условия (1.1.14). Для формализации условий (1.1.14) введем параметр Q -достаточно большое число.
Тогда рассмотрим ограничения (1.1.18):
(Q + t(i, к)) у (і, j, к) + x(i, j) - x(i, к) > t(i, к),
I — і, Z,..., /77, J == 1, Z,..., /7, К = 1, Z,..., 77, J 9- /v.
(Q + /(/.7))0 -yOJM + x(i,k)- x(i,j)> t(i,j), (i-w
I — 1, Z,..., /77, J -— 1, Z,..., /7, К — 1, Z,..., 77, J J- /v.
- пусть x(ij) - x(i,k), тогда если y(ij,k) = 1, то из (1.1.18) получаем:
Q+t(i,k)+x(i,j) -x(i,k)= Q+t(i,k)> t(i,k), что всегда верно,
x(i,k)- x(i,j) = 0>/(/j), т.к. t(i,j)<0, то t(i,j) = 0, а это означает, что деталь с номером / не проходит обработку на станкеу,
если y(i,j,k) = 0, то t(i,k)=0, т.е. деталь с номером j не обрабатывается на станке /;
пусть x{i,j) > x(i,k), т.е. деталь с номером/ выполняется после детали к, т.е. y(i,j,k)= 0, тогда из условий (1.1.18) получим x(i,j)- x(i,k)>t(i,k), т.е. условия (1.1.14) выполняются;
пусть x(ij) < x(i,k), т.е. деталь с номером у выполняется раньше детали к, T.Q.y(iJ,k)=\, тогда из условий (1.1.18) получим:
34 Q+x(i,j)> x(i,k), что всегда верно, x(i,k)-x(ij)> t(i,j), т.е. условия (1.1.14) выполняются. Таким образом, математическая модель приобретает вид (1.1.18), (1.1.15), (1.1.16), (1.1.17), и к ней добавляются естественные условия на переменные:
y(i,j,k) є {0,1}, i = l,2,...,m,j = \,2,...,n, к = \,2,...,п (1.1.19)
Постановка оптимизационной задачи.
В качестве критерия оптимальности выбирается функционал
F(t) = r->min (1.1.20)
Полученная задача (1.1.15) - (1.1.20) является задачей частично-целочисленного линейного программирования с числом ограничений М=тп(п+т-\)+\ и числом переменных N=mn(n+\)/2 +1.
1.1.5 Общая модель обслуживающих систем
Модель.
Задана многостадийная обслуживающая система, состоящая из конечного множества работ J={Ji,...,Jn}, для выполнения которых имеется конечное множество машин M={Mi,...,MmJ- Каждая работа J. є J состоит из множества операций:О' = {ol,...,o'r}. (Иначе говоря, процесс выполнения каждой работы
состоит из нескольких стадий, откуда и проистекает название «многостадийные».) На каждом множестве операций 0, Jt є J, заданы
отношения предшествования и несовместности в виде редуцированного смешанного графа G,~{0 ;Uj,Ej), где О - множество вершин, Ц— множество дуг, Ej - множество ребер. Наличие дуги {o',o")eU. в графе G, означает, что
операция о" не может начаться раньше, чем закончится операция о'. (Это отношение может быть записано также в виде о'-^о".) Наличие ребра (о',о") е Ej означает, что операции о', о" не могут выполняться одновременно.
Для каждой операции о{ задано множество допустимых исполнителей
35 M]q qM ; операция oj может выполняться на любой машине из множества MJq;
при этом время её выполнения p'q (длительность операции) не зависит от
выбора исполнителя Мі єМДІП]. Также предполагаются выполненными
следующие условия:
все работы готовы к выполнению в начальный (нулевой) момент времени;
все работы независимы (они не связаны отношениями предшествования и нет условий предпочтения в виде директивных сроков);
все операции неразрывны;
в каждый момент времени на каждой машине выполняется не более одной операции.
Частные случаи.
Опишем некоторые наиболее известные частные случаи описанной модели, представляющие самостоятельный интерес и играющие важную роль в современной теории расписаний.
Обслуживающая система, в которой операции любой работы J. є J
могут выполняться в любом порядке, но никакие две операции o',o"eOJ не могут выполняться одновременно (что выражается
условиями Uj = 0, Ej = О1 х 0J \ Up, о) \ о є О11, Jj є J), называется
системой открытого типа [116, 19, 26]. Если дополнительно
предполагается г. = т,
= 1 и MJq nMJp=0yp,q,j (т.е. машина-исполнитель для каждой операции задана однозначно, и каждая работа имеет ровно по одной операции на каждой машине), то получаем систему open shop (OS) [16, 38, 41, 10].
Если для каждой работы J. є J на множестве О1 задан линейный
порядок (т.е. граф редукции Gj состоит из единственной цепи о{'-»02-»...—»о/.), а исполнитель каждой операции oJq задан
однозначно ( MJq' = 1), то получаем системуу'об 5/20/? (JS). Легко видеть, что в системе job shop каждая работа J. є J имеет заранее заданный
маршрут прохождения машин, и этот маршрут может быть различным
для различных работ [22, 8 ,; . ].
Если J ' 1 9і j * я р при Ч*у> и На каждом
множестве О задан линейный порядок:
о/-»02у-+...-»0/, (1.1.21) то обслуживающая система называется системой поточного типа. В
= 1,V<7,
частном случае, когда
и г=т, такая система известна под названием flow shop (коротко, FS). Таким образом, в системе flow shop для каждой работы задан маршрут её прохождения по машинам, и этот
маршрут ( і' 2''"'«) одинаков для всех её работ. (Отсюда следует, что операция < выполняется на машине МІ) [20, 29, 37, 11].
Расписания.
Процесс функционирования обслуживающей системы может быть описан путём задания расписания S, в котором указывается, когда и на каких машинах выполняется каждая операция oJg. Поскольку в рассматриваемых нами моделях
все операции неразрывны, то каждая из них выполняется только на одной машине (обозначим её M(oJq)) и только в одном непрерывном интервале
времени [^,5^+/?М, однозначно задаваемом своим левым концом
^(временем «старта» операции в расписании S). Таким образом расписание
37 задаётся парой: множеством \sJq\qeD , ;Jj eJ\ неотрицательных чисел sq и
функцией M:O^M, где 0 = иу0у- множество всех операций работ /у.є,/;М(о^)єЛ/^Уо?;єО [7]. В случае, когда Mq =l,\/j,q,, функция М
однозначно определена условиями задачи, поэтому остаётся найти лишь множество \sq), которое в этом случае и будем называть расписанием.
Расписание называется допустимым, если оно удовлетворяем всем требованиям данной обслуживающей системы.
Для оценки качества расписаний во всех рассматриваемых системах будет использоваться целевая функция
CmJS) = max(sJq+pJq),
называемая длиной расписания S. Оптимальным расписанием (Sopt) называется расписание, на котором достигается минимум функции Cmax(S)ua множестве всех допустимых расписаний. Расписание S t будем называть также расписанием наименьшей длины.
1.1.6 Анализ соответствия приведённых моделей и описанной проблемы
Рассмотрим наиболее существенные, на наш взгляд, отличия проблемы, описанной во введении к данной главе, от стандартных задач теории расписаний.
1. Отсутствие составляющей, аналогичной понятию «машины». Количество проектов, которые одновременно может профинансировать инвестор, определяется не неким фиксированным числом «машин», а сочетанием средств, которыми располагает инвестор, и средств, которые требуются для финансирования рассматриваемых проектов. Это сочетание не является статичным и принимает свои значения для каждого сочетания
38 располагаемых в данный момент средств инвестора и финансируемых проектов.
Изменяемость «работ». Инфляция оказывает важное влияние на экономическую ситуацию в стране, поэтому необходимо делать пересчёт проектов в соответствии с неким инфляционным коэффициентом. Традиционная же модель теории расписаний не предусматривает изменения ресурсной составляющей рассматриваемых работ.
Возможное сочетание одно- и многостадийных проектов. В один и тот же портфель инвестор может отобрать как моно-, так и мульти- проекты. Рассмотренные модели не учитывают возможности такого сочетания.
Приведённые отличия говорят о том, что для применения теории расписаний к инвестиционной практике необходимо внести существенные коррективы в описанную в параграфе 1.1.5 модель.
1.2. Задачи ресурсного планирования комплексов работ
При постановке задач ресурсного планирования предполагается, что проект описан в виде комплекса работ с определенными зависимостями между ними. Зависимости между работами отображаются в виде сетевого графика (сети).
Существуют два способа изображения работ в сетевом графике. В первом способе работы изображаются в виде вершин сети, а зависимости между работами - в виде дуг сети. Во втором способе вершины сети соответствуют событиям сети, то есть моментам завершения одной или нескольких работ, а дуги - работам сети, при этом, для отображения всех требуемых взаимосвязей иногда приходится вводить дуги специального вида - фиктивные работы (можно считать, что такие дуги соответствуют работам нулевой продолжительности, не требующим ресурсов) [44]. На рис. 1.2.1.а приведен комплекс работ в виде «вершина - работа», а на рис. 1.2.1.6 этот же комплекс представлен в виде «вершина - событие» (зависимость, соответствующая
фиктивной работе показана пунктиром). В скобках на рис. 1.2.1.6 указаны номера работ рис. 1.2.1.а, которым соответствуют дуги рис. 1.2.1.6.
Как правило, будем применять изображение комплекса работ в виде «вершина - работа».
Для полного описания комплекса работ необходимо задать описание каждой работы [48].
о
-к 4
а) б)
Рис. 1.2.1.
Важной характеристикой работы является ее объем W. Он определяется на основе нормативов, экспертных оценок или имеющегося опыта. Объем может измеряться в единицах трудоемкости, стоимости и т.д.
Следующей характеристикой работы является ее продолжительность (время выполнения) [49]. В простейшем случае работа описывается величиной продолжительности и количеством требуемых для ее выполнения ресурсов. В этом случае будем говорить, что работа выполняется с фиксированной интенсивностью. Тогда объем работы для решения задачи ресурсного планирования не нужен, он используется при контроле хода реализации проекта. Если количество ресурсов на работу может принимать различные значения, то и продолжительность работы тоже может быть разной. При этом, если количество ресурсов в процессе выполнения работы не меняется, то будем говорить, что работа выполняется с постоянной интенсивностью. Для описания работы, выполняемой с постоянной интенсивностью достаточно задать продолжительность работы при различных уровнях ресурсов, то есть
40 зависимость т(и), где и - количество ресурсов, выполняющих работу.
Отношение
Ки) = -7Т 0-2.1)
т(и)
определяет интенсивность выполнения работы (производительность участвующих в работе ресурсов), которую мы будем называть скоростью выполнения работы (или просто - скоростью работы). Из выражения (1.2.1) видно, что скорость измеряется объемом работ, выполняемым в единицу времени. Без ограничения общности можно принять, что скорость работы является неубывающей функцией количества ресурсов.
Заметим, что одновременное увеличение (уменьшение) и объема, и скорости работы в одно и то же число раз не изменяет ее продолжительности. Следовательно, и величина объема, и его единица измерения могут быть выбраны произвольно. Как правило, единица измерения объема выбирается из содержательного смысла.
Наиболее сложным является случай, когда работа может выполняться с переменной интенсивностью, то есть количество ресурсов на работе может меняться в процессе ее выполнения [60]. Для описания работы в этом случае необходимо задать ее объем W и зависимость w = flu) скорости работы от количества выполняющих ее ресурсов. Обозначим через u(t) количество ресурсов на работе в момент времени t, th - момент начала работы, 4 - момент ее окончания. Имеет место соотношение:
'*
jf[u(t)]dr = W (1.2.2)
Типичный вид зависимости скорости операции от количества ресурсов приведен на рис. 1.2.2. Сначала с ростом количества ресурсов средняя производительность растет, а затем она начинает падать.
РОССИЙСКАЯ ІСУДАРСТВЕННАЯ БИБЛИОТЕКА
./
Рис. 1.2.2. На практике применяются более простые - либо линейные зависимости вида
0,и<а
f{u) = \a,a
b,b
либо степенные вида /(и) = иа(как правило, а< 1).
Важной характеристикой работы являются затраты ресурсов
S = \и{т)<іі
(1.2.4)
(прямые затраты сырья, материалов, трудозатраты, финансовые и т.д.). В ряде случаев ограничения наложены на затраты ресурсов на работу. Очевидно, что с ростом затрат продолжительность работ не увеличивается при разумном использовании ресурсов. Определим зависимость продолжительности работы t от затрат на ее выполнение при заданной зависимости скорости работы от количества ресурсов, предполагая, что ресурсы распределяются оптимально. Примем сначала, что зависимость Дм) является вогнутой дифференцируемой функцией, то есть, для любого 0 < а < 1 и любых щ и м2 /{ащ +(\-а)и2)> а/(щ ) + (1- а)Ди2).
Теорема 1.1 [48]. Оптимальному распределению ресурсов соответствует выполнение работы с постоянной интенсивностью.
42 Доказательство. Пусть работа выполняется за время t периодов. Поставим задачу распределить затраты по периодам так, чтобы объем выполненной работы был максимальным, то есть
при ограничении
*=i где щ - количество ресурсов в периоде к. Применяя метод множителей Лагранжа получим необходимое условие оптимальности:
Ащ) = Л,к = \ + Т
Следовательно, ик = и для всех к. Учитывая, что ит = S и f(u)xr = W, получаем:
f(-)xr = W. (1.2.5)
Из этого уравнения определяется зависимость t(S) либо S(t).
у Пример 1.2.1. Пусть f(u) = и/а,а>\. Имеем:
S V
Из этого уравнения получаем
W1 В случае а = 2, 5"(г) = —.
Заметим, что в случае линейной зависимости затраты равны объему работы W. Если величину затрат умножить на стоимость единицы ресурса, то получим стоимость работы, которая является основой формирования сметы и бюджета проекта. Если зависимость f(u) имеет произвольный вид (например, задана в
43 конечном числе точек), то строим вогнутую зависимость, максимально близкую к заданной. Способ построения ясен из рис. 1.2.3.
'і «
Рис. 1.2.3. Далее для заданной продолжительности т определяем и* и соответственно S = ut, принимая полученную вогнутую зависимость за истинную. Представим точку и* как выпуклую линейную комбинацию ближайших точек и/ и и2:
и =аи1 +(]-а)и2,0<а<1. Очевидно, что
f{u) = af{ux) + (\-a)f{u2). (1.2.6)
Задачи теории расписаний с одним обслуживающим прибором
На прием к директору записалось несколько человек. Зная время на прием каждого, требуется в таком порядке принимать посетителей, чтобы суммарное время, проведенное посетителями в очереди на приём, было минимально. Математическая модель. Исходные параметры модели. Пусть /=1,2,...,/и -номера посетителей, /(/) - время, необходимое на обслуживание посетителя с номером /, /=1,2,...,/77. Функции штрафов имеют вид Л/,/) = /, /=l,2,...,w. Варьируемые параметры.
Обозначим через /=(/(1),/(2),...,/(/7)) - перестановку из п натуральных чисел, определяющую порядок приема посетителей. Через Р - обозначим множество всевозможных перестановок натуральных чисел {l,2,...,w}. Ограничения математической модели. геР (1.1.2) Постановка оптимизационной задачи. Критерий оптимальности для задачи директора имеет вид: F(r) = //7/(/,1) + (т -1)/(/,2) +... + /(/,/77) - min (1.1.3) Задача мастера. Содержательное описание.
Мастер, придя на работу, обнаружил неисправными несколько станков. Имея в своем распоряжении одну ремонтную бригаду, требуется определить такой порядок ремонта станков (потери от простоя станков различны и зависят от производительностей станков), чтобы суммарные потери от простоя станков были минимальны. Математическая модель. Исходные параметры модели.
Пусть /=1,2,...,т -номера станков, /(/) - время, необходимое на ремонт станка с номером /, /=1,2,...,/17. Функции штрафов имеют вид: /(/,/) = c(l)t, /=1,2,...,/77. Варьируемые параметры.
Обозначим через /=( /(1),/(2),...,/(/7)) - перестановку из п натуральных чисел, определяющую порядок ремонта станков. Через Р - обозначим множество всевозможных перестановок натуральных чисел {l,2,...,w}. Ограничения математической модели. гєР (J. 1.4) Постановка оптимизационной задачи. Критерий оптимальности для задачи мастера имеет вид: F(r) = (/(1))/((0,1) + с(/(2))[/(/(1)) + /(/(2))] + ... + с(/(/77))[/(/(1))+ i /(/(2)) + t{i(m))] - min Содержательное описание.
Есть несколько деталей, которые проходят обработку на станках. Задана матрица технологических маршрутов, определяющая порядок обработки деталей на станках, и матрица трудоемкостеи, определяющая времена обработки деталей на станках.
Допустимым расписанием обработки деталей на станках назовем порядок обработки деталей на станках, при котором одновременно на одном станке не может обрабатываться более одной детали, деталь может начинать обработку на очередном станке лишь после того, как её обработка закончилась на предшествующем по технологии станке, и обработка деталей на станках происходит без перерывов до полного выполнения соответствующих операций. Требуется найти такое допустимое расписание, время завершения выполнения всех операций для которого, - минимально. Математическая модель. Исходные параметры модели. Пусть /-1,2,...,т, - номера станков,/=1,2,...,и - номера деталей.
Обозначим через R= r(i,j) - тп матрицу технологических маршрутов, элемент которой r(ij) - номер по порядку обработки детали с номером у на станке с номером / (элемент множества {1,2,...,т}). Обозначим через Т = t(i,j) - тп матрицу трудоемкостей, элемент которой t(ij) - время выполнения работы с номером / на станке с номером /. Варьируемые параметры. Пусть X=x(i,j) - тп матрица неизвестных, элемент которой x{i,j) - время начала выполнения детали с номером/ на станке с номером /. Пусть Y= y(i,j) - тп матрица неизвестных, элемент которой y{i,j) - время окончания выполнения детали с номером/ на станке с номером /. Пусть Z= z(i,j)j - тп матрица неизвестных, элемент которой z{ij) - номер по порядку (в расписании) обработки детали/ на станке /.
Постановка задачи теории расписаний как задачи частично-целочисленного линейного программирования
Рассмотрим наиболее существенные, на наш взгляд, отличия проблемы, описанной во введении к данной главе, от стандартных задач теории расписаний.
1. Отсутствие составляющей, аналогичной понятию «машины». Количество проектов, которые одновременно может профинансировать инвестор, определяется не неким фиксированным числом «машин», а сочетанием средств, которыми располагает инвестор, и средств, которые требуются для финансирования рассматриваемых проектов. Это сочетание не является статичным и принимает свои значения для каждого сочетания располагаемых в данный момент средств инвестора и финансируемых проектов.
2. Изменяемость «работ». Инфляция оказывает важное влияние на экономическую ситуацию в стране, поэтому необходимо делать пересчёт проектов в соответствии с неким инфляционным коэффициентом. Традиционная же модель теории расписаний не предусматривает изменения ресурсной составляющей рассматриваемых работ.
3. Возможное сочетание одно- и многостадийных проектов. В один и тот же портфель инвестор может отобрать как моно-, так и мульти- проекты. Рассмотренные модели не учитывают возможности такого сочетания.
Приведённые отличия говорят о том, что для применения теории расписаний к инвестиционной практике необходимо внести существенные коррективы в описанную в параграфе 1.1.5 модель.
1.2. Задачи ресурсного планирования комплексов работ
При постановке задач ресурсного планирования предполагается, что проект описан в виде комплекса работ с определенными зависимостями между ними. Зависимости между работами отображаются в виде сетевого графика (сети).
Существуют два способа изображения работ в сетевом графике. В первом способе работы изображаются в виде вершин сети, а зависимости между работами - в виде дуг сети. Во втором способе вершины сети соответствуют событиям сети, то есть моментам завершения одной или нескольких работ, а дуги - работам сети, при этом, для отображения всех требуемых взаимосвязей иногда приходится вводить дуги специального вида - фиктивные работы (можно считать, что такие дуги соответствуют работам нулевой продолжительности, не требующим ресурсов) [44]. На рис. 1.2.1.а приведен комплекс работ в виде «вершина - работа», а на рис. 1.2.1.6 этот же комплекс представлен в виде «вершина - событие» (зависимость, соответствующая фиктивной работе показана пунктиром). В скобках на рис. 1.2.1.6 указаны номера работ рис. 1.2.1.а, которым соответствуют дуги рис. 1.2.1.6.
Как правило, будем применять изображение комплекса работ в виде «вершина - работа».
Для полного описания комплекса работ необходимо задать описание каждой работы [48]. Важной характеристикой работы является ее объем W. Он определяется на основе нормативов, экспертных оценок или имеющегося опыта. Объем может измеряться в единицах трудоемкости, стоимости и т.д.
Следующей характеристикой работы является ее продолжительность (время выполнения) [49]. В простейшем случае работа описывается величиной продолжительности и количеством требуемых для ее выполнения ресурсов. В этом случае будем говорить, что работа выполняется с фиксированной интенсивностью. Тогда объем работы для решения задачи ресурсного планирования не нужен, он используется при контроле хода реализации проекта. Если количество ресурсов на работу может принимать различные значения, то и продолжительность работы тоже может быть разной. При этом, если количество ресурсов в процессе выполнения работы не меняется, то будем говорить, что работа выполняется с постоянной интенсивностью.
Сетевые модели. Расчет временных характеристик сетевых моделей
Говорят, что задана сеть, если определено множество вершин и множество дуг, соединяющих эти вершины. Формально сеть задается ориентированным графом без петель и контуров, т.е. антирефлексивным бинарным отношением f=(V, А), где AczVxV, график которого А - определяет множество дуг, а множество, на котором бинарное отношение определено, V - является множеством вершин. Сетевой моделью называют сетевой график, элементам которого (либо вершинам, либо дугам, либо и тем и другим) поставлены в соответствие некоторые величины, называемые весами. Мы в дальнейшем будем рассматривать сетевые модели, в которых веса поставлены в соответствие дугам [96].
С помощью сетевой модели будем моделировать процесс производства некоторого нового изделия. Тогда вершины будут соответствовать моментам начала или окончания выполнения работ, дуги будут соответствовать условиям взаимозависимости выполняемых работ, а веса на дугах будут соответствовать ожидаемым длительностям выполнения работ.
Пусть i=\,2,...,m, - номера работ, /(/) - длительность выполнения работы і. Обозначим через К(ї) - множество работ, непосредственно предшествующих работе с номером / (условие, определяемое технологическими требованиями на порядок выполнения работ). Требуется определить минимально возможное время, за которое можно выполнить все работы.
Для решения этой задачи пользуются специальной схемой расчета временных характеристик, позволяющей не только дать ответ на поставленный вопрос, но и найти дополнительные характеристики, позволяющие более эффективно управлять процессом изготовления нового изделия [95].
К таким характеристикам относятся: t(rn, і) - время самого раннего начала выполнения работы с номером /, t(rk,i) - время самого раннего окончания выполнения работы с номером /, t(pn,i) - время самого позднего начала выполнения работы с номером /, t(pk,i) - время самого позднего окончания выполнения работы с номером /, r(i) - резерв времени работы с номером і, т.е. время, на которое не в ущерб времени общего окончания выполнения всех работ, можно задерживать выполнение работы с номером (/), Т(к) - время выполнения всех работ изделия.
Величина Т(к) называется длиной критического пути, а критическим путём называют путь, соединяющий некоторую начальную работу - не имеющую предшествующих работ, и некоторую конечную работу - не имеющую последующих, т.е. от неё зависящих работ, суммарное время выполнения всех работ которого, максимально.
Для расчета временных характеристик можно воспользоваться следующими рекуррентными соотношениями: t(rn,i) = О, если K(i) - пустое множество. t(rk,i) = t(rn, і) + t(i), t{m,i)= max t(rkj), где максимум берется по всем работам у из множества K(i). t(pk,i) = t(rk,i), если работа / не имеет последующих, t(pn,i) = t(pk,i)(i), t(pk,i) = min t{pn,j), где минимум берется по тем работам j, которые принадлежат множеству К{ї), т.е. по тем работам, от которых зависит работа с номером /. г(/) = t(pn,i) - t{rn,i) = t{pk,i) - t{rk,i). Работы критического пути это те работы, резервы времени которых нулевые.
Пусть G=(V,A) - взвешенный ориентированный (п,т) граф и R=r(i,j) его матрица весов, элемент которой r(i,j) - вес дуги (/,/), (i,j)eA. Пусть в графе G нет петель и контуров. Выделим в нём две особые вершины - вершину "исток" (и) и вершину "сток" (s). Вершины графа G мы будем интерпретировать как географические пункты, дуги - дороги их соединяющие, веса дуг - пропускные способности дорог, т.е. количество груза, которое можно перевезти по дороге в единицу времени. Таким образом построенную сетевую модель называют транспортной сетью. Задача поиска максимального потока в транспортной сети заключается в определении максимально возможного объема груза, который может быть перевезен из истока в сток по существующим дорогам с заданными пропускными способностями [96].
Реализация алгоритма
Данный параграф посвящен описанию исследовательского прототипа программы, созданного для вычислительного эксперимента, позволившего сделать выводы о применимости предлагаемого подхода к решению поставленной задачи и оценить его эффективность на небольших размерностях входных данных.
Описанный алгоритм был реализован для частного случая задачи, когда не заданы ограничения на срок начала финансирования проекта (2.2.1) и все проекты независимы друг от друга, то есть не заданы неравенства (2.2.2). Подобная задача при І г имеет решение: при достаточно длительном хранении средств в банке сумма на счёте будет достаточной для одновременного финансирования всех проектов [102].
На рисунке 3.3.1 приведена экранная форма программа, на которой видно процедуру ввода данных, необходимых для генерации проектов. В частности, там приводятся данные, используемые программой по умолчанию.
В первом поле ввода нужно ввести данные о количестве сессий генерации проектов. Одновременная обработка результатов нескольких сессий даёт возможность сбора статистических данных о длительности работы алгоритма и среднем времени финансирования портфеля инвестиционных проектов, получаемого разными подходами к решению задачи.
Во втором поле ввода следует ввести количество проектов, которые нужно генерировать в каждом эксперименте.
Третье поле ввода задаёт длительность каждого из проектов в портфеле. Как и предыдущее окно, это число будет одинаковым для всех экспериментов, проводимых в данной сессии.
В следующих двух полях ввода задаётся процентная ставка и темп инфляции. Вводимая в программу процентная ставка должна быть больше уровня инфляции. В противном случае, решение задачи резко усложняется. Числа задаются в абсолютном, а не относительном значении.
Затем вводятся критерий отбора проектов - уровень рентабельности, удовлетворяющий инвестора. Данные здесь также вводятся в абсолютном значении.
В нижнем окне этой вкладки задаются границы выплат, которые генерирует программа. Это сделано для уменьшения времени работы программы.
Также на этой вкладке доступны кнопки «Очистить поля» и «Считать». Нажатие на кнопку «Считать» ведёт к переходу на следующую вкладку «Промежуточные результаты», где появляются данные о первом из всех заданных эксперименте. Третья вкладка «Статистика» становится доступной лишь после того, как будет обработан последний из сгенерированных портфелей.
На рисунке 3.3.2 представлен результат работы программы в случае, если число экспериментов равно 1. В таблице «Проекты» приведены сгенерированные программой проекты. Платежи выведены в строках этой таблицы. В столбцах показаны /-ые платежи проектов. На рисунке 3.3.2 приведены данные для случая, когда сгенерировано 7 проектов.
Рассчитанные программой интегральные характеристики проектов приведены в таблице «Характеристики». Номер строки соответствует номеру проекта в предыдущей таблице.
В отдельном окошке «Начальный капитал» приведены средства инвестора в начальный момент времени. Для сокращения времени расчётов, мы взяли значение этой ячейки равным значению третьей ячейки отсортированного ряда показателя «Минимум средств». Как видно, для случая, приведённого на рисунке 3.3.2, начальный капитал инвестора составил 81.
В таблице «Расписания» приведены последовательности проектов, рассчитанные по четырём методикам. В первой строке таблице приведено общее время финансирования портфеля инвестиционных проектов. Далее в каждой строке показано время начала финансирования соответствующего проекта, получаемое с помощью различными методами составления расписаний.
В первом столбце приведено расписание, получаемое с помощью принципа первого подходящего (First Fit) с начальной сортировкой проектов по убыванию их чистого дисконтированного дохода (NPV).
Во втором столбце приведено расписание, получаемое с помощью принципа первого подходящего (First Fit) с начальной сортировкой проектов по возрастанию минимума средств, необходимых для их финансирования (ММ).
В третьем столбце приведено расписание, получаемое с помощью принципа первого подходящего (First Fit) с начальной сортировкой проектов по убыванию их рентабельности (Rent или PI).
В четвёртом столбце приведено расписание, получаемое с помощью метода ветвей и границ (Branch-Bound). В качестве верхней оценки допустимого расписания использовалась наименьшая длина расписания, получаемого с помощью принципа первого подходящего.
Третья закладка «Статистика» является служебной и использовалась для оценки работы программы.
