Сетевые графики

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

Задачи планирования работ по осуществлению некоторого проекта состоят в определении времени возможного окончания как всего проекта в целом, так и отдельных работ, образующих проект в определении резервов времени для выполнения отдельных работ в определении критических работ, то есть таких работ, задержка в выполнении которых ведет к задержке выполнения всего проекта в целом в управлении ресурсами, если таковые имеются и т.п. Пусть некоторый проект W состоит из работ V1 Vn для каждой работы Vk, известно, или может быть достаточно точно оценено время ее выполнения tVk. Кроме того, для каждой работы Vk известен, возможно пустой, список ПРЕДШVk работ, непосредственно предшествующих выполнению работы Vk. Иначе говоря, работа Vk может начать выполняться только после завершения всех работ, входящих в список ПРЕДШVk. Для удобства, в список работ проекта W добавим две фиктивные работы s и p, где работа s обозначает начало всего проекта W. а работа p завершение работ по проекту W. При этом будем считать, что работа s предшествует всем тем работам vW, для которых список ПРЕДШv пуст, иначе говоря, для всех таких работ vW положим ПРЕДШvs. Положим далее ПРЕДШs , ПРЕДШpvW v не входит ни в один список ПРЕДШw, то есть считаем, что работе p предшествуют все те работы, которые могут выполняться самыми последними.

Время выполнения работ s и p естественно положить равными нулю tstp0. Весь проект W теперь удобно представить в виде сети GV,E,c. Ориентированный взвешенный граф GV,E,c называется сетью.

Сеть может быть представлена матрицей весов дуг, массивами смежностей СЛЕД или ПРЕДШ, или списками СЛЕДv или ПРЕДШv. При этом записи в списках смежности состоят из трех компонент поля имени узла, поля веса соответствующей дуги и поля ссылки на следующую запись, где сеть GV,E,c определим по правилам 1. VW, то есть множеством узлов объявим множество работ 2. Ev,w vПРЕДШw, то есть отношение предшествования задает дуги в сети 3. cv,wtw. Так построенную сеть G часто называют сетевым графиком выполнения работ по проекту W. Легко видеть, что списки смежностей этой сети ПРЕДШv совпадают с заданными для проекта списками предшествующих работ ПРЕДШv. Понятно, что сетевой график любого проекта не должен содержать контуров.

Действительно, пусть узлы Vk1,Vk2 VkrVk1 образуют контур в сети G. Это означает, что работа Vk2 не может начаться раньше, чем будет завершена работа Vk1, работа Vk3 раньше, чем завершится работа Vk2, и т.д и, наконец, Vkr Vk1 раньше, чем будет завершена работа Vkr-1. Но тогда никакая из работ Vk1 Vkr никогда не сможет быть выполнена.

А каждый реальный проект должен допускать возможность его завершения.

Следовательно, в сетевом графике нет контуров.Отсутствие контуров в сети G позволяет пронумеровать работы проекта W таким образом, чтобы для каждой дуги Vi,Vj сети G выполнялось условие i j, то есть каждая дуга идт из узла с меньшим номером в узел с большим номером.

Осуществить такую нумерацию узлов сети G можно с помощью алгоритма топологической сортировки. Поэтому в дальнейшем будем считать, что узлы в сети G топологически отсортированы. Конечной целью построения сетевой модели является получение информации о возможных сроках выполнения как отдельных работ, так и о возможном сроке выполнения всего проекта в целом.Обозначим через PBЫПv соответственно PHAЧv наиболее ранний возможный срок выполнения работы v соответственно наиболее ранний возможный срок начала работы v. Удобно считать, что PBЫПsPHAЧs0. Поскольку начать выполнять работу v можно только после того, как будут выполнены все работы, предшествующие данной работе v, то получим следующие формулы для расчета значений PHAЧv и PBЫПw PHAЧv МАКСPBЫПw wПРЕДШv, PBЫПv PHAЧv tv. Значение PBЫПp дает наиболее ранний возможный срок завершения всего проекта в целом.

