Книги по разным темам Pages:     | 1 |   ...   | 2 | 3 | 4 | 5 | 6 |   ...   | 26 |

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

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

Глава I. Оптимальные иерархические структуры.

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

з1. Общая задача об оптимальной иерархии.

1. Постановка задачи оптимизации.

В общем виде задача оптимизации иерархической структуры может быть поставлена следующим образом: необходимо найти arg min P(G), где - множество иерархических структур G (иерархий) с заданным на нем функционалом P : [0;+).

Условие P : [0;+) не ограничивает общности, так как любой функционал P : (-;+) можно привести к P с помощью монотонного преобразования области (-;+) в область [0;+). В дальнейшем считаем P неотрицательным. Функционал P назовем функционалом стоимости.

Вышеуказанная задача является общей задачей оптимизации.

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

Определение 1.1. Любая иерархическая структура G представляет собой ориентированный ациклический граф1.

То есть объект исследования - структура - представляет собой множество элементов с попарными связями между ними.

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

Поставленную задачу назовем задачей об оптимальной иерархии.

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

2. Звенья, субиерархии и слои.

Определение 1.2. Будем говорить, что вершина u V подчинена вершине v V в графе G = (V, E), если из u существует путь в v.2 Также будем говорить, что вершина v управляет вершиной u.

Под графом в данной работе подразумевается объект G = (V, E), состоящий из множества вершин V и множества ребер E. Множество вершин имеет произвольную природу, а множество ребер является множеством пар вершин:

E V V.

Вершина v подчинена самой себе, путь в данном случае состоит из одной вершины.

Определение 1.3. Для любой вершины v V через QG (v) = {u : u V,(u,v) E} обозначим множество вершин, из которых в графе G = (V, E) идут ребра в v, а через RG (v) = {u : u V,(v,u) E} - множество вершин, в которые в графе G идут ребра из v.1 Вершины из QG (v) назовем непосредственно подчиненными вершине v.

Определение 1.4. Для любого графа G = (V, E) множество вершин v V, для которых RG (v) =, обозначим через TG, а множество вершин v V, для которых QG (v) =, обозначим через NG. Вершины из TG назовем терминальными, а из NG - начальными.

Определение 1.5. Для любой вершины v V \ NG графа G = (V, E) звеном с вершиной v назовем граф ZG (v) = ({v} QG (v),{(u,v) : u QG (v)}).

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

Определение 1.6. Для любого графа G и вершины v TG \ NG назовем v -упрощением граф, полученный из G после удаления v и инцидентных ребер.

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

Определение 1.7. Субиерархией H графа G назовем граф, полученный после некоторой последовательности Если из контекста ясно, о каком графе идет речь, то нижний индекс G будем опускать.

упрощений графа G.1 Множество всех субиерархий графа G обозначим через H (G). Вырожденной субиерархией назовем граф H = (NG,), состоящий из изолированных начальных вершин графа G.

Содержательно субиерархия G представляет собой ФнижнююФ часть G, полученную после последовательного удаления неизолированных терминальных вершин. Сам граф G также считаем субиерархией2. Вырожденная субиерархия представляет собой набор изолированных (несвязанных) вершин, то есть фактически иерархия (подчинение) отсутствует.

Определение 1.8. Для графа G слоем G, соответствующим субиерархиям H1 = (V1, E1) H (G) и H = (V2, E2 ) H (G), H2 H1,3 назовем граф S = ZG (v).vV1\VБудем говорить, что субиерархия H1 разбивается на H2 и слой S.

Множество всех слоев графа G обозначим через S(G).

юбое звено является слоем. Для каждой субиерархии или слоя D = (V, E) и любых вершин u,v V можно определить подчиненность u и v, множества QD (v), ND, RD (v), TD, звенья ZD (v), v -упрощение так же, как в определениях 1.2-1.6. Ниже будем пользоваться этими обозначениями. Для пояснения понятий субиерархии, слоя и звена рассмотрим пример.

