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

Введение.

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

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

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

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

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

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

5. Простые и структурные функционалы.

§2. Редукция общей задачи к задаче об оптимальной организации.

1. Графы организации.

2. Оптимальная организация набора групп.

3. Виды организаций.

4. Деревья организации.

§3. Вид оптимальной организации для различных классов структурного функционала.

1. Монотонные функционалы.

2. Выпуклые и вогнутые функционалы.

3. Организации без повторяющихся групп.

4. Существенно выпуклые функционалы.

Глава II. Общие методы оптимизации иерархических структур в частных задачах.

§ 1. Примеры задач поиска оптимальной структуры.

1. Оптимальная организация технологического взаимодействия элементов.

2. Оптимальное алфавитное кодирование.

3. Оптимальная структура управления сетью доставки материальных потоков.

4. Оптимальная структура управления однородными элементами.

5. Задачи с неструктурным функционалом и сложными ограничениями.

§2. Примеры структурных функционалов стоимости.

1. Сложность группы. Свойства функционала стоимости. Примеры.

2. Вид оптимальной организации для функционала (I).

3. Вид оптимальной организации для функционала (II).

4. Вид оптимальной организации для функционала (III).

5. Вид оптимальной организации для функционала (IV).

Глава III. Алгоритмы поиска оптимального дерева.

§1. Точное решение задачи об оптимальном дереве.

1. Оценка сложности общей задачи на D(f). Переборный алгоритм.

2. Оценка сложности общей задачи на Dr(f). Переборный алгоритм.

3. Оценка сложности задачи на £>(/) ПРИ функционале вида

Алгоритм решения.

4. Оценка сложности задачи на Dr(f) при функционале вида P(|g,|,.,|gJ,|gj).

Алгоритм решения.

§2. Приближенное решение задачи об оптимальном дереве на £>(/).

1. Эвристический алгоритм со сложностью порядка пг при функционале вида рЫ-кМ.

2. Эвристический алгоритм со сложностью порядка п2 log« при функционале вида p(\gl\,.,\gM).

3. Первый эвристический алгоритм решения общей задачи.

4. Второй эвристический алгоритм решения общей задачи.

Глава IV.Алгоритмы поиска оптимальной последовательной организации.

§ 1. Алгоритм решения общей задачи.

1. Эквивалентность задач о поддереве минимального веса и об оптимальной на Ор (f) организации.

2. Нормализация графа задачи.

3. Построение алгоритма. Оценка сложности.

§2. Оценка сложности задачи при функционале вида />()#, Алгоритм решения.

1. NP -полнота задачи.

2. Узловые группы.

3. Модификация алгоритма для функционала вида j» - - -,|g"yt ¡»■ Оценка сложности.

Глава У. Модель управления структурными изменениями организационной системы.

§ 1. Стоимость реорганизации структуры.

1. Стоимость реорганизации групп.

2. Стоимость реорганизации наборов групп.

3. Стоимость реорганизации графов.

4. Некоторые свойства стоимости реорганизации.

§2. Динамика структуры организационной системы.

1. Определение структуры.

2. Пример содержательной интерпретации понятия "внешняя среда".

3. Управление структурой.

4. I -усечения как пример простейших управлений структурой.

§3. Исследование модели управления структурными изменениями.

1. Параметры динамики внешней среды.

2. Параметры затрат на функционирование и на реорганизацию.

3. Соотношение затрат на функционирование и на реорганизацию при различном количестве уровней иерархии.

4. Оптимальное количество уровней иерархии при различных параметрах функционала и скоростях изменения внешней среды.

Актуальность темы. Под системой в самом общем смысле слова обычно понимают совокупность некоторых элементов и связей между ними. Понятие организационной системы включает в себя также "поведение" отдельных элементов, подсистем и системы в целом, которое связано с некоторой целенаправленностью. Обычно целенаправленность определяется как оптимизация некоторого функционала [23]. Организационные системы характерны для самых различных сфер человеческой деятельности: экономической, социальной, военной и т. п., что и обусловливает актуальность их изучения. Несмотря на большое количество работ (см. обзоры [8, 9, 35]) по проблемам математического моделирования организационных систем, в настоящее время не только не создана стройная теория, но отсутствует даже общепринятое определение организационной системы (см., например, [21, 26]), не сводящееся к перечислению различных примеров. Имеющиеся модели касаются отдельных аспектов функционирования конкретных систем.

