Построение нормализованного графа

Наряду с приведенным выше обозначением передачи широко пользуются и другим обозначением, при котором отсчет ведется от конца ветви к ее началу,

что оказывается удобным при вычислениях: Построение нормализованного графа - student2.ru .

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

Построение нормализованного графа - student2.ru , (1)

где N – число вершин графа, Построение нормализованного графа - student2.ru - передачи входящих в вершину k рёбер (если в ней нет входящего ребра от какой-то вершины i, то соответствующая передача Построение нормализованного графа - student2.ru считается равной нулю). Так как в каждом узле переменная определяется формулой (1), то граф соответствует системе линейных уравнений

Построение нормализованного графа - student2.ru , где Построение нормализованного графа - student2.ru . (2)

Передачу рёбер можно записать в виде квадратной NxN матрицы Построение нормализованного графа - student2.ru . (Здесь i – номер строки, j – номер столбца, т.е. в строки записываются передачи к данному узлу от всех вершин, а в столбцы - от данного узла ко всем узлам). Если все элементы строки являются нулями, то соответствующая вершина является источником, если все элементы столбца являются нулями, то соответствующая вершина является стоком.

Пусть задана система линейных уравнений:

Построение нормализованного графа - student2.ru , (3)

по которой нужно построить граф.

На поле графа наносится N точек, причем Построение нормализованного графа - student2.ru , где Построение нормализованного графа - student2.ru - число уравнений системы, а Построение нормализованного графа - student2.ru - число правых частей, не равных нулю. Очевидно, что Построение нормализованного графа - student2.ru . Точки нумеруются, каждой точке сопоставляется одна переменная Построение нормализованного графа - student2.ru или Построение нормализованного графа - student2.ru . В результате образуется совокупность вершин графа.

Вершины, которым соответствуют переменные Построение нормализованного графа - student2.ru , являются зависимыми, независимым переменным соответствуют правые части. В однородных системах все узлы являются зависимыми.

Располагать точки на поле графа можно произвольно. Однако чтобы задать в матрице А определенное расположение строк и столбцов, первым по порядку Построение нормализованного графа - student2.ru точкам сопоставляются зависимые узлы, а оставшимся Построение нормализованного графа - student2.ru точкам - независимые (если необходимо составлять матрицу А). Если составлять матрицу А не надо, то учитывают удобство начертания и наглядность графа. Построение нормализованного графа - student2.ru

Передачи рёбер графа по заданной системе можно определять двумя способами, каждый из которых приводит к своему графу, которые являются равносильными. Граф, построенный по первому способу, называется нормализованным, по второму - ненормализованным.

Для построения нормализованного графа систему (3) переписывают таким образом, чтобы в каждом уравнении коэффициент при одной переменной Построение нормализованного графа - student2.ru был равен 1. Для этого переносят все члены уравнения, не содержащие эту переменную, в правую часть, и выражают нормализованную переменную через остальные. Например, первое уравнение системы примет вид:

Построение нормализованного графа - student2.ru .

Переписывая второе уравнение в виде, нормализованном относительно Построение нормализованного графа - student2.ru , третье - относительно Построение нормализованного графа - student2.ru , и т.д., получим соответствующие строки матрицы Построение нормализованного графа - student2.ru .

Матрица Построение нормализованного графа - student2.ru имеет вид:

Построение нормализованного графа - student2.ru ,

где Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru ; Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , и т.д.

Или, в общем виде, Построение нормализованного графа - student2.ru ; Построение нормализованного графа - student2.ru ;

Построение нормализованного графа - student2.ru ; Построение нормализованного графа - student2.ru .

После этого, в соответствии с матрицей Построение нормализованного графа - student2.ru , нужно соединить узлы графа между собой. Матрица полученного нормализованного графа называется нормализованной. В ней все элементы главной диагонали равны нулю, что соответствует отсутствию петель в нормализованном графе.

Пример 1. По данной системе уравнений построить нормализованный граф, не составляя матрицу Ан в явном виде, затем по графу составить матрицу Ан.

Построение нормализованного графа - student2.ru Построение нормализованного графа - student2.ru .

