2.3 Алгоритм построения иерархического разбиения (дендограмм) задач управления сотс

Для построения иерархического разбиения множества задач А могут быть использо­ваны методы [2, 4, 8]соединительного иерархического кластерного анализа, общий алго­ритм которых может быть представлен в следующем виде:

Шаг 0. За исходное разбиение R₀ принять тривиальное разбиение множества задач A на n одноэлементных кластеров R₀ ={A_i, i=1, 2, …,n}, где A_i={a_i}. Положить начальный уровень раз­биения l=0.

Шаг 1. Для заданного уровня разбиений l найти наибольшее зна­чение (в частности, целевого или функционального) сходства между кластерами

. Значение сходства определяется с использованием отображений соответственного целевого и функционального сходства g и f.

Шаг 2. Объединить соответствующие кластеры с наибольшим сходс­твом в один кластер и образовать новое разбиение A_s=A_q  A_t. Положить l равное l+1.

Шаг 3. Проверить выполнение условия: card R_l=1 – мощность множества R_l (все задачи объединены в один кластер). Если оно выполняется, то завершить выполнение алгоритма. Если не выполняется, то пе­рейти на шаг 4.

Шаг 4. Пересчитать значения сходства для кластеров нового раз­биения по одной из приведенных ниже формул и перейти на шаг 1.

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

1. метод ближайшего соседа (сильной связи):

2. метод дальнего соседа (слабой связи):

3. метод простого среднего (средней связи):

Для построения иерархического разбиения по целевому сходству T_g в качестве  используется отображение g, а по функциональному сходству T_f – отображение f.

Пример.

Проиллюстрируем работу описанного алгоритма с использованием метода ближайшего соседа для следующих исходных данных:

А={а₁, а₂, а₃, а₄}, отображение целевого сходства g задано матрицей

Начальное разбиение R₀={{а₁}, {а₂}, {а₃}, {а₄}}. Максимальное сходство между А₃ и А₄ равно 0.9, что требует объединения указанных кластеров в один и построение нового разбиения R₁={{а₁}, {а₂}, {а_3, а₄}}. Произведем пересчет целевого сходства для нового разбиения методом ближайшего соседа:

.

Максимальное сходство между А₁={а₁} и А^’₃={ а_3, а₄} равно 0.8, что требует объединения указанных кластеров в один и построение нового разбиения R₂={{а₂}, {а₁, а_3, а₄}}. Произведем пересчет целевого сходства для нового разбиения методом ближайшего соседа:

.

Последнее объединение всех задач в исходное множество А={а₁, а₂, а₃, а₄} со значением целевого сходства 0.7.

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

2.4 Алгоритм определения типа организационной структуры управления

Для принятие решений по выбору типа ОСУ необходимо в пространстве иерархических разбиений построить функции расстояний, с использованием которых оценить структурное подобие дендрограмм разбиений T_f и T_g. Для этого воспользуемся следующими метриками в пространстве разбиений [5, 6, 7]:

(R_i,R_j)=2card(R_i  R_j) - card R_i - card R_j,

(R_i,R_j)=card R_i + card R_i - 2card (R_i  R_j).

Пересечение разбиений R_i  R_j определяется как множество кластеров, состоя­щих из элементов, принадлежащих одному кластеру как в R_i, так и в R_j. Объединение разбиений R_i  R_j определяется как множество кластеров, состоящих из общих элементов, принадлежащих либо одному кластеру в R_i, либо одному кластеру в R_j.

Используя введенные метрики, рассмотрим следующие функции расстояний в пространстве иерархических разбиений:

,

,

где k - количество уровней иерархических разбиений; _l, _l-1 - значения сходства, при которых происходит объединение класте­ров разбиений. Для данных отображений D1 и D2 существуют пре­дельные значения на множестве всех возможных дендрограмм. Ми­нимальные значения D1 и D2 равны 0, максимальное значение D1 равно n+1, а максимальное значение D2 равно

n-1, где n=card A.

Алгоритм определения типа организационной структуры управления состоит из следующих шагов:

Шаг 1. Используя алгоритм, приведенный в параграфе 3, построить дендограммы T_g и T_f.

Шаг 2. Произвести расчет расстояний .

Шаг3. Нахождение относительных показателей структурного подобия дендограмм T_g и T_f:

Шаг 4. Если S₁ и S₂ достаточно малы (например, S₁, S₂[0, 0.25]), то T_g и T_f структурно подобны  рекомендуется выбирать линейную структуру ОСУ.

Если S₁ и S₂ близки к 1 (например, S₁, S₂[0.75, 1]), то T_g и T_f структурно различны  рекомендуется выбирать матричную структуру ОСУ.

Если S₁, S₂[0.25, 0.75]), то имеет место неопределенность  рекомендуется выбирать смешанную структуру (ЛФ или ПЦ) ОСУ в зависимости от интенсивности проявления целевой или функциональной характеристик ОСУ.

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