МЕТОДЫ РАСЧЕТА ПАРАМЕТРОВ СЕТЕВОЙ МОДЕЛИ

Для расчета параметров сетевых моделей применяют следую­щие три метода:

– метод вычислений непосредственно на сетевом графике;

– матричный метод,

– табличный метод.

Все эти методы основываются на формулах (1.6), … (1.10) и от­личаются только процедурами вычислений.

Метод вычислений на сетевом графике. Предварительно каж­дый кружок, изображающий вершину графика (событие), делится на четыре сектора: в верхний сектор записывается номер собы­тия k, в левый – значение Т_k^(p), в правый – T_k⁽ⁿ⁾, а в нижний – R_k = T_k⁽ⁿ⁾ – Т_k^(p) (рис. 1.4).

Согласно формуле (1.6) ранний срок наступления данного со­бытия определяется как сумма раннего срока непосредственно предшествующего события и длины дуги (продолжительности ра­боты), которая их соединяет. Если к событию подходят две или большее число дуг, то вычисляют указанные суммы для каждой из входящих дуг; максимальная из сумм и есть ранний срок на­ступления данного события, который записывается в левый сектор. Расчет ведется последовательно от исходящего события к завер­шающему.

Обратимся к рис. 1.4, на котором изображена та же сетевая мо­дель, что и на рис. 1.3. В левый сектор исходящего события сразу записывается значение T ₀ ^(p) = 0. Далее находим: к событию 1 под­ходит одна дуга (0, 1), поэтому T ₁ ^(p) = 0+20 = 20; к событию 2 под­ходят две дуги (0, 2) и (1, 2), поэтому T ₂ ^(p) = max{0+45; 20+0}=45, и так далее Каждое вычисленное значение T_k^(p) сразу записывает­ся в соответствующий сектор.

Поздний срок наступления данного события согласно формуле (2.10) определяется как разность между поздним сроком непосред­ственно следующего события и длиной дуги, которая их соединяет. Если из события выходят две или большее число дуг, вычисляют указанные разности для каждой из выходящих дуг; минимальная из разностей и есть поздний срок наступления данного события, который записывается в правый сектор.

Поздний срок наступления завершающего события согласно формуле (1.9) равен раннему сроку, эту величину записывают в правый сектор и далее ведут расчет последовательно от завершаю­щего события к исходящему.

Для нашего сетевого графика имеем T ₁₀ ⁽ⁿ⁾ = T ₁₀ ^(p) =305. Далее находим: из событий 9, 8, 7 выходит по одной дуге, поэтому T ₉ ⁽ⁿ⁾ = 305–100 =205; T ₈ ⁽ⁿ⁾ =205–90=115; T ₇ ⁽ⁿ⁾ =115–5=110;

из со­бытия 6 выходят две дуги (6, 7) и (6, 8), поэтому T ₆ ⁽ⁿ⁾ = min{110–0; 115–10} =105 и так далее.

После того, как рассчитаны все значения T_k⁽ⁿ⁾ вычисляют ре­зервы времени событий как разности между величинами, записан­ными в левых и правых секторах, и записывают их в нижние сек­торы. Остальные параметры сетевой модели вычисляют, по форму­лам (1.11)–(1.17). Результаты всех расчетов удобно представить в виде табл. 1.2.

Таблица 1.2.

Началь­ное со­бытие i	Конеч­ное со­бытие j	Tij			Rij
					0

Критический путь проходит через события, для которых R_j =0 (0–3–6–8–9–10).

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

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

Представим сетевой график в виде матрицы смежности, но вместо единиц запишем соответствующие значения t_ij. В результате получим табл. 1.3 (в таблицу также записаны величины T_i^(p) и T_j⁽ⁿ⁾, которые еще нужно вычислить).

Таблица 1.3

j i

Ранний срок

Поздний срок

Таблица может быть составлена как по сетевому графику, так и по упорядоченному перечню событий и работ.

Правило определения раннего срока событий вытекает из вы­ражения (1.6) и формулируется следующим образом: ранний срок события с номером j, равен сумме элемента матрицы t_ij с ранним сроком предшествующего события, причем, если предшест­вующих событий несколько, то берется максимальная из сумм, ре­зультат записывается в строку с номером i=j.

Так как ранний срок нулевого события равен нули, то сразу записывают в нулевую строку значение T ₀ ^(p) = 0. Дальше последо­вательно просматриваются столбцы (последующие события), начи­ная с первого (j =1). Из матрицы видим, что событие 1 связано только с одним предшествующим событием, а именно – с нулевым, причем t _0,1=20. Складываем t _0,1 со значением Т ₀ ^(p) = 0, записан­ным в столбце Т_i^(p) по нулевой строке, а результат t _0,1+ T ₀ ^(p) = 20 записываем в первую строку в столбец Т_i^(p). Это и будет значе­ние T ₁ ^(p).