Граф G, изображенный на рис. 1.1, является также и субиерархией, обозначим ее через H1 = G = (V1, E1). После удаления терминальной вершины 7 и инцидентных ей ребер {5,7}, {6,7} (7-упрощения) получим субиерархию H2 = (V2, E2 ), которая обведена сплошным прямоугольником. Выполнено H2 H1, следовательно субиерархиям H1 и H2 соответствует некоторый После упрощения могут появиться новые терминальные вершины, которые также могут упрощаться на следующих шагах последовательности перестроений, приводящей к субиерархии.

В этом случае последовательность упрощений пуста.

Вложенность графов понимается в смысле вложенности множеств вершин и ребер.

Объединение графов понимается в смысле объединения множеств вершин и ребер.

слой S1 графа G. Имеем V1 \V2 = {7}, следовательно слой Sсовпадает со звеном ZG (7) = S1 = (VS1, ES1 ), где VS1 = {5,6,7}, ES1 = {{5,7},{6,7}}. На рисунке слой S1 выделен пунктирным прямоугольником. Граф G получается УнадстройкойФ слоя S1 над субиерархией H2, то есть G разбивается на H2 и S1.

7 S1 HH3 5 6 S2 S 1 2 3 Рис. 1.1. Примеры субиерархий и слоев.

Если из H2 удалить терминальную вершину 6 и инцидентные ребра {3,6}, {4,6}, то получим субиерархию H3 графа G, которая обведена на рисунке пунктирно-точечной ломаной линией.

Выполнено H3 H2, следовательно субиерархиям H2 и Hсоответствует слой S2 графа G, который обведен на рисунке кругом. Аналогично H3 H1, следовательно граф S3, обведенный точечной ломаной линией, также является слоем.

3. Аддитивные и локальные функционалы.

Определение 1.9. Пополнением множества назовем множество = H (G). Множеством частей назовем G множество = (H (G) S(G)).

G Таким образом, пополнение строится путем добавления к всевозможных субиерархий, а - путем добавления всевозможных субиерархий и слоев.

Определение 1.10. Функционал P назовем аддитивным, если его можно продолжить на множество P : [0;+) так, чтобы для любой субиерархии G и любого ее разбиения на субиерархию H и слой S выполнялось равенство P(G) = P(H ) + P(S), и стоимость любой вырожденной субиерархии H0 была нулевой: P(H0 ) = 0.

Поясним определение аддитивности на примере. Для этого рассмотрим множество = {G1,G2,G3,G4}, графы которого изображены на рис. 1.2. Граф G2 отличается от G1 тем, что добавлена вершина 7 и ей подчинены вершины 1 и 2. То есть Gразбивается на субиерархию G1 и слой ZG2 (7). Аддитивность предполагает, что при этом к стоимости P(G1) должна быть добавлена некоторая величина x = P(ZG2 (7)) = P(G2 ) - P(G1) для получения P(G2 ). Аналогично при добавлении к G1 слоя ZG3 (9) к P(G1) должна быть добавлена величина y = P(ZG3 (9)) = = P(G3) - P(G1) для получения P(G3). При добавлении к G1 слоев ZG2 (7) и ZG3 (9) получим граф G4. Соответственно, должно выполняться P(G4 ) = P(G1) + x + y. То есть, определив произвольным образом P(G1) 0, P(G2 ) P(G1), P(G3) P(G1), мы вынуждены положить P(G4 ) = P(G2 ) + P(G3) - P(G1) для того, чтобы функционал был аддитивным.

8 7 8 8 9 7 8 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 Рис. 1.2. Пример множества = {G1,G2,G3,G4}. Графы изображены слева направо.

Содержательно аддитивность означает, что при добавлении к графу Уверхней частиФ (слоя) к стоимости добавляется величина, зависящая только от самой Уверхней частиФ, а не от того, к какому графу она была добавлена. Если бы в вышеуказанном примере графы ZG2 (7) и ZG3 (9) принадлежали, то на функционал налагались бы требования P(G2 ) = P(G1) + P(ZG2 (7)), P(G3) = P(G1) + P(ZG3 (9)), P(G4) = P(G1) + P(ZG2 (7)) + P(ZG3 (9)), достаточные для аддитивности, и продолжать P на было бы не нужно. Но так как в общем случае не обладает ФполнотойФ, то есть не содержит Уобщие частиФ (субиерархии и слои) своих графов, определять аддитивность необходимо через продолжение функционала. При аддитивном функционале стоимость вырожденной субиерархии (состоящей из изолированных вершин) должна быть нулевой.

