Теория графов

Особое значение для сетевого графа имеют следующие понятия:

Ранний срок свершения события - минимальное время, к которому необходимо завершить все работы, предшествующие этому событию.

Поздний срок свершения события - момент времени, после которого остается ровно столько времени, сколько необходимо для завершения всех работ, следующих за этим событием.

При оценке резервов времени удобно использовать еще два вспомогательных понятия:

Ранний срок окончания работы - срок, раньше которого нельзя закончить данную работу. Он равен сумме раннего срока свершения работы и продолжительности данной работы.

Поздний срок начала работы - срок, позже которого нельзя начинать данную работу, не увеличив общую продолжительность строительства. Он равен разнице позднего срока окончания работы и продолжительности данной работы.

Полный резерв - это наибольшее время, на которое можно задержать выполнение данной работы, не увеличивая общую продолжительность работ. Он определяется разностью между поздним и ранним началом (или поздним и ранним окончанием).

Свободный резерв - это наибольшее время, на которое можно задержать выполнение данной работы, не меняя раннего начала последующей. Этот резерв возможен только тогда, когда в событие входят две или более работы (зависимости), т.е. на него направлены две или более стрелки (сплошные или пунктирные). Тогда лишь у одной из этих работ раннее окончание будет совпадать с ранним началом последующей работы, для остальных же это будут разные значения. Эта разница у каждой работы и будет ее частным резервом.

Рассчитаем критический путь графа задания:

M1: 1-4-7-8 t1=5+9+5=19

M2: 1-4-5-6-8 t1=5+7+2+4=18

M3: 1-4-6-8 t1=5+4+4=13 M4: 1-4-5-6-7-8 t1=5+7+2+1+5=20

M5: 1-4-6-7-8 t1=5+4+1+5=15

M6: 1-3-4-5-6-7-8 t1=6+3+7+2+1+5=24

M7: 1-3-4-5-6-8 t1=6+3+7+2+4=22

M8: 1-3-4-6-8 t1=6+3+4+4=179: 1-3-4-7-8 t1=6+3+9+5=23

M10: 1-3-5-6-8 t1=6+5+2+4=17

M11: 1-3-6-8 t1=6+5+2+1+5=19

M12: 1-3-6-7-8 t1=6+2+1+5=14

M13: 1-3-5-6-7-8 t1=6+5+2+1+5=19