Человеческий фактор. Том 3. Часть 1 - Сальвенди Г.
ISBN 5-03-001815-8
Скачать (прямая ссылка):
Стохастические сетевые модели
249
A. Процессы, которые еще не начинались.
B. Процессы, которые уже завершились.
C. Процессы, которые выполняются.
При изменении выбранного момента времени подмножества А, В, С будут изменяться, поэтому удобно идентифицировать их с помощью соответствующего временного индекса, например Л», Bh С,. Если в момент i задано разбиение на подмножества Л;,
B,, Ci, то говорят, что сеть находится в состоянии s;.
Для получения разбиения на множества Лг, Bi, Ci существуют компьютерные программы [24], однако в некоторых достаточно простых случаях такое разбиение можно провести вручную, пользуясь только графом сети. Для примера возьмем сеть, изображенную на рис. 4.12. Визуальный анализ показывает, что в ней имеется всего пять различных состояний, определяемых следующими разбиениями (результат для множества Л не приводится, так как он однозначно определяется множествами В и С):
Sj (fij — 0, С^ = {хj, лга}),
*8 (^2 = ^2 =
(^з = ^3={-^i})>
«»(?* = К. *2}» с4={*з));
®б(^5=={^'1> *^2» **}. ^5=®)'
Эти состояния более удобно представить в виде ДПСП (рис. 4.12,6). Для этого поместим выполняющиеся процессы из
C, в верхнюю клетку каждого состояния, а завершившиеся процессы из В, — в нижнюю. Переход из состояния s,- в состояние S/ за один шаг возможен тогда и только тогда, когда завершение ровно одного процесса из подмножества текущих состояния s, дает разбиение, соответствующее состоянию S/. Так, возможен переход из состояния Si в состояние s2, поскольку из рис. 4.12, а ясно, что процесс х\ может завершиться раньше, чем процесс Х2, и что никакие процессы не могут начаться раньше, чем завершатся процессы х\, х2. Точно так же возможен переход из состояния Si в состояние s3, поскольку из рис. 4.12, а ясно, что процесс х2 может завершиться раньше, чем процесс Х\. Переходы из состояния в состояние удобно представлять на ДПСП. Так, два рассмотренных перехода представляются направленными дугами, ведущими из вершины S\ в вершины s2 и s3. Для большей наглядности диаграммы каждая дуга между парой состояний помечается тем процессом, выполнение которого определяет переход. Поскольку предполагается, что длительности процессов взаимно независимы, случаем одновременного завершения более чем одного процесса можно пренебречь.
250 Глава 4
Поскольку рассматриваются стохастические сети, множество состояний, доступных в некотором эксперименте, является пере* менным. Так, имеются ровно две последовательности состояний, порождаемых сетью (рис. 4.12,6). Если длительность х\ меньше длительности Х2, получается последовательность состояний (sx, S2, s4, S5): выполняются процессы xt и х2 (состояниеsi); процесс xi завершен (состояние s2); процесс х2 завершен и начинается процесс х3 (состояние s4); процесс х3 завершен (состояние s5). Наоборот, если длительность хх больше длительности х2, получается последовательность состояний (sb S3, S4, s5). Последовательность состояний также можно представлять с помощью ДПСП. Будем называть состояние S/ непосредственно следующим за состоянием S;, если на диаграмме имеется соединяющая их дуга. В этом случае st- называется непосредственным предшественником Sf. Определим начальное состояние как состояние без непосредственных предшественников и обозначим его через Si; определим конечное состояние как состояние без непосредственно следующих за ним и обозначим его sn„; где «о — число состояний на диаграмме. Определим траекторию на диаграмме как набор состояний — o(=(s;i, ..., s,A), где s,- =su Sjj— непосредственный предшественник s;/+1 и что s,A =Sn0. Определенную таким образом траекторию назовем полной последовательностью состояний. Так, на диаграмме рис. 4.12,6 имеются две траектории, задаваемые последовательностями состояний Oi = (si, s2, s5) и 02= (si, S3, s5). Отметим, что нумерация путей является произвольной.
Теперь можно вычислить ожидаемое время реакции Е(Т). Пусть ei—мощность подмножества завершившихся процессов состояния Si. Пусть ei — вектор-столбец размерностью 1 Х«о, все элементы которого, кроме элемента в строке г, равны нулю» а элемент в строке г равен 1. Тогда имеет место
Теорема 1
По—I
?[Л= 2 c-WiPhtei.
i=l
Иными словами, ожидаемое время реакции равно сумме произведений величин сг1 и где сг]—условная ожидаемая длительность состояния s,- при условии, что состояние s,- достигнуто, a e/Pbiei — вероятность достижения состояния s,-. Подробное доказательство теоремы приведено в работе [19]. Заметим только, что векторы ei (вектор-строка) и е/ (вектор-столбец} служат для выбора элемента матрицы, расположенного в строке 1 и столбце 1, возведенного в степень
Стохастические сетевые модели
251
Поясним смысл теоремы I на примере. Рассмотрим диаграмму рис. 4.12,6, полагая ^i=X2=l, Яз = 4. Тогда получим Cj = 'kl -J- Х% = 2; с2 = Я, 2 = 1', сз = = ^ > С4 = = 4.
Обозначим через а последовательность индексов состояний вдоль некоторой траектории о,- на диаграмме, например, а = = (1, 2, 4, 5), причем sai = sb sa^s2, sa4 = s4, s„b=s5. Аналогично поступим и с траекторией о2. Будем идентифицировать траекторию с множеством а, хотя оно является множеством индексов состояний, а не множеством состояний.
