Сетевое моделирование

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

В случае если решается задача о кратчайшем пути, веса дуг графа задаются расстоянием между вершинами, которые эти дуги соединяют. Пусть, например, имеется топологическая карта транспортной сети из 5 дорог, соединяющих 4 населённых пункта, причём необходимо выбрать кратчайший путь из пункта x₁ в пункт x₄:

Рис. 17. Топологическая карта транспортной сети из 5 ветвей

Оказывается, используя аналогию между длиной пути U_ij между пунктами i и j и электрическим напряжением Ūij между точками i и j электрической цепи, можно решать задачу о кратчайшем пути, моделируя транспортную сеть Рис. 17 следующей электрической схемой:

Рис. 18. Электрическая модель транспортной сети Рис. 17.

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

Моделируя сетевые структуры, следует различать некоторые разновидности графов с экстремальными характеристиками и учитывать связанные с ними понятия. Простой цепью (а)называется граф, у которого только две вершины имеют степень, равную единице, а остальные – степень, равную двум. Цикл (б) есть граф, все вершины которого имеют степень, равную двум. Число вершин в цикле называется его длиной.

Рис. 19. Цепь (а) и цикл (б) в ориентированном графе.

Цикл и цепь задаются последовательностью вершин и рёбер, входящих в них. Граф, все вершины которого попарно смежные, называется полным. Граф, все вершины которого попарно несмежные, называется пустым. Граф называется связным, если для любых вершин X_i, X_j существует цепь, которой принадлежат вершины X_i и X_j .

Компонентом связности графа (а) является подграф (б):

Связный граф на n вершинах с минимальным числом рёбер называется деревом.

В теории графов транспортной сетью называется ориентированный связной мультиграф без петель, в котором:

1) Существует одна и только одна такая вершина х₁ называемая входом сети, что g ^-1(x₁) = 0;

2) Существует одна и только одна такая вершина х_n, называемая выходом сети, что g (x_n) = 0

3) Каждой дуге U графа соответствует некоторое число K(U) ≥ 0, называемое пропускной способностью дуги.

Потоком f(U) транспортной сети называется некоторая функция f(U), определённая на множестве дуг графа и удовлетворяющая свойствам:

1) f(U) ≥ 0

2) u Î U_x^- ∑ f(U) – u Î U_x⁺ ∑ f(U) = 0 (x ¹ x₁, x ¹ x_n)

3) f(U) £ K(U); u Î U, где U_x^-, U_x⁺ - множество дуг, входящих в вершину X и выходящая из неё.

Для иллюстрации методов сетевого моделирования рассмотрим задачу о максимальном потоке более подробно. Введем несколько обозначений.

1. Сеть с пропускной способностью (N, k) состоит из N узлов i, j. Упорядоченная пара узлов (i, j) называется дугой сети. Каждой дуге (i, j) приписывается определенная пропускная способность k(i, j).

2. Потоком в сети (N,k) называется функция f, сопоставляющая каждой дуге (i,j) число f(i,j) и обладающая свойствами:

f(i,j) = - f(i,j) и f(i,j) < k(i,j). Пропускная способность и потокможет характеризовать как отдельную дугу, так и всю сеть (N, k).

3. Узел а множества N называется источником потока f, если f(s, N) > 0. Узел a' называется стоком, если f(s', N) < 0. Поток с одним источником я и одним стоком а' называется потоком отs кs'. Узлы s и s' связаны сложной промежуточной сетью N.

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

Рис. 20. Исходная сеть, исследуемая на предмет пропускной способности.

Числа при дугах указывают на пропускные способности соответствующих отрезков сети (в условных единицах). В соответствии с теорией графов, для удобства моделирования исходная исследуемая сеть (рис. 20) представляется матрицей пропускных способностей || k || (Табл. 1).

Таблица 1.