Важнейшим свойством организационных систем является иерархичность структуры, то есть определенная соподчиненность элементов и подсистем [41]. В то же время пока не создано единого методологического подхода к исследованию организационных систем как многоуровневых систем с иерархической структурой [26, 34]. Причем наименее разработанной является проблема синтеза иерархической структуры, то есть проблема поиска структуры общего вида, оптимальной в смысле заданного критерия. В подавляющем большинстве существующих моделей [21, 37, 41] рассматриваются только древовидные структуры, а ограничения, критерий эффективности и методы исследования определяются спецификой конкретной задачи. В общем же случае критерий эффективности может быть произвольным, возможно множественное подчинение, наличие нескольких элементов верхнего уровня.

Таким образом, в целях разработки единого описания иерархических организационных структур актуальным представляется исследование моделей иерархических структур общего вида (ориентированных ациклических графов) с произвольным критерием эффективности (функционалом), тем более, что такая постановка также охватывает ряд задач теории кодирования, теории массового обслуживания, различных прикладных областей (см. гл. II).

Решение общей задачи об оптимальной иерархии позволило бы находить наилучшие структуры организационных систем среди заданного множества альтернатив (максимизирующие эффективность, минимизирующие затраты на функционирование и т. п.). Такую задачу можно назвать задачей статической оптимизации. Однако, поскольку оптимальная структура неявным образом зависит от "внешних условий", актуальной является и задача динамической оптимизации, то есть поиск оптимальной иерархической структуры на заданном временном интервале с учетом изменений "внешней среды". В этом случае кроме эффективности структуры необходимо учитывать и "гибкость" ее перестроения при изменениях среды. Эта задача является ключевой в некоторых моделях "устойчивого развития" [11]. Динамическая оптимизация напрямую связана и с проблемой выбора оптимального числа уровней иерархии в зависимости от внешних условий, которая обсуждается в большинстве работ (см., например, [44, 56]) лишь на качественном уровне.

Таким образом, актуальным является создание формальных математических моделей для количественного анализа проблемы оптимального баланса "статической" и "динамической" эффективности структуры организационной системы.

Следует отметить, что структурные свойства системы в значительной мере определяются свойствами элементов и подсистем, а также законами функционирования системы. Одним из развитых направлений анализа и синтеза законов взаимодействия элементов является теория активных систем [6, 9, 36], в которой каждому активному элементу соответствует своя целевая функция. Разнообразный математический аппарат, в частности теория игр [18], позволяют синтезировать законы взаимодействия, обеспечивающие оптимальное в некотором смысле игровое равновесие. В настоящее время в теории активных систем в общем виде изучена лишь двухуровневая (веерная) организационная система - центр и подчиненные элементы. В изучении многоуровневых систем сделаны только первые шаги [34, 35]. В связи с этим актуальным является расширение моделей активной системы на иерархические структуры общего вида, что также мотивирует их изучение.

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

Для достижения цели решается следующий комплекс задач:

1. Создание математической модели иерархической организационной структуры и постановка оптимизационной задачи, в том числе - исследование ограничений на множество структур и вид критерия оптимальности.

2. Разработка аналитических и алгоритмических методов оптимизации иерархических организационных структур.

3. Использование разработанных методов для решения прикладных задач и построения модели оптимального управления структурными изменениями организационной системы.

Методы исследования. Для решения общей задачи синтеза оптимальной иерархической структуры используются методы теории графов. Исследование функционалов проводится методами математического анализа. Нижние оценки сложности дискретных задач, разработка и анализ сложности алгоритмов проводятся с использованием аппарата теории сложности. Для исследования эвристических алгоритмов и модели управления структурными изменениями применяется компьютерное моделирование.

Положения, выносимые на защиту, и научная новизна результатов исследования:

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

2. Доказаны оценки сложности, предложены методы (точные и эвристические алгоритмы) поиска оптимальных структур на различных множествах графов.

3. Построена и исследована модель оптимального управления структурными изменениями организационной системы.

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

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

Апробация работы. Основные результаты диссертационной работы были представлены на международной конференции «Теория активных систем» (Москва, 19-21 ноября 2001г.); на международной конференции «Современные сложные системы управления» (Липецк, 12-14 марта 2002г.); на международной конференции «Современные сложные системы управления» (Старый Оскол, 27-29 ноября 2002г.); на научно-практической конференции молодых ученых Волгоградской области (Волгоград, 2001г.); на семинарах кафедры математического анализа и теории функций и конференциях Волгоградского госуниверситета в 2000-2002г.г.; на семинарах Института проблем управления РАН (Москва) в 2001-2002г.г.

Публикации. Основные материалы диссертации опубликованы в 9 научных работах, включая 4 статьи и 5 тезисов докладов.

