Многие крупные проекты , такие как строительство дома , из готовление станка , разработка автоматизированной системы бухгалтерского учета и т.д ., можно разбить на большое количест во различных операций (работ ). Некоторые из этих операц ий могут выполняться одновременно , другие — только последовательно : одна операция после окончания другой . Например , при строительстве дома можно совместить во времени внутренние отде лочные работы и ра боты по благоустройству территории , однако возводить стены можно то лько после того , как будет готов фундамент . Задачи планиров ания работ по осуществлению некоторого проект а состоят в определении времени возможного окончания как всего проекта в целом , та к и отдельных работ , образующих проект ; в определении резервов времени для выполне ния отдельных работ ; в определении критически х работ , то есть таких работ , задержка в выполнении которых ведет к задержке вып олнения всего проекта в целом ; в управлени и ресурса м и , если таковые имеются и т.п. Пусть некоторый проект 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 ) определим по правилам : 1. V = W , то есть множеством узлов объявим множество работ ; 2. E = ( v , w ) : v ПРЕДШ (w) , то есть отношение п редшествования задает дуги в сети ; 3. 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 . Шаг 1. Объявить возможные ранние сроки начала РНАЧ ( v ) и выполнения Р ВЫП ( v ) работ равными нулю . Текущей вершиной объявить первую вершину v k =v 1. Шаг 2. Всем вер шинам v предшествующим текущей вер шине v k , з начение Р НАЧ ( v k ) присвоить максимум из значений РВЫП ( v ) и РНАЧ ( v k ). З начение РВЫП ( v k ) положить равн ым значению РНАЧ ( v k ) плюс время выпол нения самой работы текущей вершины t ( v k ) . Шаг 3. Если име ется следующая вершина (работа ) после текущей , то объявить ее текущей вершиной v k , иначе перейти в Шаг 5. Шаг 4. Вернуться в Шаг 2. Шаг 5. Выдать н аиболее ранние во зможные сроки начала и выполнения работ РНАЧ (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 ). Шаг 1. Объявить для вс ех работ v V значение на иб олее позднего срока выполнения работ равным Т – значению планового срока о кончание проекта и вершину v p фиктивной работы p объявить текущей v k . Шаг 2. Присвоить значение ПНАЧ текущей работы v k равным значению ПВЫП работы и вычесть время выполнения тек ущей работ ы. Шаг 3. Присвоить значению ПВЫП (v) для всех работ v ПРЕДШ (v) предшествующи х текущей работе v k минимальное значение из значений ПВЫП выполнения роботы v или ПНАЧ выполнения текущей работы v k , если таковых нет п ерейти в Шаг 4. Шаг 4. Если име ется предыдущая вершина (работа ) к текущей , то объявить её текущей , иначе перейти в Шаг 6. Шаг 5. Перейти в Шаг 2. Шаг 6. Выдать н аиболее поздние допустимые сроки выполнения и начала работ ПВЫП ( 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. Проект гаража для стоянки автопо грузчиков. Найдем значения наиболее раннего начала и выполнения раб от проекта посредством алгоритма 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. Монтаж металлоконс трукций нижней каркаса 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 Рис 2. Проект склада сажи и других материалов в помещение производственного цеха. Найдем значения наиболее раннего начала и выполнения раб от проекта посредством алгоритма 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),РНАЧ (1 0) РНАЧ (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. П ример 3: Проект водоснабжения и на ружной канализации при застройки квартала по ул . Токарей-Синяева в г . Екатеринбурге. 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 Рис 3. Проект водоснабжения и наружной канализации при з астройки квартала по ул . Токарей-Синяева в г . Екатеринбурге. Найдем значения наиболее раннего начала и выполн ения работ проекта посредств ом алгоритма 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. Литература : 1. Асанов М . О . “Ди скретная оптими зация” , УралНАУКА , Екатеринбург 1998.