В этой матрице величина элемента i, j соответствует пропускной способности дуги (i, j). Для начала насыщения исходной сети возьмем поток f₁ = 3, который слагается из вытекающих во всех направлениях из источника s условных единиц потока, и соответствующую ему матрицу потока || f₁ ||. Эта матрица || f₁ ||. вместе с ориентированным графом, соответствующим потоку f₁, изображены ниже:

Знаки (-) в матрице || f₁ || возникли в силу свойства № 2 определения потока. Теперь, чтобы выяснить, насколько полно поток f₁ насыщает исходную сеть, вычтем f₁ из k, а также соответствующие этим потокам матрицы и получим новую сеть k₁ = k – f₁ и новую матрицу пропускных способностей || k₁ || = || k || – ‌‌|‌‌‌ | f₁ ||:

	s	1						s’
s
s’

Появление в матрице || k₁ || нулей говорит о появлении насыщенных дуг (s,1), (2,s') и (5,s') в результате операции вычитания. Найдем те узлы, которых можно достичь из (а), следуя по ненасыщенным дугам. Эти узлы определяются положительными элементами первой строки матрицы || k₁ ||, т.е. это узлы (2) и (5). Из узлов (2) и (5) достижимы узлы (3) и (4) , из узлов (3) и (4) можно попасть в узел (6), а из него – (s').

Таким образом, одним из ненасыщенных путей является путь (s,2), (2,3), (3,6), (6,s'). Образующие этот путь элементы в матрице || k₁ || обведены кружками, а элементы в квадратиках образуют путь для потока в противоположном направлении. Минимальная пропускная способность пути (s,2), (2,3), (3,6), (6,s') лимитируется дугой (2,3), значит, по нему возможен поток мощностью максимум 2 единицы. Обозначив этот поток f₂ = 2, вычтем из его сети k₁. Новую матрицу пропускных способностей || k₂ || = || k₁ || - || f₂ || получим вычитанием 2 из элементов || k₁ ||, обведенных кружками, и добавлением 2 к элементам, обведённым квадратами. Вот эта матрица || k₂ ||:

	s			3				S’
s
s’

Еще один ненасыщенный путь из (s) в (s’) образован дугами (s,5), (5,4), (4,6), (6,s'). Он отмечен кружками в матрице || k₂ ||, а обратный путь - квадратами. Минимальное сечение этого пути лимитируется дугой (4,6) и равно 1, а значит, максимальный поток по этому пути f₃ = 1. Новую матрицу пропускных способностей || k₃ || = || k₂ || - || f₃ || получим, таким образом, как ранее || k₂ ||, в виде следующей таблицы:

	s	1						s’
s
s’

Единственный оставшийся ненасыщенным путь из (s) в (s’) отмечен кружками в матрице ||k₃||. Это путь (s,5), (5,4), (4,1), (1,6), (6,s'). Максимальный поток f₄ = 1 по этому пути лимитируется дугами (4,1) и (1,6). Производя снова операцию вычитания потока f₄, получим последнюю матрицу пропускных способностей ||k₄|| = || k₃ || - || f₄ ||:

Таблица 2.

	s		2					s’
s
s’

Выделенные кружками узлы, которых можно достичь, исходя из (s), не включают узел (s’). Значит, невозможно более никакого потока в этой сети. Полный поток, насыщающий исходную сеть k (рис.20), слагается из найденных частичных потоков:

f_макс = f₁ + f₂ + f₃ + f₄ = 3 + 2 + 1 + 1 = 7.

Матрицу максимального потока || f_макс || = || k || - || k₄ || получим вычитанием последней матрицы пропускных способностей (Табл. 2) из исходной матрицы (Табл.1):

Рис. 21. Матрица || f_макс || и соответствующий ей поток f_макс.

Полный поток, вытекающий из (s), равный сумме элементов первой строки || f_макс ||, равен полному стоку в (s’), т. е. сумме элементов последнего столбца, и оказывается равным 7 условных единиц. Интересно отметить, что отсутствует вклад дуги (1,2) в полный поток, хотя она обладает единичной пропускной способностью.

5.2. Сетевое планирование.

В предыдущем параграфе объект, предназначенный для моделирования, представлялся в виде ориентированной сети. Если дуги и узлы некоторой ориентированной сети соотнести с производимыми работами и происходящими при этом событиями, то в виде сети также можно представить план работ по создание некоторого проекта. В этом случае можно говорить о сетевом планировании - эффективном средстве реализации какого-либо проекта к заданному сроку.

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

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

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

2. Фиктивная работа. Она отражает связь между двумя или более работами и не требует ни времени, ни ресурсов.

3. Собственно работа.

Понятие "событие" означает конечный результат какой-либо работы. "Путь" в данном случае представляет собой непрерывную последовательность работ от исходного события к завершающему. В сетевом графике имеется множество путей. Путь максимальной длительности называется критическим. Для построения и расчета сетевого графика используется так называемая система PERT (Program Evaluation and Review Technique), включающая этапы:

1. Расчленение комплекса работ на определенные этапы.

2. Выявление и описание всех событий и работ.

3. Построение сети.

4. Определение времени выполнения каждой работы,

5. Определение критического пути.

6. Анализ сети и оптимизация сетевого графика.

Основные правила построения графиков заключаются в следующем:

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

2. Для построения сетевого графика водятся обозначения:

а) событие

б) работа в ожидании

в) фиктивная работа

