Уравнение для циклов.

Требуется найти по известным .

Вероятность.

.

Это выражение нормализует эксцидентные вероятности так, что их сумма снова равна единице.

Математическое ожидание.

.

.

Для упрощения модели используется преобразование звезда-ячейка. Это преобразование является поэтапным процессом, позволяющим исключать вершину за вершиной. Каждая итерация уменьшает на единицу число вершин в блок-схеме. Каждая итерация состоит в формировании межэлементных связей, для чего используются рассмотренные уравнения. В результате применения такой процедуры преобразования к матрице N*N последняя преобразуется в матрицу (N – 1) * (N – 1). Процесс продолжается указанным образом, приводя к исключению всех вершин, кроме входных и выходных. Наиболее удобно в качестве очередной вершины, подлежащей исключению, рассматривать вершину, представленную последней строкой и самым правым столбцом матрицы. При этом входы и выходы необходимо пометить первым числами друг за другом.

Дисперсия.

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

Начнем с элемента, стоящего в первой строке правого столбца (смотри рисунок), и получим его комбинацию этого элемента (если он не нулевой) с каждым из элементов нижней строки. Так, элемент X объединяется с элементом Z, образуя XZ, а элемент XW образуется из X и W. Эти объединения выполняются с помощью уравнений межэлементных связей.

Преобразование звезда-ячейка состоит из следующих этапов:

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

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

2. Заполнить матрицу. Ее элемент (k, j) содержит информацию о вероятности, математическом ожидании и дисперсии (если требуется) для (k, j) –го ребра. Проверить сумму вероятностей для каждой строки. Каждая такая сумма должна равняться единице, за исключением выходов, для которых она должна равняться нулю.

3. Исключить все параллельные ребра, используя уравнения преобразования параллельных ребер.

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

5. Сформировать взаимные элементы для последней вершины.

6. Повторять этапы 3, 4, 5 до тех пор, пока не останутся только ершины соответствующие входам и выходам.

Рассмотрим пример, приведенный выше.

Здесь имеется пара параллельных ребер, идущих от вершины 1 к вершине 3, и цикл у вершины 3. Рассматривая вначале вносимый параллельный элемент можно записать:

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

Теперь рассмотрим цикл у вершины 3. Необходимо изменить два ребра: ребро от вершины 3 к вершине 2 и ребро от вершины 3 к вершине 4. Применяя уравнение цикла к ребру (3, 2), получим:

Для ребра (3, 4) получим:

Матрица примет вид:

Применяем уравнение цикла к циклу у вершины 1, и подставляя:

получим

Применяем уравнение цикла еще раз и получаем окончательный результат:

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

Инцидентное преобразование указывает величину затрат при перемещении от начальных вершин (входов) к остальным вершинам. Эксцидентное преобразование указывает величину затрат при перемещении от рассматриваемой вершины к выходу.

Предположим теперь, что не вычеркиваются элементы ни в строках, ни в столбцах. Можно показать, что результат получается такой же, как при умножении матрицы на саму себя. Далее можно показать, что элементы матрицы, получающиеся при возведении матрицы в N – ю степень (N – число вершин), соответствуют вероятности и ожидаемому значению параметров комбинации всех путей, ведущих из вершины k в вершину j. Также можно показать, что степень p матрицы, полученная таким образом, имеет в качестве элементов вероятность и математическое ожидание параметров, отвечающих всем путям длины p или менее, где длина пути измеряется числом, входящих в нее ребер.

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