Исследования структуры бизнес процесса
на основании графанализ. Метода использования.
Цель работы: выполнение анализа структуры
системы с испльзованием метода графанализатора.
Эффективность любого экономического
процесса зависит от эффективности работы
элементов.
Существует несколько методов по описанию
взаимосвзяи элементов внутри системы.
1)аналитический
2)статистический
3) на основании теории граф.
Согласно теории граф каждый этап бизнес
процесса представляет вертикальный граф.
Взаимосвязь между подразделами описывается
дугами.
При выполнении практических заданий
нужно привести квадратную матрицу.
Практическую часть второй работы мы
делаем с помощью программы графоанализатора.
Графоанализатор
– визуальная среда для работы с графами.
Графоанализатор не только предоставляет
возможность создавать и обрабатывать
графы, но визуально отображать результаты
работы алгоритмов. Среда поддерживает
работу с ориентированными и простыми
графами, нагруженными и ненагруженными.
Программа реализует множество алгоритмов
для обработки графов, начиная от поиска
пути и заканчивая проверкой на планарность.
Графоанализатор – это незаменимый помощник
для решения задач с помощью графов.
Схема жизненного цикла в программе графоанализатора
выглядит следующим образом:
Для редактирования графа можно использовать
различные методы: визуально редактировать
граф или редактировать матрицу смежности
графа.
Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.
Т.е по строкам и столбцам откладываются
номера вершин. В случае если две вершины
графоанализатора связаны дугой, то в
матрице смежности на пересечении номеров
вершин откладывается вес дуги. В рассматриваемой
мной схеме вершины 2 и 3 связаны дугой
весом 5 дней. Значит в матрице смежности
в элементе a3,2 будет стоять цифра 5.
Иногда, особенно в случае неориентированного
графа, петля (ребро из i-й вершины в саму себя)
считается за два ребра, то есть значение
диагонального элемента aii в этом случае равно удвоенному
числу петель вокруг i-й вершины.
Матрица смежности простого графа (не
содержащего петель и кратных ребер) является
бинарной матрицей и содержит нули на
главной диагонали.
Построенная мной матрица смежности
является бинарной.
А теперь находим кратчайший путь, используя один из методов (Форда-Беллмана,
Дейкстры или Флойда). После поиска кратчайшего
пути мы увидим оптимальный путь.
1)Алгоритм Форда-Белмана.
Матрица в рассматриваемой мной граве
по алгоритму Флойда-Белмана выглядит
следующим образом:
Вершины 13 достижима из вершины 1 за 24.
__| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15
|
1| 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0
2| 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1
3| x 6 6 6
6 6 6 6 6
6 6 6 6 6
6
4| x x 7 7
7 7 7 7 7
7 7 7 7 7
7
5| x x x 8
8 8 8 8 8
8 8 8 8 8
8
6| x x x x
9 9 9 9 9
9 9 9 9 9
9
7| x x x x
9 9 9 9 9
9 9 9 9 9
9
8| x x x x
9 9 9 9 9
9 9 9 9 9
9
9| x x x x x
11 11 11 11 11 11 11 11
11 11
10| x x x x
x x 16 16 16 16 16
16 16 16 16
11| x x x x
x x 16 16 16 16 16
16 16 16 16
12| x x x x
x x x 17 17 17
17 17 17 17 17
13| x x x x
x x x x 24 24
24 24 24 24 24
14| x x x x
x x x x 24 24
24 24 24 24 24
15| x x x x
x x x x 24 24
24 24 24 24 24
2)Алгоритм Флойда-Уоршолла.
Алгоритм находит все кратчайшие расстояния
в графе.
Алгоритм основан на том предположении,
что расстояние между вершинами А и Б,
может быть больше, чем расстояние от А
до В + от В до Б.
Матрица в рассматриваемой мной граве
по алгоритму Флойда выглядит следующим
образом:
Вершины 13 достижима из вершины 1 длинна
пути 24.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 |
1| 0 1 6 7
8 9 9 9 11 16
16 17 24 24 24
2| x 0 5 6
7 8 8 8 10 15
15 16 23 23 23
3| x x 0 1
2 3 3 3 5 10
10 11 18 18 18
4| x x x 0
1 2 2 2 4
9 9 10 17 17 17
5| x x x x
0 1 1 1 3
8 8 9 16 16 16
6| x x x x
x 0 4 8 10 15
15 16 23 23 23
7| x x x x
x x 0 4 6 11
11 12 19 19 19
8| x x x x
x x x 0 2
7 7 8 15 15 15
9| x x x x
x x x x 0
5 5 6 13 13 13
10| x x x x
x x x x x
0 x 5 12 12 12
11| x x x x
x x x x x
x 0 1 8 8
8
12| x x x x
x x x x x
x x 0 7 7
7
13| x x x x
x x x x x
x x x 0 x
x
14| x x x x
x x x x x
x x x x 0
x
15| x x x x
x x x x x
x x x x x
0
3)Алгоритм Дейкстры .
Служит для поиска кратчайшего пути в
нагруженном графе.
На каждой шаге алгоритм обновляет расстояние
от начальной вершины до всех остальных.
Сначала рассматриваются вершины соседние
с начальной, потом соседние с соседней.
Матрица в рассматриваемой мной граве
по алгоритму Флойда выглядит следующим
образом:
Вершины 13 достижима из вершины 1 за 24
Достижимость вершин из вершины 1
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15
|
| 0| 1| 6| 7| 8| 9| 9|
9| 11| 16| 16| 17| 24| 24| 24|
Таким образом все алгоритмы по нахождению
кратчайшего пути (в данном случае путь
от соц.заказа до открытия ресторана) занимают
24 дня. После проведенного мной не сложного
анализа я могу сделать вывод, что этот
путь действительно является кротчайшим.