Приведем запись алгоритма, непосредственно вычисляющего характеристики РНАЧ и РВЫП. АЛГОРИТМ 1. Данные Сетевой график G работ V, заданный списками ПРЕДШv, vV. Результаты Наиболее ранние возможные сроки начала и выполнения работ РНАЧv, РВЫПv, vV. Шаг 1. Объявить возможные ранние сроки начала РНАЧv и выполнения РВЫПv работ равными нулю. Текущей вершиной объявить первую вершину vkv1. Шаг 2. Всем вершинам v предшествующим текущей вершине vk, значение РНАЧvk присвоить максимум из значений РВЫПv и РНАЧvk. Значение РВЫПvk положить равным значению РНАЧvk плюс время выполнения самой работы текущей вершины tvk. Шаг 3. Если имеется следующая вершина работа после текущей, то объявить ее текущей вершиной vk, иначе перейти в Шаг 5. Шаг 4. Вернуться в Шаг 2. Шаг 5. Выдать наиболее ранние возможные сроки начала и выполнения работ РНАЧv, РВЫПv, vV, конец работы алгоритма.

Пусть T плановый срок выполнения проекта W. Ясно, что Т должно удовлетворять неравенству Т РВЫПVn1. Через ПВЫПv соответственно ПНАЧv обозначим наиболее поздний допустимый срок выполнения начала работы v, то есть такой срок, который не увеличивает срок Т реализации всего проекта.

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

Полный резерв иногда его называют суммарный времени выполнения работ определяется по формуле PE3EPBvПHAЧv-PHAЧv. Значение PE3EPBv равно максимальной задержке в выполнении работы v, не влияющей на плановый срок Т. Понятно, что справедливо и такое равенство РЕЗЕРВvПВЫПv-РВЫПv. Работы, имеющие нулевой резерв времени, называются критическими.

Через любую такую работу проходит некоторый максимальный s-p-путь в сети G. Критические работы характеризуются тем, что любая задержка в их выполнении автоматически ведет к увеличению времени выполнения всего проекта.Приведем запись алгоритма, непосредственно вычисляющего характеристики ПВЫП и ПНАЧ. АЛГОРИТМ 2. Данные Сетевой график G работ V, заданный списками ПРЕДШv, vV, плановый срок окончания проекта Т. Результаты Наиболее поздние допустимые сроки выполнения и начала работ ПВЫПv и ПНАЧv. Шаг 1. Объявить для всех работ vV значение наиболее позднего срока выполнения работ равным Т значению планового срока окончание проекта и вершину vp фиктивной работы p объявить текущей vk. Шаг 2. Присвоить значение ПНАЧ текущей работы vk равным значению ПВЫП работы и вычесть время выполнения текущей работы.

Шаг 3. Присвоить значению ПВЫПv для всех работ vПРЕДШv предшествующих текущей работе vk минимальное значение из значений ПВЫП выполнения роботы v или ПНАЧ выполнения текущей работы vk, если таковых нет перейти в Шаг 4. Шаг 4. Если имеется предыдущая вершина работа к текущей, то объявить е текущей, иначе перейти в Шаг 6. Шаг 5. Перейти в Шаг 2. Шаг 6. Выдать наиболее поздние допустимые сроки выполнения и начала работ ПВЫПv и ПНАЧv, конец работы алгоритма.