Для данной системы Построение нормализованного графа - student2.ru , следовательно, число вершин Построение нормализованного графа - student2.ru .

Запишем систему в следующем виде: Построение нормализованного графа - student2.ru . Нормализованный граф изображен на рис. 29.

Построение нормализованного графа - student2.ru Построение нормализованного графа - student2.ru
Рис. 29. Рис. 30.

Над вершинами графа указаны их номера, под вершинами – соответствующие зависимые или независимые переменные (в данном случае это числа 1 и 3, обведенные окружностью). Нормализованная матрица приведена на рис. 30.

Построение нормализованного графа - student2.ru Построение нормализованного графа - student2.ru .

Определим число вершин: Построение нормализованного графа - student2.ru (рис 31). Из первого уравнения Построение нормализованного графа - student2.ru (рис. 32).

Построение нормализованного графа - student2.ru Построение нормализованного графа - student2.ru
Рис. 31. Рис. 32.

Из второго уравнения Построение нормализованного графа - student2.ru (рис. 33), из третьего – Построение нормализованного графа - student2.ru (рис.34), из четвертого – Построение нормализованного графа - student2.ru (рис.35). Объединяя все части, получим граф, изображенный на рис. 36.

Построение нормализованного графа - student2.ru Построение нормализованного графа - student2.ru
Рис. 33. Рис. 34.
Построение нормализованного графа - student2.ru Построение нормализованного графа - student2.ru
Рис. 35. Рис. 36.

Нормализованная матрица Построение нормализованного графа - student2.ru .

Пример 2. По заданной системе уравнений Построение нормализованного графа - student2.ru

составить матрицу Ан , считая источником Построение нормализованного графа - student2.ru , затем построить нормализованный граф. По графу составить систему уравнений.

Нормализованная матрица и нормализованный граф имеют следующий вид:

Построение нормализованного графа - student2.ru Построение нормализованного графа - student2.ru

Нормализованному графу соответствует следующая система уравнений:

Построение нормализованного графа - student2.ru .

§7. Задача о кратчайшем пути на графе.
Алгоритм Дейкстры

Напомним, что сетью называется пара N=(G,α), где G – орграф, а α – функция из множества вершин графа в множество действительных чисел. Другими словами, каждой дуге графа поставлено в соответствие некоторое неотрицательное число, которое в данном случае называется длиной дуги. Введем длину пути как сумму длин дуг, составляющих путь. Расстоянием d(u,v) от вершины uдо вершины v называется длина кратчайшего пути из u в v. Если нет ни одного пути из u в v, то считают d(u,v)=∞. Расстояние от u до u равно нулю.

Для сети N возникает задача нахождения расстояния d(u,v) для данных вершин u и v и соответствующего кратчайшего пути. Известно несколько способов решения этой задачи. Мы рассмотрим один из них, основой которого является алгоритм Дейкстры. Он вычисляет расстояние от фиксированной вершины v0 до всех остальных вершин сети.

Прежде, чем привести описание алгоритма, введем необходимые обозначения. Пусть N=(G,α) – сеть, v0 – фиксированная вершина этой сети, v1,…,vm – остальные вершины. На множестве пар вершин (u,v) введем функцию L(u,v) следующим образом:

L(u,v)= Построение нормализованного графа - student2.ru α(e), если e – дуга с началом в u и концом в v,
∞ – если такой дуги не существует.

В описании алгоритма участвует еще некоторое подмножество S множества V вершин графа. В ходе выполнения алгоритма вершины последовательно исключают из S, до тех пор, пока не останется ни одной, и вычисляют величины d(vi),равные кратчайшему пути из v0вvi ,не содержащему вершин из S. Алгоритм также имеет графическую реализацию, в которой множеству S соответствуют неокрашенные вершины, а окрашивание – это исключение вершины из S. Итак, дадим формальное описание алгоритма Дейкстры.

Шаг 1. (инициализация).ПоложитьS:=V\{v0} (то есть окрасить вершину v0), d(vi)=∞для всех i=1,…,m, положить y= v0.

