Календарное планирование инвестиционных проектов с кредитованием Казаковцева Евгения Андреевна

Содержание к диссертации

Введение

1 Задачи календарного планирования проектов 18

1.1 Общая постановка задачи календарного планирования 18

1.2 Задача календарного планирования инвестиционных проектов 25

1.3 Инвестиции и кредиты 32

1.4 Риски при реализации инвестиционных проектов 36

2 Календарное планирование инвестиционных проектов при возможности использования кредитов 39

2.1 Постановка задачи с кредитованием 40

2.2 Алгоритм решения задачи с кредитами 45

2.3 Оптимизация кредитов 51

2.4 Сложность задачи с кредитами 55

2.5 Максимизация прибыли инвестиционного проекта с независимыми работами единичной длительности 61

3 Календарное планирование инвестиционных проектов при случайных поступлениях дохода 68

3.1 Постановка задачи при случайных поступлениях дохода 70

3.2 Алгоритм оценки рисков незавершения проекта в задаче календарного планирования 73

3.3 Кредитование проектов при случайных поступлениях дохода 80

3.4 Подходы к решению задачи календарного планирования при случайных поступлениях дохода 83

3.5 Диверсификация и синергетический эффект 86

Заключение 92

Литература

• Задача календарного планирования инвестиционных проектов
• Алгоритм решения задачи с кредитами
• Максимизация прибыли инвестиционного проекта с независимыми работами единичной длительности
• Кредитование проектов при случайных поступлениях дохода

Введение к работе

Актуальность работы. Календарное планирование является одним из ключевых направлений теории оптимизации. Появившись в середине прошлого века, данная область в настоящее время продолжает свое бурное развитие. Причиной этому являются все новые классы задач, связанные с необходимостью построения расписаний. Такие задачи возникают в строительстве, на производстве, при планировании и запуске нового оборудования и так далее. Благодаря активному развитию экономики и технологий появляются новые задачи, решение которых зачастую зависит от правильно выбранной стратегии на этапе планирования. В настоящей работе речь идет о календарном планировании производственных инвестиционных проектов. Новейшие технологии и современные разработки в экономической сфере, а также оптимизация производственного и технологического процесса напрямую связаны с эффективностью вложения инвестиций. Оптимизация ресурсов и инвестиций выходит на первый план во многих международных сферах бизнеса. И одну из ведущих ролей в обеспечении производственной эффективности занимает грамотное планирование. Если в современном конкурентном рынке спроецировать планирование на временную шкалу, то оно занимает до 80% времени, прежде чем проект будет запущен. Например, в Японии – одной из наиболее технологически и информационно развитых стран, процесс планирования составляет до 90% времени проекта.

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

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

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

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

Задачи исследования. Для достижения цели поставлены и решены следующие задачи:

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

2. Исследованы модели задачи календарного планирования проектов при наличии рисков, возникающих в условиях неопределенности;

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

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

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

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

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

Апробация работы. Результаты диссертации опубликованы в работах [1–13], докладывались и обсуждались на следующих научных мероприятиях:

33 Региональной научно-практической студенческой конференции "Мо-4

лодежь третьего тысячелетия"(Омск, 2009 г.),

41 Всероссийской молодежной конференции "Проблемы теоретической и прикладной математики"(Екатеринбург, 2010 г.),

34 Региональной научно-практической студенческой конференции "Молодежь третьего тысячелетия"(Омск, 2010 г.),

Российской конференции "Дискретная оптимизация и исследование операций"(Новосибирск, 2010 г.),

XIV Всероссийской конференции "Математическое программирование и приложения"(Екатеринбург, 2011 г.),

V Международной школе-симпозиуме АМУР-2011 (Севастополь, 2011 г.),

V Всероссийской конференции "Проблемы оптимизации и экономические приложения"(Омск, 2012 г.),

Российской конференции "Дискретная оптимизация и исследование операций" (Новосибирск, 2013 г.),

XVI Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2014 г.),

а также на семинарах в Институте математики им. С.Л. Соболева СО РАН (Омск, Новосибирск).

Публикации. По теме диссертации опубликовано 13 работ, в том числе 3 статьи из списка ВАК.

Структура работы. Диссертация состоит из введения, трех глав, заключения, списка литературы (154 наименования), 5 рисунков.

Задача календарного планирования инвестиционных проектов

