1.3. Методы расчета параметров сетевой модели
Для расчета параметров сетевых моделей применяют следующие три метода:
- метод вычислений непосредственно на сетевом графике;
- матричный метод,
- табличный метод.
Все эти методы основываются на формулах (1.6), … (1.10) и отличаются только процедурами вычислений.
Метод вычислений на сетевом графике. Предварительно каждый кружок, изображающий вершину графика (событие), делится на четыре сектора: в верхний сектор записывается номер события k, в левый – значение Тk (p) , в правый – Tk (n) , а в нижний – Rk = Tk (n) –Тk (p) (рис. 1.4).
Согласно формуле (1.6) ранний срок наступления данного события определяется как сумма раннего срока непосредственно предшествующего события и длины дуги (продолжительности работы), которая их соединяет. Если к событию подходят две или большее число дуг, то вычисляют указанные суммы для каждой из входящих дуг; максимальная из сумм и есть ранний срок наступления данного события, который записывается в левый сектор. Расчет ведется последовательно от исходящего события к завершающему.
Обратимся к рис. 1.4, на котором изображена та же сетевая модель, что и на рис. 1.3. В левый сектор исходящего события сразу записывается значение T0 (p) = 0. Далее находим: к событию 1 подходит одна дуга (0, 1), поэтому T1 (p) = 0+20 = 20; к событию 2 подходят две дуги (0, 2) и (1, 2), поэтому T2 (p) = max=45, и так далее Каждое вычисленное значение Tk (p) сразу записывается в соответствующий сектор.
Поздний срок наступления данного события согласно формуле (2.10) определяется как разность между поздним сроком непосредственно следующего события и длиной дуги, которая их соединяет. Если из события выходят две или большее число дуг, вычисляют указанные разности для каждой из выходящих дуг; минимальная из разностей и есть поздний срок наступления данного события, который записывается в правый сектор.
Поздний срок наступления завершающего события согласно формуле (1.9) равен раннему сроку, эту величину записывают в правый сектор и далее ведут расчет последовательно от завершающего события к исходящему.
Для нашего сетевого графика имеем T10 (n) = T10 (p) =305. Далее находим: из событий 9, 8, 7 выходит по одной дуге, поэтому T9 (n) = 305–100 =205; T8 (n) =205–90=115; T7 (n) =115–5=110;
из события 6 выходят две дуги (6, 7) и (6, 8), поэтому T6 (n) = min =105 и так далее.
После того, как рассчитаны все значения Tk (n) вычисляют резервы времени событий как разности между величинами, записанными в левых и правых секторах, и записывают их в нижние секторы. Остальные параметры сетевой модели вычисляют, по формулам (1.11)–(1.17). Результаты всех расчетов удобно представить в виде табл. 1.2.
Критический путь проходит через события, для которых Rj=0 (0–3–6–8–9–10).
При расчете параметров сетевой модели непосредственно на графике можно не нумеровать события так, чтобы выполнялось условие ij для любой дуги (i, j).
Матричный метод. Метод сводится к простым формальным операциям над величинами tij без необходимости обращаться к графику. Процедуру расчета рассмотрим на примере сетевой модели, изображенной на рис. 1.3.
Представим сетевой график в виде матрицы смежности, но вместо единиц запишем соответствующие значения tij. В результате получим табл. 1.3 (в таблицу также записаны величины Ti (p) и Tj (n) , которые еще нужно вычислить).
Таблица может быть составлена как по сетевому графику, так и по упорядоченному перечню событий и работ.
Правило определения раннего срока событий вытекает из выражения (1.6) и формулируется следующим образом: ранний срок события с номером j, равен сумме элемента матрицы tij с ранним сроком предшествующего события, причем, если предшествующих событий несколько, то берется максимальная из сумм, результат записывается в строку с номером i=j.
Так как ранний срок нулевого события равен нули, то сразу записывают в нулевую строку значение T0 (p) =0. Дальше последовательно просматриваются столбцы (последующие события), начиная с первого (j=1). Из матрицы видим, что событие 1 связано только с одним предшествующим событием, а именно – с нулевым, причем t0,1=20. Складываем t0,1 со значением Т0 (p) = 0, записанным в столбце Тi (p) по нулевой строке, а результат t0,1+T0 (p) = 20 записываем в первую строку в столбец Тi (p) . Это и будет значение T1 (p) .
Переходим ко второму столбцу (j=2). Событие 2 связано с двумя предшествующими событиями: 0 и 1, причем t0,2=45; t1,2=0. Составляем две суммы t0,2+ Т0 (p) = 45+0=45; t1,2+T1 (p) = 0+20 = 20 и большую записываем во вторую строку в столбец Тi (p) .
Рассмотрим еще восьмой столбец (j=8). Событие 8 связано с тремя предшествующими событиями 5, 6 и 7. Составляем суммы 10+85=95; 10+105=115; 5+105=110 и в восьмую строку в столбец Тi (p) записываем наибольшую, равную 115.
Правило вычисления позднего срока события следует из выражения (2.10) и формулируется следующим образом: поздний срок события с номером i, определяется путем вычитания элемента матрицы tij из позднего срока последующего события, причем, если последующих событий несколько, то берется минимальная из разностей; результат записывается в столбец с номером j=i.
Вычисления начинают с завершающего события и сразу записывают в столбец для j=N величину TN (n) = ТN (p) . В нашем случае в столбец для j=10 записывают Т10 (n) =305. Теперь просматриваем последовательно строки, начиная с N–1 (в нашем случае девятой). Из таблицы видно, что событие 9 связано с одним последующим событием 10, причем t9,10=100. Вычитаем согласно правилу из T10 (n) =305 величину t9,10=100 и разность, равную 205, записываем в девятый столбец в строку Тj (n) . Это и будет величина T9(n)=205.
Переходим к следующей, восьмой строке (i=8). Событие 8, как видно из матрицы, связано с одним последующим событием 9, причем t8,9=90. Составим разность 205–90=115 и результат запишем в восьмой столбец в строку Tj (n) .
Рассмотрим пятую строку. Событие 5 связано с двумя последующими событиями 7 и 8, а соответствующие элементы матрицы t5,7=0 и t5,8=10. Составляем две разности 110–0=110; 115–10=105 и меньшую из них запишем в пятый столбец в строку Tj (n) . Это и будет T5 (n) =105
Остальные параметры вычисляют по формулам (1.11) – (1.17), записывают их в табл. 1.2 и определяют критический путь.
Табличный метод в принципе не отличается от изложенных методов и преимуществ перед ними не имеет.
Теперь обратимся к сетевым моделям, у которых продолжительности работ являются случайными величинами. В этом случае продолжительность критического пути также является случайной величиной; сохраним за ней обозначение Ткр. Исходная информация таких моделей содержит сеть, законы распределения вероятностей величин tij (или вероятностные оценки aij, bij, mij) и (но не обязательно) директивный срок наступления завершающего события Тдир.
Основными задачами анализа этих моделей являются:
– определение среднего значения и дисперсии критического времени Tкр;
– определение закона распределения величины Tкр;
– определение таких сроков наступления событий, которые с заданной вероятностью не будут превышены;
– определение законов распределения для моментов наступления событий;
– определение вероятности прохождения критического пути через данную работу или совокупность работ.
Существующие аналитические методы решения перечисленных задач весьма громоздки и не нашли практического применения. Более широкое применение получил метод статистических испытаний.
Далее излагается практически удобный для расчетов метод вероятностной оценки наступления завершающего события. Необходимо подчеркнуть, что вероятностный анализ для завершающего события особенно важен, поскольку для продолжительности выполнения комплекса, как правило, устанавливается директивный срок и характер распределения случайного реального завершения комплекса работ по отношению к директивному сроку может существенно влиять на принятые решения при управлении выполнением комплекса.
Рассмотрим следующие задачи вероятностного анализа свершения завершающего события:
– определить вероятность того, что продолжительность критического пути (выполнения комплекса работ) Tкр лежит в заданных пределах
– определить вероятность того, что продолжительность критического пути не превысит заданный директивный срок;
– определить такой директивный срок, который с заданной вероятностью не будет превышен.
В методе приняты некоторые допущения, из которых выделим два основных:
1. Дисперсия Dкр величины критического времени зависит только от дисперсий работ, лежащих на критическом пути.
2. Величина Tкр распределена по нормальному закону. Это допущение основывается на предположении, что число работ критического пути достаточно велико и что продолжительности этих работ являются независимыми случайными величинами. Согласно центральной предельной теореме сумма достаточно большого числа независимых случайных величин, сравнимых по дисперсии, приближенно распределена по нормальному закону.
Расчет для всех задач начинается с вычисления математических ожиданий продолжительностей tij для всех работ комплекса по формуле (1.1) или (1.3). Затем, оперируя величинами как детерминированными:
– вычисляют продолжительность критического пути , представляющую собой математическое ожидание случайной величины Tкр;
– определяют критический путь Lкр;
– вычисляют дисперсии Dij продолжительностей работ, лежащих на критическом пути, по формуле (1.2) или (1.4);
– на основании известной теоремы, что дисперсия суммы независимых величин равна сумме дисперсий слагаемых, находят дисперсию продолжительности критического пути
Теперь при сделанных допущениях можно решить первую из перечисленных выше задач, а именно – определить вероятность того, что продолжительность критического пути лежит в заданных пределах : |
t – аргумент функции Лапласа ;
– математическое ожидание случайной величины Ткр;
Перейдем ко второй задаче. Согласно принятому допущению случайная величина Ткр распределена по нормальному закону, поэтому на основании правила трех сигм можно написать
Очевидно, что директивный срок должен лежать в тех же пределах:
Действительно, если то вероятность выполнения комплекса работ равна нулю; если же взять то без оснований будет растянут срок выполнения комплекса.
Кроме того, должно выполняться условие
Из неравенств (1.20), (1.21), (1.22) следует, что
Теперь можно найти решение второй задачи – определить вероятность того, что продолжительность критического пути не превысит заданный директивный срок. Искомую вероятность получим из выражения
Третью задачу можно решить следующим образом. С учетом заданной вероятности Р3 перепишем выражение (1.24) в виде
По известным величинам Р3, и кр можно определить с помощью таблиц функции Лапласа величину Тдир, удовлетворяющую уравнению (1.25).
Недостаток метода состоит в том, что анализ проводится лишь для одного критического пути. Но при случайных длительностях tij совокупность работ, составляющих критический путь, также является случайной и может не совпадать с совокупностью работ анализируемого критического пути. Возможность таких несовпадений возрастает, если имеются полные пути, продолжительность которых незначительно отличается от продолжительности критического пути. Поэтому для принятия эффективных решений необходимо иметь надежные вероятностные оценки длительности работ комплекса.