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

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

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


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

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

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

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

? Рассмотрим следующую задачу. Пусть имеется проект, состоящий из п работ, последовательность выполнения которых задается матрицей Л — (а у), / = 1, ..., nj— 1, ..., п, при этом если а.. = 1, то, для того чтобы выполнить работу /', рекомендуется предварительно выполнить работу j, и йг. = 0 в противном случае, т.е. когда безразлично, выполнена или нет работа j. Иными словами, вектор = (йг;1, ..., ajn) — это вектор, состоящий из нулей и единиц, и единица на j-м месте вектора aj означает, что работу j рекомендуется выполнить до начала выполнения работы /.

Например, если aj = (0, 1, 0, 0, 1,0), то, прежде чем выполнить работу /, рекомендуется выполнить работы 2 и 5.

Вектору aj(i— 1,..., п) соответствует двумерная матрица В — (Ьф, / = 1,..., п; / = 1,2. При этом:

  • • если йг. = 0, то Ьп 0 и bi2 0;
  • • если а у = 1, то й(1 = xlJtа Ьй =

Здесь Ту задает увеличение длительности работы /', если она будет выполняться до выполнения работы j; Zy — дополнительные затраты на выполнение работы /, если она начала выполняться до того, как полностью завершена работа j.

Например, если aj = (0, 1, 0, 0, 1), то

Здесь т/2 и т/5 — увеличение длительности работы /, если она начнет выполняться до того, как будет закончена работа 2 и 5 соответственно. Если обе эти работы не будут завершены до начала выполнения работы /, то ее продолжительность возрастет на величину т/2 + т/5. Аналогично увеличивается стоимость выполнения работы / при нарушении рекомендуемых зависимостей. ?

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

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

Для решения этой задачи будем использовать традиционную схему метода ветвей и границ.

Шаг 1. Вычисление нижней границы оптимальной продолжительности инвестиционной фазы проекта. Для этого снимаем все ограничения на последовательность выполнения работ, т.е. заменяем ориентированный граф G(m, п), задающий рекомендуемую последовательность выполнения работ, на граф (7(0, п) и решаем задачу минимизации времени завершения инвестиционной фазы с использованием, например, метода, изложенного в параграфе 7.1. Нижней границей будем считать продолжительность полученного плана. Обозначим ее через Т .

Шаг 2. Вычисление верхней оценки оптимальной продолжительности инвестиционной фазы проекта. В качестве верхней оценки выбираем продолжительность оптимального плана при соблюдении всех рекомендуемых ограничений, заданных исходным ориентированным графом G(m, п). Для этого также может быть использован метод, изложенный в параграфе 7.1. Обозначим величину верхней оценки через Тъ.

Шаг 3. Вычисление текущих нижних оценок при формировании плана реализации инвестиционной фазы проекта. На этом шаге алгоритма рассматриваются все возможные варианты выполнения инвестиционной фазы проекта (при этом допускается нарушение рекомендуемых зависимостей) с вычислением текущих нижних оценок Гнтск(т) и FTeK(i) в каждый момент времени, связанный с окончанием очередной работы проекта, по формулам:

где /' — продолжительность работы / с учетом ее выполнения до момента времени т;

М — число исполнителей;

Q — множество нарушений рекомендуемой последовательности работ;

Z- — дополнительные финансовые затраты, если работу / начали выполнять до завершения работы j.

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

где F— лимит дополнительных финансовых затрат, связанных с нарушением мягких ограничений.

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

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

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

? Пусть рекомендуемая последовательность выполнения работ проекта задана следующим ориентированным графом G(m, п) (рис. 7.7).

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

Рис. 7.7. Ориентированный граф, задающий последовательность выполнения работ проекта

Продолжительность каждой работы tj = 1 (/ = 1,2,..., 8). Каждая работа выполняется одним исполнителем, общее количество исполнителей равно 4. Затраты, связанные с нарушением выполнения рекомендуемой последовательности работ, лимитированы суммой /’=10. Матрица Л = (азадающая последовательность выполнения работ для этой ситуации, такова:

Затраты, связанные с нарушением рекомендуемой последовательности выполнения работ, равны z2] = z3l = z32 = z4] z42 ~ z43

~~ Z65 ~ Z15 ~ Z76 ~ ^85 _ ^86 ~~ ^87 _

Увеличение продолжительности работ, связанное с нарушением мягких ограничений, задано следующим образом: т21 = т31 =

- Х32 — Х41 — Х42 _ Х43 — Х65 _ Х75 _ Х76 — Х85 _ Х86 _ Х87 ^,5.

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

Шаг 1. Вычисляем нижнюю границу для оптимального решения задачи. Учитывая, что при снятии всех рекомендуемых ограничений на последовательность выполнения работ оптимальное значение продолжительности равно 2, получаем Тн = 2. Соответствующая диаграмма Гантта решения приведена на рис. 7.8.

Шаг 2. Вычисляем верхнюю границу для оптимального решения задачи. Оптимальное решение задачи при соблюдении всех рекомендуемых ограничений задается следующей диаграммой Гантта (рис. 7.9).

Диаграмма Гантта в условиях отсутствия технологических ограничений на последовательность выполнения работ

Рис. 7.8. Диаграмма Гантта в условиях отсутствия технологических ограничений на последовательность выполнения работ

Оптимальное решение в задаче минимизации инвестиционной фазы проекта с учетом рекомендуемых ограничений на последовательность

Рис. 7.9. Оптимальное решение в задаче минимизации инвестиционной фазы проекта с учетом рекомендуемых ограничений на последовательность

выполнения работ

Продолжительность этого плана равна 4, следовательно, TR = 4. Шаг 3. Вычисляем текущие оценки. Формируем новый план выполнения работ проекта (рис. 7.10).

Диаграмма Гантта при игнорировании рекомендуемых технологических ограничений на последовательность выполнения работ

Рис. 7.10. Диаграмма Гантта при игнорировании рекомендуемых технологических ограничений на последовательность выполнения работ

В момент времени т = 1 (выполнены работы 1 и 5) вычисляем текущие оценки данного плана:

Так как ограничения (7.10) и (7.11) не выполняются, переходим к моменту времени т = 1,5. К этому моменту выполнены работы 6 и 2. Вычислим значения Гнтек(1,5) и Т7тек(1,5):

Ограничения (7.10) и (7.11) не выполняются, следовательно, продолжаем анализировать этот план. Вычисляем значения Гнтек(т) и 7гтек(х) на момент времени т = 2,5, когда завершены работы 7 и 3:

Ограничения (7.10) и (7.11) также не выполняются. Следовательно, продолжаем формировать план и вычисляем момент времени завершения работ 4 и 8. Легко видеть, что это время т = 3,5. Следовательно, сформирован план, продолжительность которого Т* = 3,5 < 4 = Т. Согласно описанию метода присваиваем Тв значение 3,5 и переходим к формированию следующего допустимого плана. ?

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