Задача календарного планирования проектов заключается в определении сроков выполнения технологически взаимосвязанных работ. Первые научные статьи в этой области появились еще в конце 50-х годов XX века. При проектировании ракетной системы "Полярис" была использована технология PERT (Program Evaluation and Review Technique) [74, 92]. Примерно в это же время при реконструкции заводов фирмы "Дюпон" был разработан метод критического пути [109, 110, 117]. Стоит отметить, что применение технологии PERT позволило завершить проект, состоящий из шестидесяти тысяч работ, на два года раньше планируемого срока. Эти технологии оказались настолько просты, наглядны и эффективны, что быстро получили широкое распространение. В русскоязычной литературе данное направление получило название "Сетевое планирование и управление" [8, 20]. Бурное развитие календарное планирование получило во второй половине двадцатого века с появлением работ коллективов, возглавляемых Бруккером П., Зуховицким С. И., Михалевичем В.С., Шкурбой В.В., Расселом А., Танаевым В.С., Гимади Э. Х. и так далее [7, 10, 12, 31, 32, 47, 59, 61, 75, 76, 104, 129, 136]. В настоящее время задачи календарного планирования проектов не потеряли своей актуальности. Наоборот, с развитием экономики многообразие рассматриваемых задач значительно расширились. Каждый год появляются все новые классы задач, требующие глубокого исследования, анализа вычислительной сложности, разработки как точных, так и приближенных алгоритмов их решения [9,18,30,34,62,70,80,90,93,112,114,115,119,120,124,135,152]. Прикладные работы по задачам календарного планирования ведутся и в институтах СО РАН. Например, в институте экономики и организации промышленного производства разрабатывается стратегия освоения нефтегазовых ресурсов Восточной Сибири и Дальнего Востока [50,51]. Рассмотрим ключевые понятия задач календарного проектирования.

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

Ресурсы. Различают два типа ресурсов: возобновимые [80] и невозоб-новимые. К первым можно отнести оборудование, рабочих, специалистов, производственные помещения и так далее. В российской литературе вместо понятия невозобновимые чаще используется термин складируемые, так как данный тип ресурсов является накопительным [7–10,20,30]. К складируемым ресурсам относятся расходные материалы, сырье, финансы и так далее. В каждый момент времени известны объемы всех типов ресурсов.

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

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

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

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

Риски. В условиях современной экономики, когда кризисные явления возникают все чаще, конкуренция возрастает, а курсы валют очень нестабильны, инвестору все сложнее назвать точную сумму будущего дохода от выполнения того или иного проекта. В такой ситуации возникает необходимость оперировать уже не детерминированными, а вероятностными величинами. В настоящей работе будем рассматривать постановку задачи календарного планирования проектов, когда поступления дохода от выполнения работ являются случайной величиной с заданной функцией распределения. Классификация, анализ рисков и алгоритмы сравнения расписаний в условиях неопределенности будут рассмотрены в главе 3. Многообразие задач календарного планирования очень велико. Опишем базовую модель задачи с ограниченными ресурсами. Пусть имеется проект, состоящий из множества работ V = {1, 2,..., N}, связанных отношением предшествования Е. Длительность выполнения работы pj будем считать целочисленной величиной. Рассмотрим ресурсы двух видов: складируемые и возобновимые. Соответствующие множества обозначим через А и В. На период планирования проекта в момент t, t = 0,1,... поступает Ka(t) единиц ресурса вида а Є А и во временном полуинтервале [t,t + 1) имеется Ka(t) единиц ресурса вида а Є В. Каждая работа j Є V характеризуется потребностью Щ{т) в ресурсе вида а Е A[J В в интервале [т т + 1), г = 0,1,... ,pj — 1, отсчитывая от начала выполнения этой работы. В некоторых постановках могут быть заданы директивные сроки dj Є Z+ завершения выполнения работы j Є V. Если они не играют роли, то полагаем директивные сроки достаточно большими. Предполагается, что каждая из работ выполняется непрерывно. Требуется определить такие сроки выполнения работ проекта с учетом технологического порядка, директивных сроков и ограничений на ресурсы, при которых достигается оптимальное значение некоторой целевой функции.

Алгоритм решения задачи с кредитами

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

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

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

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

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

Доказательство. Любой кредит однозначно определяет поток платежей, причем первый платеж - положительный, остальные - отрицательные. Декомпозируем кредит по годам. Определим последовательность потоков платежей, которая задается следующей процедурой [39]: по завершению года г полностью возвращаем кредит вместе с набежавшими процентами в объеме (1 + r)FT_i, а в начале следующего года оформляем новый кредит на сумму FT, чтобы соответствующая разность была равна платежу по исходному потоку. Последовательность потоков платежей

Такой подход позволяет ввести только один дополнительный тип переменных D{t) - размер кредита, взятого в год t, и модель с кредитами и реинвестированием дохода примет следующий вид: построить расписание выполнения работ S = (si, S2,..., sw), при котором - соблюдается технологический порядок выполнения работ Si + Pi Sj, [і-,]) Є Е] - в каждый момент времени t Є Z+ сохраняется неотрицательный платеж ный баланс с учетом взятых кредитов, выплат по ним, реинвестирования дохода и размещения свободного капитала под ставку г: E l Kit) —v с jit — Sj) Dit) — (1 + r)D(t — 1) \ \7 + / \7 " \7- — О? l (1+Го) - (1 + To) (1 + To) / – чистая приведенная прибыль с учетом выплат по кредитам достигает максимального значения: NPVj s— D(t) — (1 + r)D(t — 1) NPV(S) = h , ГТ max, где T - горизонт планирования проекта, D(—l) = 0 и D(T) = 0. Заметим, что суммарные поступления по проекту на заключитель т ный момент времени Т составят NPV (S)(l + Го)т + K(t)(l + ro)T_t, t=o т причем величины (1 + го)т и Х ( )(1 + го)Т 1 являются константами. t=o Таким образом, максимальные значения NPV(S) и итоговых поступлений достигаются одновременно. Данный факт верен и для частичных расписа ний, что важно при реализации описанного ниже алгоритма. В качестве аналога задачи с использованием кредитов можно рассмотреть задачу с платой за использование ресурсов. В [119] исследуется задача календарного планирования с возобновимыми ресурсами и критерием минимизации стоимости приобретаемых ресурсов. Отличие постановки, рассматриваемой в данной главе, заключается в том, что затраты на закупку ресурсов, т.е. кредиты, напрямую влияют на целевую функцию.

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

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