Шаг 2. Для всех v Построение нормализованного графа - student2.ruS (т.е. для всех неокрашенных вершин) пересчитать d(v) по формуле: d(v) =min{ d(v), d(y)+L(y,v)}. Если все d(v)= ∞, перейти к шагу 5 (это означает, что в графе отсутствуют пути из v0в неокрашенные вершины).

Шаг 3. Выбрать в S вершину w,для которой величина d(v) минимальна, и положить S:=S\{w}, т.е. окрасить вершину w.Окрасить дугу, ведущую в вершину w из вершины, которая была взята в качестве y последний раз, когда в менялось значение d для вершины w . Положить y= w. Если S не пусто, перейти к шагу 2, иначе к шагу 4.

Шаг 4. Конец работы алгоритма.

При графической реализации алгоритма для графа будет построено покрывающее дерево с корнем в вершине v0 (если оно существует). Если требуется определить не сам кратчайший путь, а лишь его длину, то можно не проводить окрашивание, а только вычислять на каждой итерации множество S . Расчет условно оформлять в виде таблице, как показано в следующем примере.

Пример 1.Для графа, изображенного на рис. 37, найти расстояния от вершины v0до остальных вершин и построить дерево кратчайших путей с корнем в v0.

Построение нормализованного графа - student2.ru

Рис. 37.

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


y d(v1) d(v2) d(v3) d(v4) d(v5) Рисунок
v0 ¥ ¥ ¥ ¥ ¥ Рис.38
v0 ¥ ¥ ¥ Рис.39
v2   ¥ ¥ Рис.40
v1     Рис.41
v3       Рис.42
v4         Рис.43

Строка с номером ноль соответствует состоянию переменных после выполнения шага 1. Клетка d(vi)заполняется только для вершин, входящих в S. Пока это все вершины, кроме v0. Строка номер 1 показывает состояние переменных после выполнения шага 2. Действительно, L(v0, v1)=4 (см. рис.37), следовательно, новое значение для d(v1)есть min(4, ∞)=4. Аналогично вычисляются остальные значения d(vi). Наименьшим из них является d(v2)=1 (выделено жирным шрифтом), следовательно, на шаге 3 вершина v2будет принята в качестве w, окрашена и исключена из S. Значение d(v2)изменилось последний раз при переходе от строки 0 к строке 1, в строке 1 стоит y= v0,значит, окрашиваем ребро, ведущее из v0в v2 (см. рис. 39). После этого присваиваем переменной yзначение v2,и, таккак есть еще неокрашенные вершины, переходим опять к шагу 2. На этом первый проход алгоритма заканчивается. Заметим, что d(v2)=1 является расстоянием от v0до v2.

Построение нормализованного графа - student2.ru Построение нормализованного графа - student2.ru Построение нормализованного графа - student2.ru
Рис. 38. Рис. 39. Рис. 40.

При втором проходе на шаге 2 снова пересчитываются значения d(vi)для неокрашенных вершин. (Заметим, что фактически значения d(vi) нужно пересчитывать лишь для вершин, которые имеют входящее ребро из вершины y, так как для остальных неокрашенных вершин L(y,vi)=∞ ). Результат приведен в строке 2 таблицы. Минимальным является d(v1)=3,поэтому на шаге 3 вершина v1 будет окрашена и исключена из S. Кроме того, будет окрашено ребро, соединяющее v2 и v1 (рис. 40). После этого переменная w получает значение v1 и мы снова переходим ко второму шагу.

На третьем проходе алгоритма после пересчета d(vi)окрашивается вершина v3и ребро, ведущее в неё из вершины v1 (рис. 41).

Построение нормализованного графа - student2.ru Построение нормализованного графа - student2.ru Построение нормализованного графа - student2.ru
Рис. 41 Рис. 42 Рис.43

На четвертом проходе получаются значения, приведенные в строке 4. Минимальным является d(v4)=5. Последний раз значение d(v4) менялось при переходе от строки 1 к строке 2, в строке 2 было y=v2 , следовательно, нужно окрасить ребро, соединяющее v2 с v4 (рис. 42). Аналогично, на пятом проходе окрашиваем ребро, соединяющее v5 с v1. На этом работа алгоритма заканчивается, получившееся дерево кратчайших путей показано на рис. 43, расстояния от до остальных вершин выделены в таблице жирным шрифтом.