Проиллюстрируем работу приведенных алгоритмов на следующих примерах Пример 1 Проект гаража для стоянки автопогрузчиков. nНаименование работыПредшеству-ющие работыВремя вы-полнения tvk1Начало проекта фиктивн. работаНет02Срезка растительного слоя грунта153Монтаж каркаса2304Обшивка стен профнастилом3155Кровля из профнастила3126Заполнение проема воротами457Масляная окраска ворот и профнастила5,6108Щебночное основание под полы739Асфальтовое покрытие8310Уборка строительного мусора после строит.7311Конец проекта фиктивная работа9, Рис 1. Проект гаража для стоянки автопогрузчиков.

Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов. Шаг nДействия выполняемые шагом1Объявление значений РНАЧv и РВЫПv, vV равными нулю. Текущая вершина vk1.2Вершин предшествующей первой нет. РВЫП1РНАЧ1t1. РНАЧ1 стало равным 03Текущая вершина vk2.4Переход в Шаг 2.2РНАЧ2МАКСРВЫП1,РНАЧ2 РНАЧ2 стало равным 0 РВЫП2РНАЧ2t2 РВЫП2 стало равным 5.3Текущая вершина vk3.4Переход в Шаг 2.2РНАЧ3МАКСРВЫП2,РНАЧ3 РНАЧ3 стало равным 5 РВЫП3РНАЧ3t3 РВЫП3 стало равным 35.3Текущая вершина vk4.4Переход в Шаг 2.2РНАЧ4МАКСРВЫП3,РНАЧ4РНАЧ4 стало равным 35 РВЫП4РНАЧ4t4 РВЫП4 стало равным 50.3Текущая вершина vk5.4Переход в Шаг 2.2РНАЧ5МАКСРВЫП3,РНАЧ5РНАЧ5 стало равным 35 РВЫП5РНАЧ5t5 РВЫП5 стало равным 47.3Текущая вершина vk6.4Переход в Шаг 2.2РНАЧ6МАКСРВЫП4,РНАЧ6РНАЧ6 стало равным 50 РВЫП6РНАЧ6t6 РВЫП6 стало равным 55.3Текущая вершина vk7.4Переход в Шаг 2.2РНАЧ7МАКСРВЫП5,РНАЧ7РНАЧ7 стало равным 47 РНАЧ7МАКСРВЫП6,РНАЧ7РНАЧ7 стало равным 55 РВЫП7РНАЧ7t7 РВЫП7 стало равным 65.3Текущая вершина vk8.4Переход в Шаг 2.2РНАЧ8МАКСРВЫП7,РНАЧ8 РНАЧ8 стало равным 65 РВЫП8РНАЧ8t8 РВЫП8 стало равным 68.3Текущая вершина vk9.4Переход в Шаг 2.2РНАЧ9МАКСРВЫП8,РНАЧ9РНАЧ9 стало равным 68 РВЫП9РНАЧ9t9 РВЫП9 стало равным 71.3Текущая вершина vk10.4Переход в Шаг 2.2РНАЧ10МАКСРВЫП7,РНАЧ10РНАЧ10 стало равным 653Текущая вершина vk11.4Переход в Шаг 2.2РНАЧ11МАКСРВЫП9,РНАЧ11РНАЧ11 стало равным 71 РНАЧ11МАКСРВЫП10,РНАЧ11РНАЧ11 стало равным 713Переход в Шаг 5.5Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ.

Таблица результатов работы алгоритма. n1234567891011РНАЧv0053535505565686571РВ ЫПv05355047556568716871 Получили, что минимальное время, требуемое для выполнения проекта равно ТРВЫП11, Т71. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ.

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