Личный вклад автора. В совместно опубликованных работах автору принадлежат формулировки и доказательства полученных результатов.

Структура работы. Работа состоит из пяти глав. В главе I поставлена общая задача об оптимальной структуре (иерархии), проведена ее редукция к задаче на множестве графов специального вида (графов организации) для так называемых структурных функционалов. Проведен содержательный анализ требования структурности. Доказан ряд теорем по поводу вида оптимальной организации для различных классов структурного функционала. Таким образом, глава I посвящена постановке задачи в общем виде, описанию некоторых ограничений и получению результатов при их выполнении. Материал главы I не зависит от возможных содержательных интерпретаций рассматриваемого множества структур и посвящен исследованию иерархической структуры как таковой.

В главе II различные частные задачи синтеза оптимальной иерархической структуры рассмотрены в контексте общих результатов главы I. Описан анализ частных задач общими методами. Приведены содержательные интерпретации общих свойств функционала, определенных в главе I. Рассмотрены различные примеры функционалов, исследованы их свойства.

В главе III исследована сложность и построены алгоритмы поиска оптимальных деревьев. Как показано в главе I, древовидные структуры в ряде случаев будут оптимальными организациями. Кроме того, к задаче об оптимальном дереве сводится ряд задач, рассмотренных в главе II.

В главе IV исследована сложность задачи и построены алгоритмы поиска оптимальной последовательной организации. Как показано в главе I, такие структуры будут оптимальными для определенного класса функционалов.

В главе V рассмотрены возможные подходы к применению разработанного аппарата для моделирования структурных изменений организационной системы. Для построения динамической модели введена метрика на множестве структур - стоимость реорганизации -и определен динамический критерий - суммарные затраты на функционирование и на реорганизацию в течение конечного отрезка времени. Проведен анализ оптимальности различных управлений структурой системы в зависимости от параметров функционала и интенсивности изменений внешней среды. Для расчетов использован пример функционала из главы II, алгоритмы главы IV и общий аппарат главы I.

В работе принята двойная нумерация определений, лемм, утверждений, теорем, формул, рисунков и таблиц, то есть сначала указывается номер главы, затем через точку номер определения, леммы и т. п. в этой главе. Используются арабские цифры. Номера формул указываются в скобках. Исключение составляют введенные в главе II функционалы (I)-(IV), которые нумеруются римскими цифрами без указания номера главы (в связи с большим количеством ссылок).

Краткое содержание работы.

В общем виде задача оптимизации иерархической структуры поставлена в §1 главы I следующим образом: необходимо найти arg min P(G), где Q - множество допустимых

GeCl иерархических структур (иерархий) с заданным на нем функционалом Р: Q -> [0;+°о), который мы в дальнейшем будем называть функционалом стоимости. Под иерархической структурой Geü понимается ориентированный ациклический граф. Таким образом, под структурой понимается множество элементов с попарными связями между ними. Понятие иерархической структуры предполагает несимметричность связей (начальник -подчиненный) и невозможность циклического подчинения, то есть ориентированность графа и его ацикличность.

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

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

Поставленная общая задача исследована при следующих ограничениях.

1. Изучаются лишь конечные графы. Некоторые методы изучения бесконечных иерархий приведены в [16].

2. Изучаются структурные функционалы. Некоторые частные задачи, приведенные в главе П, описываются неструктурными функционалами и мотивируют актуальность их исследования.

3. Изучаются не все возможные множества графов, а некоторые их варианты1.

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

В §2 главы I описана редукция общей задачи об оптимальной иерархии к задаче на множестве графов специального вида. Графом организации (организацией) над множеством элементов N назовем граф, в котором на нижнем уровне находятся элементы из N, подчиняющиеся управляющим вершинам последующих уровней, причем каждая управляющая вершина однозначно характеризуется группой (множеством) подчиненных ей элементов. Доказано, что в случае структурного функционала решение задачи на некотором множестве графов организации даст решение и на исходном множестве Q произвольных графов, причем множество элементов N будет соответствовать начальным вершинам графов из Q . В дальнейшем рассматриваются только графы организации. Изучаемые варианты множеств определены ниже в §2.

Введем понятие графа организации заданного набора € = {/,,.,/„} групп элементов (/¡с^Ы), то есть графа, который содержит все группы набора. Множество таких графов обозначим через Решением задачи на О (Г) будет граф, оптимальный среди графов организации, которые "управляют" группами элементов из Г.

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

Ог{{), Ор(£), 0({), Ог($) обозначим соответственно множество г-организаций, последовательных организаций, организаций без пересечений, г -организаций без пересечений, которые входят в 0(1), то есть управляют группами из набора { .

Если набор f = {/} состоит из одной группы, то 0([) будет множеством деревьев организации одной группы /. Через /)(/) = £(/) и Dr{f)-Or(f) обозначим соответственно множество деревьев и г -деревьев из <?(/). Веерной (двухуровневой) организацией назовем организацию, в которой каждая группа организуется непосредственно из составляющих ее элементов. Примеры видов организации приведены на рис. 1.4.

Решение задачи на объединении множеств 0{Т), Ог({), Ор(1), 0({), Ог({) для различных наборов Г получается после решения задачи на каждом из множеств по отдельности. С помощью таких объединений можно представить достаточно широкий класс множеств организаций. В дальнейшем в работе изучаются только вышеуказанные варианты множеств.

В §3 главы I найден вид оптимальной организации для различных классов структурного функционала, который на множестве графов организации выглядит следующим образом: Р(0) = 1, > гДе С = (У,Е) е 0(Ы) - граф организации,

Мс - множество начальных вершин (7 (элементов), g],.,gk - подгруппы, непосредственно подчиненные управляющей вершине (группе) g Величина />(£!,.,)^0 определяет стоимость звена, управляющего набором групп То есть структурный функционал полностью определен, если величина задана на всевозможных наборах групп.

Функционал назван монотонным, если его значение не убывает при расширении одной из подгрупп и при добавлении новой подгруппы. Функционал назван выпуклым, если при к>3 вместо организации подгрупп в группу g можно, не увеличивая стоимость, сначала организовать некоторые подгруппы из g^,.,gk, а затем полученную группу организовать с оставшимися подгруппами из ■ Функционал назван вогнутым, если уменьшить стоимость таким образом нельзя. Выпуклый функционал назван существенно выпуклым, если при организации двух неэлементарных подгрупп можно из одной удалить произвольный элемент, а затем организовать его с полученной группой, не увеличивая стоимости2. Доказан ряд теорем о видах оптимальной организации.

1 Например, на рис. 2.2 слева управляющей вершине III (группе £ = {1,2,3,4,5,6,7}) непосредственно подчинены подгруппы g1 = {1,2,3}, = {4,5,6} и g3 = {7}.

2 Примеры функционалов, анализ их монотонности, выпуклости, вогнутости, существенной выпуклости, содержательные интерпретации выпуклости и вогнутости приведены в главе II.

По поводу организации произвольного набора групп Г из доказанных теорем сделаны следующие основные выводы: а) При выпуклом функционале 2-организация минимальной стоимости будет оптимальной (решения на 02(£) и 02(I1) будут оптимальны соответственно на Ог(£), 0(1) и О,.(Г), 0({)). Ь) При существенно выпуклом функционале последовательная организация минимальной стоимости будет оптимальной (решение на Ор (Г)1 будет оптимально и на <9(1"), Ог (Г), ОЦ), Ог ^)).

По поводу организации одной группы / сделаны следующие основные выводы: а) При монотонном функционале дерево минимальной стоимости также будет и оптимальной организацией (решения на £>(/) и £>,.(/)2 будут оптимальны соответственно на <3(/) и Ог (/)). Ь) При монотонном выпуклом функционале 2-дерево минимальной стоимости также будет и оптимальной организацией (решение на £>2 (/) будет оптимально на /)(/), Вг (/), 0(/), Ог (/)). с) При монотонном вогнутом функционале веерная организация будет оптимальна на 0(/) и 0(/).

В §1 главы II приведены примеры задач, являющихся частными случаями общей задачи об оптимальной иерархии, причем многие из них описываются структурным функционалом стоимости, что позволяет применить полученные в работе общие методы решения. Вполне естественно, что для конкретных задач могут существовать более эффективные частные методы. Однако универсальность общих методов позволяет проанализировать каждую новую частную задачу "в первом приближении", а затем при необходимости учитывать ее специфику.

В пункте 1 описана задача об оптимальной организации технологического взаимодействия элементов, которое задано с помощью технологического графа. Между вершинами графа (конечными исполнителями или элементарными операциями технологического процесса) идет обмен материалами, информацией, энергией и т. п., что описывается ребрами графа и соответствующими им векторами мощности потоков. Для организации взаимодействия необходимо создание управляющих центров, координирующих потоки между элементами некоторых групп. Управляющие центры следующего уровня координируют потоки между подчиненными группами и т.д. Затраты на управляющий центр описываются функцией затрат К(•) от суммарной мощности координируемых потоков. В результате получаем задачу об оптимальном на £>(/) дереве организации со структурным функционалом стоимости Р, где / = N = {а{,. .,ап} - множество (группа) элементов технологического графа.

На рис. 2.2 приведены различные примеры надстройки организационного графа над технологическим. Слева приведен пример организации, в которой управляющий центр I координирует взаимодействие группы элементов {1,2,3}, центр II- группы {4,5,6}, центр III - взаимодействие групп {1,2,3}, {4,5,6} и {7}. В центре приведен пример 2-организации, справа изображена веерная организация. Если потоки на ребрах технологического графа одномерные и К(0) = 0, то выпуклость/вогнутость функции затрат влечет соответственно выпуклость/вогнутость функционала Р. То есть в случае выпуклой функции затрат оптимальна 2-организация, в случае вогнутой - веерная организация (см. гл. I), имеющие, соответственно, максимальное и минимальное число управляющих центров.

В пункте 2 доказано, что задача построения оптимального алфавитного кода при заданных вероятностях появления символов входного алфавита эквивалентна задаче об оптимальном г-дереве организации над этим алфавитом (г-число символов выходного

1 Алгоритмы поиска оптимальной на Ор{f) организации описаны в главе IV.

2 Алгоритмы поиска оптимального на £>(/) и Dr (/) дерева описаны в главе III. алфавита), причем функционал стоимости структурен и имеет достаточно простой вид. Для него алгоритм Хаффмана позволяет решить задачу об оптимальном на Д.(/) г-дереве за п\о^п операций, где п - число элементов (символов входного алфавита).

В пунктах 3-5 показано, что описанные в различных работах (см., например, [21, 37, 41]) задачи об оптимальной структуре управления сетью доставки материальных потоков, оптимальной структуре управления однородными элементами и некоторые другие представляют собой частные случаи задачи об оптимальном дереве организации. Причем в некоторых случаях функционал структурен, в других нет, что иллюстрирует необходимость дальнейшего развития общих методов и для неструктурных функционалов.

В §2 главы II определены так называемые анонимные функционалы, то есть структурные функционалы, которые зависят не от самих организуемых групп, а от некоторой их характеристики - сложности. Исходя из анализа различных вариантов взаимодействия людей в группах, которое на качественном уровне изучается во многих работах (см., например, [47, 53, 55]), предложены различные примеры функционалов (см. формулы (1)-(1У)).

Исследована монотонность, выпуклость, вогнутость, существенная выпуклость функционалов (1)-(1У), и из общих теорем главы I сделаны соответствующие выводы по поводу вида оптимальной организации. Полученные результаты схематично представлены в виде карт параметров (см. рис. 2.5-2.8), в которых каждой области соответствует определенный вид оптимальной организации. Для ряда наборов параметров функционалы не являются ни выпуклыми, ни вогнутыми. Аналитическое решение задачи в этих областях на данный момент отсутствует. На рис. 3.2, 3.4, 3.5 приведены примеры использования алгоритмических методов решения, из которых можно сделать вывод, что в указанных областях оптимальная организация ведет себя сложным образом.

В главе III рассмотрены методы поиска оптимальных на £>(/) и 1)г(/) деревьев организации одной группы /, |/| = п . §1 главы III посвящен точному решению задачи об оптимальном дереве. Доказано, что для структурного функционала общего вида не существует полиномиальных по п алгоритмов, дающих точное решение на £>(/) и А (/) > причем погрешность любого полиномиального алгоритма может быть сколь угодно велика. Построены переборные алгоритмы экспоненциальной сложности.

Как показывает §1 главы II, существуют функционалы, для которых задача об оптимальном г-дереве на Д.(/) полиномиально разрешима. В связи с этим представляют интерес классы функционалов, для которых задача на Ог (/) решается полиномиальным по п алгоритмом. Доказано, что такой класс образуют, например, функционалы вида зависящие не от самих подгрупп g^,.,gk, организуемых в группу g, а лишь от их мощностей (числа элементов в группе). Для этого класса функционалов построен алгоритм решения задачи на £>г (/) со сложностью не более п . Также построен алгоритм и проанализирована сложность решения задачи на £>(/). Однако вопрос о полиномиальности алгоритма на £>(/) открыт.

В связи с достаточно высокой сложностью точных алгоритмов решения задачи на £*(/) в §2 главы III построены эвристические алгоритмы меньшей сложности. В общем случае они дают сколь угодно большую погрешность, однако для некоторых функционалов обладают приемлемой точностью и могут быть использованы после предварительного тестирования.

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

Доказано, что для определенных классов функционалов эвристические алгоритмы дают точное решение. Вне этих классов необходимо тестирование "качества работы" алгоритма. Приведен пример такого тестирования. Сделаны эмпирические выводы о величине средней и максимальной погрешности, о нарастании погрешности при росте п. В результате тестирования можно сделать выводы о том, какой алгоритм предпочтительнее использовать для конкретного функционала. Кроме того, приведен пример эмпирического анализа самого функционала на классе деревьев £>(/), из которого можно сделать выводы о том, насколько отличается стоимость деревьев, оптимальных на £>2(/) и Ор(/), от стоимости оптимального на £(/) дерева, от стоимости веерной организации. То есть приведен пример анализа разброса стоимости различных деревьев. Полученные с помощью такого анализа результаты могут помочь в выявлении некоторых закономерностей функционала.

В главе IV рассмотрена задача поиска оптимальной на О последовательной организации произвольного набора групп f = Проанализирована сложность и построены алгоритмы ее решения для структурного функционала общего вида и для функционала вида РС^,!,.,^),^), зависящего лишь от мощностей. Через я = |/, и. и /И| обозначено общее количество элементов, через т - количество групп в наборе I. Как показано в главе I, для существенно выпуклых функционалов построенные алгоритмы решают задачу и на множествах О(С), Ог (С), О (Г), Ог(1).

В §1 главы IV показано, что для структурного функционала общего вида на оптимальность последовательной организации могут влиять порядка п2" значений функционала. Любой алгоритм должен вычислить такое количество значений. Доказано, что задача об оптимальной на О последовательной организации эквивалентна задаче поиска поддерева некоторого графа Я, которое имеет минимальный вес среди всех поддеревьев с заданным корнем и листьями. Построен алгоритм решения, сложность которого в худшем случае оценивается величиной п2"Зт . В среднем сложность алгоритма зависит от структуры пересечений групп набора С. Эмпирическое тестирование алгоритма на различных наборах показывает, что при т, п < 15 сложность остается приемлемой.

В §2 главы IV показано, что для функционала вида Р^,],.,^!,!^) необходимо вычислить лишь п значений функционала, в отличие от п2" в общем случае. Доказано, что задача ТУР-полна, даже если мощности всех групп набора £ = .,/„,} не превосходят трех. Таким образом, не существует полиномиального по т алгоритма (если Р Ф МР, то есть МР -полные задачи полиномиально неразрешимы). Построен алгоритм с линейной оценкой сложности по п и экспоненциальной оценкой сложности по т. От структуры пересечений групп набора Г зависит сложность алгоритма в среднем, которая остается приемлемой при т < 15 и п в пределах десятков тысяч.