Часто проектными рисками называется возможное снижение показателей эффективности проекта, возникающее под влиянием неопределенности. Под количественным выражением риска понимается изменение численных характеристик проекта, таких как чистая приведенная прибыль (NPV ) или внутренняя норма доходности (irr). Отметим виды рисков: маркетинговый, общеэкономический, риск несоблюдения графика выполнения работ, риск превышения бюджета и так далее [16,25,28,58,67]. Маркетинговый риск – это риск недополучения ожидаемой прибыли по причине неверно спрогнозированного спроса, цены на конечный товар или состояния рынка. Он является одним из ключевых для любого инвестиционного проекта. В качестве примера можно привести отказ от реализации северных проектов Газпрома в 2012 году из-за разработок сланцевого газа. Риск несоблюдения графика проекта приводит к нарушению сроков выполнения работ, и, соответственно, к убыткам из-за недополученной вовремя прибыли. Риск превышения бюджета проекта возникает, если были неверно просчитаны затраты на выполнение работ проекта или изменилась рыночная ситуация. Данный вид риска может привести к полному отказу от реализации проекта по причине нехватки средств на его выполнение. Общеэкономические риски связаны с внешними факторами. К ним можно отнести изменения процентных ставок, курсов валют, изменение уровня инфляции, увеличение конкуренции, выхода на рынок новых предприятий и так далее. Риски также могут быть технологического, экономического, политического, социального, экологического, законодательно-правового характера.

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

В данной главе рассмотрены следующие типы рисков:

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

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

В параграфе 3.1 строится модель задачи календарного планирования инвестиционного проекта с учетом ограничений на финансовые ресурсы и реинвестирования получаемого дохода для случая, когда поступления от выполнения работ – случайные величины. Выделены характеристики, определяющие успешность того или иного расписания S. В параграфе 3.2 предложены алгоритмы вычисления параметров заданного расписания S. Так как вторая глава диссертации посвящена использованию кредитов в календарном планировании инвестиционных проектов, особое внимание следует уделить кредитному инвестиционному риску, который возникает, когда реализация проекта осуществляются за счет заемных средств. Привлечение кредитных средств значительно расширяет область допустимых действий в рамках проекта, в параграфе 3.3 алгоритм оценки рисков для заданного расписания обобщен для случая с кредитами. В разделе 3.4 предложены подходы к решению задачи календарного планирования в условиях неопределенности. Описаны некоторые известные метаэвристики. Как один из способов уменьшения риска используется диверсификация вложений, когда финансируется сразу несколько проектов, и потери в одном из них компенсируются прибылью в других. Такая ситуация рассмотрена в параграфе 3.5.

