Содержание к диссертации
Введение
Г лава I. Оптимальные иерархические структуры 14
1. Общая задача об оптимальной иерархии 14
1. Постановка задачи оптимизации 14
2. Звенья, субиерархии и слои 15
3. Аддитивные и локальные функционалы 16
4. Подчиненные группы. Структурная эквивалентность 18
5. Простые и структурные функционалы 20
2. Редукция общей задачи к задаче об оптимальной организации 22
1. Графы организации 22
2. Оптимальная организация набора групп 23
3. Виды организаций 25
4. Деревья организации 26
3. Вид оптимальной организации для различных классов структурного функционала.. 27
1. Монотонные функционалы 27
2. Выпуклые и вогнутые функционалы 28
3. Организации без повторяющихся групп 30
4. Существенно выпуклые функционалы 31
Глава II. Общие методы оптимизации иерархических структур в частных задачах 36
1. Примеры задач поиска оптимальной структуры 36
1. Оптимальная организация технологического взаимодействия элементов 36
2. Оптимальное алфавитное кодирование 39
3. Оптимальная структура управления сетью доставки материальных потоков 42
4. Оптимальная структура управления однородными элементами 43
5. Задачи с неструктурным функционалом и сложными ограничениями 45
2. Примеры структурных функционалов стоимости 46
1. Сложность группы. Свойства функционала стоимости. Примеры 46
2. Вид оптимальной организации для функционала (I) 48
3. Вид оптимальной организации для функционала (II) 51
4. Вид оптимальной организации для функционала (III) 53
5. Вид оптимальной организации для функционала (IV) 57
Глава III. Алгоритмы поиска оптимального дерева 60
1. Точное решение задачи об оптимальном дереве 61
1. Оценка сложности общей задачи на (/). Переборный алгоритм 61
2. Оценка сложности общей задачи на Д.(/). Переборный алгоритм 65
3. Оценка сложности задачи на (/) при функционале вида 7 ( ,...,) ,у).
Алгоритм решения 68
4. Оценка сложности задачи на ,(/) при функционале вида / (Ы --- ,?ДЫ)
Алгоритм решения 73
2. Приближенное решение задачи об оптимальном дереве на (/) 75
1. Эвристический алгоритм со сложностью порядка пг при функционале вида 2. Эвристический алгоритм со сложностью порядка п2\о%п при функционале вида
дЫ -,Ы,Ы) 78
3. Первый эвристический алгоритм решения общей задачи 81
4. Второй эвристический алгоритм решения общей задачи 82 Глава IV .Алгоритмы поиска оптимальной последовательной организации 87
1. Алгоритм решения общей задачи 87
1. Эквивалентность задач о поддереве минимального веса и об оптимальной на Ор (!)
организации 87
2. Нормализация графа задачи 90
3. Построение алгоритма. Оценка сложности 92
2. Оценка сложности задачи при функционале вида Алгоритм решения 95
1. ЯР -полнота задачи 95
2. Узловые группы 97
3. Модификация алгоритма для функционала вида Оценка сложности 99
Глава V. Модель управления структурными изменениями организационной системы 104
1. Стоимость реорганизации структуры 105
1. Стоимость реорганизации групп 105
2. Стоимость реорганизации наборов групп 106
3. Стоимость реорганизации графов 108
4. Некоторые свойства стоимости реорганизации 111
2. Динамика структуры организационной системы 112
1. Определение структуры 112
2. Пример содержательной интерпретации понятия “внешняя среда” 113
3. Управление структурой 114
4. I -усечения как пример простейших управлений структурой 116
3. Исследование модели управления структурными изменениями 118
1. Параметры динамики внешней среды 119
2. Параметры затрат на функционирование и на реорганизацию 120
3. Соотношение затрат на функционирование и на реорганизацию при различном количестве уровней иерархии 122
4. Оптимальное количество уровней иерархии при различных параметрах функционала и скоростях изменения внешней среды 124
Заключение 128
Литература 129
- Звенья, субиерархии и слои
- Оптимальное алфавитное кодирование
- Оценка сложности общей задачи на Д.(/). Переборный алгоритм
- Пример содержательной интерпретации понятия “внешняя среда”
Звенья, субиерархии и слои
В общем виде задача оптимизации иерархической структуры может быть поставлена следующим образом: необходимо найти аг т тГ{С), где О - множество иерархических структур (иерархий) с заданным на нем функционалом Р : -» [0;+оо). Условие Р: О. - [0;+со) не ограничивает общности, так как любой функционал Р : О. (-оо;+оо) можно привести к Р с помощью монотонного преобразования области (-со;+ао) в область [0;+со). В дальнейшем считаем Р неотрицательным. Функционал Р назовем функционалом стоимости. Вышеуказанная задача является общей задачей оптимизации. В данной работе рассматривается оптимизация иерархических структур. Определим понятие иерархической структуры, ограничивая круг задач, исследуемых в работе. Определение 1.1. Любая иерархическая структура И е С2 представляет собой ориентированный ациклический граф .
То есть объект исследования - структура - представляет собой множество элементов с попарными связями между ними. Понятие иерархической структуры предполагает несимметричность связей (начальник - подчиненный) и невозможность циклического подчинения, то есть ориентированность графа и его ацикличность. В различных частных задачах ребрам графа могут приписываться скалярные или векторные веса, вершинам могут соответствовать какие-либо величины и т. и., но в соответствии с определением все эти характеристики мы относим к “правилам взаимодействия” элементов, считая что собственно структура описывается графом. Поставленную задачу назовем задачей об оптимальной иерархии.
Как в теоретическом, так и в прикладном аспекте большой интерес представляет изучение бесконечных иерархических структур. Например, конечные структуры с большим числом элементов можно изучать с помощью предельного случая - бесконечных структур. Некоторые варианты решения таких задач предложены в [16]. В данной работе мы ограничимся исследованием конечных структур. То есть далее любой граф СеП считаем конечным, не оговаривая это специально. При этом само множество графов О может быть бесконечным. 2. Звенья, субиерархии и слои. Определение 1.2. Будем говорить, что вершина и еУ подчинена вершине V е V в графе Я = (У,Е) е С2, если из и существует путь в V. Также будем говорить, что вершина V управляет вершиной и. Определение 1.3. Для любой вершины уеУ через Qc(v) = {и :и еУ,(и,у) е Е} обозначим множество вершин, из которых в графе Я = (V, Е) е О идут ребра в V, а через Яа(у) = {и:и е У,(у, и) е Е} - множество вершин, в которые в графе Я идут ребра из V. Вершины из Оа (V) назовем непосредственно подчиненными вершине V. Определение 1.4. Для любого графа й = (У,Е)еП множество вершин V е V, для которых Кс (г) = 0, обозначим через Т0 , а множество вершин V е V, для которых (2а(у) = 0, обозначим через Ы0. Вершины из Тс назовем терминальными, а из Ма - начальными. Определение 1.5. Для любой вершины veV\Na графа б = (К,)еП звеном с вершиной V назовем граф ZG y) {{v} uQc(y),{(u,y ):u eQG y)}). Как следует из определения, звено ZG (у) представляет собой подграф Я, который состоит из вершины у, непосредственно подчиненных ей вершин и ребер, соответствующих этим подчинениям.
Определение 1.6. Для любого графа Я е 2 и вершины у е Т0 \ ]Уа назовем у - упрощением граф, полученный из С после удаления у и инцидентных ребер.
Содержательно У-упрощение представляет собой операцию, при которой удаляется терминальная неизолированная вершина и ребра, соответствующие ее связям с непосредственно подчиненными вершинами.
Определение 1.7. Субиерархией Я графа бсО назовем граф, полученный после некоторой последовательности упрощений графа С . Множество всех субиерархий графа О обозначим через Я (С). Вырожденной субиерархией назовем граф Я = (Яс,0), состоящий из изолированных начальных вершин графа Я .
Содержательно субиерархия О представляет собой нижнюю” часть С, полученную после последовательного удаления неизолированных терминальных вершин. Сам граф Я также считаем субиерархией . Вырожденная субиерархия представляет собой набор изолированных (несвязанных) вершин, то есть фактически иерархия (подчинение) отсутствует. Будем говорить, что субиерархия Я, разбивается на Я2 и слой 5. Множество всех слоев графа О обозначим через 5(С),
Любое звено является слоем. Для каждой субиерархии или слоя Б = (У,Е) и любых вершин и,гєУ можно определить подчиненность и и У, множества 2п(у), Я0(г), Та, звенья Ев(у), V-упрощение так же, как в определениях 1.2-1.6. Ниже будем пользоваться этими обозначениями. Для пояснения понятий субиерархии, слоя и звена рассмотрим пример.
Граф С, изображенный на рис. 1.1, является также и субиерархией, обозначим ее через Я, = Є = (У1,Е1). После удаления терминальной вершины 7 и инцидентных ей ребер {5,7}, {6,7} (7-упрощения) получим субиерархию Н2=(У2,Е2), которая обведена сплошным прямоугольником. Выполнено Я2 сЯц следовательно субиерархиям Я, и Я2 соответствует некоторый слой 5, графа Є. Имеем У1\Уг= {7}, следовательно слой 5, совпадает со звеном 2С(7) = 6 1 =(У3 ,Е5 ), где У5 ={5,6,7}, Ев = {{5,7},{6,7}}. На рисунке слой 5, выделен пунктирным прямоугольником. Граф в получается “надстройкой” слоя 5, над субиерархией Я2, то есть С разбивается на Я2 и Д.
Если из Я2 удалить терминальную вершину 6 и инцидентные ребра {3,6}, {4,6}, то получим субиерархию Я3 графа С, которая обведена на рисунке пунктирно-точечной ломаной линией. Выполнено Я3 с Н2, следовательно субиерархиям Н2 и Я3 соответствует слой Б2 графа в, который обведен на рисунке кругом. Аналогично Я3 с Я,, следовательно граф Д, обведенный точечной ломаной линией, также является слоем. Определение 1.9. Пополнением множества О. назовем множество О = исеПя(е)- Множеством частей назовем множество О = иСбП(Я«7)и5(С)). Таким образом, пополнение С2 строится путем добавления к О всевозможных субиерархий, ай- путем добавления всевозможных субиерархий и слоев.
Определение 1.10. Функционал Р назовем аддитивным, если его можно продолжить на множество О Р: 2 - [0;+ю) гак, чтобы для любой субиерархии беП и любого ее разбиения на субиерархию Н и слой 5 выполнялось равенство Р((3) = Р(Н) + Р(Б), и стоимость любой вырожденной субиерархии На была нулевой: Р(Н0) = 0.
Поясним определение аддитивности на примере. Для этого рассмотрим множество 2 = {0,,02,С3,04}, графы которого изображены нарис. 1.2. Граф С2 отличается от С] тем, что добавлена вершина 7 и ей подчинены вершины 1 и 2. То есть 02 разбивается на субиерархию в, и слой 20 (7). Аддитивность предполагает, что при этом к стоимости Р(С,) должна быть добавлена некоторая величина х = Р(2Сг (7)) = Р(С2) - / (6 1) для получения Р(С2). Аналогично при добавлении к б, слоя 2С (9) к / (С?,) должна быть добавлена величина у = Р(20і (9)) = Р(С2) - Р(0]) для получения Р{С2). При добавлении к Ох слоев 20г(7) и ZC:l(9) получим граф ?4. Соответственно, должно выполняться Р(С4) = Р(Сгх) + х + у. То есть, определив произвольным образом Р(01) 0, Р(Сі2) Р(Є1), Р(С3) Р(йх), мы вынуждены положить Р(04) = Р(02) + Р(С,) - Р(С,) для того, чтобы функционал был аддитивным.
Оптимальное алфавитное кодирование
При заданном стимулировании функционал Р( ) структурен, так как для любой группы й е V \ Нв величины (рф), лф), сф) определяются только самой группой И и группами из которые непосредственно подчинены й, то есть набором подчиненных групп. Таким образом, для поиска оптимальной структуры управления, то есть дерева О е /)(/), минимизирующего потери Р(О), можно использовать алгоритмы поиска оптимального дерева, разработанные в главе III. При этом неважно, какая сеть рассматривается - однопродуктовая или многопродуктовая, так как величины л и ср могут быть как числами, так и векторами. В [37] отмечается, что задача в общем случае весьма сложна. В [10] для однопродуктовой сети и функции Д(у) специального вида рассмотрена комбинированная задача выбора стимулирования (правил функционирования) и структуры управления.
В работе [21] рассмотрена следующая задача. Задано множество N элементов нулевого уровня, п = Л/. Каждый элемент нулевого уровня должен быть связан с одним элементом первого уровня, в свою очередь элемент первого уровня - с одним элементом второго, и т.д. Элементы уровня I -1 связываются с единственным элементом уровня I. С каждым элементом уровня у связан по крайней мере один элемент уровня у — 1. Обозначим через п} количество элементов на у-ом уровне управления, у = 0, п. Тогда 1 = п1 лм ... «, па -п. Обозначим через хИ 1 количество элементов уровня у — 1, которые подчинены /-му элементу уровня у, У = 1/ = 1, И, , У „.глхн — П]-Предполагается, что затраты Кфхл) О на создание пункта управления зависят только от количества подчиненных хм и от уровня _/. То есть все элементы одного уровня предполагаются однородными, так что затраты зависят лишь от количества подчиненных элементов, но не от их состава. Задача построения оптимальной структуры управления заключается в поиске чисел 1,п] ,х , которые удовлетворяют вышеуказанным ограничениям и минимизируют суммарную величину затрат (х ). При этом количество уровней не должно превосходить некоторой предельной величины:
Очевидно, что рассматриваемые структуры представляют собой деревья из (/), где /-N. Длина пути из начальной вершины в / не должна превосходить Ь. Обозначим множество таких деревьев через ) (/)с)(/). Кроме того, накладывается ограничение на подчиненность: длина пути в вершину g из любой подчиненной начальной вершины {a}c1g одинакова и равна уровню g . Обозначим множество таких деревьев через Д(/) Т С/). На множестве /,(/) задан функционал стоимости дерева В = (У,Е) є /)і(У): Р(В) = .;еГ Л. К (бо(Я)) В общем случае функционал не структурен, так как зависит не только от групп, непосредственно подчиненных группе , но и от уровня У группы g, то есть от длины пути из начальной вершины в g. Таким образом, рассмотренная задача представляет собой задачу об оптимальной организации с неструктурным функционалом стоимости. Очевидно, что функционал Р можно продолжить на .ОД/) по вышеуказанной формуле. Тогда верно следующее утверждение.
Утверждение 2.4. Если для любого у выполнено К-1 (\) = 0, то оптимальное на О І (/) дерево будет оптимальным и на В, (/).
Доказательство. Рассмотрим произвольное дерево В = (V,Е) є ), (/). Для произвольной вершины gєV\ND через 1 ) обозначим длину максимального пути из подчиненных начальных вершин {а)с в g. Пусть 2о(Г) = {і & } и Г = тах(/( 1),...,/(уі.)). Если для некоторой вершины gl выполнено /(#,) / , то проделаем следующее. Добавим в В ц = / -/(у,) экземпляров группы gi, обозначив их через g),...,gql. Удалим ребро (,,) Вместо него создадим цепь gl -gj g [ -g, то есть добавим ребра (я,1,, ( Г .8І), (?,) После этого для всех вершин /г е (уУ величина 1(И) будет одинакова и равна Г. Проделав такие преобразования для всех вершин gєV\ND, получим дерево В є /,(/), в котором длина пути в вершину g из любой подчиненной начальной группы {а} с g одинакова. В силу К (1) = 0 такое преобразование не изменит стоимости. Тогда оптимальному на Ві (/) дереву О соответствует дерево В є /.(/), для которого Р(В ) = Р(В ). В силу Т)г(ЛГ) с В, (М) дерево В оптимально на /, (У). Утверждение доказано.
Таким образом, решив задачу об оптимальном дереве на /.(/), найдем решение и на Вь(/). Обратно, решив задачу на ),(/), преобразуем решение в оптимальное дерево на /.(/) так, как указано в доказательстве утверждения 2.4. То есть при К (\) = 0 задачи на Д/) и Оь (/) эквивалентны. В этом случае разработанные в [21] методы могут быть использованы для решения задачи на Т)А(/) с неструктурным функционалом Р (при достаточно большом Ь эти же методы решают задачу и на )).
Поставленная задача в [21] называется однородной, если функция затрат одинакова на всех уровнях: К1 = К(-). В этом случае функционал стоимости структурен. Разработанные в главе III общие алгоритмы поиска оптимального дерева на (/) могут быть модифицированы для решения задачи на Д (/ ) (см. соответствующие сноски главы III). Тогда при К( 1) = 0 общие алгоритмы позволяют решать однородную задачу. Но, разумеется, алгоритмы, разработанные в [21] для конкретного функционала стоимости, более эффективны.
Таким образом, из теоремы 1.6 следует один из результатов, полученных в [21]. )(/), в которых все пути из начальных вершин в корень имеют одинаковую длину от. Обозначим такое дерево через В =(У,Е). В нем все начальные вершины имеют уровень 1, подчинены управляющим вершинам уровня 2, те, в свою очередь, управляющим вершинам уровня 3, и так далее, вершины уровня от -1 подчинены корню /.
Для каждой группы ИеУ\Ыв уровня /, I = 2,т ее стоимость определяется следующим образом: ФВ(К) = -, ,—р ; где “сила взаимосвязи” групп и g" рекурсивно определяется как средняя “сила взаимосвязи” групп, которые непосредственно подчинены группам g , g" (и так далее, “сила взаимосвязи” групп первого уровня задана). Таким образом, стоимость ФВ(Ь) зависит не только от групп из QD (И), которые непосредственно подчинены /?, но и от всего поддерева с корнем /г.
Общая стоимость дерева записывается как Ф(Т ) = —— — Ф(/г), где к, 1 1=2 1 АеГ уровня/ количество вершин уровня /. То есть Ф(О) - некоторая средняя сила взаимосвязи всех управляющих центров дерева. Задача об оптимальной иерархии представляет собой задачу поиска дерева вышеуказанного вида, для которого достигается максимум Ф( ), то есть задачу на определенном подмножестве (/) с неструктурным функционалом . Как указано в [39], при от = 3 и фиксированном к2 эта задача сводится к широко известной задаче классификации, то есть разбиения множества объектов на заданное число классов по критерию “близости” объектов, оказывающихся внутри одного класса, и “удаленности” объектов, находящихся в разных классах (используется в теории распознавания образов). То есть даже в сугубо частном случае задача весьма сложна (см., например, [4, 22, 27, 28]). В общем случае в [39] построены лишь эвристические алгоритмы решения.
Оценка сложности общей задачи на Д.(/). Переборный алгоритм
Значения Ч(п) приведены в таблице 3.5. Из таблицы можно сделать вывод, что при увеличении п отношение (и)/ (и-1) уменьшается. Этот факт позволяет предположить, что порядок минимальной сложности точного алгоритма не превосходит а” для любого а 1. То же самое можно сказать и про сложность У (ri) построенного алгоритма. Вопрос теоретического доказательства приведенной гипотезы остается открытым. Также открыт вопрос о существовании полиномиальной по п оценки величин Ч(п), У (ri).
Значения У (ri) приведены в таблице 3.6. Из таблицы видно, что построенный алгоритм имеет приемлемую сложность для п 100. Кроме того, сложность алгоритма превосходит минимально возможную сложность точного алгоритма не более, чем на порядок (Т(100)/(7(100) 10). С другой стороны, нижняя оценка q(ri) сложности точного алгоритма неприемлемо высока при п существенно большем 100. Таким образом, имеет смысл построение эвристических алгоритмов, которые решают задачу с приемлемой погрешностью для некоторых функционалов стоимости (см. 2).
Приведем пример найденного алгоритмом оптимального на (/) дерева организации группы / = {а,,...,а70} из семидесяти элементов (и =70) для функционала (II) с функцией сложности вида (2.2) (см. 2 гл. II). Для примера положим а = 0.5 и р = 1.5, то есть точку из области, в которой функционал не является ни выпуклым, ни вогнутым (см. рис. 2.6). Для того, чтобы функционал имел вид P(gj,...,gt,g), то есть зависел только от мощностей подгрупп, сложности элементов должны быть равны: С(а,) =... = С(а10). В силу однородности функционала масштаб сложности не влияет на оптимальность организации. Положим сложности элементов равными единице: С(а] )=... = С(а10 ) = 1.
Оптимальное дерево изображено на рис. 3.5. При п = 25, и =125 и п = 625 оптимально симметричное 5-дерево, в котором каждая управляющая вершина имеет 5 подчиненных. При рассмотренном значении п= 70 элементы а,,...,а40 группируются в четверки, элементы а4,...,а70 группируются в пятерки. То есть все элементы подчиняются шестнадцати управляющим вершинам нижнего уровня, которые затем группируются в / с помощью симметричного 4-дерева.
При приближении /? к единице функционал “приближается” к вогнутому и становится оптимальной веерная организация. При увеличении /3 становится оптимальной 2-организация (в рассматриваемом примере при (3 3). Следовательно, численные эксперименты позволяют предположить, что для любого г можно подобрать такое Р, при котором будет оптимальна симметричная г-организация (для п = г , то есть для соответствующего количества элементов).
Таким образом, построенные алгоритмы позволяют анализировать закономерности поведения оптимального дерева организации в зависимости от параметров функционала. Следующее утверждение представляет собой аналог утверждения 3.5 для ОД/).
Утверждение 3.7. Алгоритм, решающий задачу об оптималвном г-дереве на ОД/), / = п 4 с функционалом вида 3 ( ,,..., А, ), должен проанализировать не менее д(п,г) значений функционала Р. Любой алгоритм, анализирующий менее д(п,г) значений Р. может выдать решение, стоимость которого сколь угодно больше стоимости оптимального г -дерева.
Доказательство. Зададим функционал Р ,,..., ) стоимости организации подгрупп g ,...,gk в группу g = g]u...иgk в соответствии с формулой (3.4) (см. утв. 3.5). Тогда любое г-дерево Б е Д (/) имеет стоимость у. Предположим, что алгоритм, решающий задачу об оптимальном г-дереве на Д(/), анализирует менее д(п,г) значений Р. Применим его для решения задачи с функционалом Р . Обозначим полученное г-дерево через е Д(/). Найдется такой набор подгрупп /2р...,/г,, / = /г, и...ийу, у г, что все варианты организации /, стоимость которых проанализирует алгоритм, будут существенно отличаться от Если в О набор Оа(/) существенно отличается от , то зададим функционал Р" в соответствии с формулой (3.5), иначе, выбрав произвольное г у, зададим функционал Р" в соответствии с формулой (3.6) (см. утв. 3.5).
Применим алгоритм для решения задачи с функционалом Р". Мы изменили значения функционала только для тех вариантов организации /, которые несущественно отличаются от йр..., йр Эти значения алгоритм не анализировал. Следовательно, в качестве решения опять будет выдано г -дерево В . При первом варианте выбора Р" г -деревья из Д (/), в которых группа / организуется из подгрупп к1,...,Ь], имеют нулевую стоимость, а ( ) = у . При втором варианте выбора Р" в силу п 4 в Д (/) существует по крайней мере одно г-дерево, в котором группа / организуется из набора подгрупп, существенно отличающегося от Стоимость такого г-дерева равна у, а Р(В ) = г. В обоих случаях стоимость выданного решения может быть сколь угодно большей, чем стоимость оптимального г-дерева. Утверждение доказано.
Если функционал имеет вид Р( ,,...,А, ) и при каждом г = 2,п для некоторой группы g мощности г известно ее разбиение (2 ) в некотором оптимальном г - дереве Д е Д Д) организации g, то можно построить оптимальное на Д (/) г-дерево организации /, / = п, не вычисляя значений функционала стоимости.
Доказательство проводится повторением доказательства леммы 3.3 с точностью до замены слов “дерево” на “ г -дерево” и множества /)(/) на Д (/). Лемма доказана. Доказательство следующего утверждения дает алгоритм поиска оптимального г- дерева на Д(/) с функционалом вида Л(1,..., 4, ) и его сложность. Утверждение 3.8. Существует алгоритм, решающий задачу об оптимальном г -дереве организации на Д(/), / = « с функционалом вида Р(1,..., к, ) за 7(п,г) = — д(г,г) вычислений Р.
Доказательство. Проводится повторением доказательства утверждения 3.6 с точностью до замены слов “дерево” на “г-дерево”, множества (/) на Д(/), величин д(г) и («) соответственно на д(і,г) и (и,г), ссылки на лемму 3.3 ссылкой на лемму 3.4. Утверждение доказано.
Поясним утверждения 3.7 и 3.8 на примере (см. рис. 3.1). Предположим, что необходимо найти оптимальное 2-дерево. Тогда подходят только три варианта разбиения / = {а,,а2,а3}, изображенные слева. Все эти три варианта имеют одинаковую стоимость, поэтому функционал можно не вычислять вообще, а выбрать любое дерево в качестве оптимального. По этой причине в утверждении 3.7 введено условие / = и 4, которое гарантирует, что при разбиении / найдутся по крайней мере два существенно различных варианта. Построенный алгоритм (см. утв. 3.8) вычислит (3,2) = /(3,2) + д(2,2) = 2 значения функционала и найдет стоимость оптимального дерева.
Пример содержательной интерпретации понятия “внешняя среда”
Во введении к работе было дано неформальное определение организационной системы и присущей ей иерархической структуры. В данной главе рассматриваются некоторые вопросы моделирования структуры организационной системы.
Сначала остановимся на статических моделях поиска оптимальной структуры среди некоторого множества альтернатив. Если структура описывается ориентированным ациклическим графом, то моделирование сводится к поставленной в главе I задаче об оптимальной иерархии. Таким образом, приведенные ранее примеры частных постановок (см. гл. II) одновременно являются примерами статических моделей, а весь аппарат глав 1-1У может использоваться для статического моделирования в случае структурного функционала стоимости. Ключевым моментом при определении статической модели является выбор функционала. Для различных примеров организационных систем (например, для отраслей промышленности) накоплен огромный эмпирический материал, позволяющий определить некоторые агрегированные параметры структуры. Например, норма управляемости (максимальное число подчиненных) [3], численность управленческого персонала [25] и т. п. Такие исследования позволяют сравнивать некоторые “типичные” структуры и выбирать из них наиболее подходящую для конкретной системы. Тестирование функционалов на этих “типичных” вариантах позволяет уточнять их вид и параметры, исходя из эмпирических данных и результатов моделирования. Ниже считаем, что функционал стоимости некоторым образом задан.
При переходе от статических моделей к динамическим будем считать, что функционал соответствует стоимости функционирования системы (затратам) в течение некоторой единицы времени. Если “ситуация” остается неизменной, то достаточно минимизировать затраты (найти структуру, минимизирующую функционал) для получения “наиболее эффективной” системы и модель сводится к статической. Если же “ситуация” изменяется, то старая структура может “не отвечать новым требованиям” и необходима реструктуризация (перестроение), требующая некоторых затрат. В этом случае в динамике может оказаться оптимальной “более дорогая”, но и “более гибкая” структура, требующая меньших затрат на перестроение.
Выбор структуры, оптимальной в динамике, является ключевой проблемой в некоторых моделях “устойчивого развития” организационных систем (см., например, [11]). Вопрос о выборе критерия оптимальности в динамике для организационных систем не имеет однозначного решения [5, 24]. В отсутствии исчерпывающего прогноза изменений внешней среды постановки оптимизационных задач неизбежно включают в себя элементы эмпирики. Ниже мы рассмотрим один из возможных эмпирических критериев, который при необходимости может быть модифицирован.
Ограничения на траектории структур (графов) могут описываться различным образом. В качестве одного из вариантов аппарата описания траекторий структурных изменений отметим приведенное в [1, 2] построение так называемых “уравнений графодинамики”. Ниже в 2 мы рассмотрим единственное ограничение на преобразования структуры - в каждый момент времени она должна быть графом организации некоторого набора групп (см. опр. 1.22), определяемого “внешней средой”.
Динамическая оптимизация напрямую связана и с проблемой выбора оптимального числа уровней иерархии в зависимости от внешних условий, которая обсуждается в большинстве работ (см., например, [44, 56]) лишь на качественном уровне. Излагаемая модель позволяет дать количественные оценки оптимального числа иерархических уровней (см. 3). 1. Стоимость реорганизации структуры.
В данном параграфе строится один из возможных примеров содержательно интерпретируемой метрики на графах организации - стоимость реорганизации. За основу взята некоторая метрика на множестве групп (см. опр. 5.1). Далее построены метрики на множестве наборов групп и на множестве графов (см. опр. 5.2 и 5.3), причем аналогичное построение можно также провести на основе любой другой метрики на множестве групп. Таким образом, проиллюстрирован возможный подход к построению метрики общего вида. В последующих параграфах стоимость реорганизации используется для моделирования структурных изменений организационной системы.
Определение 5.1. Стоимостью реорганизации группы geTu{0} в группу h е Fu {0} назовем величину p(g,h) - У1_Е,1,р {а) + У,пг р"{а) где р (а) 0 - заданная стоимость исключения элемента а из группы, а р"{а) 0 - заданная стоимость включения элемента а в группу. Величину p(0,h) назовем стоимостью организации h “с нуля”, величину p(g,0) - стоимостью деорганизации g.
Таким образом, предполагаем, что для любого элемента а е N заданы стоимости включения и исключения а из группы. Для организационной системы затраты на включение (исключение) могут соответствовать “налаживанию взаимодействия” элемента в новой группе, некоторому “обучению” и т. и. Предполагаем, что стоимость включения (исключения) зависит лишь от самого элемента а, а не от той группы, в которую он включается (из которой исключается).
Определению 5.1 можно дать следующую содержательную интерпретацию. Для реорганизации группы g в группу h сначала последовательно исключаем те элементы g, которые не входят в h, a затем последовательно включаем те элементы h, которые не входят в g. Сумма p{g,h) всех затрат и будет стоимостью реорганизации g в h. Если положить g = 0, то получим стоимость организации группы h “с нуля”, то есть стоимость включения всех элементов группы. Если положить h = 0, то получим стоимость деорганизации группы g, то есть стоимость исключения всех элементов группы.
Если в нем есть две паРы вида (g,0), (0,h), g Ф 0, h it 0, то переформируем их в пары (g,h), (0,0). При таком разбиении снова получим р(0Г,0"), так как сумма не увеличилась в силу p(g,h) p(g,0)-r p(0,h) (см. лемму 5.3), р(0,0) = 0. Повторяя такие действия, получим в результате разбиение, в котором нет двух пар вида (g,0), (0,/г). Такое разбиение может быть получено из некоторого разбиения наборов 0, и 0, добавлением пар, состоящих из пустых множеств. Таким образом
Лемма 5.5. Если для любых групп fug выполнена первая аксиома метрики, то и для любых наборов непустых групп 0 и g2 также выполнена первая аксиома метрики: равенство р(0, 0,) = 0 эквивалентно равенству 0, = 02. Доказательство. р(0,,02) = О тогда и только тогда, когда 0, = 02 = А, так как иначе добавляются пустые множества, a p(g, 0) 0 и p(0,h) 0 для любых непустых групп g и А. Далее имеем р(0р02) = min T — p{g,,ht) = 0 тогда и только тогда, когда наборы 0, и 02 разбиваются на пары (g,,/г,), для которых p(gi,hi) = 0, то есть на пары одинаковых множеств, что возможно лишь при 0, = 02. Лемма доказана.