Переходим ко второму столбцу (j =2). Событие 2 связано с двумя предшествующими событиями: 0 и 1, причем t _0,2=45; t _1,2=0. Составляем две суммы t _0,2+ Т ₀ ^(p) = 45+0=45; t _1,2 +T ₁ ^(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, определяется путем вычитания элемента матрицы t_ij из позднего срока последующего события, причем, если последующих событий несколько, то берется мини­мальная из разностей; результат записывается в столбец с номе­ром j = i.

Вычисления начинают с завершающего события и сразу запи­сывают в столбец для j=N величину T_N⁽ⁿ⁾= Т_N^(p). В нашем случае в столбец для j =10 записывают Т ₁₀ ⁽ⁿ⁾ =305. Теперь просматриваем последовательно строки, начиная с N– 1 (в нашем случае девя­той). Из таблицы видно, что событие 9 связано с одним последую­щим событием 10, причем t _9,10=100. Вычитаем согласно правилу из T ₁₀ ⁽ⁿ⁾ =305 величину t _9,10=100 и разность, равную 205, записы­ваем в девятый столбец в строку Т_j⁽ⁿ⁾. Это и будет величина T _{9 (n)} =205.

Переходим к следующей, восьмой строке (i =8). Событие 8, как видно из матрицы, связано с одним последующим событием 9, причем t _8,9=90. Составим разность 205–90=115 и результат за­пишем в восьмой столбец в строку T_j⁽ⁿ⁾.

Рассмотрим пятую строку. Событие 5 связано с двумя после­дующими событиями 7 и 8, а соответствующие элементы матрицы t _5,7=0 и t _5,8=10. Составляем две разности 110–0=110; 115–10=105 и меньшую из них за­пишем в пятый столбец в строку T_j⁽ⁿ⁾. Это и будет T ₅ ⁽ⁿ⁾ =105

Остальные параметры вычисляют по формулам (1.11) – (1.17), записывают их в табл. 1.2 и определяют критический путь.

Табличный метод в принципе не отличается от изложенных ме­тодов и преимуществ перед ними не имеет.

Теперь обратимся к сетевым моделям, у которых продолжи­тельности работ являются случайными величинами. В этом случае продолжительность критического пути также является случайной величиной; сохраним за ней обозначение Т_кр. Исходная инфор­мация таких моделей содержит сеть, законы распределения веро­ятностей величин t_ij (или вероятностные оценки a_ij, b_ij, m_ij) и (но не обязательно) директивный срок наступления завершающего события Т_дир.

Основными задачами анализа этих моделей являются:

– определение среднего значения и дисперсии критического времени T_кр;

– определение закона распределения величины T_кр;

– определение таких сроков наступления событий, которые с заданной вероятностью не будут превышены;

– определение законов распределения для моментов наступле­ния событий;

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

Существующие аналитические методы решения перечисленных задач весьма громоздки и не нашли практического применения. Более широкое применение получил метод статистических испы­таний.

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

Рассмотрим следующие задачи вероятностного анализа сверше­ния завершающего события:

– определить вероятность того, что продолжительность крити­ческого пути (выполнения комплекса работ) T_кр лежит в задан­ных пределах

– определить вероятность того, что продолжительность крити­ческого пути не превысит заданный директивный срок;

– определить такой директивный срок, который с заданной ве­роятностью не будет превышен.

В методе приняты некоторые допущения, из которых выделим два основных:

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

2. Величина T_кр распределена по нормальному закону. Это допущение основывается на предположении, что число работ крити­ческого пути достаточно велико и что продолжительности этих работ являются независимыми случайными величинами. Согласно центральной предельной теореме сумма достаточно большого числа независимых случайных величин, сравнимых по дисперсии, при­ближенно распределена по нормальному закону.

Расчет для всех задач начинается с вычисления математических ожиданий продолжительностей t_ij для всех работ комплекса по формуле (1.1) или (1.3). Затем, оперируя величинами как детерминированными:

– вычисляют продолжительность критического пути , представляющую собой математическое ожидание случайной величины T_кр;

– определяют критический путь L_кр;

– вычисляют дисперсии D_ij продолжительностей работ, лежащих на критическом пути, по формуле (1.2) или (1.4);

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

. (1.18)

Теперь при сделанных допущениях можно решить первую из перечисленных выше задач, а именно – определить вероятностьтого, что продолжительность критического пути лежит в заданных пределах : |

, (1.19)

где – функция Лапласа;

t – аргумент функции Лапласа;

– математическое ожидание случайной величины Т_кр;

.

Перейдем ко второй задаче. Согласно принятому допущению случайная величина Т_кр распределена по нормальному закону, по­этому на основании правила трех сигм можно написать

. (1.20)

Очевидно, что директивный срок должен лежать в тех же пре­делах:

. (1.21)

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

Кроме того, должно выполняться условие

Т_кр < Т_дир. (1.22)

Из неравенств (1.20), (1.21), (1.22) следует, что

(1.23)

Теперь можно найти решение второй задачи – определить ве­роятность того, что продолжительность критического пути не пре­высит заданный директивный срок. Искомую вероятность получим из выражения

(1.24)

так как Ф(3) =0,9973.

Третью задачу можно решить следующим образом. С учетом заданной вероятности Р₃ перепишем выражение (1.24) в виде

. (1.25)

По известным величинам Р ₃, и s_кр можно определить с помощью таблиц функции Лапласа величину Т_дир, удовлетворяю­щую уравнению (1.25).

Недостаток метода состоит в том, что анализ проводится лишь для одного критического пути. Но при случайных длительностях t_ij совокупность работ, составляющих критический путь, также является случайной и может не совпадать с совокупностью работ анализируемого критического пути. Возможность таких несовпаде­ний возрастает, если имеются полные пути, продолжительность ко­торых незначительно отличается от продолжительности критиче­ского пути. Поэтому для принятия эффективных решений необхо­димо иметь надежные вероятностные оценки длительности работ комплекса.

Вероятностные модели систем

2.1. ОРИЕНТИРОВАННЫЙ ГРАФ СОСТОЯНИЯ СИСТЕМЫ.
МАРКОВСКИЕ ПРОЦЕССЫ.

Вероятностные (стохастические) модели используются для исследования таких систем, процесс функционирования которых определяется случайными факторами. Учет случайных факторов является обязательным при исследовании процессов применения, эксплуатации, ремонта и обеспечения технических комплексов, при оценке их эффективности, разработке автоматизированных систем управления, обосновании технических требований к системам и так далее.

Мощным средством разработки и исследования вероятностных моделей является аппарат теории марковских случайных процессов в развитие которого внесли большой вклад русские и советсткие ученые А.А.Марков, А.Я.Хинчин, А.Н.Колмогоров, Б.В.Гнеденко, И.Н.Коваленко, Н.П.Бусленко, Ю.В.Прохоров и многие другие.

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

Множество S ={ S ₀, S ₁, S ₂, …} возможных состояний системы и множество возможных ее переходов из одного состояния в другое удобно представлять в виде ориентированнного графа (рис 2.1.), вершинам которого соответствуют состояния системы, а дугам – возможные переходы, причем направление дуги указывает, из какого состояния и в какое возможен переход системы. Процесс функционирования системы в данном случае можно представить как случайное перемещение (блуждание) точки, изображающей систему, по графу состояний. Характерной особенностью стохастических систем является то, что для любого момента времени t нельзя однозначно указать, в каком из состояний находится система, а можно определить только распределение вероятностей для состояний, то есть определить значения вероятностей P_k (t) того, что в момент времени система находится в состоянии S_k..

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

, (2.1)

где N +1 – число возможных состояний системы.

Совокупность функциональных соотношений и логических условий, позволяющих вычислить значение вероятностей P_k (t) для k=0,N, и представляет собой вероятностную модель системы.

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

Множество S можно определить, во-первых, как множество допустимых комбинаций возможных состояний элементов системы. Важным при этом является анализ и учет взаимосвязей между элементами системы.

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

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

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

Поток – это последовательность однородных событий, следующих одно за другим в случайные моменты времени (например, поток отказов технических систем, поток сообщений, поступающих в АСУ, и тому подобные).

Наиболее важными свойствами потоков являются: стационарность, ординарность и отсутствие последействия.

Стационарность потока означает, что его вероятностные характеристики не зависят от времени. Важнейшей характеристикой потока является его интенсивность l – среднее число событий в единице времени. Для стационарного потока l=const, а для нестационарного l=l (t) – функция времени.

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

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

Поток событий, обладающий всеми тремя свойствами, называется простейшим или стационарным пуассоновским потоком. Число событий пуассоновского потока, попадающих на любой участок, распределено по закону Пуассона, то есть вероятность попадания ровно k событий на участок (t ₀, t ₀+ t)

(2.2)

где а – среднее число событий, приходящихся на участок t. Для простейшего потока а = lt, а для нестационарного пуассоновского

.

Определим закон распределения F (t) интервала времени между событиями. Так как F (t) – вероятность того, что на участок длительности t попадает хотя бы одно событие, то

F (t)= 1– P (0)=1–e^{- lt} (2.3)

f (t) = F’ (t)= l e^{- lt}, t ³ 0.

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

Математическое ожидание M_t (средняя длительность интервала между событиями), дисперсия D_t и среднее квадратическое отклонение s_t случайной величины, распределенной по показательному закону, определяются соотношениями

. (2.4)

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

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

Из сказанного следует: если переход системы из состояния S_i в состояние S_j происходит под воздействием L простейших потоков интенсивности , то

.

Таким образом, каждой дуге (i,j) графа состояний можно поставить в соответствие интенсивность суммарного потока событий l_ij. Такой граф называется размеченным, и ему соответствует квадратная матрица интенсивностей переходов порядка (N +1, N +1), причем . Для размеченного графа состояний (рис 2.1) имеем

.

Можно доказать следующее утверждение: если все потоки событий, переводящие систему из состояния в состояние, пуассоновские, то процесс функционирования системы представляет собой марковский процесс с непрерывным временем. Отличительной особенностью марковского процесса является то, что вероятность любого состояния системы в будущем зависит только от ее состояния в настоящем и не зависит от того, когда и каким образом система пришла в это состояние. Понятие «марковский процесс» ввел советский математик А.Н.Колмогоров в честь русского ученого А.А.Маркова (1856–1922), внесшего большой вклад в теорию случайных процессов.

2.2. Уравнения Колмогорова для вероятностей
состояний

Введем обозначения:

P_k (t) – вероятность того, что система в момент времени t находится в состоянии S_k (k =0, 1, 2, …, N);

P_ik (D t) – условная вероятность того, что система, будучи в момент t в состоянии S_i, за время перейдет в состояние S_k (k ¹ i).

Так как P_ik (D t) – вероятность появления хотя бы одного события за время D t, то

,

где l_ik – интенсивность потока событий, под воздействием которого система переходит из состояния S_i в состояние S_k.

Разлагая показательную функцию в ряд Тейлора, имеем:

. (2.5)

Пусть в момент времени t система находится в одном из возможных состояний. Определим вероятность P_k (t+) того, что в момент t+Dt она будет находиться в состоянии S_k (k =0,1,…, N).

Предположим, что за время Dt система может только один раз изменить свое состояние. Это означает, что система может попасть в состояние S_k двумя способами.

1. В момент t система находилась в одном из состояний S_i (i¹k), которое соединено дугой (i, k) с состоянием S_k , а за время Dt перешла в состояние S_k . Вероятность этого события
,
где – множество дуг, заходящих в вершину S_k . Например, для состояния S ₁ (рис. 2.1) ,
P ₁= P ₀(t) P ₀₁(Dt)+ P ₂(t) P ₂₁(Dt).

2. В момент t система находилась в состоянии S_k и за время Dt не вышла из него ни по одной из дуг, исходящих из вершины S_k.. Вероятность этого события
,
где – множество дуг, исходящих из вершины S_k. Для состояния S ₁ (рис. 2.1) ,
P ₂= P ₁(t)[1– P ₁₀(Dt)– P ₁₂(Dt)],
где [ P ₁₀(Dt)+ P ₁₂(Dt)] – вероятность того, что система, будучи в момент t в состоянии S ₁, за время Dt перейдет из него в состояние S ₀ или S ₂.

Так как оба способа несовместны, то

(2.6)

Перенесем P_k (t) в левую часть и разделим все члены уравнения (2.6) на Dt, получим

.

В результате предельного перехода при Dt ®0 с учетом выражения (2.5) получим систему дифференциальных уравнений Колмогорова

(2.7)

Уравнение (2.7) в отличие от уравнения (2.6) является точным, так как члены, соответствующие двум и более переходам системы за время Dt и опущенные в выражении (2.6), в результате предельного перехода обращаются в нуль. Действительно, пусть за время Dt система может перейти из состояния S_i в состояние S_k через состояние S_j. Условная вероятность этого события с учетом формулы (2.5)

При записи правой части уравнения (2.7) целесообразно руководствоваться мнемоническим правилом: «то, что втекает, прибавляется, а что вытекает – вычитается».

Для рассматриваемого примера (рис 2.1) уравнения Колмогорова имеют вид (читателю рекомендуется записать их самостоятельно)

Интегрируя систему линейных дифференциальных уравнений (2.7) с учетом условия нормировки (2.1) при заданных начальных условиях (например, P_k (0)=1, а для всех i ¹ k P_i (0)=0 – в начальный момент система находится в состоянии S_k), можно определить распределение для вероятностей состояний системы в любой момент времени.

На практике часто наибольший интерес представляет поведение системы в установившемся режиме при t ®¥. Здесь сразу же возникает вопрос, как поведут себя вероятности P_k (t) при t ®¥, стремятся ли они к каким либо пределам, существует ли в системе некоторый установившийся (стационарный) режим.

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

Предельная вероятность P_k – это средняя доля времени, в течение которого система находится в состоянии S_k. Если, например, P_k =0,3, то это означает, что в состоянии S_k система времени ее функционирования.

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

(2.8)

Так как система (2.8) однородна, то при вычислении вероятностей P_k одно из уравнений (2.8) заменяют нормировочным условием

.

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

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: