4.2. Параметры сетевой модели

Пусть сетевая модель задана. Рассмотрим ее числовые характеристики. Будем считать, что каждой вершине сети присан номер из множества {1,…,N}, а каждой дуге – номер из множества {1,…,M}. Более того, предположим источник имеет номер 1, а сток – номер N. Заметим, что, если первоначально в сетевой модели несколько входов (выходов), следует ввести один фиктивный вход (выход), с которым связать фиктивными дугами все входы (выходы).

Далее считаем, что сетевая модель представлена списком дуг, каждая из которых закодирована четырьмя числами:

- J – номер дуги;

- I(J) – номер начальной вершины;

- K(J) – номер конечной вершины;

- TJ – длина (продолжительность соответствующей работы).

Определение 4.5. Наиболее ранним временем наступления события I Является величина =|M*(1,I)|. Время T = назовем Критическим временем проекта (это минимально возможное время выполнения всего проекта). Путь M*(1,N), а также дуги (работы) и вершины (события), принадлежащие этому пути, являются также Критическими.

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

Определение 4.6. Свободным резервом выполнения работы J является величина --TJ, которая равна максимальному увеличению продолжительности выполнения работы J, не меняющему ранние времена выполнения других работ.

Определение 4.7. Наиболее поздним временем наступления события I является величина = T – |M*(I,N)|. Это значит, что если событие I наступит не позже момента , тогда время выполнения всего проекта не увеличится.

Событие I является критическим тогда и только тогда, когда = .

Определение 4.8. Полным резервом выполнения работы J является величина --TJ. На такую величину можно увеличить продолжительности выполнения работы J, чтобы не изменилось критическое время проекта.

Очевидно, критические работы имеют нулевой свободный и полный резервы.

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

Для нахождения рангов событий используется

Алгоритм Форда.

Шаг 0. Для всех вершин I=1,…,N полагаем Ri = 0.

Пусть в результате (K-1) шагов найдены величины Ri.

Шаг K. Просматриваем последовательно работы J=1,…,M и пересчитываем величины Rk(J) := Max{Rk(J) , Ri(J) + 1}.

Если на каком-то шаге K величины Ri, I=1,…,N, не меняются, тогда они являются рангами событий. Иначе полагаем K=K+1 и повторяем Шаг K.

Теорема 4.1. В результате выполнения K шагов алгоритма Форда получим:

1) Ri £ Ri;

2) Ri = Ri, если ранг события I не превосходит K.

Доказательство. Докажем утверждение 1) для фиксированного K индукцией по рангу события. Для входа R1 = 0, т. к. эта вершина не является концевой ни для одной дуги. Предположим неравенство справедливо для событий рангов 1,…,R. Рассмотрим событие I, ранг которого Ri>R. Пусть K(J)=I и J - последняя работа, при рассмотрении которой изменилась величина Ri (т. е. произошло присваивание Ri = R¢I(J) + 1). Тогда, по предположению индукции, Ri = R¢I(J)+ 1 £ Ri(J) + 1 £ Ri(J) + 1 £ Ri.

Докажем 2) индукцией по номеру шага алгоритма. На шаге 0 для единственной вершины ранга 0 имеем R1 = R1 = 0. Пусть величины Ri (Ri = K) найдены в результате работы шагов 1,…, K. Рассмотрим работу J Такую, что K(J) = I, Ri(J) = K-1. По индукционному предположению и утверждению 1) величина Ri(J) не меняется на шаге K и равна Ri(J). Следовательно, Ri ³ Ri(J) + 1 = Ri(J) + 1 = K.¨

Отметим, что трудоемкость алгоритма Форда равна O(Mn).

Определение 4.6. Нумерация вершин (событий) называется Правильной, если I(J) < K(J) для всех работ J=1,…,M.

Зная ранги событий, легко осуществить правильную нумерацию вершин:

- вход (вершина нулевого ранга) получает номер 1;

- вершинам ранга 1 приписываются номера 2,…,N1;

- вершины, имеющие ранг 2, нумеруются числами N1+1,…,N2;

- и т. д.

- выход получает номер N.

Алгоритм Форда для ранних времен наступления событий:

Шаг 0. Для всех I=1,…,N полагаем = 0.

Пусть в результате (K-1) шагов найдены значения .

Шаг K. Просматриваем последовательно работы J=1,…,M и пересчитываем величины := max{ , + TJ}.

Если на каком-то шаге K времена не меняются, то алгоритм останавливается. В протимном случае увеличиваем на единицу K и повторяем Шаг K.

Определение 4.7. Дуги сети правильно упорядоченны, если P < Q в случае, когда PQ. То есть, если в проекте работа P предшествует работе Q, то ее номер должен быть меньше Q.

Предположим вершины занумерованы правильно. Для получения правильно упорядоченного списка дуг (работ) в этом случае достаточно воспользоваться номерами конечных вершин. Ниже приведено описание этой простой процедуры.

Шаг 0. Положим K=1, Nk=0.

Шаг K. Дуги, входящие в вершину K, нумеруются числами Nk+1,…,Nk+Mk, где Mk=|{I: (I,K)ÎU}|. Если K¹N, полагаем K=K+1, Nk=Nk+Mk И повторяем Шаг K. Иначе, стоп.

Теорема 4.2. Если работы правильно упорядочены, алгоритм Форда находит ранние времена наступления событий за один просмотр работ J=1,…,M.

Доказательство. Пусть работы правильно упорядочены и величины Ti, I=1,…,N являются ранними временами, вычисленными на первом шаге алгоритма Форда. Предположим, что на втором шаге алгоритм не остановился. Значит существует вершина I, у которой раннее время, полученное на первом шаге , меньше значения , полученного на втором шаге. Пусть работа J Является первой в списке, когда величина Ti = Tk(J) изменилась на втором шаге алгоритма. Тогда для вершины I(J) раннее время также изменилось на втором шаге, т. е. < . Но должно выполняться равенство = Ti(J), так как в правильно упорядоченном списке работ дуги, заканчивающиеся в вершине I(J) предшествуют работе J. Следовательно, изменение Ti(J) на втором шаге алгоритма (до просмотра работы J) противоречит выбору этой работы.¨

Алгоритм Форда для поздних времен наступления событий:

Шаг 0. Для всех I=1,…,N полагаем = Т = .

Пусть на (K-1) шаге найдены величины .

Шаг K. Просматриваем работы списка J=1,…,M и пересчитываем величины := min{, - TJ }.

Если времена не меняются, то алгоритм останавливается. Иначе повторяем шаг K.

Замечание 4.1. В случае правильной упорядоченности работ величины находятся за один просмотр дуг в обратном порядке J=M,…,1.

Когда ранние T и позние T времена наступления событий известны, другие параметры (характеристики) сети (критические события и работы, свободный и полный ресурсы) могут быть легко найдены за один просмотр списка работ.

< Предыдущая