Определение 1.11. Функционал P назовем локальным, если для любого графа G = (V, E) выполнено P(G) = vV \NG P(ZG (v)),1 где величина P(ZG (v)) 0 однозначно определяется своим аргументов - звеном - и не зависит от графа G, в который звено входит.

Таким образом, локальный функционал можно представить в виде суммы значений стоимости отдельных звеньев. Если V \ NG =, то пустую сумму считаем нулевой.

Теорема 1.1. Функционал стоимости аддитивен тогда и только тогда, когда он локален.

Доказательство. Докажем, что из аддитивности следует локальность. По определению аддитивности продолжим функционал P на. Рассмотрим произвольную субиерархию G = (V, E) и неизолированную терминальную вершину v TG \ NG. Через H обозначим субиерархию, полученную из G после v -упрощения. Тогда G разбивается на H и слой S = ZG (v), следовательно P(G) = P(H ) + P(S) и P(ZG (v)) = P(S) = = P(G) - P(H ). Величина P(ZG (v)) = P(S) 0 определяется своим аргументом - звеном, а не графом, в который это звено входит.

Имеем P(G) = P(ZG (v)) + P(H ). Для H проделаем аналогичную операцию. И так далее. В итоге получим, что P(G) = vV / NG P(ZG (v)) + P(H0 ), где H0 - вырожденная субиерархия. По определению аддитивности P(H0 ) = 0.

Обратно, докажем, что из локальности следует аддитивность.

Рассмотрим произвольный граф G = (V, E) \. Для любой Здесь и далее одной и той же буквой P обозначается как стоимость графов из, так и стоимость отдельных звеньев, не входящих в.

вершины v V \ NG определена величина P(ZG (v)), так как звено ZG (v) входит по меньшей мере в один из графов. Положим по определению P(G) = vV \NG P(ZG (v)). Докажем, что построенное продолжение функционала является искомым. Рассмотрим произвольную субиерархию G = (V, E) и ее разбиение на субиерархию H = (VH, EH ) и слой S = (VS, ES ). Рассмотрим вершину v V \ NG. По определению 1.8, если v VH, то ZG (v) S (v VS \ NS ), иначе ZG (v) S (v VS \ NS ). Таким образом, каждое звено G входит либо в H, либо в S.

Следовательно, имеют место следующие равенства:

P(G) = NP(Z (v)) = vVH NH (v)) + vVS NS (v)) = P(S) + P(D) / P(ZH / P(ZS G vV / G Теорема доказана.

При доказательстве того, что из аддитивности следует локальность, равенство P(G) = P(H ) + P(S) (см. опр. 1.10) было использовано лишь для случая, когда S - звено, а не произвольный слой. Следовательно, такое определение аддитивности эквивалентно определению 1.10. Теорема 1.1 дает критерий возможности представления функционала в виде суммы стоимостей отдельных звеньев: при сложении частей стоимости должны складываться, стоимость вырожденных графов должна быть нулевой.

4. Подчиненные группы. Структурная эквивалентность.

Определение 1.12. Множеством элементов N = NG G назовем множество вершин, которые являются начальными хотя бы в одном из графов.1 Элементы будем обозначать через a N.

Определение 1.13. Множеством групп назовем множество F всевозможных непустых конечных подмножеств N. Группу g назовем элементарной, если она состоит из одного элемента:

Множество элементов может быть бесконечным.

g = {a}, a N. Мощностью группы g назовем количество содержащихся в ней элементов g.

Определение 1.14. Для любого графа G = (V, E) и любой вершины v V множество начальных вершин, подчиненных v, обозначим через gG (v) и назовем подчиненной группой.

Выполнено gG (v) NG N, то есть gG (v) F. Элементы можно интерпретировать как нижний уровень NG графа G, над которым надстраивается структура управления - иерархия. Каждая вершина v V управляет подчиненной группой элементов gG (v).

Начальная вершина v NG управляет элементарной группой gG (v) = {v}. Докажем вспомогательную лемму, которая понадобится в дальнейшем.

Pages:     | 1 |   ...   | 2 | 3 | 4 | 5 | 6 |   ...   | 26 |    Книги по разным темам