Материал: УП - Методы оптимальных решений

i = 2, 3

Итак, если событием j заканчивается одна работа (i, j), то t_p (j) равно сумме t_p (i) – раннего срока свершения ее начального события и t_p (i, j) – продолжительность этой работы.

Если же событием j заканчивается несколько работ, то по каждой работе находится свой ранний срок, а искомый t_p (j) будет максимальной из них.

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

И

j

выходящих из i-события, t_п (j) – поздний срок свершения конечного события (i, j).

Поздний срок t_п (J) = 0, t_п (S) = t_p (S) = t_КР. В нашем примере t_п (5) = 12.

Чтобы не нарушился критический срок, событие 4 должно произойти по крайней мере на 5 дней раньше события 5, поэтому . Аналогично для события 3: по работе ; по работе .

Разность между поздним и ранним сроками свершения события i называется резервом времени этого события:

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

У критических событий ранние и поздние сроки свершения равны, так как резерв времени у них равен 0.

Полный резерв времени – это max количество времени, на которое можно задержать начало работы или увеличить её продолжительность, не нарушая критический срок:

Существуют различные способы расчета временных параметров сети. Рассмотрим способ подсчета непосредственно на сети и разберем его на примере 31. Каждое событие изобразим кружком и разделим диаметрами на четыре сектора (рис. 20 и 21):

Пример 31. На основе данных примера 29 рассчитать временные параметры сети.

Решение.

Работы проводят (вычисляют) в 4 этапа, а именно, вычисляют 1) 2) 3) 4) критический путь.

1 этап. При вычислении перемещаются по сети от события J к событию S в порядке возрастания номеров: событие 1 => => в левом секторе кружка 1 записываем 0. Событие 2 =>

Событие 3 =>

во всех работах фиктивные работы учитываются наряду с реальными. Аналогично считаем все оставшиеся сроки.

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

Так как , то в правый сектор кружка 6 мы записываем .

Событие 5:

Из события 4 выходят две работы (4 – 5) и (4 – 6), поэтому

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

3 этап. Для определения резервов времени событий из чисел, записанных в правом секторе, вычитаем числа, записанные в левых секторах и заполняем нижние секторы.

В итоге получим сеть, представленную на рис. 21.

Рис. 21

4 этап. У критических событий резерв времени равен 0, поэтому критическими являются события .

Чтобы найти полный резерв времени , применяем формулу: и т. д.

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

Задания для самостоятельной работы

На данной сети дорог (рис. 22) имеется несколько маршрутов, по которым можно доставить груз из пункта 1 в пункт 10. Известны стоимости c_ij перевозки единицы груза между пунктами сети. Найти наиболее экономный маршрут доставки груза из пункта 1 в пункт 10 и соответствующие ему затраты.

Рис. 22

Все необходимые данные приведены в табл. 40.

Таблица 40