СЕТЕВЫЕ ГРАФИКИ
Такие крупные проекты, как строительство дома, разработка автоматизированной системы бухгалтерского учета, изготовление станка и т.д. можно разбить на большое количество различных операций (работ). Одни операции могут выполняться одновременно, другие — только последовательно: одна операция после окончания другой. Например, при строительстве дома можно совместить во времени внутренние отделочные работы и работы по благоустройству территории, однако возводить стены можно только после того, как будет готов фундамент 
Основные задачи планирования работ по осуществлению некоторого проекта: 
определение времени возможного окончания как всего проекта в целом, так и отдельных работ, образующих проект; 
определение резервов времени для выполнения отдельных работ; 
определение критических работ, то есть таких работ, задержка в выполнении которых ведет к задержке выполнения всего проекта в целом; 
управление ресурсами, если таковые имеются и т.п 
Пусть некоторый проект W состоит из работ V 1 ,..., V n ; для каждой работы V k известно, или может быть достаточно точно оценено время ее выполнения t ( V k ). Кроме того, для каждой работы V k известен, возможно пустой, список ПРЕДШ( V k ) работ, непосредственно предшествующих выполнению работы V k . Иначе говоря, работа V k может начать выполняться только после завершения всех работ, входящих в список ПРЕДШ( V k ) 
В список работ проекта W добавим две фиктивные работы s и p , где работа s обозначает начало всего проекта W. а работа p — завершение работ по проекту W. При этом будем считать, что работа s предшествует всем тем работам v Î W, для которых список ПРЕДШ(v) пуст, иначе говоря, для всех таких работ v Î W   положим   ПРЕДШ(v)={s}.   Положим далее ПРЕДШ(s) = Æ , ПРЕДШ( p )={v Î W: v не входит ни в один список ПРЕДШ(w)}, то есть считаем, что работе p предшествуют все те работы, которые могут выполняться самыми последними. Время выполнения работ s и p естественно положить равными нулю:    t(s)=t( p )=0 
Весь проект W теперь удобно представить в виде сети G =( V , E , c ). Ориентированный взвешенный граф G =( V , E , c ) называется сетью. Сеть может быть представлена матрицей весов дуг, массивами смежностей СЛЕД или ПРЕДШ, или списками СЛЕД[ v ] или ПРЕДШ[ v ]. При этом записи в списках смежности состоят из трех компонент: поля имени узла, поля веса соответствующей дуги и поля ссылки на следующую запись), где сеть G =( V , E , c ) определим по правилам: 
V = W , то есть множеством узлов объявим множество работ; 
E ={( v , w ) : v Î ПРЕДШ(w)}, то есть отношение предшествования задает дуги в сети; 
c(v,w)=t(w) 
Построенную сеть G часто называют сетевым графиком выполнения работ по проекту W. Легко видеть, что списки смежностей этой сети ПРЕДШ(v) совпадают с заданными для проекта списками предшествующих работ ПРЕДШ(v) 
Очевидно, что сетевой график любого проекта не должен содержать контуров. Действительно, пусть узлы V k 1 , V k 2 ,..., V kr = V k 1 образуют контур в сети G. Это означает, что работа V k 2 не может начаться раньше, чем будет завершена работа V k 1 , работа V k 3 — раньше, чем завершится работа V k 2 , и т.д., и, наконец, V kr = V k 1 — раньше, чем будет завершена работа V kr -1 . Но тогда никакая из работ V k 1 ,..., V kr никогда не сможет быть выполнена. А каждый реальный проект должен допускать возможность его завершения. Следовательно, в сетевом графике нет контуров 
Отсутствие контуров в сети G позволяет пронумеровать работы проекта W таким образом, чтобы для каждой дуги ( V i , V j ) сети G выполнялось условие i < j , то есть каждая дуга идёт из узла с меньшим номером в узел с большим номером. Осуществить такую нумерацию узлов сети G можно с помощью алгоритма топологической сортировки. Поэтому в дальнейшем будем считать, что узлы в сети G топологически отсортированы 
Конечной целью построения сетевой модели является получение информации о возможных сроках выполнения, как отдельных работ, так и о возможном сроке выполнения всего проекта в целом. Обозначим через PB ЫП( v ) (соответственно PHA Ч( v )) наиболее ранний   возможный   срок   выполнения работы   v (соответственно наиболее ранний возможный срок начала работы v). Удобно считать, что PB ЫП( s )= PHA Ч( s )=0. Поскольку начать выполнять работу v можно только после того, как будут выполнены все работы, предшествующие данной работе v, то получим следующие формулы для расчета значений PHA Ч( v ) и PB ЫП( w ) : 
PHA Ч( v ) = МАКС{ PB ЫП( w ): w Î ПРЕДШ(v)}, 
PBЫП(v)= PHAЧ(v) + t(v) 
Значение PB ЫП( p ) дает наиболее ранний возможный срок завершения всего проекта в целом. Приведем запись алгоритма, непосредственно вычисляющего характеристики РНАЧ и РВЫП 

