оптимальным, обязательно будет больше чем номер предыдущего допустимого решения, бывшего оптимальным при меньшем уровне инфляции.
В заключение необходимо отметить, что предложенная процедура получения интервалов устойчивости оптимальных решений задачи может быть использована и для любого подмножества допустимых решений X а,Х допустимых решений.
11.2. Задача оптимизации времени выполнения проекта
11.2.1. Постановка задачи и метод решения. При реализации подавляющего большинства инвестиционных проектов на фазе предынвестиционного ана-
Задача оптимизации времени выполнения проекта является NP-полной. Для решения задач этого класса применяются схемы направленного перебора, лиза для инвестора немаловажным к которым относится мод в-представляется такой показатель, как вей и границ, время его реализации.I=
Рассмотрим задачу оптимизации выполнения проекта, в которой при анализе плана реализации этапов проекта учитывают ресурсные ограничения. Пусть необходимо выполнить проект, состоящий из п этапов, технологическая последовательность выполнения которых задана ациклическим ориентированным графом G(m, п), где т - число дуг графа, п - число вершин. Для выполнения этапа i проекта ему должны быть выделены ресурсы нескладируемого вида в объеме а, = (а/1, Щщ), Прерывать выполнение этапа до его полного завершения нельзя.
Напомним, что нескладируемыми ресурсами являются оборудование, станки, механизмы, транспортные средства, трудовые ресурсы и т.д., то есть все виды ресурсов, которые могут быть многократно использованы при выполнении различных этапов проекта, и после завершения очередного из этапов они передаются для использования их на последующих.
Задан также общий объем упомянутых нескладируемых ресурсов всех видов, которые используются исполнителями проекта Ъ = {Ъх
Кроме того, известно время выполнения каждого из этапов /,(/=!,..., п). Выполнение каждого этапа i должно осуществляться непрерывно в
течение времени г,, при условии, что для его выполнения выделены ресурсы в объеме а, = (а, Л/т) и все этапы, предшествующие этапу / согласно ориентированному графу G(m, п\ уже выполнены. Необходимо выбрать такую последовательность выполнения всех этапов проекта, которая не нарушала бы технологических ограничений заданных графом G(w, п) и ограничений на объем используемых ресурсов в каждый момент времени t реализации проекта и была бы минимальной по продолжительности.
Данная задача принадлежит, как показано в [40], к классу ТР-полных задач, которые будут рассмотрены в последующей главе. Точными методами решения подобных дискретных оптимизационных задач является, в частности, метод ветвей и границ.
Рассмотрим схему метода ветвей и границ применительно к решению данной задачи.
Шаг 1. Вычисление нижней оценки целевой функции задачи. Рассмотрим формулу для вьшисления нижней оценки для трех случаев. 1. Ресурсы, рассматриваемые в задаче, являются ресурсами типа станков или приборов, и для вьшолнения одного этапа необходим один станок. Всего станков М Тогда нижняя оценка вычисляется по следующей формуле:
Г„ =тах
(11.13)
где Step- длина критического пути графа G(m, п). Суть нижней оценки состоит в том, что время вьшолнения проекта, с одной стороны, не может бьггь меньше чем продолжительность критического пути, так как все этапы, входящие в этот путь, должны выполняться последовательно и не допускают вьшолнения двух различных этапов в один и тот же момент времени, а с другой - продолжительностью такого плана реализации проекта, когда все станки (приборы) непрерывно работают в течение всего времени реализации проекта, т.е. плана,
продолжительность которого -.
2, В этом случае для вьшолнения каждого этапа необходимо (зД1 а, < АО единиц ресурсов (оборудования, транспортных единиц, обслужи-302
вающего персонала и т.д.). В этой ситуации нижняя оценка вычисляется так:
(11.14)
3. в общем случае, т.е. когда л, = (лл, Щт), нижняя оценка может быть вычислена таким образом:
Г„ =тах
/•,Sp,max
y=l,w bj
(11.15)
Шаг 2. Вычисление верхней оценки осуществляется путем построения какого либо допустимого плана реализации проекта, и продолжительность этого плана выбирается в качестве верхней оценки Те.
Если выполняется равенство Г„ = Г, то решение задачи получено и им будет тот план, который соответствует оценке Те. В противном случае переходим к шагу 3.
Шаг 3. Выполнение шага 3 заключается в построении очередного допустимого плана выполнения проекта, в процессе которого после завершения очередного этапа проекта вычисляется нижняя текущая оценка
Тн{т) по следующей формуле:
7;"(r) = r + max
l=\,k
(11.16)
к-число путей в графе G(w, п)\
т- момент завершения какого либо из этапов проекта;
tf - продолжительность этапа / с учетом его частичного или полного выполнения к моменту времени г (в последнем случае полагаем tj = О); Sj - продолжительность пути S/k моменту времени г с учетом полного или частичного выполнения этапов, входящих в путь S/.