Шаг nДействия выполняемые шагом1Объявление значений ПВЫПv, vV равным Т. Текущая вершина vk11.2ПНАЧ11ПВЫП11-t11 ПНАЧ11 стало равным 71.3ПВЫП9МИНПВЫП9,ПНАЧ11ПВЫП9 стало равным 71 ПВЫП10МИНПВЫП10,ПНАЧ11ПВЫП10 стало равным 714Текущая вершина vk10.5Переход в Шаг 2.2ПНАЧ10ПВЫП10-t10 ПНАЧ10 стало равным 683ПВЫП7МИНПВЫП7,ПНАЧ10ПВЫП7 стало равным 684Текущая вершина vk9.5Переход в Шаг 2.2ПНАЧ9ПВЫП9-t9 ПНАЧ9 стало равным 683ПВЫП8МИНПВЫП8,ПНАЧ9ПВЫП8 стало равным 684Текущая вершина vk8.5Переход в Шаг 2.2ПНАЧ8ПВЫП8-t8 ПНАЧ8 стало равным 653ПВЫП7МИНПВЫП7,ПНАЧ8ПВЫП7 стало равным 654Текущая вершина vk7.5Переход в Шаг 2.2ПНАЧ7ПВЫП7-t7 ПНАЧ7 стало равным 553ПВЫП5МИНПВЫП5,ПНАЧ7ПВЫП5 стало равным 55 ПВЫП6МИНПВЫП6,ПНАЧ7ПВЫП6 стало равным 554Текущая вершина vk6.5Переход в Шаг 2.2ПНАЧ6ПВЫП6-t6 ПНАЧ6 стало равным 503ПВЫП4МИНПВЫП4,ПНАЧ6ПВЫП5 стало равным 504Текущая вершина vk5.5Переход в Шаг 2.2ПНАЧ5ПВЫП5-t5 ПНАЧ5 стало равным 433ПВЫП3МИНПВЫП3,ПНАЧ5ПВЫП3 стало равным 434Текущая вершина vk4.5Переход в Шаг 2.2ПНАЧ4ПВЫП4-t4 ПНАЧ4 стало равным 353ПВЫП3МИНПВЫП3,ПНАЧ4ПВЫП3 стало равным 354Текущая вершина vk3.5Переход в шаг 2.2ПНАЧ3ПВЫП3-t3 ПНАЧ3 стало равным 53ПВЫП2МИНПВЫП2,ПНАЧ3ПВЫП2 стало равным 54Текущая вершина vk2.5Переход в Шаг 2.2ПНАЧ2ПВЫП2-t2 ПНАЧ2 стало равным 03ПВЫП1МИНПВЫП1,ПНАЧ2ПВЫП1 стало равным 04Текущая вершина vk1.5Переход в Шаг 2.2ПНАЧ1ПВЫП1-t1 ПНАЧ1 стало равным 03Переход в Шаг 4.4Переход в Шаг 6.6Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ.Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE3EPBvПНАЧv-PHAЧv или РЕЗЕРВvПВЫПv-РВЫПv. РаботыРНАЧРВЫППНАЧПВЫПРезерв Из таблицы видно, что критическими работами являются 1, 2, 3, 4, 6, 7, 8, 9, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т71. Пример 2 Проект склада сажи и других материалов в помещение производственного цеха. nНаименование работыПредшеству-ющие работыВремя вы-полнения tvk1.Начало проекта фиктивн. работаНет02.Монтаж металлоконструкций нижней обвязки каркаса153.Устройство бетона под стойки234.Монтаж стоек3105.Монтаж опорных столиков456.Монтаж балок277.Монтаж металлоконструкций ворот678.Обшивка стен и кровли волнистым листом6129.Монтаж козлового крана7510.Устройство асфальтобетонных покрытий8511.Конец проекта фиктивн. работа5,9, Рис 2. Проект склада сажи и других материалов в помещение производственного цеха. Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов. Шаг nДействия выполняемые шагом1Объявление значений РНАЧv и РВЫПv, vV равным нулю. Текущая вершина vk1.2Вершин предшествующей первой нет. Значение РНАЧ1РВЫП1t1.3Текущая вершина vk2.4Переход в Шаг 2.2РНАЧ2МАКСРВЫП1,РНАЧ2 РНАЧ2 стало равным 0 РВЫП2РНАЧ2t2 РВЫП2 стало равным 5.3Текущая вершина vk3.4Переход в Шаг 2.2РНАЧ3МАКСРВЫП2,РНАЧ3 РНАЧ3 стало равным 5 РВЫП3РНАЧ3t3 РВЫП3 стало равным 8.3Текущая вершина vk4.4Переход в Шаг 2.2РНАЧ4МАКСРВЫП3,РНАЧ4 РНАЧ4 стало равным 8 РВЫП4РНАЧ4t4 РВЫП4 стало равным 18.3Текущая вершина vk5.4Переход в Шаг 2.2РНАЧ5МАКСРВЫП4,РНАЧ5 РНАЧ5 стало равным 18 РВЫП5РНАЧ5t5 РВЫП5 стало равным 23.3Текущая вершина vk6.4Переход в Шаг 2.2РНАЧ6РВЫП2,РНАЧ6 РНАЧ6 стало равным 5 РВЫП6РНАЧ6t6 РВЫП6 стало равным 12.3Текущая вершина vk7.4Переход в Шаг 2.2РНАЧ7МАКСРВЫП6,РНАЧ7 РНАЧ7 стало равным 12 РВЫП7РНАЧ7t7 РВЫП7 стало равным 19.3Текущая вершина vk8.4Переход в Шаг 2.2РНАЧ8МАКСРВЫП6,РНАЧ8 РНАЧ8 стало равным 12 РВЫП8РНАЧ8t8 РВЫП8 стало равным 24.3Текущая вершина vk9.4Переход в Шаг 2.2РНАЧ9МАКСРВЫП7,РНАЧ9 РНАЧ9 стало равным 19 РВЫП9РНАЧ9t9 РВЫП9 стало равным 24.3Текущая вершина vk10.4Переход в Шаг 2.2РНАЧ10МАКСРВЫП8,РНАЧ10 РНАЧ10 стало равным 24 РВЫП10РНАЧ10t10 РВЫП10 стало равным 29.3Текущая вершина vk11.4Переход в Шаг 2.2РНАЧ11МАКСРВЫП9,РНАЧ11 РНАЧ11 стало равным 24 РНАЧ11МАКСРВЫП10,РНАЧ10РНАЧ11 стало равным 29 РВЫП11РНАЧ11t11 РВЫП11 стало равным 29.3Переход в Шаг 5.5Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ.