Алгоритм Дейкстры может быть применен и для поиска кратчайшего пути в неориентированном графе, для этого нужно в определении функции L(u,v) учитывать все ребра.

Пример 2. Найти расстояния от вершины v1до остальных вершин и построить дерево кратчайших путей для следующего графа:

Построение нормализованного графа - student2.ru

Результаты работы алгоритма приведены в таблице, дерево кратчайших путей – на рис. 44.

N y d(v2) d(v3) d(v4) d(v5) d(v6) d(v7) d(v8) d(v9)
v1 ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥
v1 ¥ ¥ ¥ ¥ ¥
v2   ¥ ¥ ¥ ¥
v4     ¥ ¥
v3       ¥ ¥
v5         ¥
v6          
v7            
v8              

Построение нормализованного графа - student2.ru

Рис. 44.

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

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

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

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

Таблица 1.

Операция Предшествующие операции Время выполнения
a1
a2
a3
a4 a1, a2
a5 a2, a3
a6 a4, a5

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

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

Пример 2. Сетевой график для проекта, заданного таблицей 1, изображен на рис. 45.

Построение нормализованного графа - student2.ru

Рис. 45.

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

Пример 3. Упростить сетевой график некоторого проекта, изображенный на следующем рисунке.

Построение нормализованного графа - student2.ru

При упрощении выброшены дуги α, β, γ. Последовательность выполнения работ при этом не изменилась. Дугу δ выбросить нельзя, так как после этого дуги – работы a4 и a7 будут неразличимы (рис. 46).

Построение нормализованного графа - student2.ru

Рис. 46.

Сетевой график не может содержать циклов. Действительно, если предположить, что имеется некоторый цикл (a1, a2, …, an-1, an, a1), то операция a1 может быть выполнена только после завершения операции an , операция an только после завершения операции an-1, ..., операция a2 – только после завершения операции a1. В этом случае проект никогда не может быть выполнен.

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

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

1. Нумеруют все начальные вершины.

2. Вычеркивают все дуги, выходящие из начальных вершин. При этом получают новые начальные вершины. Если не все вершины перенумерованы, переходят к шагу 1.

Конечная вершина получает при этом наибольший номер.

Рассмотрим временные параметры сетевого графика. Предположим, что выполнение работы начато в момент времени t=0. Пусть tij – заданная продолжительность работы (vi, vj), которая соответствует ребру, соединяющему вершины vi и vj. Величины tij записывают на соответствующих дугах сетевого графика и считают их длинами.

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

Если из вершины vi выходит несколько работ, то ранние сроки начал этих работ совпадают и называются ранним сроком наступления события vi. Ранний срок начала работы (vi, vj) обозначают через Построение нормализованного графа - student2.ru , а ранний срок наступления события vi – через Построение нормализованного графа - student2.ru . Для удобства величины Построение нормализованного графа - student2.ru записывают в верхней трети каждой вершины (рис. 47).

Построение нормализованного графа - student2.ru

Рис. 47.

Если работа начата в ранний срок начала, то время ее окончания называется ранним сроком окончания работы. Ранний срок окончания работы (vi, vj) обозначается Построение нормализованного графа - student2.ru .

Будем считать, что нумерация вершин является правильной, и вместо viбудем указывать только номер i этой вершины.

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

1. Полагают Построение нормализованного графа - student2.ru .

2. Для i=2, 3, ..., п вычисляют Построение нормализованного графа - student2.ru , где Bi – множество вершин, из которых выходят ребра, входящие в вершину i.

Номер k той вершины, для которой получено значение Построение нормализованного графа - student2.ru , заносят в левую треть вершины i (рис. 47).

После нахождения величин Построение нормализованного графа - student2.ru рассчитывают ранние сроки начал и окончаний работ по формулам:

Построение нормализованного графа - student2.ru = Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru = Построение нормализованного графа - student2.ru + tij .

