Метод анализа и оценки проекта REPT-метод

Одно из наиболее известных приложений теории потоков в сетях называется PERT (program evaluation and review technique — метод анализа и оценки программ)^[1]. Эта техника используется для оптимального распределения денежных ресурсов среди заданий проекта, при котором проект можно завершить в кратчайшие сроки. Рассмотрим долгосрочный проект, состоящий из множества работ. Работы частично упорядочены в соответствии с технологическими ограничениями. Например, промывка должна производиться раньше сушки. Проект можно представить ориентированной сетью. Где работы - ориентированные дуги. Для каждой индивидуальной работы имеется время нормального завершения и абсолютно минимальное время завершения.

Варианты задачи:

1) Чем больше денег затрачивается на работу, тем быстрее эта работа будет завершена. Задача заключается в том, чтобы завершить весь проект как можно раньше при фиксированном бюджете.

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

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

Необходимо определить работы, которые входят в самый длинный путь, что бы дополнительные деньги потратить на эти работы (например, какая-то работа нормально выполняется за три дня, но при затрате на нее 3-х долларов она может быть закончена за 2 дня, а при затрате 6-ти долларов — за 1 день), тем самым уменьшить время завершения всего проекта. Это называется планированием критических путей.

Идея алгоритма:

Для того, чтобы сократить время завершения проекта, нужно сократить самый длинный путь из V₀ в V_n. Так как в самом длинном пути дуг много, то потратим деньги на дуги (работы) с наименьшими значениями . Это бы наиболее эффективно уменьшило длину самого длинного пути. Продолжим сокращение дуги до тех пор, пока не выполнится хотя бы одно из условий (i) или (ii).

(i) Дуга сокращена до минимального времени .

(ii) Рассматриваемый путь не длиннее самого длинного пути.

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

Иногда дуга пути Р’ сокращается до минимального времени на одном из ранних этапов. В дальнейшем сокращаются и другие дуги из Р’ и P’ не станет самым длинным путем, даже если дугу удлинить до ее исходной длины. (Заметим, что удлинение дуги означает возможность экономии денег.)

Коротко алгоритм PERT.

Введем некоторые понятия.

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

1. На основе текущих длин дуг найти все самые длинные пути из V₀ в V_n. Сделать все дуги самых длинных путей активными.

2. Рассматривая величины для активных дуг как их пропускные способности, найти максимальный поток из V₀ в V_n. (При нахождении максимального потока получаем минимальный разрез, указывающий самый дешевый способ для сокращения длительности всего проекта.)

3. Если дуга становится жесткой, то присваиваем ей бесконечную пропускную способность.

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

5. Найти расстояние от V₀ до каждого узла. Расстояние до узла V_i, соответствует кратчайшему времени, за которое этот узел может быть достигнут. Если длина активной дуги короче разности расстояний между ее концевыми узлами, то увеличиваем длину этой дуги. (Это эквивалентно уменьшению стоимости.)