Основные понятия. Примеры решения задач
Сетевой анализвключает ряд приемов, которые используются при планировании и реализации взаимосвязанных мероприятий; также помогает оптимизировать выполнение проектов, контролировать ресурсы и затраты операций.
На практике часто используется графическое изображение плана выполнения комплекса работ внешне напоминающее сеть, состоящую из направленных отрезков (работ) и вершин (событий), которые отображают логическую взаимосвязь всех операций. Работа это любые целенаправленные действия, трудовые процессы, сопровождающиеся затратами ресурсов и времени и приводящие к определенным результатам (событиям). Событие это результат завершения одной или нескольких работ.
Сетевой график это связный орграф без петель и контуров. Он должен иметь только одно исходное событие (исток сети J) — начало комплекса работ; и только одно завершающее событие (сток сети S) -окончание всех работ комплекса.
Правила построения сетевой модели
1) Каждая операция в сети может быть представлена одной и только одной дугой.
2) Ни одна пара операций не должна определяться одинаковым начальным и конечным событиями.
3) При включении каждой операции в сетевую модель для обеспечения правильного упорядочения необходимо дать ответы на следующие вопросы:
а) какие операции необходимо завершить непосредственно перед началом рассматриваемой операции?
б) какие операции должны непосредственно следовать после завершения данной операции?
в) какие операции могут выполняться одновременно с рассматриваемой.
Это правило позволяет проверять (и перепроверять) отношения упорядочения в процессе построения сети.
Пример 1. Построить сетевую модель, включающую операции A, B, C,…L и отображающую следующие отношения упорядочения:
1. A, B, C – исходные операции программы, которые можно выполнять одновременно.
2. A, B предшествуют D.
3. B предшествует E, F, H.
4. F, C предшествуют G.
5. E, H предшествуют I, J.
6. C, D, F, J предшествует K.
7. K предшествует L.
8. I, G, L – завершающие операции программы.
Сеть соответствующая этим соотношениям упорядочения, приведена на рис.3.1.
Рис. 3.1 Сетевая модель
Операции D1, D2, D3 – фиктивные. События сети пронумерованы так, что возрастание номеров соответствует ходу выполнения программы.
Расчет сетевой модели
Наиболее продолжительный по времени путь от истока к стоку называется критическим.Критический путь определяет минимальное время выполнения всех работ данного комплекса. Это максимальное среди всех полных путей время называют критическим сроком .
Критическими называют события и работы, расположенные на критическом пути.
Расчет сетевой модели включает два этапа.
Этап. Прямой ход
Вычисления начинаются с исходного события и продолжаются до тех пор, пока не будет достигнуто завершающее событие всей сети. Для каждого события вычисляется ранний срокего наступления (на рис.3.2 числа в квадратах)
,
где – множество работ, входящих в -ое событие.
Этап. Обратный ход
Вычисления начинаются с завершающегося события сети и продолжаются, пока не будет достигнуто исходное событие. Для каждого события вычисляется поздний срок его наступления (на рис.3.2 числа в треугольниках).
,
где – множество работ, выходящих из -го события.
Определение критического пути
Работа (i, j) принадлежит критическому пути, если она удовлетворяет трем условиям:
1. tп(i) = tp(i);
2. tп(j) = tp(j);
3. tр(j) — tp(i) = tп(j) — tп(i) = tij.
Эти условия означают, что между ранним сроком и поздним сроком запас времени отсутствует. Т. е. критический путь определяет кратчайшую возможную продолжительность всей программы в целом
Пример 2. На рис. 3.2 показана сетевая модель с исходным событием 0 и завершающим событием 6.
Рис. 3.2 Расчет сетевой модели