Сетевое моделирование
Наиболее часто в области сетевого моделирования рассматриваются две задачи, связанные с сетями: задача о кратчайшем пути и задача о максимальном потоке. Например, если в роли взвешенного орграфа выступает сеть нефтепроводов, то при решении задачи о максимальном потоке нефти через эту сеть веса, данные в скобках рядом с дугами, указывают на скорость потребления нефти и пропускную способность труб. Вершины такого орграфа представляют собой потребителей или производителей нефти, а дуги - нефтепроводы.
В случае если решается задача о кратчайшем пути, веса дуг графа задаются расстоянием между вершинами, которые эти дуги соединяют. Пусть, например, имеется топологическая карта транспортной сети из 5 дорог, соединяющих 4 населённых пункта, причём необходимо выбрать кратчайший путь из пункта x1 в пункт x4:
Рис. 17. Топологическая карта транспортной сети из 5 ветвей
Оказывается, используя аналогию между длиной пути Uij между пунктами i и j и электрическим напряжением Ūij между точками i и j электрической цепи, можно решать задачу о кратчайшем пути, моделируя транспортную сеть Рис. 17 следующей электрической схемой:
Рис. 18. Электрическая модель транспортной сети Рис. 17.
Впрочем, любая электрическая схема сама по себе представляет ориентированный и взвешенный граф. Ориентированным граф будет в силу протекающих в определённом направлении токов по разным участкам схемы. Величины токов могут играть роль весов соответствующих дуг графа, а величины напряжений - роль весов соответствующих вершин графа. Свойство постоянства потока в сети равносильно высказыванию о том, что поток в промежуточной вершине не исчезает и не возникает. Это свойство эквивалентно закону Кирхгофа для цепи постоянного тока.
Моделируя сетевые структуры, следует различать некоторые разновидности графов с экстремальными характеристиками и учитывать связанные с ними понятия. Простой цепью (а)называется граф, у которого только две вершины имеют степень, равную единице, а остальные – степень, равную двум. Цикл (б) есть граф, все вершины которого имеют степень, равную двум. Число вершин в цикле называется его длиной.
Рис. 19. Цепь (а) и цикл (б) в ориентированном графе.
Цикл и цепь задаются последовательностью вершин и рёбер, входящих в них. Граф, все вершины которого попарно смежные, называется полным. Граф, все вершины которого попарно несмежные, называется пустым. Граф называется связным, если для любых вершин Xi, Xj существует цепь, которой принадлежат вершины Xi и Xj .
Компонентом связности графа (а) является подграф (б):
Связный граф на n вершинах с минимальным числом рёбер называется деревом.
В теории графов транспортной сетью называется ориентированный связной мультиграф без петель, в котором:
1) Существует одна и только одна такая вершина х1 называемая входом сети, что g -1(x1) = 0;
2) Существует одна и только одна такая вершина хn, называемая выходом сети, что g (xn) = 0
3) Каждой дуге U графа соответствует некоторое число K(U) ≥ 0, называемое пропускной способностью дуги.
Потоком f(U) транспортной сети называется некоторая функция f(U), определённая на множестве дуг графа и удовлетворяющая свойствам:
1) f(U) ≥ 0
2) u Î Ux- ∑ f(U) – u Î Ux+ ∑ f(U) = 0 (x ¹ x1, x ¹ xn)
3) f(U) £ K(U); u Î U, где Ux-, Ux+ - множество дуг, входящих в вершину 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.
s | s’ | |||||||
s | ||||||||
s’ |
В этой матрице величина элемента i, j соответствует пропускной способности дуги (i, j). Для начала насыщения исходной сети возьмем поток f1 = 3, который слагается из вытекающих во всех направлениях из источника s условных единиц потока, и соответствующую ему матрицу потока || f1 ||. Эта матрица || f1 ||. вместе с ориентированным графом, соответствующим потоку f1, изображены ниже:
S | s’ | |||||||
s | ||||||||
-1 | ||||||||
-1 | ||||||||
-1 | ||||||||
-1 | ||||||||
s’ | -1 | -1 | -1 |
Знаки (-) в матрице || f1 || возникли в силу свойства № 2 определения потока. Теперь, чтобы выяснить, насколько полно поток f1 насыщает исходную сеть, вычтем f1 из k, а также соответствующие этим потокам матрицы и получим новую сеть k1 = k – f1 и новую матрицу пропускных способностей || k1 || = || k || – | | f1 ||:
s | 1 | s’ | ||||||
s | ||||||||
s’ |
Появление в матрице || k1 || нулей говорит о появлении насыщенных дуг (s,1), (2,s') и (5,s') в результате операции вычитания. Найдем те узлы, которых можно достичь из (а), следуя по ненасыщенным дугам. Эти узлы определяются положительными элементами первой строки матрицы || k1 ||, т.е. это узлы (2) и (5). Из узлов (2) и (5) достижимы узлы (3) и (4) , из узлов (3) и (4) можно попасть в узел (6), а из него – (s').
Таким образом, одним из ненасыщенных путей является путь (s,2), (2,3), (3,6), (6,s'). Образующие этот путь элементы в матрице || k1 || обведены кружками, а элементы в квадратиках образуют путь для потока в противоположном направлении. Минимальная пропускная способность пути (s,2), (2,3), (3,6), (6,s') лимитируется дугой (2,3), значит, по нему возможен поток мощностью максимум 2 единицы. Обозначив этот поток f2 = 2, вычтем из его сети k1. Новую матрицу пропускных способностей || k2 || = || k1 || - || f2 || получим вычитанием 2 из элементов || k1 ||, обведенных кружками, и добавлением 2 к элементам, обведённым квадратами. Вот эта матрица || k2 ||:
s | 3 | S’ | ||||||
s | ||||||||
s’ |
Еще один ненасыщенный путь из (s) в (s’) образован дугами (s,5), (5,4), (4,6), (6,s'). Он отмечен кружками в матрице || k2 ||, а обратный путь - квадратами. Минимальное сечение этого пути лимитируется дугой (4,6) и равно 1, а значит, максимальный поток по этому пути f3 = 1. Новую матрицу пропускных способностей || k3 || = || k2 || - || f3 || получим, таким образом, как ранее || k2 ||, в виде следующей таблицы:
s | 1 | s’ | ||||||
s | ||||||||
s’ |
Единственный оставшийся ненасыщенным путь из (s) в (s’) отмечен кружками в матрице ||k3||. Это путь (s,5), (5,4), (4,1), (1,6), (6,s'). Максимальный поток f4 = 1 по этому пути лимитируется дугами (4,1) и (1,6). Производя снова операцию вычитания потока f4, получим последнюю матрицу пропускных способностей ||k4|| = || k3 || - || f4 ||:
Таблица 2.
s | 2 | s’ | ||||||
s | ||||||||
s’ |
Выделенные кружками узлы, которых можно достичь, исходя из (s), не включают узел (s’). Значит, невозможно более никакого потока в этой сети. Полный поток, насыщающий исходную сеть k (рис.20), слагается из найденных частичных потоков:
fмакс = f1 + f2 + f3 + f4 = 3 + 2 + 1 + 1 = 7.
Матрицу максимального потока || fмакс || = || k || - || k4 || получим вычитанием последней матрицы пропускных способностей (Табл. 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
Определение длительности работы производится следующим образом. Если нет точного определения длительности, то экспертами намечается три возможных срока выполнения работы tij:
1. Пессимистическая оценка tij=tmax.
2. Оптимистическая оценка tij=tmax.
3. Наиболее вероятная (ожидаемая) tIJ=tож.
Оптимистическая оценка - это минимальное время, за которое все будет обеспечено в срок при наилучших условиях.
Пессимистическая оценка - это максимальное время, за которое будет выполнена работа.
Ожидаемая оценка срока определится соотношением: tож=(2tmax+3tmin)/5.
Для расчета сетевого графика необходимо ввести понятия:
1. Время раннего начала работы (i)→(j)определяется из условия, что все предваряющие события (i) работы должны быть закончены, т.е. , где - путь максимальной длительности от события (1) до события (i), начального для данной работы.
1. Время раннего окончания работы: .
Время раннего начала и окончания работ на сетевом графике определяется для всех событий, начиная с исходного и кончая завершающим.
3. Время позднего начала работы (i)→(j) представляет самый поздний срок, к которому должно произойти событие (i) так, чтобы не нарушался сетевой график, т. е. должно выполняться: , где Ткр - время окончания проекта (завершающего события), а определяется как путь максимальной длины от завершающего события до события (i). Значения вычисляются аналогично , начиная от завершающего график события и кончая событием (1).
4. Время позднего окончания работы есть самый поздний срок завершения работы.
5. Общий резерв времени представляет собой разность между поздним и ранним началом или поздним и ранним окончанием работы . Эта величина показывает, насколько можно передвинуть срок выполнения данных работ, не нарушая графика. Если Rij=0, значит, работа лежит на критическом пути. Для остальных путей Rij>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). Он изображен на рисунке двойной стрелкой.
Дата добавления: 2022-07-20; просмотров: 108;