Книги по разным темам Pages:     | 1 |   ...   | 19 | 20 | 21 | 22 | 23 |   ...   | 26 |

Доказательство. Пусть G = (V, E) Op (f ) - оптимальная на Op (f ) последовательная организация набора групп f = { f1,, fm}, которая удовлетворяет условиям утверждения 4.3. Сконструируем ~ ~ ~ поддерево D = (VD, ED ) графа H = (VH, EH ). Обозначим через VU множество узловых групп из V : VU = V U. Положим VD =VU {}. Построим множество ребер ED следующим образом.

Рассмотрим g VU. Пусть QG (g) = {g1,{ai1}}. Если g1 VU и g1 > 1, то рассмотрим QG (g1) = {g2,{ai2 }} и повторим рассуждения для g2. И так далее, в итоге дойдем до gk VU или до элементарной группы gk, gk =1. Если gk элементарна, то вершине g в графе G не подчинена никакая другая узловая вершина. Следовательно, не существует g U, g g (см.

условие b утв. 4.3). Если gk VU, то из узловой вершины gk в узловую вершину g в графе G существует путь, не содержащий других узловых вершин. Следовательно, не существует g U, gk g g (см. условие a утв. 4.3). В первом случае ребро ~ ~ (, g) EH, во втором ребро (gk, g) EH. Добавим соответству Под эквивалентностью задач подразумевается, что решение одной задачи можно преобразовать в решение другой и наоборот, причем сложность процедуры преобразования УнесущественнаФ по сравнению со сложностью решения самих задач. Например, сложность построенных в доказательстве теоремы преобразований линейно зависит от числа вершин графа организации G или поддерева D.

ющее ребро в ED. Вес добавленного ребра будет равен суммарной стоимости организации вершин gk-1, gk-2,, g1, g.

Покажем, что в результате действительно получим поддерево ~ D графа H. В каждую вершину D, кроме, входит ровно одно ребро. D содержит все неэлементарные группы набора f, так как они являются узловыми. Если некоторая группа h VU не является терминальной в G, то из нее в графе G существует путь в некоторую узловую вершину g, не содержащий других узловых вершин. При построении D будет добавлено ребро (h, g), то есть h не является листом D. Следовательно, листья D могут содержаться только среди терминальных вершин G, то есть среди групп набора f.

Покажем, что P(G) = (D). Пусть h V \ NG. Если h - узловая, то в нее в дереве D входит ребро e, вес которого (e) включает в себя стоимость P(QG (h)) организации h. Если h - не узловая, то h f и по утверждению 4.2 из h выходит ровно одно ребро. Следовательно, существует единственный путь из h в некоторую узловую вершину g, не содержащий других узловых вершин. В дереве D в g входит ребро e, вес которого (e) включает в себя стоимость P(QG (h)) организации h. Итак, стоимость организации каждой неэлементарной подгруппы графа G входит в вес ребер D один и только один раз. Имеем P(G) = (D).

~ Обратно, пусть D = (VD, ED ) - поддерево графа H.

Построим последовательную организацию G = (V, E). Добавим в V вершины (VD {{a1}, {an}}) \ {}. Пусть g VD \ {}. В дереве D в нее входит ровно одно ребро e = (h, g). Пусть hj = h {ai1,,aij} g \ h ={ai1,,aik }. Тогда добавим в V вершины, j = 1,k -1 (кроме элементарной {ai1} при h = ), организовав hj из h и {aij }, где h0 = h. Группа g организуется из hk -1 и {aik }.

j-Сумма стоимостей организации g и добавленных в V вершин будет равна (e). В результате построим G Op (f ), так как D содержит все группы набора f, причем P(G) = (D).

~ Итак, каждому поддереву D графа задачи H соответствует одна и только одна последовательная организация G Op (f ), причем стоимость организации равна весу соответствующего поддерева. То есть задачи о последовательной организации минимальной стоимости и о поддереве минимального веса эквивалентны. Теорема доказана.

