Глава 7. Модели сетевого планирования.
§1. Сетевая модель и ее основные элементы
Определение 1. Сетевое планирование и управление - это система методов планирования и управления разработкой крупных народно - хозяйственных комплексов.
Определение 2. Сетевая модель - это совокупность взаимосвязанных работ и событий, отражающих процесс достижения определенной цели.
Определение 3. Графическое изображение сети или сетевой модели называется сетевым графиком. Он представляет собой ориентированный конечный связный граф, который имеет начальную вершину (источник) и конечную вершину (сток).
Основные понятия сетевой модели - это работа, события и путь.
События изображаются вершинами графа, а работы - ориентированными ребрами.
Обозначение работ: (0,1), (1,4) и «→»
Продолжительность работ: t(1,4) = 3 у. е.
На приведенном сетевом графике 8 событий и 15 работ. Если на сетевом графике нет числовых оценок продолжительности работ, то модель называется структурной.
Определение 4. Работа в сетевой модели понимается в обобщенном смысле:
1. материальное действие - действительная работа, требующая затрат ресурсов и времени, например, сборка мебели, изделий;
2. ожидание - это протяженный во времени процесс, требующий затрат ресурсов, но не требующий затрат труда, например, затвердевание бетона;
3. фиктивная работа показывает логическую связь между работами. Фиктивная работа не требует затрат денег, труда и ресурсов.
На графике фиктивная работа изображается пунктирной стрелкой «- - - →».
Определение 5. Событие - это момент или результат завершения какой-либо работы, отображающий отдельный этап выполнения проекта.
Свойства событий:
1. Двойственность - одно и то же событие может быть конечным для всех непосредственно - предшествующих ему работ и начальным для всех непосредственно за ним следующих работ.
2. Событие не имеет продолжения и считается как бы мгновенным, когда оканчивается последняя из работ, входящая в него.
3. Исходное событие обозначается числом «0», у него нет предшествующих работ.
4. Завершающее событие обозначается символом 
, оно не имеет последующих работ, в него работы только входят.
Определение 6 . Упорядоченным называется такой сетевой график, в котором события и работы расположены так, что для любой работы предшествующей ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием. Иначе, в упорядоченном сетевом графике все работы - стрелки направлены слева - направо от событий с меньшими номерами к событиям с большими номерами.
Определение 7. Путь - это любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работой.
Определение 8. Полный путь - это любой путь, начало которого совпадает с исходным событием сети, а конец - с завершающим событием.
Определение 9. Наиболее продолжительный путь в сетевом графике называется критическим. Работа и событие на этом пути тоже называются критическими. Продолжительность критического пути обозначается 
. Несвоевременное выполнение критических работ ведет к срыву всего комплекса работ. Для определения 
и есть специальные алгоритмы.
§2. Примеры ошибок при построении сетевой модели
1. В сетевой модели не должно быть работы вида (4,3), так как для каждой пары i и j должно быть i < j => нужно перенумеровать события.
2. Не должно быть событий тупиковых, вида (5), тупиковым может быть только завершающее событие.
3. Должны отсутствовать события, кроме начального, которым не предшествует ни одна работа - хвостовые события.
4. В сетевой модели не должно быть циклов и петель: (3,2,4,3) - цикл.
5. Любые два события должны быть связаны не более чем одной работой - стрелкой.
6. В сетевой модели рекомендуется иметь одно исходное и одно завершающее событие. Если этого нет, то вводят фиктивные события работы.
§3. Линейная диаграмма сетевого графика
После упорядочения сетевого графика можно рассматривать его линейную диаграмму.
1. Каждая работа изображается отрезком горизонтальной оси 0-t, длина которого равна продолжительности этой работы.
2. При наличии фиктивной работы ее изображают точкой.
3. События i, j, работы (i, j) помещают соответственно в начале и в конце отрезка, причем i < j.
4. Отрезки располагают один над другим снизу вверх или сверху вниз с порядком возрастания индекса i.
5. Если предшествующих событий на диаграмме несколько, то выбирают то из них, которое имеет наибольшую координату по времени.
6. Критическое, т. е. max время всего комплекса работ равно координате на оси времени 0-t самого правого конца всех отрезков диаграммы, т. е. 
7. По линейной диаграмме можно определить обратным ходом критический путь , а также резервы времени всех работ.
8. При небольшом количестве работ вычисление легко проделать вручную, реальные же сетевые графики содержат сотни и тысячи работ и их анализ возможен только при помощи ЭВМ.
§4. Решение задачи сетевого планирования
Задача: при разработке проекта водонасосной башни было выделено 8 станций - событий 0, 1, 2, 3, 4, 5, 6, 7 и 15 связывающих их путей - работ, с указанием их пропускной способности.
1. построить сетевой график оттоков
2. найти несколько полных путей
3. построить линейную диаграмму сетевого графика и определить по нему критический путь и протяженность критического пути, т. е. максимально возможный поток воды.
Решение:
1)
2) 
3) Построим линейную диаграмму
§5. Аналитический способ определения критического пути
Определение 1. Ранний срок свершения события равен величине наиболее длинного отрезка пути от исходного события до рассматриваемого. Для определения раннего срока свершения события существует рекуррентное соотношение:
, причем 
Определение 2. Поздний срок свершения события i характеризует самый поздний допустимый срок, к которому должно свершиться событие, не вызывая при этом срыва срока начального события.
 |
 |