Таблица результатов работы алгоритма. n1234567891011РНАЧv00581851212192429РВЫП v0581823121924242929 Получили, что минимальное время, требуемое для выполнения проекта равно ТРВЫП11, Т29. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ.

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

Шаг nДействия выполняемые шагом1Объявление значений ПВЫПv, vV равным Т. Текущая вершина vk11.2ПНАЧ11ПВЫП11-t11 ПНАЧ11 стало равным 29.3ПВЫП9МИНПВЫП9,ПНАЧ11ПВЫП9 стало равным 29 ПВЫП10МИНПВЫП10,ПНАЧ11ПВЫП10 стало равным 29.4Текущая вершина vk10.5Переход в Шаг 2.2ПНАЧ10ПВЫП10-t10 ПНАЧ10 стало равным 24.3ПВЫП8МИНПВЫП8,ПНАЧ10ПВЫП8 стало равным 244Текущая вершина vk9.5Переход в Шаг 2.2ПНАЧ9ПВЫП9-t9 ПНАЧ9 стало равным 24.3ПВЫП7МИНПВЫП7,ПНАЧ9ПВЫП7 стало равным 24.4Текущая вершина vk8.5Переход в Шаг 2.2ПНАЧ8ПВЫП8-t8 ПНАЧ8 стало равным 12.3ПВЫП6МИНПВЫП6,ПНАЧ8ПВЫП6 стало равным 12.4Текущая вершина vk7.5Переход в Шаг 2.2ПНАЧ7ПВЫП7-t7 ПНАЧ7 стало равным 17.3ПВЫП6МИНПВЫП6,ПНАЧ7ПВЫП6 стало равным 12.4Текущая вершина vk6.5Переход в Шаг 2.2ПНАЧ6ПВЫП6-t6 ПНАЧ6 стало равным 5.3ПВЫП2МИНПВЫП2,ПНАЧ6ПВЫП2 стало равным 5.4Текущая вершина vk5.5Переход в шаг 2.2ПНАЧ5ПВЫП5-t5 ПНАЧ5 стало равным 24.3ПВЫП4МИНПВЫП4,ПНАЧ5ПВЫП4 стало равным 24.4Текущая вершина vk4.5Переход в Шаг 2.2ПНАЧ4ПВЫП4-t4 ПНАЧ4 стало равным 14.3ПВЫП3МИНПВЫП3,ПНАЧ4ПВЫП3 стало равным 14.4Текущая вершина vk3.5Переход в Шаг 2.2ПНАЧ3ПВЫП3-t3 ПНАЧ3 стало равным 11.3ПВЫП2МИНПВЫП2,ПНАЧ3ПВЫП2 стало равным 5.4Текущая вершина vk2.5Переход в Шаг 2.2ПНАЧ2ПВЫП2-t2 ПНАЧ2 стало равным 0.3ПВЫП1МИНПВЫП1,ПНАЧ2ПВЫП1 стало равным 0.4Текущая вершина vk1.5Переход в Шаг 2.2ПНАЧ1ПВЫП1-t1 ПНАЧ1 стало равным 0.3Переход в Шаг 4.4Переход в Шаг 6.6Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ.

Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE3EPBvПHAЧv-PHAЧv или РЕЗЕРВvПВЫПv-РВЫПv. РаботыРНАЧРВЫППНАЧПВЫПРезерв Из таблиы видно, что критическими работами являются 1, 2, 6, 8, 10, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т29. Пример 3 Проект водоснабжения и наружной канализации при застройки квартала по ул. Токарей-Синяева в г. Екатеринбурге. nНаименование работыПредшеству-ющие работыВремя вы-полнения tvk1.Начало проекта фиктивн.