~ Задачу об оптимальном поддереве в H можно решить точно так же, как и задачу об оптимальном поддереве в H, то есть ~ нормализовав H (см. опр. 4.4) и применив теорему 4.2 к полученному нормализованному графу. Этот факт справедлив, так как пункты 2 и 3 з1 не используют никаких свойств графа H, ~ кроме ацикличности, то есть могут быть применены и к графу H.

Пример найденной алгоритмом оптимальной последовательной организации приведен на рис. 5.3.

~ Количество вершин графа H независимо от n ограничено величиной 2m, так как число узловых групп не превышает 2m -1.

Это позволяет пересмотреть верхнюю оценку сложности алгоритма (см. следствие 1 из теор. 4.2) для функционала вида P( g1,, gk, g ).

Следствие 2 (из теоремы 4.2). Для функционала вида P( g1,, gk, g ) существует алгоритм, решающий задачу об оптимальной последовательной организации путем сравнения менее 222m3m весов поддеревьев нормализованного графа задачи ~ ~ ~ H = (Vnorm, Enorm ).

norm ~ ~ ~ Доказательство. Граф H = (VH, EH ) содержит не более 2m вершин, из каждой выходит не более 2m -1 ребер. Следовательно, ~ ~ конструируя граф H, добавим к Vnorm не более 2m+1 - norm ~ вершин для каждой вершины из VH (см. опр. 4.4). Всего добавим ~ ~ не более 22m+1 - 2m+1 вершин. Итак, V2 (H ) Vnorm < 222m (см.

norm теор. 4.2), что и доказывает следствие.

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

При этом только сложность первого и последнего этапов зависят от числа элементов n. Сложность последнего этапа несущественна (линейно зависит от числа вершин в графе организации), поэтому ~ считаем, что от n зависит лишь сложность построения H. При ~ построении H для поиска пересечения групп или для определения вложенности одной группы в другую можно проанализировать соответствующие группам двоичные вектора длины n.1 Число ~ вершин и ребер H от n не зависит.2 То есть сложность процедуры ~ построения H зависит от n линейно. Наибольшую сложность имеет этап поиска оптимального поддерева в нормализованном графе (алгоритм теор. 4.2). Таким образом, при увеличении n линейно возрастает меньшее слагаемое суммарной сложности, что позволяет решать задачу для больших значений n.

Аналогично пункту 3 з1 можно оценить сложность алгоритма в среднем, генерируя случайным образом набор групп (элемент входит в группу с вероятностью 0,5) и оценивая сложность по нескольким тестам. Как и в общем случае, сложность остается приемлемой, если m не превосходит полутора десятков, независимо от значения n.Кратко подведем итоги данной главы. Как показывает пункт 1 з2, даже для функционала вида P( g1,, gk, g ) и мощностей всех групп набора f = { f1,, fm} не более трех не существует полиномиального по m алгоритма, решающего задачу об оптимальной на Op (f ) последовательной организации (если P NP, см. теор. 4.3). Алгоритм с линейной оценкой сложности по числу элементов n и экспоненциальной оценкой сложности по числу групп m для функционала вида P( g1,, gk, g ) построен в пункте 3 з2. Алгоритм основан на поиске поддерева графа задачи ~ H, число вершин которого определяется структурой пересечений групп набора f (см. опр. 4.5 и 4.6). Таким образом, Фпри более сложнойФ структуре пересечений сложность алгоритма возрастает и наоборот. В среднем сложность алгоритма приемлема при m независимо от значения n в пределах десятков тысяч.

i -я компонента вектора определяет, входит элемент ai в группу или нет.

Эти величины определяются структурой пересечений групп набора f = { f1,, fm}.

Имеется в виду УразумноеФ значение в пределах нескольких десятков тысяч.

