Постановка задачи минимизации затрат на проект

 

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

Пусть дан граф G(N ,А), представляющий собой сетевую модель комплекса работ. Поставим в соответствие каждой работе сети два параметра:

1) продолжительность выполнения - t_ij ,

2) затраты на выполнение - p_ij .

Очевидно, что затраты находятся в обратной зависимости от продолжительности, т. е. чем раньше надо закончить работу, тем больше средств (исполнители, оборудование и пр.) придется в нее вложить. Эта зависимость имеет сложный характер, и для упрощения решения задачи ее надо аппроксимировать прямой, график которой представлен на рис. 4.4.

   p_ij

   p₀

   p_a

 

                          g

   p_b

   а _ij                            b_ij                    t_ij

Рис. 4.4. График зависимости затрат на работу от ее продолжительности

Здесь b_ij - нормальная продолжительность работы, а_ij - ускоренная продолжительность работы, p_b - затраты при нормальной продолжительности, p_a - затраты при ускоренной продолжительности,

a_ij £ t_ij £ b_ij .

Угол наклона прямой (без учета знака) характеризует интенсивность нарастания затрат, т. е. приращение затрат, необходимое для сокращения длительности работы на единицу: tg g = с _ij = (p_a - p_b)/(b_ij - a_ij).

Приращение затрат - величина обратная эффективности вложения средств в сокращение длительности работы: ε _ij = 1/с_ij . Другими словами, вложение дополнительных средств наиболее эффективно в те работы, которые имеют минимальные значения «угловых коэффициентов» с _ij .

Затраты на выполнение работы в общем случае определяются по формуле

p_ij = p₀ - с _ij t_ij ,

где p₀ - условная точка пересечения прямой затрат с осью ординат.

Суммарные затраты на выполнение всего проекта, которые следует минимизировать, тогда могут быть определены следующим образом:

Р_S  = Þ min,

где Р₀ - суммарные условные затраты (константа для данного проекта).

Задача минимизации затрат на проект - это оптимизационная задача, которая ставится как задача параметрического линейного программирования:

åс_ij t_ij Þ max

^(ij)ÎA

t_pj £ t_pi + t_ij

a_ij £ t_ij £ b_ij

T_кр = t_pt ³ 0

Для ряда допустимых значений продолжительности критического пути, как параметра, требуется найти наборы значений переменных t_pj и t_ij , минимизирующие затраты на выполнение проекта. Графически оптимальное решение имеет вид кривой, ограничивающей снизу область допустимых решений задачи. Это «кривая затрат на проект» (см. рис. 4.5).

Р_S

 

                                       Т_a                 Т_b           Т_кр

Рис. 4.5. Графическая интерпретация решения задачи

 

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

Обратная постановка задачи: как распределить между работами ограниченные дополнительные инвестиции, чтобы достичь максимального сокращения срока завершения проекта.

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

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

 

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться: