П. 8. Сетевые графы или графики

Рассмотрим пример из повседневной жизни. Строится школа. Как организовать работу, как распределить рабочую силу, финансы, с какого участка взять людей для переделок и т. д. и т.п…., так, чтобы все обошлось максимально дешево? Это задача для специальных графов, с помощью которых можно построить сеть сложного комплекса работ, определить по сети самые ответственные работы, вычислить время завершения всего комплекса, найти резервы времени для отдельных событий и работ.

Определение 47. Всякий намеченный комплекс работ, необходимых для достижения цели, называют проектом.

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

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

Определение 48. Изображение сети называется сетевым графиком.

Основные правила построения сетевого графика.

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

2. Строят без лишних пересечений.

3. Во все вершины, кроме той, которая соответствует исходному событию, должна входить, по меньшей мере, одна стрелка (т. к. все события, кроме исходного, имеют предшествующую работу).

4. Из всех вершин, кроме завершающей, должны выходить стрелки.

5. Не должно образовываться циклов.

6. Если одно событие служит началом для двух и более работ, после завершения которых начинается выполнение следующей работы, то вводится штриховая стрелка и дополнительное событие со своим номером.

Примеры правильного и неправильного построения сетевых графиков.

Определение 49. Путь в сети от исходного события до завершающего называют полным путем (L).

Определение 50. Продолжительностью пути называется время, необходимое для выполнения всех работ, лежащих на этом пути. (t(L)).

Пример.

Найти продолжительности путей L₁, L₂, L₃ в сетевом графике.