Сетевое планирование в условиях неопределенности. Анализ и оптимизация сетевого графика

              Необходимо: а) построить сетевой график; б) определить средние (ожидаемые) значения продолжительности работ; в) определить критический путь и его длину; г) резерв времени и коэффициент напряжённости работы. Полагая, что продолжительность критического пути распределена по нормальному закону, найти: а)вероятность того, что срок выполнения комплекса работ не превысит 20 суток; б) максимальное значение продолжительности выполнения проекта, которое можно гарантировать с надёжностью 0,95.

Решение:

Сетевой график имеет вид:

                                          рис. 6

Рассчитаем средние (ожидаемые) значения продолжительности работ по  формуле:

Tож ij=(t0+4tнв+tп)/6

Таблица 2.

После построения графика и сбора необходимых исходных данных рассчитывают параметры сети: сроки совершения событий, резервы времени, продолжительность критического пути. Для описания сети в "терминах событий" используются следующие понятия:

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

Tpi=max tож ij                                        

Тр(1)=0;

Тр(2)=9;

Тр(3)=6;

Тр(4)=max(9;6+14)=20;

Тр(5)=max(20+5;9+11)=25;

- максимальный путь от исходного события 1 до завершающего называется критическим путем сети (Tкр);

- поздний срок наступления событий (Tni) - максимально допустимый срок наступления данного события, при котором сохраняется возможность соблюдения ранних сроков наступления последующих событий, равен разности между продолжительностью критического пути и наибольшего из путей, ведущих от завершающего события 1 к данному:

Tni=Tкр-max tож                                

Тп(5)=25;

Тп(4)=25-5=20;

Тп(3)=20-14=6;

Тп(2)=25-11=14;

Тп(1)=min(14-9;6-6;20-9)=0;

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

Ri=Tni-Tpi                                           

R(1)=0-0=0;

R(2)=14-9=5;

R(3)=6-6=0;

R(4)=20-20=0;

R(5)=25-25=0;

При описании сети в "терминах работ" определяют:

- ранние и поздние сроки начала и окончания работ i, j:

−        ранний срок начала: Tpнij=Tpi                                      

−        поздний срок начала: Tnнij=Tнj-tij                                        

−        ранний срок окончания: Tpoij=Tpi+tij                                           

−        поздний срок окончания: Tnoij=Tni                                                  

Работы сетевой модели могут иметь два вида резервов времени: полный(Rnij) и свободный (Rcij).

Полный резерв показывает, на сколько может быть увеличена продолжительность данной работы или сдвинуто её начало так, чтобы продолжительность максимального из проходящих через неё путей не превысила критического пути.

Rnij=Tnj-Tpi-tij                                   

Свободный резерв показывает максимальное время, на которое можно увеличить продолжительность данной работы или изменить её начало, не меняя ранних сроков начала последующих работ.

Rcij=Tpj-Tpi-tij                                 

Результаты расчета параметров сетевого графика приведены в таблице 3.

Таблица 3.

Параметры сетевого графика

Путь Lкр = 1-3-4-5 является критическим. Его продолжительность равна 25 дням.

              Проведем анализ сетевого графика на основе рассчитанных выше временных характеристик.

              Рассчитаем коэффициенты напряженности, показывающие степень близости данного пути к критическому. Коэффициент напряженности пути Kн определяется по следующей формуле:

Kн=(Lmax-Lкр)/(Lкр-Lкр)                                       

где  Lmax - продолжительность рассматриваемого пути;

Lкр   - продолжительность критического пути;

Lкр- продолжительность участков, принадлежащих критическому пути.

              Расчет коэффициентов напряженности позволяет проанализировать топологию сети в отношении выравнивания коэффициентов напряженности. Чем выше коэффициент напряженности, тем ближе данный путь к критическому и наоборот и чем меньше коэффициент напряженности, тем большими резервами обладает данный путь. Для работ критического пути (1,3), (3,4), (4,5) Kн=1. Для других работ

Kн(1-2)=Kн(2-5)=(23-0)/(25-0)=0,92

Kн(1-4)=(10-5)/(25-5)=0,25

Определим вероятность того, что срок выполнения комплекса работ не превысит 20 суток на основе интеграла вероятностей Лапласа Ф(z) использованием формулы:

P (t kp < T) = 0,5 + 0,5 Ф(z),

Где нормированное отклонение случайной величины: z = (Т - tKp)/S Kp;

SKp — среднее квадратическое отклонение, вычисляемое как корень квадратный из дисперсии продолжительности критического пути.

Тогда имеем:             

∑ dКр- сумма значений дисперсий работ критического пути.

Дисперсия, является мерой неопределенности случайной величины tож. Для метода двух оценок дисперсия определяется по формуле:

d2=((tmax-tmin)/5)2                         

d2=(9-4)2:25+(16-11)2:25+(6-3)2:25=2,36

Значение функции Px находят по ее аргументу, используя таблицу4 интеграла Фурье, приводимую в справочниках по математической статистики[3].

Р(tкр <20) = 0,5 + 0,5 Ф{(20 - 25)/2,361/2} =

= 0.5 + 0.5 Ф(-3,26)=0,5-0,5*0,99889=0,00055

Таким образом, вероятность того, что весь комплекс работ будет выполнен не более чем за 20 дней, составляет всего 0,055% .

Для нахождения максимального значения продолжительности выполнения проекта, которое можно гарантировать с надёжностью 0,95, прежде всего в табл.4 найдем значение аргумента z, которое соответствует заданной вероятности 95% . В графе Ф(z)  соответствует z = 1,96. В этой связи в формуле (3) будем использовать именно это значение. Тогда получим:

Т = tож(Lкр) + z*SKp = 25 + 1,96*2,361/2 = 28,01 дн.

Следовательно, максимальный срок выполнения всего комплекса работ при заданном уровне вероятности р = 95% составляет 28,01 дней.             

Фрагмент Таблицы значений функции Лапласа

при разных значениях t; F(–t) = –F(t) (функция нормального распределения).

Таблица 4.