Сетевая модель и ее основные элементы

Граф - это совокупность множества узловых точек X (узлов или вершин) и множества соединяющих их дуг А. Формально граф обозначается G= (X, А). Обычно вершинам приписывают номера – 1, 2,..., n, а дуги изображают прямыми или кривыми линиями, каждая из которых соединяет ровно две вершины, и обозначают (i, j). Где i, j - вершины, определяющие начало и конец дуги. На рисунке 9.1. вершины графа – это кружки с номерами 1, 2, 3, 4, 5. Дуги этого графа: (1, 2), (1, 4), (5, 1), (2, 3), (2, 5), (3, 5).

Сеть – это граф, каждой дуге которого поставлено в соответствие одно или несколько чисел (весов).

Если нет необходимости различать начало и конец дуги, дуга является неориентированной и называется ребром. Граф, в котором ни одна из дуг не имеет ориентации, называется неориентированным (и ориентированным в противном случае). Граф на рисунке 9.1 – ориентированный. 

 

 Вершины в графе называются смежными, если они различны и существует дуга, соединяющая эти вершины. Две дуги называются смежными, если они имеют общую концевую вершину. Последовательность дуг, соединяющая вершины i и j без учета их ориентации называется путем. Граф называется связным, если существует по крайней мере один путь между любой парой его вершин. Конечный путь, начальная и конечная вершины которого совпадают, называется циклом. Если все дуги пути, связывающего узлы i и j, ориентированы так, что действительно можно пройти по этому пути из i и j, то такой путь часто называют ориентированной цепью. Например, на рисунке 9.1. путь из 1 в 5, проходящий через узлы 1, 2, 3, 5, есть ориентированная цепь. Замкнутая цепь называется ориентированным циклом или контуром. Например, на рисунке 9.1 контуром является ориентированная цепь, соединяющая вершины 1, 2, 5, 1. Сеть, не имеющая циклов (контуров), называется ациклической (бесконтурной).

Важным частным случаем сети является связная сеть, содержащая n узлов и n-1 дугу. Сеть такой структуры не содержит циклов и называется деревом (рисунок 9.2). Для любых двух вершин дерева существует единственный путь, соединяющий их.

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

Сеть – конечный граф без циклов и петель, ориентированный в одном направлении.

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

Правила построения сетевых моделей:

- основой является структурно-временная таблица, содержащая перечень всех операций, длительность и порядок их следования (опорной называется операция (работа), без выполнения которой невозможно выполнение последующих операций);

- всем стрелкам сетевого графика задают общее направление слева направо;

- между одной парой событий можно изобразить только одну работу;

- не должно быть стрелок, которые ниоткуда не выходят и никуда не входят;

- сеть может содержать несколько начальных вершин (в которые не входит ни одна дуга). В этом случае можно добавить еще одну вершину и провести из нее дуги c нулевыми длительностями работ во все начальные вершины. Тогда сеть будет иметь одну начальную вершину. Аналогично вводят конечную вершину;

- для упрощения анализа сети, устраняют пересечения работ преобразованием взаимного расположения работ и событий;

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

Основными понятиями моделей задач сетевого планирования и управления являются работа, событие и путь.

Под работой понимаются:

- любые действия, требующие затрат времени, труда, материальных ресурсов и производственных мощностей;

- ожидание, т.е. пассивный процесс, требующий только затрат времени;

- зависимость или причинно-следственная связь между двумя или несколькими работами, не предполагающая затрат ресурсов и времени (фиктивная работа).

 

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

Последовательность работ, ведущая от исходного события к завершающему, называется полным путем. Продолжительность пути равна сумме продолжительностей работ, составляющих этот путь. Наиболее продолжительный полный путь называется критическим. Он определяет минимальное время выполнения всего комплекса работ. Это минимальное время называется критическим сроком (^{T кр}). Составляющие критический путь работы называются критическими. Это объясняется тем, что любое увеличение их продолжительности или задержка в их выполнении увеличивают время осуществления всего комплекса работ.