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

     Для работ, начинающихся с номера , предшествующих работ нет. Для работы, начинающейся на номер , просматриваются все верхние строчки второй графы таблицы и отыскиваются строки, оканчивающиеся на этот номер. Количество найденных работ записывается во все строчки, начинающиеся с номера . Например, для работы (5,8) в гр. 1 поставим цифру 2, так как в гр. 2 на номер 5 оканчиваются две работы: (2,5) и (4,5).

     Заполнение  таблицы начинается с расчета  раннего срока  начала работ. Для  работ, имеющих цифру «ноль» в  первой графе, в гр. 4 также заносятся  нули, а их значение в гр. 5 получается в результате суммирования гр. 3 и 4.  В нашем случае таких работ  только одна — (1, 2), поэтому в гр. 4 в соответствующей ей строке проставим 0, а в гр. 5-0+6=6.

     Для заполнения следующих строк гр.4, т. е. строк, начинающихся с номера 2, просматриваются заполненные строки гр.  5, содержащие работы, которые оканчиваются на этот номер, и максимальное значение переносится в гр. 4 обрабатываемых строк. В данном  случае такая работа лишь одна (1, 2), о чем  можно судить по гр. 1. Цифру 6 из гр. 5 переносим в гр. 4 для всех работ, начинающихся с номера 2, т. е. в три последующие строки с номерами (2, 3), (2, 4), (2,5). Далее для каждой   из этих работ путем   суммирования их значений гр. 3 и 4 сформируем значение гр.5.: 
 

     Этот  процесс повторяется до тех пор, пока не будет заполнена последняя строка таблицы.

     Графы 7 и 6 заполняются «обратным ходом», т. е. снизу вверх. Для этого просматриваются строки, оканчивающиеся на номер последнего события, и из гр. 5 выбирается максимальная величина, которая записывается в гр. 7 по всем строчкам, оканчивающимся на номер последнего события (см. формулу ). В нашем случае . Затем для этих строчек находится содержимое гр. 6 как разность между гр. 7 и 3 Имеем: 

     Далее просматриваются строки, оканчивающиеся на номер события, которое непосредственно  предшествует завершающему событию (10). Для определения гр. 7 этих строк (работы (5,10), (7,10), (8,10), (9,10)) просматриваются все строчки гр. 6, лежащие ниже и начинающиеся с номера 10.

     В гр. 6 среди них выбирается минимальная  величина, которая переносится в гр. 7 по обрабатываемым строчкам. В нашем случае она одна — (10,11), поэтому заносим  во все строки указанных работ цифру . Процесс повторяется до тех пор, пока не будут заполнены все строки по гр. 6 и 7.

     Содержимое  гр. 8 равно разности гр. 6 и 4 или гр. 7 и 5 . Гр. 9 проще получить, воспользовавшись формулой.

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

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

     Где — продолжительность максимального пути, проходящего через работу ;

     — продолжительность  отрезка рассматриваемого пути, совпадающего с критическим путем.

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

     -напряженные ;

     -под критические ;

     -резервные

     В результате перераспределения ресурсов стараются максимально уменьшить  общую продолжительность работ, что возможно при переводе всех работ  в первую группу.

     При расчете этих показателей целесообразно  пользоваться графиком СМ. Итак, для  работ критического пути (1,2), (2,4), (4,5), (5,10), (10,11) . Для других работ: 
 

       и т.д.

     В соответствии с результатами вычислений Кн для остальных работ, которые  представлены в последней графе  табл. 5.1, можно утверждать, что оптимизация  СМ возможна в основном за счет двух резервных работ: (6,11) и (2,5). 
 
 

 

2.3.Сетевое планирование в условиях неопределенности

 

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

     Минимальная (оптимистическая) оценка характеризует продолжительность выполнения работы при наиболее благоприятных обстоятельствах, а максимальная (пессимистическая) — при наиболее неблагоприятных. Продолжительность работы в этом случае рассматривается, как случайная величина, которая в результате реализации может принять любое значение в заданном интервале. Такие оценки называются вероятностными (случайными), и их ожидаемое значение toж оценивается по формуле (при бета-распределении плотности вероятности): 

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

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

     Кроме обычных характеристик СМ, при  вероятностном задании продолжительности работ можно решить две дополнительные задачи:

     1) определить вероятность того, что  продолжительность критического  пути tкр не превысит заданного директивного уровня Т;

     2) определить максимальный срок  выполнения всего комплекса работ  Т при заданном уровне вероятности  р.

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

     Где нормированное отклонение случайной  величины:  

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

     Соответствие  между z и симметричным   интегралом   вероятностей  приведено в табл. 2. Более точно соответствие между этими величинами (когда z вычисляется более чем с одним знаком в дробной части) можно найти в специальной статистической литературе.

     При достаточно большой полученной величине вероятности (более 0,8) можно с высокой  степенью уверенности предполагать своевременность выполнения всего комплекса работ.

     Для решения второй задачи используется формула: 
 

     Таблица 2

     Фрагмент  таблицы стандартного нормального  распределения 

 

     Кроме описанного способа расчета сетей  с детерминированной структурой и вероятностными оценками продолжительности выполнения работ, используется метод статистических испытаний (метод Монте-Карло). В соответствии с ним на вычислительной технике многократно моделируется продолжительность выполнения работ и рассчитывается на основе этого основные характеристики сетевой модели. Большой объем испытаний позволяет более точно выявить закономерность моделируемой сети.

     ПРИМЕР. Построение сетевой модели Структура сетевой модели и оценки продолжительности работ (в сутках) заданы в табл. 3. Требуется:

     а) получить все характеристики СМ;

     б) оценить вероятность выполнения всего комплекса работ за 35 дней, за 30 дней;

     в) оценить максимально возможный  срок выполнения всего комплекса  работ с надежностью 95% (т. е. р=0,95).

     Три первые графы табл. 3. содержат исходные данные, а две последние графы — результаты расчетов по формулам Так, например, 
 
 
 
 
 
 

     Таблица 3