Алгоритм 1. 
Данные: Сетевой график G работ V , заданный списками ПРЕДШ( v ), v Î V 
Результаты: Наиболее ранние возможные сроки начала и выполнения работ РНАЧ( v ), РВЫП( v ), v Î V 
Объявить возможные ранние сроки начала РНАЧ( v ) и выполнения РВЫП( v ) работ равными нулю. Текущей вершиной объявить первую вершину v k = v 1. 
Всем вершинам v предшествующим текущей вершине v k , значение РНАЧ( v k ) присвоить максимум из значений РВЫП( v ) и РНАЧ( v k ). Значение РВЫП( v k ) положить равным значению РНАЧ( v k ) плюс время выполнения самой работы текущей вершины t ( v k ) 
Если имеется следующая вершина (работа) после текущей, то объявить ее текущей вершиной v k , иначе перейти в Шаг 5 
Вернуться в Шаг 2 
Выдать наиболее ранние возможные сроки начала и выполнения работ РНАЧ(v), РВЫП(v), v Î V, конец работы алгоритма 
  Пусть T — плановый срок выполнения проекта W. Ясно, что Т должно удовлетворять неравенству Т >= РВЫП( V n +1 ) 
Через ПВЫП( v ) (соответственно ПНАЧ( v )) обозначим наиболее поздний допустимый срок выполнения (начала) работы v , то есть такой срок, который не увеличивает срок Т реализации всего проекта 
Значения возможных и допустимых сроков выполнения работ позволяют определить резервы времени для выполнения той или иной работы. Полный резерв (иногда его называют суммарный) времени выполнения работ определяется по формуле: 
PE3EPB(v)=ПHAЧ(v)-PHAЧ(v) 
Значение PE 3 EPB ( v ) равно максимальной задержке в выполнении работы v, не влияющей на плановый срок Т. Понятно, что справедливо и такое равенство: РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v) 
Работы, имеющие нулевой резерв времени, называются критическими. Через любую такую работу проходит некоторый максимальный s- p -путь в сети G. Критические работы характеризуются тем, что любая задержка в их выполнении автоматически ведет к увеличению времени выполнения всего проекта 
Приведем запись алгоритма, непосредственно вычисляющего характеристики ПВЫП и ПНАЧ 
Алгоритм 2. 
Данные: Сетевой график G работ V , заданный списками ПРЕДШ( v ), v Î V , плановый срок окончания проекта – Т 
Результаты: Наиболее поздние допустимые сроки выполнения и начала работ ПВЫП( v ) и ПНАЧ( v ) 
Объявить для всех работ v Î V значение наиболее позднего срока выполнения работ равным Т – значению планового срока окончание проекта и вершину v p фиктивной работы p объявить текущей v k 
Присвоить значение ПНАЧ текущей работы v k равным значению ПВЫП работы и вычесть время выполнения текущей работы 
Присвоить значению ПВЫП(v) для всех работ v Î ПРЕДШ(v) предшествующих текущей работе v k минимальное значение из значений ПВЫП выполнения роботы v или ПНАЧ выполнения текущей работы v k , если таковых нет перейти в Шаг 4 
Если имеется предыдущая вершина (работа) к текущей, то объявить её текущей, иначе перейти в Шаг 6 
Перейти в Шаг 2 
Выдать наиболее поздние допустимые сроки выполнения и начала работ ПВЫП( v ) и ПНАЧ( v ), конец работы алгоритма 
Проиллюстрируем работу приведенных алгоритмов на следующих примерах: 
Пример 1 : Проект   гаража для стоянки автопогрузчиков 
n 	Наименование работы 	Предшествующие работы 	Время выполнения t ( v k ) 	
1 	Начало проекта (фиктивная работа) 	Нет 	0 	
2 	Срезка растительного слоя грунта 	1 	5 	
3 	Монтаж каркаса 	2 	30 	
4 	Обшивка стен профнастилом 	3 	15 	
5 	Кровля из профнастила 	3 	12 	
6 	Заполнение проема воротами 	4 	5 	
7 	Масляная окраска ворот и профнастила 	5,6 	10 	
8 	Щебёночное основание под полы 	7 	3 	
9 	Асфальтовое покрытие 	8 	3 	
10 	Уборка строительного мусора после строит 	7 	3 	
11 	Конец проекта (фиктивная работа) 	9,10 	0 	
Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов 
Шаг n 	Действия выполняемые шагом 	
1 	Объявление значений РНАЧ( v ) и РВЫП( v ), v Î V равными нулю. Текущая вершина v k =1 	
2 	Вершин предшествующей первой нет 
РВЫП(1)=РНАЧ(1)+ t (1). { РНАЧ(1) стало равным 0 } 	
3 	Текущая вершина v k =2 	
4 	Переход в Шаг 2 	
2 	РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)} {РНАЧ(2) стало равным 0} 
РВЫП(2)=РНАЧ(2)+ t (2) {РВЫП(2) стало равным 5} 	
3 	Текущая вершина v k =3 	
4 	Переход в Шаг 2 	
2 	РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)} {РНАЧ(3) стало равным 5} 
РВЫП(3)=РНАЧ(3)+ t (3) {РВЫП(3) стало равным 35} 	
3 	Текущая вершина v k =4 	
4 	Переход в Шаг 2 	
2 	РНАЧ(4)=МАКС{РВЫП(3),РНАЧ(4)}{РНАЧ(4) стало равным 35} 
РВЫП(4)=РНАЧ(4)+ t (4) {РВЫП(4) стало равным 50} 	
3 	Текущая вершина v k =5 	
4 	Переход в Шаг 2 	
2 	РНАЧ(5)=МАКС{РВЫП(3),РНАЧ(5)}{РНАЧ(5) стало равным 35} 
РВЫП(5)=РНАЧ(5)+ t (5) {РВЫП(5) стало равным 47} 	
3 	Текущая вершина v k =6 	
4 	Переход в Шаг 2 	
2 	РНАЧ(6)=МАКС{РВЫП(4),РНАЧ(6)}{РНАЧ(6) стало равным 50} 
РВЫП(6)=РНАЧ(6)+ t (6) {РВЫП(6) стало равным 55} 	
3 	Текущая вершина v k =7 	
4 	Переход в Шаг 2 	
2 	РНАЧ(7)=МАКС{РВЫП(5),РНАЧ(7)}{РНАЧ(7) стало равным 47} 
РНАЧ(7)=МАКС{РВЫП(6),РНАЧ(7)}{РНАЧ(7) стало равным 55} 
РВЫП(7)=РНАЧ(7)+ t (7) {РВЫП(7) стало равным 65} 	
3 	Текущая вершина v k =8 	
4 	Переход в Шаг 2 	
2 	РНАЧ(8)=МАКС{РВЫП(7),РНАЧ(8)} {РНАЧ(8) стало равным 65} 
РВЫП(8)=РНАЧ(8)+ t (8) {РВЫП(8) стало равным 68} 	
3 	Текущая вершина v k =9 	
4 	Переход в Шаг 2 	
2 	РНАЧ(9)=МАКС{РВЫП(8),РНАЧ(9)}{РНАЧ(9) стало равным 68} 
РВЫП(9)=РНАЧ(9)+ t (9) {РВЫП(9) стало равным 71} 	
3 	Текущая вершина v k =10 	
4 	Переход в Шаг 2 	
2 	РНАЧ(10)=МАКС{РВЫП(7),РНАЧ(10)}{РНАЧ(10) стало равным 65} 	
3 	Текущая вершина v k =11 	
4 	Переход в Шаг 2 	
2 	РНАЧ(11)=МАКС{РВЫП(9),РНАЧ(11)}{РНАЧ(11) стало равным 71} 
РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(11)}{РНАЧ(11) стало равным 71} 	
3 	Переход в Шаг 5 	
5 	Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ 	
Таблица результатов работы алгоритма 
n 	1 	2 	3 	4 	5 	6 	7 	8 	9 	10 	11 	
РНАЧ( v ) 	0 	0 	5 	35 	35 	50 	55 	65 	68 	65 	71 	
РВЫП( v ) 	0 	5 	35 	50 	47 	55 	65 	68 	71 	68 	71 	
Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=71. Теперь найдем посредством алгоритма 2 значение времени   наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов 
Шаг n 	Действия, выполняемые шагом 	
1 	Объявление значений ПВЫП( v ), v Î V равным Т 
Текущая вершина v k =11 	
2 	ПНАЧ(11)=ПВЫП(11)- t (11) {ПНАЧ(11) стало равным 71} 	
3 	ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(11)}{ПВЫП(9) стало равным 71} 
ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(11)}{ПВЫП(10) стало равным 71} 	
4 	Текущая вершина v k =10 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(10)=ПВЫП(10)- t (10) {ПНАЧ(10) стало равным 68} 	
3 	ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(10)}{ПВЫП(7) стало равным 68} 	
4 	Текущая вершина v k =9 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(9)=ПВЫП(9)- t (9) {ПНАЧ(9) стало равным 68} 	
3 	ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(9)}{ПВЫП(8) стало равным 68} 	
4 	Текущая вершина v k =8 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(8)=ПВЫП(8)- t (8) {ПНАЧ(8) стало равным 65} 	
3 	ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(8)}{ПВЫП(7) стало равным 65} 	
4 	Текущая вершина v k =7 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(7)=ПВЫП(7)- t (7) {ПНАЧ(7) стало равным 55} 	
3 	ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(7)}{ПВЫП(5) стало равным 55} 
ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(7)}{ПВЫП(6) стало равным 55} 	
4 	Текущая вершина v k =6 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(6)=ПВЫП(6)- t (6) {ПНАЧ(6) стало равным 50} 	
3 	ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(6)}{ПВЫП(5) стало равным 50} 	
4 	Текущая вершина v k =5 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(5)=ПВЫП(5)- t (5) {ПНАЧ(5) стало равным 43} 	
3 	ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(5)}{ПВЫП(3) стало равным 43} 	
4 	Текущая вершина v k =4 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(4)=ПВЫП(4)- t (4) {ПНАЧ(4) стало равным 35} 	
3 	ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(4)}{ПВЫП(3) стало равным 35} 	
4 	Текущая вершина v k =3 	
5 	Переход в шаг 2 	
2 	ПНАЧ(3)=ПВЫП(3)- t (3) {ПНАЧ(3) стало равным 5} 	
3 	ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(3)}{ПВЫП(2) стало равным 5} 	
4 	Текущая вершина v k =2 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(2)=ПВЫП(2)- t (2) {ПНАЧ(2) стало равным 0} 	
3 	ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(2)}{ПВЫП(1) стало равным 0} 	
4 	Текущая вершина v k =1 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(1)=ПВЫП(1)- t (1) {ПНАЧ(1) стало равным 0} 	
3 	Переход в Шаг 4 	
4 	Переход в Шаг 6 	
6 	Конец работы алгоритма, выдача значений времени   наиболее позднего начала и выполнения работ 	
Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE 3 EPB ( v )=ПНАЧ( v )- PHA Ч( v ) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v) 
Работы 	РНАЧ 	РВЫП 	ПНАЧ 	ПВЫП 	Резерв 	
1 	0 	0 	0 	0 	0 	
2 	0 	5 	0 	5 	0 	
3 	5 	35 	5 	35 	0 	
4 	35 	50 	35 	50 	0 	
5 	35 	47 	43 	55 	8 	
6 	50 	55 	50 	55 	0 	
7 	55 	65 	55 	65 	0 	
8 	65 	68 	65 	68 	0 	
9 	68 	71 	68 	71 	0 	
10 	65 	68 	68 	71 	3 	
11 	71 	71 	71 	71 	0 	
Из таблицы видно, что критическими работами являются 1, 2, 3, 4, 6, 7, 8, 9, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=71 

