Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Упростить выражение
Примеры решений Теория игр Задача о назначениях Поток сети
Сетевой график онлайн Задача коммивояжера Системы МО
Транспортная задача Симплекс-метод Двойственная задача

Критический путь

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

Пример. Выполняется комплекс работ. Заданы работы (i, j), длительность их выполнения tij. В процессе решения необходимо:

  1. Составить экономическое содержание задачи и перечислить перечень работ.
  2. Построить сетевой график и определить критический путь.
  3. Рассчитать параметры сетевого графика и поздние сроки поступления событий, резервы времени.

Решение находим с помощью калькулятора.
Все вычисления будем заносить в таблицу.
Перечень работ и их продолжительность перенесем во вторую и третью графы. При этом работы следует записывать в графу 2 последовательно: сначала начиная с номера 1, затем с номера 2 и т.д.
Во второй графе поставим число, характеризующее количество непосредственно предшествующих работ (КПР) тому событию, с которого начинается рассматриваемая работа.
Так, для работы (3,4) в графу 1 поставим число 2, т.к. на номер 3 оканчиваются 2 работы: (1,3),(2,3).
Далее заполняем графы 4 и 5. Для работ, имеющих цифру 0 в графе 2, в графу 4 также заносятся нули, а их значения в графе 5 получаются в результате суммирования граф 3 и 4.
Для заполнения следующих строк графы 4, т.е. строк начиная с номера 2, просматриваются заполненные строки графы 5, содержащие работы, которые оканчиваются на этот номер, и максимальное значение переносится в графу 4 обрабатываемых строк.
Этот процесс повторяется до тех пор, пока не будет заполнена последняя строка таблицы.
Заполнение графы 4.
Рассмотрим события: (1,2): 3. Заносим значение 3 в графу.
Рассмотрим события: (1,3): 6;(2,3): 5. Максимальное значение: 6. Заносим его в графу.
Рассмотрим события: (1,4): 4;(3,4): 13. Максимальное значение: 13. Заносим его в графу.
Рассмотрим события: (2,5): 8;(3,5): 10. Максимальное значение: 10. Заносим его в графу.
Графы 6 и 7 заполняются обратным ходом, т.е. снизу вверх. Для этого просматриваются строки, оканчивающиеся на номер последнего события, и из графы 5 выбирается максимальная величина, которая записывается в графу 7 по всем строчкам, оканчивающимся на номер последнего события (т.к. tр(i)= tп(i)).
Процесс повторяется до тех пор, пока не будут заполнены все строчки по графам 6 и 7.
Заполнение графы 7.
Рассмотрим события:
(3,6): 10
(4,6): 19
(5,6): 12
Максимальное значение: 19. Записываем его в графу 7 по всем строчкам, оканчивающимся на номер последнего события 6.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 5. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 5.
(5,6): 19 - 2 = 17;
Данное значение переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 17.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 4. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 4.
(4,6): 19 - 6 = 13;
Данное значение переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 13.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 5. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 5.
(5,6): 19 - 2 = 17;
Данное значение переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 17.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 3. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 3.
(3,4): 13 - 7 = 6;
(3,5): 17 - 4 = 13;
(3,6): 19 - 4 = 15;
В графу 6 среди них выбирается минимальная величина, которая переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 6.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 4. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 4.
(4,6): 19 - 6 = 13;
Данное значение переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 13.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 3. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 3.
(3,4): 13 - 7 = 6;
(3,5): 17 - 4 = 13;
(3,6): 19 - 4 = 15;
В графу 6 среди них выбирается минимальная величина, которая переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 6.
Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 2. Для определения графы 7 этих строк просматриваются все строчки, начинающиеся с номера 2.
(2,3): 6 - 2 = 4;
(2,5): 17 - 5 = 12;
В графу 6 среди них выбирается минимальная величина, которая переносится в графу 7 по обрабатываемым строчкам.. В нашем случае это значение: 4.
Содержимое графы 8 равно разности граф 6 и 4 или граф 7 и 5.
Работа (i,j)Количество предшествующих работПродолжительность tijРанние сроки: начало tijР.Н.Ранние сроки: окончание tijР.О.Поздние сроки: начало tijП.Н.Поздние сроки:окончание tijП.О.Резервы времени: полный tijПРезервы времени: свободный tijС.В.Резервы времени: событий Rj
(1,2)030314101
(1,3)060606000
(1,4)0404913990
(2,3)123546110
(2,5)15381217927
(3,4)27613613000
(3,5)246101317707
(3,6)246101519990
(4,6)2613191319000
(5,6)2210121719770
Критический путь: (1,3)(3,4)(4,6)
Продолжительность критического пути: 19

Перейти к онлайн решению своей задачи

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