Для случая структурного функционала общего вида задача значительно усложняется, так как на оптимальность последовательной организации могут влиять порядка n2n значений функционала вместо n значений для функционала вида P( g1,, gk, g ). Следствие 2 к теореме 4.1 показывает, что даже при m = 1 любой алгоритм должен вычислить порядка n2n значений P. В то же время вычисления такого количества значений достаточно для построения графа задачи H (см. опр.

4.1), а следовательно и для решения задачи (см. теор. 4.1). Пункты 2 и 3 з1 представляют собой построение алгоритма, порядок сложности которого в худшем случае n2n3m (см. следствие 1 к теор. 4.2). В среднем сложность алгоритма также зависит от УсложностиФ структуры пересечений групп набора f.

Тестирование алгоритма на различных наборах (см. таблицу 4.1) показывает, что при m, n 15 сложность остается приемлемой.

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

Данная глава показывает, что задача об оптимальной организации нескольких групп весьма сложна. Если группы набора f пересекаются сложным образом, то необходимо выбирать промежуточные группы с учетом того, что они могут использоваться для организации нескольких групп набора f. То есть в общем случае при объединении оптимальных организаций для каждой из групп получим неоптимальную организацию набора групп. Для структурного функционала общего вида представляется сомнительным существование эффективных алгоритмов решения задачи об оптимальной организации набора групп на ~ ~ множествах O(f ), Or (f ), O(f ), Or (f ) даже для малых значений n и m. Поэтому перспективным направлением исследования является поиск классов структурного функционала, для которых задача упрощается. Например, для существенно выпуклых функционалов достаточно решить задачу на Op (f ), чтобы получить решение на всех вышеуказанных множествах (см. теор. 1.8).

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

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

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

Если структура описывается ориентированным ациклическим графом, то моделирование сводится к поставленной в главе I задаче об оптимальной иерархии. Таким образом, приведенные ранее примеры частных постановок (см. гл. II) одновременно являются примерами статических моделей, а весь аппарат глав I - IV может использоваться для статического моделирования в случае структурного функционала стоимости. Ключевым моментом при определении статической модели является выбор функционала. Для различных примеров организационных систем (например, для отраслей промышленности) накоплен огромный эмпирический материал, позволяющий определить некоторые агрегированные параметры структуры. Например, норма управляемости (максимальное число подчиненных) [3], численность управленческого персонала [25] и т. п. Такие исследования позволяют сравнивать некоторые УтипичныеФ структуры и выбирать из них наиболее подходящую для конкретной системы. Тестирование функционалов на этих УтипичныхФ вариантах позволяет уточнять их вид и параметры, исходя из эмпирических данных и результатов моделирования.

Ниже считаем, что функционал стоимости некоторым образом задан.

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

Выбор структуры, оптимальной в динамике, является ключевой проблемой в некоторых моделях Уустойчивого развитияФ организационных систем (см., например, [11]). Вопрос о выборе критерия оптимальности в динамике для организационных систем не имеет однозначного решения [5, 24]. В отсутствии исчерпывающего прогноза изменений внешней среды постановки оптимизационных задач неизбежно включают в себя элементы эмпирики. Ниже мы рассмотрим один из возможных эмпирических критериев, который при необходимости может быть модифицирован.

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

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

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

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

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

Определение 5.1. Стоимостью реорганизации группы g F {}1 в группу h F {} назовем величину (g, h) = = ag \h (a) + ah\ g (a),2 где (a) 0 - заданная стоимость исключения элемента a из группы, а (a) 0 - заданная стоимость включения элемента a в группу. Величину (,h) назовем стоимостью организации h Ус нуляФ, величину (g,) - стоимостью деорганизации g.

Таким образом, предполагаем, что для любого элемента a N заданы стоимости включения и исключения a из группы.

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

Предполагаем, что стоимость включения (исключения) зависит лишь от самого элемента a, а не от той группы, в которую он включается (из которой исключается).

Pages:     | 1 |   ...   | 19 | 20 | 21 | 22 | 23 |   ...   | 26 |    Книги по разным темам