РаботаНет02.Разработка грунта экскаваторами с ковшом 0.5 м3 с погрузкой на автомобили- самосвалы.1163.Зачистка дна и стенок с выкидкой грунта.2104.Монтаж водопроводных колодцев1325.Монтаж плит перекрытий из легкого бетона.3216.Пробивка в бетонных стенах и полах отверстий.557.Оклейка плит рубероидом и гидроизолом на нефтебитуме в 1 слой.4,5148.Заделка сальников при проходе труб через фундаменты или стены подвалов.5109.Монтаж скоб.6710.Устройство стяжек цементных.9511.Конец проекта. фиктивн.

Работа7,8, Рис 3. Проект водоснабжения и наружной канализации при застройки квартала по ул. Токарей-Синяева в г. Екатеринбурге.

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

Шаг nДействия выполняемые шагом1Объявление значений РНАЧv и РВЫПv, vV равным нулю. Текущая вершина vk1.2Вершин предшествующей первой нет. Значение РНАЧ1РВЫП1t1.3Текущая вершина vk2.4Переход в Шаг 2.2РНАЧ2МАКСРВЫП1,РНАЧ2РНАЧ2 стало равным 0 РВЫП2РНАЧ2t2 РВЫП2 стало равным 16.3Текущая вершина vk3.4Переход в Шаг 2.2РНАЧ3МАКСРВЫП2,РНАЧ3РНАЧ2 стало равным 16 РВЫП3РНАЧ3t3 РВЫП3 стало равным 26.3Текущая вершина vk4.4Переход в Шаг 2.2РНАЧ4МАКСРВЫП1,РНАЧ4РНАЧ4 стало равным 0 РВЫП4РНАЧ4t4 РВЫП4 стало равным 32.3Текущая вершина vk5.4Переход в Шаг 2.2РНАЧ5МАКСРВЫП3,РНАЧ5РНАЧ5 стало равным 26 РВЫП5РНАЧ5t5 РВЫП5 стало равным 47.3Текущая вершина vk6.4Переход в Шаг 2.2РНАЧ6МАКСРВЫП5,РНАЧ6РНАЧ6 стало равным 47 РВЫП6РНАЧ6t6 РВЫП6 стало равным 52.3Текущая вершина vk7.4Переход в Шаг 2.2РНАЧ7МАКСРВЫП5,РНАЧ7РНАЧ7 стало равным 47 РВЫП7РНАЧ7t7 РВЫП7 стало равным 61.3Текущая вершина vk8.4Переход в Шаг 2.2РНАЧ8МАКСРВЫП5,РНАЧ8РНАЧ8 стало равным 47 РВЫП8РНАЧ8t8 РВЫП8 стало равным 57.3Текущая вершина vk9.4Переход в Шаг 2.2РНАЧ9МАКСРВЫП6,РНАЧ9РНАЧ9 стало равным 52 РВЫП9РНАЧ9t9 РВЫП9 стало равным .3Текущая вершина vk10.4Переход в Шаг 2.2РНАЧ10МАКСРВЫП9,РНАЧ10РНАЧ10 стало равным 59 РВЫП10РНАЧ10t10 РВЫП10 стало равным 64.3Текущая вершина vk11.4Переход в Шаг 2.2РНАЧ11МАКСРВЫП7,РНАЧ11РНАЧ11 стало равным 61 РНАЧ11МАКСРВЫП8,РНАЧ11РНАЧ11 стало рвным 61 РНАЧ11МАКСРВЫП10,РНАЧ11РНАЧ11 стало равным 64 РВЫП11РНАЧ11t11 РВЫП11 стало равным 64.3Переход в Шаг 5.5Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ.