Кредитование проектов при случайных поступлениях дохода

Задача календарного планирования с критерием чистой приведенной прибыли является NP-трудной в сильном смысле, поэтому основными инструментами получения точных решений являются схемы направленного перебора. Большинство известных алгоритмов основано на методе ветвей и границ [79,85,128,140], также используется метод динамического программирования [52].

В случае двухкритериальной задачи "прибыль-риск" , описанной в параграфе 3.1, метод ветвей и границ использовать затруднительно, так как непонятно, по какому критерию производить отсев неперспективных вариантов. В конечном итоге выбор между рискованностью и прибыльностью проекта должен оставаться за инвестором, поэтому решением рассматриваемой задачи со случайными поступлениями дохода должно быть множество недоминируемых расписаний. Для таких целей хорошо подходят различные метаэвристики, работающие с популяциями решений. Целью данного параграфа не является разработка конкретных алгоритмов решения поставленных задач, так как существует достаточно много универсальных подходов, с которыми можно ознакомиться, например в [60]. В данном параграфе рассмотрим общие схемы работы некоторых их них.

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

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

Работа генетического алгоритма начинается с формирования конечного набора допустимых решений задачи, называемых начальной популяцией. Каждый шаг алгоритма можно разбить на несколько этапов: отбор кандидатов, операция скрещивания, мутация и обновление популяции. При отборе кандидатов рассматривается часть популяции, содержащая наиболее перспективных родителей. Формируются пары, и с помощью операции скрещивания строятся новые решения. Далее полученные решения подвергаются небольшим изменениям, называемым мутацией, и добавляются в популяцию. После чего происходит обновление популяции – отсев доминируемых вариантов. Данный процесс продолжается до тех пор, пока не выполнен критерий остановки. Генетические алгоритмы для задачи календарного планирования можно найти, например в [99,100].

Генетический алгоритм удобно использовать при решении двухкри-териальных задач, оставляя в популяции на каждой итерации недоминируемые решения. Алгоритмы расчета параметров заданного расписания, описанные в параграфе 3.2, позволяют применить любой из описанных подходов для решения рассмотренной в данной главе задачи календарно 85 го планирования с двумя критериями: максимизация чистой приведенной прибыли при минимизации рисков.

Для решения задачи с одним критерием, описанной в параграфе 3.3, можно также использовать эвристические алгоритмы [49,77,79,113,134,139, 145]. Одним их популярных алгоритмов решения задачи календарного планирования является алгоритм имитации отжига. Впервые данный подход был использован в 1983 году [111]. Он основан на имитации кристаллизации вещества. Исследование поведения атомов и кристаллической решетки при остывании тела привело к появлению вероятностных алгоритмов, оказавшихся эффективными для решения задач дискретной оптимизации. В настоящее время алгоритм имитации отжига является популярным благодаря тому, что для него удается аналитически доказать асимптотическую сходимость и исследовать свойства, а также благодаря своей простоте и эффективности применения.

Алгоритм имитации отжига является пороговым вариантом локального поиска. Пусть задан некоторый порог Рт. На каждом шаге алгоритма выбирается некоторое решение S в окрестности текущего решения STO, и если разность целевой функции по новому и текущему решению не больше Рт, то решение S становится новым текущим решением. Иначе выбирается другое решение из окрестности. В [81] предложен алгоритм, использующий в качестве кодировки решения вектор значений приоритета. В [78] применяется кодировка в виде списка.

Другим распространенным вариантом метода локального поиска является поиск с запретами (Tabu search). Впервые данный алгоритм был предложен Ф. Гловером. В работе [97] он описал принципиально новую схему алгоритма локального поиска. Смысл ее заключается в том, что алгоритм не останавливается в точке локального оптимума, как это происходит в стандартном варианте, а переходит от одного локального оптимума к другому. Этот переход становится возможен благодаря механизму под названием "список запретов" . Список строится по нескольким последним решениям и запрещает часть окрестности текущего решения N(Sm). Очередное решение STO+i является оптимальным решением подзадачи /(STO+i) = max{/(S)j Є N(Sm) \Tabuh(Sm)} где /(S) - значение целевой функции решения S, а h 0 - константа, определяющая память алгоритма. Если h = О, получаем стандартный алгоритм локального поиска. Список запретов обычно запрещает использование тех частей решения, которые менялись на последних h шагах алгоритма. Кроме того, учитывается специфика задачи. Различные алгоритмы поиска с запретами рассматриваются в [14,68,106,122,146,153].