Полная версия

Главная arrow Логистика arrow Методы управления инвестициями в логистических системах

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

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

Общая постановка задачи состоит в следующем. Пусть необходимо выполнить проект, состоящий из п этапов, технологическая последовательность выполнения которых задана ациклическим ориентированным графом G{m, п), где т — число дуг графа, п — число вершин. Для выполнения этапа / проекта должны быть выделены ресурсы нескладируемого вида в объеме я;. = (ап, ..., ajm). Прерывать выполнение этапа до его полного завершения нельзя.

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

Задан также общий объем нескладируемых ресурсов всех видов, которые используются исполнителями проекта, b = (/>,,..., Ьт).

Кроме того, известно время выполнения каждого из этапов /. (/ = 1,..., п). Каждый этап / должен осуществляться непрерывно в течение времени /. при условии, что на него выделены ресурсы в объеме aj = п, ..., ajm) и все предшествующие ему согласно ориентированному графу G(m, п) этапы уже выполнены.

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

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

Рассмотрим метод ветвей и границ применительно к решению данной задачи.

Шаг 1. Вычисление нижней оценки целевой функции задачи. Рассмотрим формулу вычисления нижней оценки для трех случаев.

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

где S — длина критического пути графа G(m, п).

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

2. Для выполнения каждого этапа необходимо aj (1 < я. < М) единиц ресурсов (оборудования, транспортных единиц, обслуживающего персонала и т.п.). В этой ситуации нижняя оценка вычисляется так:

3. В общем случае, т.е. когда я. = (я.р ..., ajm), нижняя оценка может быть вычислена таким образом:

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

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

Шаг 3. Построение очередного допустимого плана выполнения проекта и вычисление нижней текущей оценки. В процессе построения этого плана после завершения очередного этапа проекта вычисляется нижняя текущая оценка 7нтек(т):

где т — момент завершения какого-либо этапа проекта; к — число путей в графе G(m, п);

/т — продолжительность этапа i с учетом его частичного или полного выполнения к моменту времени т (в последнем случае полагаем П = 0);

Sf— продолжительность пути Sl к моменту времени т с учетом полного или частичного выполнения этапов, входящих в путь Sr

Если оказалось, что Гнтек(т) > Г , то построение текущего плана прекращают ввиду его неперспективности и переходят на начало шага 3, т.е. выбирают новый вариант построения плана. В случае если Гтек(т) < Г, выбирают очередной этап для выполнения, выделяют для него ресурсы и в момент завершения т11 > т) какого- либо этапа проекта вычисляют /^(т1). При построении плана реализации проекта возможна одна из альтернатив: либо для какого-то т* окажется, что Гнтек(т*) > Т , либо будет построен новый план реализации проекта продолжительностью Т< Т. В последнем случае значение Тв полагают равным Ти переходят к анализу очередного варианта реализации проекта.

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

Рассмотрим теперь пример решения задачи оптимизации времени выполнения проекта.

? Будем предполагать, что последовательность выполнения этапов проекта задана ориентированным ациклическим графом G(m, п) следующего вида (рис. 7.1).

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

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

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

Не уменьшая общности, можно сказать, что продолжительность каждого этапа проекта совпадает с его номером и для выполнения каждого этапа проекта необходим один исполнитель, т.е. а( = 1 (/ = 1,..., 10), число исполнителей равно двум (b = 2).

Вычислим продолжительности путей графа. В путь входят этапы 1, 2, 3, 9, 10, и, следовательно, его длина равна 25. Аналогично S2 = 31, S3 = 33, S4 = 37. Следовательно, S = S4 = 37.

Определим сумму продолжительностей всех этапов проекта:

Затем вычислим Тн по формуле

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

Продолжительность выполнения проекта по этому плану (решению) равна 41. Следовательно, Г = 41. Так как Тн < Г, переходим к анализу следующего варианта выполнения проекта. Выберем, например, этап 6 и этап 7 в качестве исходных элементов для выполнения. Тогда в момент т = 6 завершится выполнение этапа 6; на диаграмме Гантта эта ситуация отразится следующим образом (рис. 7.3).

Диаграмма Гантта для первого допустимого плана реализации этапов проекта

Рис. 7.2. Диаграмма Гантта для первого допустимого плана реализации этапов проекта

Диаграмма Гантта для второго допустимого плана после завершения этапа 6

Рис. 7.3. Диаграмма Гантта для второго допустимого плана после завершения этапа 6

По формуле (7.4) вычислим Гнтек(т) при х = 6:

Так как Тнтек(6) < Тв, выбираем следующий этап для выполнения. Пусть это будет этап 4. Тогда в момент времени х = 7 завершится выполнение этапа 7; отметим эту ситуацию на диаграмме Гантта (рис. 7.4). Вновь вычислим TjeK(7) по формуле (7.4):

Диаграмма Гантта для второго допустимого плана на момент окончания этапа 7

Рис. 7.4. Диаграмма Гантта для второго допустимого плана на момент окончания этапа 7

Далее продолжаем анализ этого и других допустимых решений согласно схеме, приведенной на рис. 7.5. ?

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

Логическая схема метода ветвей и границ для оптимизации инвестиционной фазы проекта

Рис. 7.5. Логическая схема метода ветвей и границ для оптимизации инвестиционной фазы проекта

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

Здесь Тв последнее значение верхней оценки; Тн значение нижней оценки; К — требуемая относительная точность решения в процентах.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>