8.5 Сети. Критический путь
Часто приходится решать задачи, в которых каждому ребру заданного графа приписано некоторое положительное (неотрицательное) число (его вес). Обычно, граф нагруженный подобным образом, называется сетью, его вершины – узлами, а ребра – дугами.
Предположим, что требуется проанализировать сложный проект с точки зрения минимальных временных затрат на его выполнение. Для этого проект разбивают на отдельные этапы (работы, операции), оценивают время, необходимое на проведение каждой работы. Составляют таблицу, в которую заносят все виды работ по проекту, их продолжительность и последовательность выполнения.
По данным таблицы строится ориентированная сеть, дуги которой соответствуют работам проекта, а узлы – событиям, обозначающим начало и/или конец этапов. Каждая дуга нагружена числом, равным продолжительности выполнения соответствующей работы. Понятно, что операции, соответствующие дугам, исходящим из произвольного узла сети, не могут начаться прежде, чем закончатся операции, отвечающие дугам, входящим в этот узел.
Подобная сеть называется сетевым графиком проекта или диаграммой работ.
В результате вычерчивания диаграммы работ определяется путь, наибольшей продолжительностью. Этот путь называется критическим. Он и определяет минимальное время выполнения проекта. Работы, входящие в критический путь, называются критическими работами.
Рассмотрим пример построения сетевого графика, определения критического пути и критических работ, а также минимального времени выполнения всех работ.
Составлена таблица последовательности работ проекта, в которой также указаны предшествующие работы и записано время выполнения каждой работы. Построить сетевой график данного проекта.
Критический путь
Путь – любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующий за ней работы.
Полный путь L – любой путь, начало которого совпадает с исходным событием сети, а конец – с завершающим.
Наиболее продолжительный полный путь в сетевом графике называется критическим. Критическими также называются работы и события расположенные на этом пути. Работы этого пути определяют общий цикл завершения всего комплекса работ, планируемых при помощи сетевого графика. И для сокращения продолжительности проекта необходимо в первую очередь сокращать продолжительность работ, лежащих на критическом пути.
- Составить экономическое содержание задачи и перечислить перечень работ.
- Построить сетевой график и определить критический путь.
- Рассчитать параметры сетевого графика и поздние сроки поступления событий, резервы времени.
| Работа (i,j) | Количество предшествующих работ | Продолжительность tij | Ранние сроки: начало tij Р.Н. | Ранние сроки: окончание tij Р.О. | Поздние сроки: начало tij П.Н. | Поздние сроки:окончание tij П.О. | Резервы времени: полный tij П | Резервы времени: свободный tij С.В. | Резервы времени: событий Rj |
| (1,2) | 0 | 3 | 0 | 3 | 1 | 4 | 1 | 0 | 1 |
| (1,3) | 0 | 6 | 0 | 6 | 0 | 6 | 0 | 0 | 0 |
| (1,4) | 0 | 4 | 0 | 4 | 9 | 13 | 9 | 9 | 0 |
| (2,3) | 1 | 2 | 3 | 5 | 4 | 6 | 1 | 1 | 0 |
| (2,5) | 1 | 5 | 3 | 8 | 12 | 17 | 9 | 2 | 7 |
| (3,4) | 2 | 7 | 6 | 13 | 6 | 13 | 0 | 0 | 0 |
| (3,5) | 2 | 4 | 6 | 10 | 13 | 17 | 7 | 0 | 7 |
| (3,6) | 2 | 4 | 6 | 10 | 15 | 19 | 9 | 9 | 0 |
| (4,6) | 2 | 6 | 13 | 19 | 13 | 19 | 0 | 0 | 0 |
| (5,6) | 2 | 2 | 10 | 12 | 17 | 19 | 7 | 7 | 0 |
Критический путь: (1,3)(3,4)(4,6)
Продолжительность критического пути: 19 Перейти к онлайн решению своей задачи Пример . Рассчитать параметры сетевого графика мероприятия по совершенствованию системы управления. Сетевая модель задана таблично. Продолжительность выполнения работ дана в виде минимальной и максимальной оценок. Требуется вычислить табличным методом все основные характеристики работ и событий, найти критический путь и его продолжительность.
Скачать