Пример 4. Найти ранние сроки начал и окончаний работ для сети, изображенной на рис. 48.

Построение нормализованного графа - student2.ru

Рис. 48.

Полагаем Построение нормализованного графа - student2.ru . После этого рассматриваем вершины в
порядке их номеров: Построение нормализованного графа - student2.ru . В левую треть
вершины v2 ставим номер вершины v2; далее, Построение нормализованного графа - student2.ru . В левую треть вершины v3 записываем номер вершины v2 (так как при движении из v2получено значение Построение нормализованного графа - student2.ru ). Аналогичным образом вычисляем, что Построение нормализованного графа - student2.ru и Построение нормализованного графа - student2.ru . После этого находим ранние сроки начал и окончаний работ: Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru . Результаты вычислений вносим на сетевой график (рис. 49).

Построение нормализованного графа - student2.ru

Рис. 49.

Критическое время и критический путь. Ранний срок наступления конечного события называется критическим временем и обозначается Построение нормализованного графа - student2.ru . Весь проект не может быть завершен раньше момента времени Построение нормализованного графа - student2.ru , т. е. критическое время – это минимальный срок окончания всего комплекса работ. На сетевом графике Построение нормализованного графа - student2.ru – это длина пути наибольшей длины из начальной вершины в конечную.

Всякий путь длины равной Построение нормализованного графа - student2.ru из начальной вершины в конечную называется критическим путем. Для его построения используется следующий алгоритм. Начинают построение с конечной вершины. В ее левой трети стоит номер той вершины, при движении из которой определялся ранний срок наступления события. Критический путь идет из конечной вершины в вершину с этим номером; затем в вершину, номер которой стоит в левой трети полученной при движении вершины, и так до начальной вершины.

Пример 5.Для сети, изображенной на рис. 49, критический путь выделен жирной линией.

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

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

Поздние сроки начал и окончаний работ. Заметим, что каждое событие должно произойти не слишком поздно, чтобы обеспечить последовательное выполнение всех операций некоторого пути от этого события до конечного. С учетом этого всем событиям удобно сопоставить второе множество чисел, называемых поздними сроками наступления этих событий. Они аналогичны ранним срокам наступления, но их измерение производится относительно конечного события, а не начального. Дадим формальное определение. Зададим время Т выполнения всего комплекса работ. Очевидно, что должно выполняться неравенство Т≥ Построение нормализованного графа - student2.ru . Обычно берут Т= Построение нормализованного графа - student2.ru , что и предполагается в дальнейшем.

Поздним сроком окончания работы называется наибольшее допустимое время окончания работы без нарушения срока завершения всего проекта. Поздний срок окончания работы (vi, vj) обозначается Построение нормализованного графа - student2.ru . Можно определить поздний срок начала работы (vi, vj) по формуле

Построение нормализованного графа - student2.ru = Построение нормализованного графа - student2.ru – tij .

Поздним сроком Построение нормализованного графа - student2.ru наступления события vj называется наиболее поздний срок окончания всех работ, входящих в соответствующую вершину. Для вычисления поздних сроков наступления событий используется следующий алгоритм.

1. Полагают Построение нормализованного графа - student2.ru .

2. Для j=n-1, n-2, ...,2, 1 вычисляют Построение нормализованного графа - student2.ru , где Aj – множество вершин, в которые входят ребра, выходящие из вершины j.

Таким образом, для конечной вершины поздний срок наступления событий совпадает со временем выполнения всего проекта. Затем просматривают все вершины в порядке убывания их номеров. Для каждой вершины рассматривают множество всех выходящих работ. Из поздних сроков наступления их концов вычитают продолжительность этих работ. Минимальная из этих разностей и равна Построение нормализованного графа - student2.ru . Величину Построение нормализованного графа - student2.ru записывают для удобства вычислений в правой трети вершины vj (рис. 47).

Пример 6. Положим для сети, изображенной на рис. 48, время окончания всего комплекса работ Т= Построение нормализованного графа - student2.ru =15 и поставим это значение в правую треть вершины v5. Перейдем к событию v4: Построение нормализованного графа - student2.ru . Аналогично находим Построение нормализованного графа - student2.ru .

