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

Продолжительность выполнения работ часто трудно задать точно и потому в практической работе вместо одного числа (детерминированная оценка) задаются две оценки — минимальная и максимальная.
Минимальная (оптимистическая) оценка t_min(i,j) характеризует продолжительность выполнения работы при наиболее благоприятных обстоятельствах, а максимальная (пессимистическая) t_mах(i,j) — при наиболее неблагоприятных. Продолжительность работы в этом случае рассматривается, как случайная величина, которая в результате реализации может принять любое значение в заданном интервале. Такие оценки называются вероятностными (случайными), и их ожидаемое значение t _oж оценивается по формуле (при бета-распределении плотности вероятности):
t_ож(i,j)=(3t_min (i,j)+2t_max(i,j))/5.
Для характеристики степени разброса возможных значений вокруг ожидаемого уровня используется показатель дисперсии S²:
S²(i,j)=(t_max(i,j)–t_min(i,j))²/5²=0,04(t_max(i,j)–t_min(i,j))²
На основе этих оценок можно рассчитать все характеристики СМ, однако они будут иметь иную природу, будут выступать как средние характеристики. При достаточно большом количестве работ можно утверждать (а при малом — лишь предполагать), что общая продолжительность любого, в том числе и критического, пути имеет нормальный закон распределения со средним значением, равным сумме средних значений продолжительности составляющих его работ, и дисперсией, равной сумме дисперсий этих же работ.
Кроме обычных характеристик СМ, при вероятностном задании продолжительности работ можно решить две дополнительные задачи:
1) определить вероятность того, что продолжительность критического пути tкр не превысит заданного директивного уровня Т;
2) определить максимальный срок выполнения всего комплекса работ Т при заданном уровне вероятности р.
Первая задача решается на основе интеграла вероятностей Лапласа Ф(z) использованием формулы:
P(t_kp<T)=0,5+0,5Ф(z),
Где нормированное отклонение случайной величины:
z =(Т - t _Kp)/ S _Kp;
S _Kp — среднее квадратическое отклонение, вычисляемое как корень квадратный из дисперсии продолжительности критического пути.
Соответствие между z и симметричным интегралом вероятностей приведено в табл. 5.2. Более точно соответствие между этими величинами (когда z вычисляется более чем с одним знаком в дробной части) можно найти в специальной статистической литературе.
При достаточно большой полученной величине вероятности (более 0,8) можно с высокой степенью уверенности предполагать своевременность выполнения всего комплекса работ.
Для решения второй задачи используется формула:
Т=t_ож(L_kp)+z×S_kp

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

Кроме описанного способа расчета сетей с детерминированной структурой и вероятностными оценками продолжительности выполнения работ, используется метод статистических испытаний (метод Монте-Карло). В соответствии с ним на вычислительной технике многократно моделируется продолжительность выполнения работ и рассчитывается на основе этого основные характеристики сетевой модели. Большой объем испытаний позволяет более точно выявить закономерность моделируемой сети.
ПРИМЕР. Построение сетевой модели Структура сетевой модели и оценки продолжительности работ (в сутках) заданы в табл. 5.3. Требуется:
а) получить все характеристики СМ;
б) оценить вероятность выполнения всего комплекса работ за 35 дней, за 30 дней;
в) оценить максимально возможный срок выполнения всего комплекса работ с надежностью 95% (т. е. р=0,95).
Три первые графы табл. 5.3. содержат исходные данные, а две последние графы — результаты расчетов по формулам Так, например,
t_ож(i,j)=(3t_min(i,j)+2t_max(i,j))/5;
t_ож(1,2)=(3*5+2*7,5)/ 5=6;
t_ож(2,3)=(3*4+2*6,5)/ 5=5;
S²(i,j)=(t_max(i,j)–t_min(i,j)²/5²=0.04×(t_max(i,j)–t_min(i,j)²;
S²(1,2)=(7,5-5)²/25=0,25;
S²(2,3)=(6,5-4)²/25=0,25.

Таблица 5.3

Получим сетевую модель, аналогичную рассмотренной в п. 5.2.:

Получим сетевую модель, аналогичную рассмотренной в п. 5.2.: Таким образом, ход расчета характеристик модели остается аналогичен рассмотренному ранее. Напомним, что критическим является путь: L_кр=(1,2,4,5,10,11), а его продолжительность равна t_кр=t_ож=33 дня.
Дисперсия критического пути составляет:
S²_Kp=S²(l,2)+S²(2,4)+S²(4,5)+S²(5,10)+S²(10,M)=0,25+1,00+0,25+1,00+0,25=2,75.
Для использования формулы показателя дисперсии необходимо иметь среднее квадратическое отклонение, вычисляемое путем извлечения из значения дисперсии квадратного корня, т. е. S_Kp=1,66. Тогда имеем:
Р(t_кр<35)=0,5+0,5Ф{(35-33)1,66}=0.5+0.5Ф(1,2)=0,5+0,5*0,77=0,885
Р(t_кр<30)=0,5+0,5Ф{(30-33)/1,66}=0,5-0,5Ф(1,8)=0,5-0,5•0,95=0,035.
Таким образом, вероятность того, что весь комплекс работ будет выполнен не более чем за 35 дней, составляет 88,5%, в то время как вероятность его выполнения за 30 дней — всего 3,5%.
Для решения второй (по существу обратной) задачи прежде всего в табл. 5.2. найдем значение аргумента z, которое соответствует заданной вероятности 95%. В графе Ф(z) наиболее близкое значение (0,9545•100%) к ней соответствует z =1,9. В этой связи в формуле будем использовать именно это (не совсем точное) значение. Тогда получим:
Т=t_ож(L_кр)+z-S_Kp=33+1,9×1,66=36,2 дн.
Следовательно, максимальный срок выполнения всего комплекса работ при заданном уровне вероятности р=95% составляет 36,2 дня.