Сетевые модели. Тема10_Сетевые модели_net_lec. Тема 10 Сетевые модели

• Название: Тема 10 Сетевые модели
• Анкор: Сетевые модели
• Дата: 28.04.2021
• Размер: 1.35 Mb.
• Имя файла: Тема10_Сетевые модели_net_lec.pdf
• Тип: Анализ; #199664
• страница: 2 из 4

Алгоритм использует три массива из N чисел каждый.
Первый массив S содержит метки с двумя значения:
0 (вершина еще не рассмотрена) и 1 (если уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие расстояния от и до соответ- ствующей вершины; третий массив С содержит номера вершин - k-й элемент С[k] есть номер предпоследней вер- шины на текущем кратчайшем пути из V
i в V
k
Матрица расстояний A[i,k] задает длины дуге (i,k); если такой дуги нет, то A[i,k] присваивается большое число M, равное "машинной бесконечности".
1. (Инициализация). В цикле от 1 до N заполнить нулями массив S; заполнить числом i массив C; перенести i-ю строку матрицы A в массив B, S[i]:=1;
C[i]:=0 (i - номер стартовой вершины).
2. (Общий шаг). Hайти минимум среди неотмеченных (т. е. тех k, для которых S[k]=0). Пусть минимум достигается на индексе j, т. е. B [j] ≤B[k].
Затем выполняются следующие операции:
S[j]:=1; если B[k] > B[j]+A[j,k], то B[k]:=B[j]+A[j,k]; C[k]:=j
Условие означает, что путь V
i
... V
k длиннее, чем путь V
i
...V
j
V
k
Если все S[k] отмечены, то длина пути от V
i до V
k равна B[k]. Теперь надо перечислить вершины, вхо- дящие в кратчайший путь.
3. (Выдача ответа). Путь от V
i до V
k выдается в обратном порядке следующей процедурой:
3.1. z:=C[k];
3.2.
Выдать z;
3.3. z:=C[z]. Если z = О, то конец, иначе перейти к 3.2.
Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм
Дейкстры имеет квадратичную сложность. Алгоритм Дейкстры не может быть использован, если веса некоторых дуг отрицательны. В этом случае для поиска кратчайшего пути в графе с отрицательным ве- сом применяется Алгоритм Форда, являющийся модификацией алгоритма Дейкстры.
3.2. Определение кратчайшего пути на сети с циклами с использованием матрицы
Введем вспомогательные величины:
V
j
= min
i
{U
i
+ d
ij
}
, где:
U
i
– кратчайшее растояние между узлами 1 и j, d
ij
– длина дуги между смежными узлами.
Процесс начинается с
i
=
1
и
V
1
=
U
1
=
0
. После определения
V
j
полагаем
U
i
= V
j
. Заметим, что
U
i
включает расстояние до узла
i
, которое затем используется для определения расстояния до ближай- шего узла.
Формула рекурсивная и для сети без циклов решение получается за один проход. При наличии циклов (имеется путь меньшей длины от узлов с большими номерами к меньшим номерам) необходим итерационный процесс, по сути напоминающий метод потенциалов в транспортной задаче.
Конец итерационного процесса определяется по условию
d
ij
≥ V
j
-
U
i
для всех строкматрицы. При обнаружении несоответствия в строке вычислить новые
V
j
= U
i
+ d
ij
для j
не удовлетворяюших условию, положить
U
j
= V
j
и продолжить расчет.
3.3. Пример нахождения кратчайшего пути на сети с циклами
Рассмотрим задачу нахождения кратчайшего пути в сети с циклами на конкретном примере.

Дана следующая сеть (рис. 1):
Рис. 1. Граф сети.
Необходимо найти кратчайший путь из пункта 1 в пункт 10 и обратно.
Определим кратчайший путь на сети с циклами с использованием матрицы.
Пусть расстояния между узлами приведены в виде следующей табл. 1:
Таблица 1. Матричное представление графа сети
1
2
3
4
5
6
7
8
9
10
U
i
1
3 8
11
2
7 9
2 2
3
4 15 7
9 3
4
4 5
4
5
8 2
3 4
1
6
4 2
1 7
6 7
7
12 5
2 4
8
8
7 6
8 3
9
4 1
3 7
13 2 6
10
1 4
1 8
5
V
j
Применяя рекурсивную формулу для расчета расстояний, найдем опорное решение (табл. 2).
Таблица 2. Опорное решение
1
2
3
4
5
6
7
8
9
10
U
i
1
3 8
11 0
2
7 9
2 2
3
3
4 15 7
9 3
10
4
4 5
4 12
5
8 2
3 4
1 5
6
4 2
1 7
6 7
8
7
12 5
2 4
8 5
10 1
2 8
4 7
5 9
3 6

8
7 6
8 3
9
9
4 1
3 7
13 2 6
6
10
1 4
1 8
5 12
V
j
0 3
10 12 5 8
5 9
6 12
Проверяем условие:
d
ij
≥ V
j
-
U
i
.
В строке 5 условие не выполнено для
d
53
, проводим перерасчет с учетом найденных элементов
V
3
= U
5
+
d
53
=7
,
полагаем
U
3
= V
3
=7
и продолжаем проверку. Следующие несоответствующие элементы
d
74
,
d
76
,
d
98
. Результаты приведены в дополнительнойстроке и столбце таблицы 3.
Таблица 3. Окончательное решение
1
2
3
4
5
6
7
8
9
10
U
i
1
3 8
11 0
2
7 9
2 2
3
3
4 15 7
9 3
10 7
4
4 5
4 12 10
5
8 2
3 4
1 5
6
4 2
1 7
6 7
8 7
7
12 5
2 4
8 5
8
7 6
8 3
9 8
9
4 1
3 7
13 2 6
6
10
1 4
1 8
5 12
V
j
0 3
10 12 5 8
5 9
6 12 7
10 7
8
В результате получили матрицу расстояний от пункта 1 к любому другому.
Найдем кратчайший путь к пункту 1, используя условие из рекуррентной формулы:
U
i
= V
j
-
d
ij
(табл.4).
Таблица 4. Решение для поиска пути из первого пункта в последний.
1
2
3
4
5
6
7
8
9
10
U
i
1
3 8
11 0
2
7 9
2 2
3
3
4 15 7
9 3
7
4
4 5
4 10
5
8 2
3 4
1 5
6
4 2
1 7
6 7
7
7
12 5
2 4
8 5
8
7 6
8 3
8
9
4 1
3 7
13 2 6
6
10
1 4
1 8
5 12
V
j
0 3
7 10 5
7 5
8 6
12
Кратчайший путь:
1 2
5 9
10 с расстоянием в 12 единиц.
Для нахождения обратного пути матрица просчитывается от конечного пункта с учетом циклич- ности сети.
В результате получим опорное решение (табл.5).
Таблица 5. Решение для поиска пути из последнего пункта в первый.
1
2
3
4
5
6
7
8
9
10
U
i

1
3 8
11 7
2
7 9
2 2
5
3
4 15 7
9 3
4
4
4 5
4 1
5
8 2
3 4
1 4
6
4 2
1 7
6 7
3
7
12 5
2 4
8 1
8
7 6
8 3
7
9
4 1
3 7
13 2 6
5
10
1 4
1 8
5 0
V
j
7 5
4 1
4 3
1 7
5 0
Т. к. условие
d
ij
≥ V
j
-
U
i
выполняется везде, то по таблице начиная с левой верхней ячейки (с конца) находим обратный путь: в первой колонке для
U
i
=7 1- 6, в шестой колонке для
U
i
=3 6-7, в седьмой колонке для
U
i
=1 7-10, так что окончательно путь длины 7 определяет цепь
10 7
6 1
Определим кратчайший путь на сети с использованием алгоритма Дейкстры.
Построим дерево, соответствующее заданной сети. Дерево строится не до всех конечных узлов путей возможных для данной вершины графа, а лишь для тех, которые ведут к заданной конечной вер- шине. Причем вершины, для которых не имеет смысла продолжать путь, оставляются без дальнейшего внимания.
Корнем дерева возьмем соответствующий начальный узел сети (вершину графа) - 1 (рис.2).
Помечаем вершину 1.
Рис. 2
Сначала пойдем по левой ветви, т. к. до вершины 2 путь наименьший. Помечаем вершину 2 (рис.3).
2 4
3 5
6 1
2 3
7 5
6 1
9 8
1 0
8 7
3 2
7 5
4 3
2 5
1 0
7 9
8 3
2 2
4 6
9 1

Рис. 3.
Далее опять идем по меньшему пути , т. е. к вершинам 5 и 7. При этом, т. к. пути 2 3, 1 5, 1 6 ока- зываются длиннее, мы их не будем рассматривать. В результате подобных рассуждений мы получим три пути:
1. 1 2
4 10 (длина = 16)
2. 1 2
7 4
10 (длина = 14)
3. 1 2
7 10 (длина = 13)
Осталось рассмотреть вершины 3, 8 и 9, исходящие из пятой. Результаты представлены на рис.4.
Рис. 4.
Таким образом нашли еще один путь
1 2
5 9
10 (длина = 12), причем все остальные пути оказались заведомо большими.
Сравнивая полученные результаты, выбираем кратчайший:
1 2
5 9
10 (длина = 12).
4. Максимальный поток
4.1. Алгоритм нахождения максимального потока
Рассматривается задача определения максимального потокамежду двумя выделенными узлами связной сети. Каждая дуга сети обладает пропускными способностями в обоих направлениях, которые определяют максимальное количество потока, проходящего по данной дуге. Ориентированная (одно- сторонняя) дуга соответствует нулевой пропускной способности в запрещенном направлении.
Пропускные способности с ij сети можно представить в матричной форме. Для определения мак- симального потока из источника s в сток t используются следующие шаги.
Шаг 1. Найти цепь, соединяющую s с t, по которой поток принимает положительное значение в направ- лении s→t. Если такой цепи не существует, перейти к шагу 3. В противном случае перейти к шагу 2.
Шаг 2. Пусть c
- ij
— пропускные способности дуг цепи (s, t) в направлении s→t(t→s) и
=min{c
- ij
}>0
Матрицу пропускных способностей C
ij можно изменить следующим образом:
(а) вычесть из всех c
- ij
;
(б) прибавить ко всем c
+
ij
. При этом общая пропускная способность сети не изменится. Перейти к шагу 1.
Операция (а) дает возможность использовать остатки пропускных способностей дуг выбранной цепи в направлении s→t. Операция (б) восстанавливает исходные пропускные способности сети, по- скольку уменьшение пропускной способности дуги в одном направлении можно рассматривать как уве- личение ее пропускной способности в противоположном направлении.
6 8
9 6
4 2
3 1
3 4
6 8
8 2
1 3
5 7
1 0
9

Шаг 3. Найти максимальный поток в сети. Пусть С=||с ij
|| — исходная матрица пропускных способно- стей, и пусть С*=||с
*
ij
|| — последняя матрица, получившаяся в результате модификации исходной мат- рицы (шаги 1 и 2).
Оптимальный поток X=||x ij
|| в дугах задается как
ij
ij
ij
ij
ij
ij
ij
c
c
c
c
c
c
x
*
*
*
,0
,
Максимальный поток из s в t равен
j
jt
i
si
x
x
z
4.2. Пример нахождения максимального потока
Рассмотрим сеть на рис.5 с данными пропускными способностями.
Рис. 5. Граф сети.
Матрица пропускных способностей С приведена в табл. 6.
Табл. 6 . Цепь (s→1→4→t), =5 Табл. 7 . Цепь (s→3→2→t), =10 s
1 2
3 4 t s
5 3
14 4
1 10 5
9 0
2 5
6 15 10 3
12 7
10 7
2 4
3 14 8
8 t
3 4
10
В качестве исходной цепи можно выбрать s→1→4→t. Таким образом, ячейки (s, 1), (1, 4) и (4, t) помечаются знаком (-), а ячейки (1, s), (4, 1) и (t, 4) - знаком (+). Для данной цепи максимальный поток определяется как
=min{c s1
, c
14
, c
4t
=min{10, 5,13 =5.
Матрица С в табл. 6 корректируется путем вычитания =5 из всех элементов, помеченных зна- ком (-), и сложения со всеми элементами, имеющими знак (+). Результаты приведены в табл. 7.
Результаты последующих итераций приведены в табл. 8-11.
Табл. 8. Цепь (s→1→3→4→t), =5. Табл. 9. Цепь (s→1→3→4→t), =3. s
1 2
3 4 t s
10 3
14 4
1 5
5 9
5 2
5 6
15 10 3
12 7
10 7
2 4
3 9
8 13 t
3 4
5

s
1 2
3 4 t s
0 3
4 4
1 15 5
4 0
2 5
6 25 0
3 22 12 0
2 2
4 3
14 13 3 t
13 4
15
Табл. 10. Цепь (s→3→t), =2 . Табл.
11. Нет стока. s
1 2
3 4 t s
0 3
2 1
1 15 5
4 0
2 5
6 25 0
3 24 12 0
2 0
4 6
14 13 0 t
13 4
20
Из табл. 11 следует, что между s и t нельзя построить цепей с положительным потоком, посколь- ку все элементы в столбце t равны нулю. Таким образом, табл. 4.6 дает матрицу C
*
. Из табл.6 (матрица
С) и табл.11 (матрица С
*
) вычисляем матрицу оптимального потока, элементы которой Х=C-C* с заме- ной отрицательных величин нулями. В табл.12 приведена матрица X, а в табл.13 показана исходная матрица с отметкой узлов, через которые происходит сток
Таблица 12. Матрица оптимального потока Таблица 13. Исходная матрица
Из табл.12 видно, что z=10+12+3=25. Сумма всех (=5+10+5+3+2=25) также дает максимальный поток.
5. Календарное планирование
5.1. Историческая справка
До появления сетевых методов календарное планирование программ (планирование во времени) осуществлялось в небольшом объеме. Наиболее известным средством такого планирования быллен- точный (линейный)график Ганта, задававший сроки начала и окончания каждой операции на горизон- тальной шкале времени. Его недостаток заключается в том, что он не позволяет установить зависимости между различными операциями (определяющие в значительной мере темпы реализации программы). В связи с повышением сложности современных программ потребовалась разработка более четких и эф- фективных методов планирования, обеспечивающих оптимизацию всего процесса осуществления про- грамм. При этом эффективность интерпретируется как минимизация продолжительности выполнения программы с учетом экономических факторов использования имеющихся ресурсов.
Организационное управление программами стало новой областью теоретических и прикладных исследований благодаря разработке двух аналитических методов структурного и календарного плани- рования, а также оперативного управления программами. Эти методы, разработанные почти одновре- менно в 1956— 1958 гг. двумя различными группами, получили названия метод критического пути
s
1 2
3 4 t s
5 3
4 4
1 10 5
9 0
2 5
6 25 0
3 22 7
0 7
2 4
3 14 8
8 t
13 4
10 s
1 2
3 4 t s
0 3
4 1
1 15 5
4 0
2 5
6 25 0
3 22 12 0
2 2
4 6
14 13 0 t
13 4
18 s
1 2
3 4 t s
10 12 3
1 5
5 2
10 3
10 5
2 4
13 t s
1 2
3 4 t s
10 3
14 4
1 5
5 9
5 2
5 6
15 10 3
12 7
10 7
2 4
3 9
8 13 t
3 4
5

(МКП) и метод оценки и пересмотра программ (ПЕРТ). Метод критического пути был предложен фирмой Е. I. du Font de Nemours & Company для управления программами строительства, а затем был развит и обобщен фирмой Mauchly Associates. Метод ПЕРТ разработан консультативной фирмой по заказу военно-морского министерства США для календарного планирования научно- исследовательских и опытно-конструкторских работ программы создания ракет ―Поларис‖.
В методах ПЕРТ и МКП основное внимание уделяется временному аспекту планов в том смысле, что оба метода в конечном счете определяют календарный план программы. Хотя эти методы были раз- работаны независимо, они отличаются поразительным сходством. Пожалуй, самым существенным раз- личием первоначально было то, что в методе МКП оценки продолжительности операций предполага- лись детерминированными величинами, а в методе ПЕРТ — случайными. В настоящее время оба мето- да составляют единый метод сетевого планирования и управления (СПУ) программами.
Сетевое планирование и управление (СПУ) программами включает три основных этапа:структурное
планирование, календарное планирование и оперативное управление.
Этап структурного планирования начинается с разбиения программы на четко определенные операции. Затем определяются оценки продолжительности операций и строится сетевая модель (сете- вой график, стрелочная диаграмма), каждая дуга (стрелка) которой отображает работу. Вся сетевая мо- дель в целом является графическим представлением взаимосвязей операций программы. Построение сетевой модели на этапе структурного планирования позволяет детально проанализировать все опера- ции и внести улучшения в структуру программы еще до начала ее реализации. Однако еще более суще- ственную роль играет использование сетевой модели для разработки календарного плана выполнения программы.
Конечной целью этапа календарного планирования является построение календарного графика, определяющего моменты начала и окончания каждой операции, а также ее взаимосвязи с другими опе- рациями программы. Кроме того, календарный график должен давать возможность выявлять критиче- ские операции (с точки зрения времени), которым необходимо уделять особое внимание, чтобы закон- чить программу в директивный срок. Что касается некритических операций, то календарный план дол- жен позволять определять их резервы времени, которые можно выгодно использовать при задержке вы- полнения таких операций или с позиций эффективного использования ресурсов.
Заключительным этапом является оперативное управление процессом реализации программы.
Этот этап включает использование сетевой модели и календарного графика для составления периодиче- ских отчетов о ходе выполнения программы. Сетевая модель подвергается анализу и в случае необхо- димости корректируется. В этом случае разрабатывается новый календарный план выполнения осталь- ной части программы.