В главе V рассмотрен возможный подход к управлению структурой организационной системы в динамике. Изменение внешних "условий существования" организационной системы может приводить к необходимости решения последовательности статических оптимизационных задач, что мотивирует актуальность постановки и решения динамической задачи об оптимальной иерархии. В этом случае кроме эффективности структуры необходимо учитывать и "гибкость" ее перестроения при изменениях среды. В данной главе предложена одна из возможных динамических моделей количественного анализа проблемы оптимального баланса "статической" и "динамической" эффективности структуры организационной системы. Динамическая оптимизация напрямую связана и с проблемой выбора оптимального числа уровней иерархии в зависимости от внешних условий, которая обсуждается в большинстве работ (см., например, [44, 56]) лишь качественно.

Значение функционала интерпретируется как стоимость функционирования (затраты) системы с соответствующей структурой в течение единицы времени. Возможный способ выбора функционала на основе эмпирических данных рассмотрен в начале главы.

В §1 главы V, исходя из известных величин стоимости включения и исключения каждого из элементов в группу, с помощью решения ряда задач о назначении определена содержательно интерпретируемая метрика на множестве графов организации - стоимость реорганизации.

В §2 главы V описана динамическая модель структурных изменений. Считаем, что в течение каждой единицы времени структура системы должна представлять собой граф организации набора групп {, го есть организовывать взаимодействие исполнителей (элементов) в некоторых группах, заданных "внешней средой". В следующей единице времени может появиться необходимость в организации новых групп, и наоборот, отпасть необходимость в старых группах (например, при увеличении спроса на одни изделия и снижении на другие).

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

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

В §3 главы V проведено численное исследование модели управления структурными изменениями. Для моделирования использован функционал (I) (см. §2 гл. II). /-усечения строятся с помощью алгоритмов главы IV, то есть усекается оптимальная последовательная организация.

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

В заключение работы кратко изложим основные результаты и выводы:

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

2. Доказана оптимальность дерева для монотонного функционала стоимости, 2-организации - для выпуклого функционала, веерной организации - для вогнутого функционала, последовательной организации - для существенно выпуклого функционала.

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

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

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

1. Айзерман М.А., Гусев Л.А., Петров C.B. и др. Динамические подходы к анализу структур, описываемых графами (основы графодинамики). Часть 1 // Автоматика и телемеханика. 1979. №7. С. 135-151.

2. Айзерман М.А., Гусев Л.А., Петров C.B. и др. Динамические подходы к анализу структур, описываемых графами (основы графодинамики). Часть 2 // Автоматика и телемеханика. 1979. №9. С. 123-136.

3. Базилевич Л.А. Обоснование нормативов управляемости на модели трудоемкости руководства. В кн.: Повышение эффективности управления объединениями и отраслями промышленности. Новосибирск, 1977.

4. Браверман Э.М., Дорофеюк A.A., Лумельянский В.Я. и др. Диагонализация матрицы связей и выявление скрытых факторов. В кн.: Проблемы расширения возможностей автоматов. Вып. 1. М., 1971.

5. Бурков В.Н., Кондратьев В.В. Механизмы функционирования организационных систем. М.: Наука, 1981.

6. Бурков В.Н. Основы математической теории активных систем. М.: Наука, 1977.

7. Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении организационными системами. М.: Синтег, 2001.

8. Бурков В.Н., Новиков Д.А. Теория активных систем и задачи организационного управления / Труды международной научно-практической конференции «Теория активных систем». Москва: ИПУ РАН, 19-21 ноября 2001. Том 1. С. 12-16.

9. Бурков В.Н., Новиков Д.А. Теория активных систем: состояние и перспективы. М.: Синтег, 1999.

10. Власюк Б.А., Моросанов Н.С. Синтез иерархической структуры управления в больших системах // Автоматика и телемеханика. 1973. №3.

11. Воронин A.A. Устойчивое развитие миф или реальность? // Математическое образование. 2000. №1(12). С. 59-67.

12. Воронин A.A., Мишин С.П. Алгоритмы поиска оптимальной структуры организационной системы // Автоматика и телемеханика. 2002. №5. С. 120-132.

13. Воронин A.A., Мишин С.П. Математическое моделирование устойчивого развития организационных систем / Труды международной научно-практической конференции «Теория активных систем». Москва: ИПУ РАН, 19-21 ноября 2001. Том 1. С. 28-29.

14. Воронин A.A., Мишин С.П. Моделирование структуры организационной системы. Об алгоритмах поиска оптимального дерева // Вестн. Волг, ун-та. 2001. Сер. 1: Математика. Физика. С. 93-113.

15. Воронин A.A., Мишин С.П. Модель оптимального управления структурными изменениями организационной системы // Автоматика и телемеханика. 2002. №8. С. 136150.

16. Губко М.В. Структура оптимальной организации континуума исполнителей // Автоматика и телемеханика. 2002. №12. С. 116-130.

17. Губко М.В., Мишин С.П. Оптимальная структура системы управления технологическими связями / Материалы международной научной конференции «Современные сложные системы управления». Старый Оскол: СТИ, 27-29 ноября 2002. С. 50-54.

18. Губко М.В., Новиков Д.А. Теория игр в управлении организационными системами. М.: Синтег, 2002.

19. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. М.: Мир, 1982.

20. Дедиков Э.А., Ершов С.Г. Определение критериев формирования структур обработки информации // Управляющие системы и машины. 1973. №1.

21. Дементьев В.Т., Ерзин А.И., Ларин P.M. и др. Задачи оптимизации иерархических структур. Новосибирск: Изд-во Новосиб. ун-та, 1996.

22. Дорофеюк А.А. Алгоритмы автоматической классификации (обзор) // Автоматика и телемеханика. 1971. №12.

23. Дружинин В.В., Конторов Д.С. Проблемы системологии. М.: Сов. радио, 1976.

24. Дубовский C.B., Уздемир А.П. Критерии оптимальности и вариационные подходы в динамических моделях экономики // Автоматика и телемеханика. 1974. №6.

25. Лейбкинд А.Р., Рудник Б.Л., Чухнов А.И. Математические методы синтеза организационных структур управления. Препринт. М., Всесоюзный научно-исследовательский институт системных исследований, 1978.

26. Месарович М., Мако Д., Такахара И. Теория иерархических многоуровневых систем. М.: Мир, 1973.

27. Миркин Б.Г. Задача классификации (обзор). В кн.: Сложные системы. Новосибирск, 1975.

28. Миркин Б.Г. Модели качественного анализа социально-экономической информации. В кн.: Математика в социологии: моделирование и обработка информации. М., 1977.

29. Мишин С.П. Оптимальное управление структурой организационной системы / Сборник трудов международной научно-технической конференции «Современные сложные системы управления». Липецк, 12-14 марта 2002. С. 101-102,

30. Мишин С.П. Оптимизация иерархических структур / Материалы международной научной конференции «Современные сложные системы управления». Старый Оскол: СТИ, 2002. С. 100-105.

31. Мишин С.П. Стоимость реорганизации структуры системы // Тр. кафедры математ. анализа и теории функций Волг, ун-та. 2002. С. 178-198.

32. Мишин С.П. Структура многоуровневой системы в изменяющейся внешней среде / Труды международной научно-практической конференции «Теория активных систем». Москва, 19-21 ноября 2001. Том 1. С. 54-55.

33. Наумчук О.Ф., Саввин Г.Г. Методы анализа сетей передачи и распределения информации. В кн.: Сети передачи информации и их автоматизация. М., 1965.

34. Новиков Д.А. Механизмы функционирования многоуровневых организационных систем. М.: Фонд «Проблемы управления», 1999.

35. Новиков Д.А. Типология задач управления организационными структурами / Материалы международной научной конференции «Современные сложные системы управления». Старый Оскол: СТИ, 27-29 ноября 2002. С. 110-115.

36. Новиков Д.А., Петраков С.Н. Курс теории активных систем. М.: Синтег, 1999.

37. Овсиевич Б.И. Модели формирования организационных структур. Л.: Наука, 1979.

38. Поваров Г.Н. О структурной теории сетей связи. В кн.: Проблемы передачи информации. Вып. 1. М., 1959.

39. Рубинштейн М.И. Задачи синтеза иерархических систем управления. В кн.: Согласованное управление. М., 1975.

40. Харди Г.Г., Литтльвуд Дж.Е., ПолиаГ. Неравенства. М.: Иностранная литература, 1948.

41. Цвиркун А.Д. Основы синтеза структуры сложных систем. М.: Наука, 1982.

42. Яблонский C.B. Введение в дискретную математику. М.: Высш. 1Пк., 2001.

43. Bensoussan A., Hurst E.G., Naslund В. Management applications of modem control theory. Amsterdam-Oxford-New York, 1974.

44. Carzo R.J., Janouzas J.N. Effects of flat and tall organization structure. Administrât. Sci. Quart., 1969, vol. 14, no. 2.

45. Chapple E., Sayles L. The measure of management. N. Y., 1961.

46. Conrath D.W. Communications environment and its relationship to organizational structure. -Manag. Sci., 1974, vol. 20, no. 4.

47. Davies G., Smith M., Twigger W. Leading people: a model of choice and fate for leadership development. Leadership & organization development, 1991, vol. 12, no. 1, pp. 7-11.

48. Huffman D.A. A method for the construction of minimum-redundancy codes. Proc. IRE, 1952, no. 9, pp. 1098-1101.

49. Jago A.G., Vroom V.H. Perceptions of leadership style: superior and subordinate descriptions of decision-making behavior. In Leadership Frontiers, ed. Hunt J.G, Larson L.L. Carbondale: Southern Illinois university press, 1975, pp. 103-120.

50. Manz C.C., Sims H.P. Leading workers to lead themselves: the external leadership of self-managing work teams. Administrât. Sci. Quart., 1987, pp. 106-129.

51. McMillan B. Two inequalities implied by unique decipherability. IRE Trans., 1956. IT-2, no. 4, pp. 115-116.

52. Miller E.J. Technology, territory and time. Human Relations, 1959, vol. 12.

53. Oldman G.R., Hackman J.R. Relationships between organization structure and employee reactions: comparing alternative frameworks. Administrât. Sci. Quart., 1981, pp. 66-83.

54. Peters T. Thriving on chaos. N. Y.: Knopf, 1987.

55. Senge P. The fifth discipline: the art and practice of the learning organization. N. Y.: Doubleday/Currence, 1990.

56. Worthy J.C. Organization structure and employee morale. Amer. Sociol. Rev., 1950, vol. 15, no. 1.

57. Печатные работы автора по теме диссертации приведены в общем списке литературы под номерами 12., [13], [14], [15], [17], [29], [30], [31], [32] (9 работ).