Таблица результатов работы алгоритма. n1234567891011РНАЧv0016026474747525964РВ ЫПv016263247526157596464 Получили, что минимальное время, требуемое для выполнения проекта равно ТРВЫП11, Т64. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ.

Работу алгоритма изложим в виде последовательности выполняемых шагов. Шаг nДействия выполняемые шагом1Объявление значений ПВЫПv, vV равным Т. Текущая вершина vk11.2ПНАЧ11ПВЫП11-t11 ПНАЧ11 стало равным 64.3ПВЫП7МИНПВЫП7,ПНАЧ11ПВЫП7 стало равным 64 ПВЫП8МИНПВЫП8,ПНАЧ11ПВЫП8 стало равным 64 ПВЫП10МИНПВЫП10,ПНАЧ10ПВЫП9 стало равным 64.4Текущая вершина vk10.5Переход в Шаг 2.2ПНАЧ10ПВЫП10-t10 ПНАЧ10 стало равным 59.3ПВЫП9МИНПВЫП9,ПНАЧ10 ПВЫП9 стало равным 59.4Текущая вершина vk9.5Переход в Шаг 2.2ПНАЧ9ПВЫП9-t9 ПНАЧ9 стало ранвым 52.3ПВЫП6МИНПВЫП6,ПНАЧ9ПВЫП6 стало равным 52.4Текущая вершина vk8.5Переход в Шаг 2.2ПНАЧ8ПВЫП8-t8 ПНАЧ8 стало равным 54.3ПВЫП5МИНПВЫП5,ПНАЧ8ПВЫП5 стало равным 54.4Текущая вершина vk7.5Переход в Шаг 2.2ПНАЧ7ПВЫП7-t7 ПНАЧ7 стало равным 50.3ПВЫП5МИНПВЫП5,ПНАЧ7ПВЫП5 стало равным 50 ПВЫП4МИНПВЫП4,ПНАЧ7ПВЫП4 стало равным 50.4Текущая вершина vk6.5Переход в Шаг 2.2ПНАЧ6ПВЫП6-t6 ПНАЧ6 стало равным 47.3ПВЫП5МИНПВЫП5,ПНАЧ6ПВЫП5 стало равным 47.4Текущая вершина vk5.5Переход в Шаг 2.2ПНАЧ5ПВЫП5-t5 ПНАЧ5 стало равным 26.3ПВЫП3МИНПВЫП3,ПНАЧ5ПВЫП3 стало равным 26.4Текущая вершина vk4.5Переход в Шаг 2.2ПНАЧ4ПВЫП4-t4 ПНАЧ4 стало равным 18.3ПВЫП1МИНПВЫП1,ПНАЧ4ПВЫП1 стало равным 18.4Текущая вершина vk3.5Переходв Шаг 2.2ПНАЧ3ПВЫП3-t3 ПНАЧ3 стало равным 16.3ПВЫП2МИНПВЫП2,ПНАЧ3ПВЫП2 стало равным 16.4Текущая вершина vk2.5Переход в Шаг 2.2ПНАЧ2ПВЫП2-t2 ПНАЧ2 стало равным 0.3ПВЫП1МИНПВЫП1,ПНАЧ2ПВЫП1 стало равным 0.4Текущая вершина vk1.5Переход в Шаг 2.2ПНАЧ1ПВЫП1-t1 ПНАЧ1 стало равным 0.3Переход в Шаг 4.4Переход в Шаг 6.6Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ.

Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE3EPBvПHAЧv-PHAЧv или РЕЗЕРВvПВЫПv-РВЫПv. РаботыРНАЧРВЫППНАЧПВЫПРезерв Из таблицы видно, что критическими работами являются 1, 2, 3, 5, 6, 9, 10, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т64. Литература 1. Асанов М. О. Дискретная оптимизация, УралНАУКА, Екатеринбург 1998.