г) критический путь

3. Недопустимо совпадение начального и конечного событий у двух и более работ, выполняемых параллельно во времени, т.е. недопустим фрагмент:

4. В случае нарушения правила № 3 таком случае вводятся дополнительные события, соединяемые фиктивными работами с одним конечным событием:

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

6. В сети не должно быть замкнутых контуров, таких как, например:

2

1

3

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

1. Пессимистическая оценка t_ij=t_max.

2. Оптимистическая оценка t_ij=t_max.

3. Наиболее вероятная (ожидаемая) t_IJ=t_ож.

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

Пессимистическая оценка - это максимальное время, за которое будет выполнена работа.

Ожидаемая оценка срока определится соотношением: t_ож=(2t_max+3t_min)/5.

Для расчета сетевого графика необходимо ввести понятия:

1. Время раннего начала работы (i)→(j)определяется из условия, что все предваряющие события (i) работы должны быть закончены, т.е. , где - путь максимальной длительности от события (1) до события (i), начального для данной работы.

1. Время раннего окончания работы: .

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

3. Время позднего начала работы (i)‌→(j) представляет самый поздний срок, к которому должно произойти событие (i) так, чтобы не нарушался сетевой график, т. е. должно выполняться: , где Т_кр - время окончания проекта (завершающего события), а определяется как путь максимальной длины от завершающего события до события (i). Значения вычисляются аналогично , начиная от завершающего график события и кончая событием (1).

4. Время позднего окончания работы есть самый поздний срок завершения работы.

5. Общий резерв времени представляет собой разность между поздним и ранним началом или поздним и ранним окончанием работы . Эта величина показывает, насколько можно передвинуть срок выполнения данных работ, не нарушая графика. Если R_ij=0, значит, работа лежит на критическом пути. Для остальных путей R_ij>0.

6. Частный резерв времени есть разность между временем раннего начала следующей работы в ранним окончанием данной работы: . Эта величина показывает, насколько возможно продление данной работы без нарушения срока раннего начала последующей работы. В качестве примера сетевого планирования рассмотрим следующий сетевой график некоторого гипотетического проекта длительностью Т_кр=16 ус
ловных единиц:

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

При расчете сетевого графика составляется таблица, в которую заносятсявсе определенные выше сроки работ и резервы времени. Для приведенного выше сетевого графика составляется следующая таблица:

Работа	tij					Rij	rij
1-2
l-3
2-4
2-3
3-4
3-5
4-5
4-6
5-6

Выявление работ с нулевым резервом времени в приведенной выше таблице показывает, что критический путь на данном сетевом графике определяется следующей последовательностью событий: (1)→(3)→(4)→(6). Он изображен на рисунке двойной стрелкой.