Пример 2 : Проект водоснабжения и наружной канализации при застройки квартала по ул. Токарей-Синяева в г. Екатеринбурге 
n 	Наименование работы 	Предшествующие работы 	Время выполнения t ( v k ) 	
1 	Начало проекта (фиктивная работа) 	Нет 	0 	
2 	Разработка грунта экскаваторами с ковшом 0.5 м 3 с погрузкой на автомобили-самосвалы 	1 	16 	
3 	Зачистка дна и стенок с выкидкой грунта 	2 	10 	
4 	Монтаж водопроводных колодцев 	1 	32 	
5 	Монтаж плит перекрытий из легкого бетона 	3 	21 	
6 	Пробивка в бетонных стенах и полах отверстий 	5 	5 	
7 	Оклейка плит рубероидом и гидроизолом на нефтебитуме в 1 слой 	4,5 	14 	
8 	Заделка сальников при проходе труб через фундаменты или стены подвалов 	5 	10 	
9 	Монтаж скоб 	6 	7 	
10 	Устройство стяжек цементных 	9 	5 	
11 	Конец проекта. (фиктивная работа) 	7,8,10 	0 	
Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов 
Шаг n 	Действия, выполняемые шагом 	
1 	Объявление значений РНАЧ( v ) и РВЫП( v ), v Î V равным нулю 
Текущая вершина v k =1 	
2 	Вершин предшествующей первой нет 
Значение РНАЧ(1)=РВЫП(1)+ t (1) 	
3 	Текущая вершина v k =2 	
4 	Переход в Шаг 2 	
2 	РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)}{РНАЧ(2) стало равным 0} 
РВЫП(2)=РНАЧ(2)+ t (2) {РВЫП(2) стало равным 16} 	
3 	Текущая вершина v k =3 	
4 	Переход в Шаг 2 	
2 	РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)}{РНАЧ(2) стало равным 16} 
РВЫП(3)=РНАЧ(3)+ t (3) {РВЫП(3) стало равным 26} 	
3 	Текущая вершина v k =4 	
4 	Переход в Шаг 2 	
2 	РНАЧ(4)=МАКС{РВЫП(1),РНАЧ(4)}{РНАЧ(4) стало равным 0} 
РВЫП(4)=РНАЧ(4)+ t (4) {РВЫП(4) стало равным 32} 	
3 	Текущая вершина v k =5 	
4 	Переход в Шаг 2 	
2 	РНАЧ(5)=МАКС{РВЫП(3),РНАЧ(5)}{РНАЧ(5) стало равным 26} 
РВЫП(5)=РНАЧ(5)+ t (5) {РВЫП(5) стало равным 47} 	
3 	Текущая вершина v k =6 	
4 	Переход в Шаг 2 	
2 	РНАЧ(6)=МАКС{РВЫП(5),РНАЧ(6)}{РНАЧ(6) стало равным 47} 
РВЫП(6)=РНАЧ(6)+ t (6) {РВЫП(6) стало равным 52} 	
3 	Текущая вершина v k =7 	
4 	Переход в Шаг 2 	
2 	РНАЧ(7)=МАКС{РВЫП(5),РНАЧ(7)}{РНАЧ(7) стало равным 47 
РВЫП(7)=РНАЧ(7)+ t (7) {РВЫП(7) стало равным 61} 	
3 	Текущая вершина v k =8 	
4 	Переход в Шаг 2 	
2 	РНАЧ(8)=МАКС{РВЫП(5),РНАЧ(8)}{РНАЧ(8) стало равным 47} 
РВЫП(8)=РНАЧ(8)+ t (8) {РВЫП(8) стало равным 57} 	
3 	Текущая вершина v k =9 	
4 	Переход в Шаг 2 	
2 	РНАЧ(9)=МАКС{РВЫП(6),РНАЧ(9)}{РНАЧ(9) стало равным 52} 
РВЫП(9)=РНАЧ(9)+ t (9) {РВЫП(9) стало равным } 	
3 	Текущая вершина v k =10 	
4 	Переход в Шаг 2 	
2 	РНАЧ(10)=МАКС{РВЫП(9),РНАЧ(10)}{РНАЧ(10) стало равным 59} 
РВЫП(10)=РНАЧ(10)+ t (10) {РВЫП(10) стало равным 64} 	
3 	Текущая вершина v k =11 	
4 	Переход в Шаг 2 	
2 	РНАЧ(11)=МАКС{РВЫП(7),РНАЧ(11)}{РНАЧ(11) стало равным 61} 
РНАЧ(11)=МАКС{РВЫП(8),РНАЧ(11)}{РНАЧ(11) стало рвным 61} 
РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(11)}{РНАЧ(11) стало равным 64} 
РВЫП(11)=РНАЧ(11)+ t (11) {РВЫП(11) стало равным 64} 	
3 	Переход в Шаг 5 	
5 	Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ 	
Таблица результатов работы алгоритма 
n 	1 	2 	3 	4 	5 	6 	7 	8 	9 	10 	11 	
РНАЧ( v) 	0 	0 	16 	0 	26 	47 	47 	47 	52 	59 	64 	
РВЫП( v ) 	0 	16 	26 	32 	47 	52 	61 	57 	59 	64 	64 	
Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=64. Теперь найдем посредством алгоритма 2 значение времени   наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов 
Шаг n 	Действия, выполняемые шагом 	
1 	Объявление значений ПВЫП( v ), v Î V равным Т 
Текущая вершина v k =11 	
2 	ПНАЧ(11)=ПВЫП(11)- t (11) {ПНАЧ(11) стало равным 64} 	
3 	ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(11)}{ПВЫП(7) стало равным 64} 
ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(11)}{ПВЫП(8) стало равным 64} 
ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(10)}{ПВЫП(9) стало равным 64} 	
4 	Текущая вершина v k =10 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(10)=ПВЫП(10)- t (10) {ПНАЧ(10) стало равным 59} 	
3 	ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(10)} {ПВЫП(9) стало равным 59} 	
4 	Текущая вершина v k =9 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(9)=ПВЫП(9)- t (9) {ПНАЧ(9) стало равным 52} 	
3 	ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(9)}{ПВЫП(6) стало равным 52} 	
4 	Текущая вершина v k =8 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(8)=ПВЫП(8)- t (8) {ПНАЧ(8) стало равным 54} 	
3 	ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(8)}{ПВЫП(5) стало равным 54} 	
4 	Текущая вершина v k =7 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(7)=ПВЫП(7)- t (7) {ПНАЧ(7) стало равным 50} 	
3 	ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(7)}{ПВЫП(5) стало равным 50} 
ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(7)}{ПВЫП(4) стало равным 50} 	
4 	Текущая вершина v k =6 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(6)=ПВЫП(6)- t (6) {ПНАЧ(6) стало равным 47} 	
3 	ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(6)}{ПВЫП(5) стало равным 47} 	
4 	Текущая вершина v k =5 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(5)=ПВЫП(5)- t (5) {ПНАЧ(5) стало равным 26} 	
3 	ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(5)}{ПВЫП(3) стало равным 26} 	
4 	Текущая вершина v k =4 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(4)=ПВЫП(4)- t (4) {ПНАЧ(4) стало равным 18} 	
3 	ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(4)}{ПВЫП(1) стало равным 18} 	
4 	Текущая вершина v k =3 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(3)=ПВЫП(3)- t (3) {ПНАЧ(3) стало равным 16} 	
3 	ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(3)}{ПВЫП(2) стало равным 16} 	
4 	Текущая вершина v k =2 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(2)=ПВЫП(2)- t (2) {ПНАЧ(2) стало равным 0} 	
3 	ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(2)}{ПВЫП(1) стало равным 0} 	
4 	Текущая вершина v k =1 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(1)=ПВЫП(1)- t (1) {ПНАЧ(1) стало равным 0} 	
3 	Переход в Шаг 4 	
4 	Переход в Шаг 6 	
6 	Конец работы алгоритма, выдача значений времени   наиболее позднего начала и выполнения работ 	
Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE 3 EPB ( v )=П HA Ч( v )- PHA Ч( v ) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v) 
Работы 	РНАЧ 	РВЫП 	ПНАЧ 	ПВЫП 	Резерв 	
1 	0 	0 	0 	0 	0 	
2 	0 	16 	0 	16 	0 	
3 	16 	26 	16 	26 	0 	
4 	0 	32 	18 	50 	32 	
5 	26 	47 	26 	47 	0 	
6 	47 	52 	47 	52 	0 	
7 	47 	61 	50 	64 	3 	
8 	47 	57 	54 	64 	10 	
9 	52 	59 	52 	59 	0 	
10 	59 	64 	59 	64 	0 	
11 	59 	64 	64 	64 	0 	
Из таблицы видно, что критическими работами являются 1, 2, 3, 5, 6, 9, 10, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=64 
Пример 3 : Проект склада сажи и других материалов в помещение производственного цеха 
n 	Наименование работы 	Предшествующие работы 	Время выполнения t ( v k ) 	
1 	Начало проекта (фиктивная работа) 	Нет 	0 	
2 	Монтаж металлоконструкций нижней обвязки каркаса 	1 	5 	
3 	Устройство бетона под стойки 	2 	3 	
4 	Монтаж стоек 	3 	10 	
5 	Монтаж опорных столиков 	4 	5 	
6 	Монтаж балок 	2 	7 	
7 	Монтаж металлоконструкций ворот 	6 	7 	
8 	Обшивка стен и кровли волнистым листом 	6 	12 	
9 	Монтаж козлового крана 	7 	5 	
10 	Устройство асфальтобетонных покрытий 	8 	5 	
11 	Конец проекта (фиктивная работа) 	5,9,10 	0 	
Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов 
Шаг n 	Действия, выполняемые шагом 	
1 	Объявление значений РНАЧ( v ) и РВЫП( v ), v Î V равным нулю 
Текущая вершина v k =1 	
2 	Вершин предшествующей первой нет 
Значение РНАЧ(1)=РВЫП(1)+ t (1) 	
3 	Текущая вершина v k =2 	
4 	Переход в Шаг 2 	
2 	РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)} {РНАЧ(2) стало равным 0} 
РВЫП(2)=РНАЧ(2)+ t (2) {РВЫП(2) стало равным 5} 	
3 	Текущая вершина v k =3 	
4 	Переход в Шаг 2 	
2 	РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)} {РНАЧ(3) стало равным 5} 
РВЫП(3)=РНАЧ(3)+ t (3) {РВЫП(3) стало равным 8} 	
3 	Текущая вершина v k =4 	
4 	Переход в Шаг 2 	
2 	РНАЧ(4)=МАКС{РВЫП(3),РНАЧ(4)} {РНАЧ(4) стало равным 8} 
РВЫП(4)=РНАЧ(4)+ t (4) {РВЫП(4) стало равным 18} 	
3 	Текущая вершина v k =5 	
4 	Переход в Шаг 2 	
2 	РНАЧ(5)=МАКС{РВЫП(4),РНАЧ(5)} {РНАЧ(5) стало равным 18} 
РВЫП(5)=РНАЧ(5)+ t (5) {РВЫП(5) стало равным 23} 	
3 	Текущая вершина v k =6 	
4 	Переход в Шаг 2 	
2 	РНАЧ(6)={РВЫП(2),РНАЧ(6)} {РНАЧ(6) стало равным 5} 
РВЫП(6)=РНАЧ(6)+ t (6) {РВЫП(6) стало равным 12} 	
3 	Текущая вершина v k =7 	
4 	Переход в Шаг 2 	
2 	РНАЧ(7)=МАКС{РВЫП(6),РНАЧ(7)} {РНАЧ(7) стало равным 12} 
РВЫП(7)=РНАЧ(7)+ t (7) {РВЫП(7) стало равным 19} 	
3 	Текущая вершина v k =8 	
4 	Переход в Шаг 2 	
2 	РНАЧ(8)=МАКС{РВЫП(6),РНАЧ(8)} {РНАЧ(8) стало равным 12} 
РВЫП(8)=РНАЧ(8)+ t (8) {РВЫП(8) стало равным 24} 	
3 	Текущая вершина v k =9 	
4 	Переход в Шаг 2 	
2 	РНАЧ(9)=МАКС{РВЫП(7),РНАЧ(9)} {РНАЧ(9) стало равным 19} 
РВЫП(9)=РНАЧ(9)+ t (9) {РВЫП(9) стало равным 24} 	
3 	Текущая вершина v k =10 	
4 	Переход в Шаг 2 	
2 	РНАЧ(10)=МАКС{РВЫП(8),РНАЧ(10)} {РНАЧ(10) стало равным 24} 
РВЫП(10)=РНАЧ(10)+ t (10) {РВЫП(10) стало равным 29} 	
3 	Текущая вершина v k =11 	
4 	Переход в Шаг 2 	
2 	РНАЧ(11)=МАКС{РВЫП(9),РНАЧ(11)} {РНАЧ(11) стало равным 24} 
РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(10)}{РНАЧ(11) стало равным 29} 
РВЫП(11)=РНАЧ(11)+ t (11) {РВЫП(11) стало равным 29} 	
3 	Переход в Шаг 5 	
5 	Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ 	
Таблица результатов работы алгоритма 
n 	1 	2 	3 	4 	5 	6 	7 	8 	9 	10 	11 	
РНАЧ( v ) 	0 	0 	5 	8 	18 	5 	12 	12 	19 	24 	29 	
РВЫП( v) 	0 	5 	8 	18 	23 	12 	19 	24 	24 	29 	29 	
Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=29. Теперь найдем посредством алгоритма 2 значение времени   наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов 
Шаг n 	Действия выполняемые шагом 	
1 	Объявление значений ПВЫП( v ), v Î V равным Т 
Текущая вершина v k =11 	
2 	ПНАЧ(11)=ПВЫП(11)- t (11) {ПНАЧ(11) стало равным 29} 	
3 	ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(11)}{ПВЫП(9) стало равным 29} 
ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(11)}{ПВЫП(10) стало равным 29} 	
4 	Текущая вершина v k =10 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 24} 	
3 	ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(10)}{ПВЫП(8) стало равным 24} 	
4 	Текущая вершина v k =9 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(9)=ПВЫП(9)- t (9) {ПНАЧ(9) стало равным 24} 	
3 	ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(9)}{ПВЫП(7) стало равным 24} 	
4 	Текущая вершина v k =8 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(8)=ПВЫП(8)- t (8) {ПНАЧ(8) стало равным 12} 	
3 	ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(8)}{ПВЫП(6) стало равным 12} 	
4 	Текущая вершина v k =7 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(7)=ПВЫП(7)- t (7) {ПНАЧ(7) стало равным 17} 	
3 	ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(7)}{ПВЫП(6) стало равным 12} 	
4 	Текущая вершина v k =6 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(6)=ПВЫП(6)- t (6) {ПНАЧ(6) стало равным 5} 	
3 	ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(6)}{ПВЫП(2) стало равным 5} 	
4 	Текущая вершина v k =5 	
5 	Переход в шаг 2 	
2 	ПНАЧ(5)=ПВЫП(5)- t (5) {ПНАЧ(5) стало равным 24} 	
3 	ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(5)}{ПВЫП(4) стало равным 24} 	
4 	Текущая вершина v k =4 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(4)=ПВЫП(4)- t (4) {ПНАЧ(4) стало равным 14} 	
3 	ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(4)}{ПВЫП(3) стало равным 14} 	
4 	Текущая вершина v k =3 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(3)=ПВЫП(3)- t (3) {ПНАЧ(3) стало равным 11} 	
3 	ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(3)}{ПВЫП(2) стало равным 5} 	
4 	Текущая вершина v k =2 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(2)=ПВЫП(2)- t (2) {ПНАЧ(2) стало равным 0} 	
3 	ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(2)}{ПВЫП(1) стало равным 0} 	
4 	Текущая вершина v k =1 	
5 	Переход в Шаг 2 	
2 	ПНАЧ(1)=ПВЫП(1)- t (1) {ПНАЧ(1) стало равным 0} 	
3 	Переход в Шаг 4 	
4 	Переход в Шаг 6 	
6 	Конец работы алгоритма, выдача значений времени   наиболее позднего начала и выполнения работ 	
Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE 3 EPB ( v )=П HA Ч( v )- PHA Ч( v ) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v) 
Работы 	РНАЧ 	РВЫП 	ПНАЧ 	ПВЫП 	Резерв 	
1 	0 	0 	0 	0 	0 	
2 	0 	5 	0 	5 	0 	
3 	5 	8 	11 	14 	3 	
4 	8 	18 	14 	24 	10 	
5 	18 	23 	24 	29 	5 	
6 	5 	12 	5 	12 	0 	
7 	12 	19 	17 	24 	7 	
8 	12 	24 	12 	24 	0 	
9 	19 	24 	24 	29 	5 	
10 	24 	29 	24 	29 	0 	
11 	29 	29 	29 	29 	0 	
Из таблицы видно, что критическими работами являются 1, 2, 6, 8, 10, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=29 

Список используемой литературы: 
  
1. Асанов М. О. «Дискретная оптимизация», УралНАУКА, Екатеринбург 1998