Из вершины v2выходят две работы, поэтому

Построение нормализованного графа - student2.ru .

Аналогично получаем Построение нормализованного графа - student2.ru . Результаты вычислений приведены на рис. 50.

Построение нормализованного графа - student2.ru

Рис. 50.

Из алгоритма вычисления поздних сроков следует, что увеличение позднего срока окончания проекта Т на t единиц ведет к увеличению поздних сроков наступления всех событий также на t единиц.

После определения Построение нормализованного графа - student2.ru можно вычислить поздние сроки начала и окончаний всех работ проекта:

Построение нормализованного графа - student2.ru = Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru = Построение нормализованного графа - student2.ru – tij .

Резервы времени. Рассмотрим некоторую работу (vi, vj). Найдем время, которое можно выделить для выполнения этой работы без задержки срока окончания всего проекта. Работа (vi, vj) не может быть начата раньше срока Построение нормализованного графа - student2.ru и должна быть закончена не позднее времени Построение нормализованного графа - student2.ru . Для выполнения этой работы можно затратить не более Построение нормализованного графа - student2.ruПостроение нормализованного графа - student2.ru единиц времени. По плану эту работу можно сделать за tij единиц времени.

Максимально допустимое время, на которое можно увеличить продолжительность выполнения работы (vi, vj)или отложить начало так, что это не вызовет задержки выполнения всего проекта, называется полным резервом времени.

Полный резерв времени работы (vi, vj)обозначают Rij, он равен

Rij= Построение нормализованного графа - student2.ruПостроение нормализованного графа - student2.ru – tij

Если полный резерв времени некоторой работы равен нулю, то задержка ее выполнения вызовет такую же по времени задержку выполнения всего проекта.

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

Найдем время, которое можно дополнительно выделить для выполнения работы (vi, vj) без введения дополнительных ограничений на время выполнения последующих работ. Для этого выполнение работы должно быть закончено к моменту времени Построение нормализованного графа - student2.ru . Таким образом можно выделить Построение нормализованного графа - student2.ruПостроение нормализованного графа - student2.ru единиц времени на выполнение работы (vi, vj).

Величина rij= Построение нормализованного графа - student2.ruПостроение нормализованного графа - student2.ru – tij называется свободным резервом времени работы (vi, vj). Если использовать свободный резерв на некоторой операции, то последующие работы могут быть по-прежнему начаты в свои ранние сроки.

Резервы времени удобно рассчитывать по сетевому графику, так как величины Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru записаны в его вершинах. Полученные значения резервов записывают около соответствующих дуг сетевого графика. Сначала ставят полный резерв, а затем свободный.

Отметим, что если поздние сроки найдены при Т= Построение нормализованного графа - student2.ru , то для любой работы (vi, vj), лежащей на критическом пути, Построение нормализованного графа - student2.ru = Построение нормализованного графа - student2.ru , Построение нормализованного графа - student2.ru = Построение нормализованного графа - student2.ru + tij, и следовательно, Rij=rij=0.

Пример 7. Для сети, изображенной на рис. 50, имеем:

R24= Построение нормализованного графа - student2.ruПостроение нормализованного графа - student2.ru – t24=14–2–5=7, r24= Построение нормализованного графа - student2.ruПостроение нормализованного графа - student2.ru – t24=7–2–5=0,

R45= Построение нормализованного графа - student2.ruПостроение нормализованного графа - student2.ru – t45=15–7–1=7, r45= Построение нормализованного графа - student2.ruПостроение нормализованного графа - student2.ru – t45=15–7–1=7,

R13= Построение нормализованного графа - student2.ruПостроение нормализованного графа - student2.ru – t13=8–0–4=4, r13= Построение нормализованного графа - student2.ruПостроение нормализованного графа - student2.ru – t13=8–0–4=4.

Для остальных работ резервы времени равны нулю, так как они лежат на критическом пути. Результаты вычислений показаны на рис. 51.

Наши рекомендации