WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 22 | 23 || 25 | 26 |

Результат управления структурой при каждом t складывается из затрат на функционирование системы, определяемых функционалом P (см. введение к главе), и из затрат на реструктуризацию (Gt-1,Gt ) (см. §1), то есть из стоимости создания (построения) структуры Gt из сложившейся к началу единицы времени t структуры Gt-1. Считаем, что в первый момент времени структура G1 “уже имеется” и не требует затрат на построение (G0 = G1). Общий результат управления структурой В определении суммарные затраты делятся на T, то есть вычисляются удельные затраты на единицу времени. При фиксированном T это никак не влияет на оптимальность управления. Во введении и заключении затраты названы суммарными для краткости.

1 T зависит от динамики внешней среды f, f и от управления, определяющего структуры G1,,GT.

Определение 5.11. Оптимальным управлением назовем управление структурой, минимизирующее результат, то есть 1 T arg min R(f, f, ).

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

Если имеется некоторый прогноз – вероятностное распределение динамики внешней среды, то можно определить управление, оптимальное в среднем.

Определение 5.12. Оптимальным в среднем управлением назовем управление структурой, минимизирующее средний 1 T результат, то есть arg min R(f, f, ), где математическое 1 T ожидание берется по динамике внешней среды f, f с известным распределением.

Задача об оптимальном управлении представляется весьма сложной для аналитического решения. Однако, если отображения 1,,T эффективно вычисляются, то результат управления 1 T структурой при заданной динамике внешней среды f, f также может быть эффективно вычислен. Таким образом, если рассматривается набор эффективно вычисляемых управлений, то среди них можно найти оптимальное. Оптимальное в среднем управление можно вычислить путем замены математического ожидания выборочным средним.

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

Определение 5.13. Для произвольного графа организации G = (V, E) O(N ) уровнем LG (g) вершины g V назовем максимальную длину пути из g в терминальную вершину.

Уровень любой вершины конечен в силу ацикличности графа организации (см. опр. 1.19). Уровень терминальных вершин нулевой, уровень остальных вершин равен максимальной длине цепочки “начальников” данной вершины, то есть максимальной длине пути в терминальную вершину.

Определение 5.14. Уровнем L(G)1 графа организации G = (V, E) O(N ) назовем максимальный уровень вершины графа:

L(G) = max LG (g).

gV Далее в этой главе будем рассматривать множество O(f ) организаций различных наборов групп f с заданным структурным функционалом стоимости. Если в набор f = { f1,, fm-1,{a}} входит элементарная группа {a}, то в случае a f1 fm-удаление {a} из набора f не изменит графов O(f ), а в случае a f1 fm-1 после добавления к графам O({ f1,, fm-1}) изолированной вершины {a} получим графы из O(f ), причем стоимость не изменится в силу структурности функционала. В силу леммы 5.8 добавление изолированных вершин не изменяет также стоимость реорганизации. Таким образом, не ограничивая общности, ниже будем считать, что набор f содержит только неэлементарные группы.

Утверждение 5.5. Для произвольной организации G = (V, E) O(f ) набора групп f = { f1,, fm} выполнено L(G) = тогда и только тогда, когда G – веерная организация.

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

Доказательство. Пусть G – веерная организация. Тогда V состоит из групп f1,, fm и неповторяющихся элементарных групп вида {a}, где a f1 fm, причем ребра в f1,, fm могут идти только из элементарных групп (см. опр. 1.26). Все элементарные группы являются начальными. Все терминальные вершины G входят в набор f = { f1,, fm}. Если бы существовал путь длины два и более из начальной вершины {a} в терминальную вершину fi, то нашлась бы промежуточная вершина g, g > 1, с помощью которой организуется fi, что противоречит определению веерной организации. Таким образом, L(G) = 1.

Пусть L(G) = 1. Если неэлементарная вершина g V не принадлежит набору f, то g не является терминальной и из нее выходит по крайней мере одно ребро. В силу неэлементарности g в нее также входит ребро. То есть в G существует путь длины 2, что противоречит равенству L(G) = 1. Итак, V состоит из групп f1,, fm и элементарных групп вида {a}, где a f1 fm (элементарных групп другого вида быть не может, так как в этом случае найдется терминальная вершина, не входящая в f ). Если элементарная группа {a} повторяется, то хотя бы один из экземпляров {a} неначальный, в него входит ребро из другого экземпляра {a}. Кроме того, {a} f (f содержит лишь неэлементарные группы), следовательно {a} нетерминальная и из нее выходит хотя бы одной ребро. То есть в G существует путь длины 2, что противоречит равенству L(G) = 1. Итак, элементарные группы не повторяются. Группа fi, i = 1, m организуется из элементарных подгрупп, так как иначе в G нашелся бы путь длины 2. То есть G – веерная организация. Утверждение доказано.

Таким образом, веерная организация и только она имеет минимальный уровень среди всех организаций множества O(f ).

Определение 5.15. Для произвольного графа организации G = (V, E) O(f) набора групп f = { f1,, fm} назовем l -усечением графа G, l 1 граф Gl O(f ), который получается в результате следующей процедуры. Удаляем из G неначальные вершины с уровнем, большим или равным l, вместе с инцидентными им ребрами. Получим граф G = (V,E ), где V = (V \{g : LG(g) l}) NG.

Если неначальная вершина g V не покрывается в G подгруппами из QG (g), то добавляем к E ребра ({a}, g) для всех a g \ h. Если для некоторого 1 i m fi V, то hQG (g) добавим к V группу fi, а к E ребра ({a}, fi ) для a fi. В результате получим граф Gl O(f ) организации набора групп f.

Если l > L(G), то никаких перестроений не происходит. При l L(G) в графе Gl останутся начальные вершины и вершины с уровнем l -1 и менее. Следовательно, уровень некоторых начальных вершин будет равен l, то есть выполнено L(Gl ) = l.

Таким образом, Gl получается из G с сохранением l старших уровней иерархии (с номерами от 0 до l -1) и удалением остальных неначальных вершин.

На рис. 5.1 приведен пример графа G организации двух групп f1, f2 и его 2-усечение G2. Выполнено LG ( f2 ) = 2, следовательно при построении G2 вершина f2 будет удалена, а затем организована из входящих в нее элементарных групп.

f1 = {a1,a2,...,a8} f1 = {a1,a2,...,a8} {a1,a2,a3,a4} {a5,a6,a7,a8} {a1,a2,a3,a4} {a5,a6,a7,a8} f2 = {a7,a8} {a1,a2} {a3,a4} {a5,a6} f2 = {a7,a8} {a1} {a2} {a3} {a4} {a5} {a6} {a7} {a8} {a1} {a2} {a3} {a4} {a5} {a6} {a7} {a8} Рис. 5.1. Граф G O({ f1, f2}) организации набора групп { f1, f2} и его 2-усечение G2.

На рис. 5.2 приведен еще один пример 2-усечения графа G O({ f1, f2}). Выполнено LG ({a3, a4}) = 2. Удаляем группу {a3, a4}. Она использовалась при организации групп f1 = {a1, a2, a3,a4} и {a3, a4,a5}. Соответственно, добавляем ребра ({a3}, f1) и ({a4}, f1) для организации группы f1 (группа {a1, a2} и ребро ({a1,a2}, f1) остаются без изменений). Группа {a3,a4, a5} в G2 организована из входящих в нее элементарных групп.

f1 = {a1,a2,a3,a4} f2 = {a3,a4,a5,a6} f1 = {a1,a2,a3,a4} f2 = {a3,a4,a5,a6} {a3,a4,a5} {a3,a4,a5} {a1,a2} {a3,a4} {a1,a2} {a1} {a2} {a3} {a4} {a5} {a6} {a1} {a2} {a3} {a4} {a5} {a6} Рис. 5.2. Граф G O({ f1, f2}) организации набора групп { f1, f2} и его 2-усечение G2.

Итак, для любого графа G O(f ) определение 5.15 дает ряд графов G1,G2,,GL(G) O(f ), первый из которых представляет собой “простейшую“ веерную организацию, последний совпадает с графом G. То есть в графах G1,G2,,GL(G) последовательно “появляются” новые уровни управляющих (неначальных) вершин до тех пор, пока не будет получена исходная организация G.

Определение 5.16. Для l 1 l -управлением структурой l назовем простейшее управление (см. опр. 5.9), которое в каждый t t момент времени t = 1,T имеет вид lt (f ) = Glt, где Glt O(f ) – t t t l -усечение оптимальной на O(f ) организации G* O(f ) набора t групп f, то есть организации, минимизирующей функционал P:

t G* = arg mint P(G).

GO(f ) В каждый момент времени 1-управление 1 определяет веерную организацию заданного внешней средой набора групп.

t-1 t Если в группах наборов f и f нет ни одного общего элемента (группы отличаются “максимально сильно”), то переход от структуры Gt-1 к Gt сопровождается деорганизацией Gt-1 и организацией Gt “с нуля”. По утверждению 5.4 для веерной организации стоимость деорганизации и организации “с нуля” минимальна. То есть в случае максимальных изменений наборов организуемых групп управление 1 минимизирует затраты на 1 T реорганизацию (вторую часть результата (f, f, 1)).

При достаточно большом l = l max управление l max определяет оптимальную (в статике) организацию заданного внешней средой набора групп. То есть управление l max минимизирует суммарные затраты на функционирование системы 1 T (первую часть результата P(f, f,l max )).

Итак, при минимальном и максимальном l получаем в некотором смысле противоположные управления, которые соответствуют минимуму и максимуму уровней иерархии.

Если стоимость реорганизации нулевая, то оптимально управление l max, если функционал P нулевой, то при максимальных изменениях наборов групп оптимально управление 1. В общем случае оптимально1 некоторое “промежуточное” управление l, 1 < l < l max, при котором структуры содержат l уровней иерархии. Таким образом, построен набор простейших управлений.

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

В данном параграфе проводится численное сравнение результатов l -управлений l и находится оптимальное управление lopt.

В главе IV разработаны алгоритмы поиска оптимальной на Op (f ) последовательной организации произвольного набора групп. Для существенно выпуклых функционалов они дают также и оптимальную на O(f ) организацию (см. теор. 1.8). В этом случае применяем вышеуказанные алгоритмы для вычисления l -управлений l. Аналогичным образом поступаем и в случае не существенно выпуклого функционала, используя оптимальную на t Op (f ) организацию для вычисления l -управления вместо t организации, оптимальной на O(f ), и комментируя полученные результаты соответствующим образом.

Имеется ввиду оптимальное среди всех l -управлений.

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

Для моделирования рассмотрим следующий пример. Количество исполнителей (элементов) n = 30, соответственно множество исполнителей N = {a1,, a30}. Определим тридцать групп f1 = {a1, a2,, a12}, f2 = {a2,a3,, a13},…, f30 = {a30, a1,a2,,a11}.

Группы f1,, f30 имеют мощность 12. Группа fi+1 отличается от группы fi тем, что в нее добавлен один исполнитель, а один наоборот убран.

Определим наборы групп f1 = { f1,, f10}, f2 = { f2,, f11}, …,f30 = { f30, f1,, f9}. То есть f1 включает группы с первой по десятую, f2 – со второй по одиннадцатую, и т. д. Рассмотрим организационную систему на протяжении тридцати единиц времени, T = 30. Введем параметр скорости изменения внешней среды 0 s 1. Тогда в качестве набора групп, организуемых в момент t времени t, определим следующий набор f = f1+s(t-1), t = 1,T.

При максимальной скорости s = 1 выполнено f = f1, 2 f = f2,…,f = f30, то есть внешней средой последовательно определяются наборы f1,,f30. При s = 0.5 последовательно определяются наборы f1, f1, f2, f2,,f15, f15. То есть содержательно s – количество новых групп, появляющихся в наборе в течение единицы времени, и количество старых групп, которые удаляются из набора в течение единицы времени. Причем максимальной скоростью изменения мы считаем появление и удаление одной группы по истечению каждой единицы времени.

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

Характер изложенных далее результатов вычислений не меняется, если вместо наборов f1,,f30 рассмотреть случайные наборы из 10 случайных групп мощности 12 (распределение равномерное, то есть вероятность появления всех групп одинакова). Общие тенденции останутся теми же. Таким образом, вместо оптимального управления, рассматриваемого ниже, можно вычислять оптимальное в среднем управление с сохранением характера результатов. Величины 10 и 12 определялись требованием достаточно быстрого поиска оптимальной последовательной организации.

Расчеты проводились при скоростях изменения внешней среды s = 0,04;0,07;0,1;0,2; ;1,0. При минимальной скорости набор организуемых групп меняется один раз на протяжении рассматриваемого промежутка времени t = 1,T. При максимальной скорости – тридцать раз.

В рассматриваемом примере уровень любой последовательt ной организации из Op (f ) равен 11, так как мощности всех организуемых (терминальных) групп равны 12. То есть для t t оптимальной последовательной организации G* Op (f ) выполt t нено L(G* ) = 11. При l = l max = 11 l -усечение Glt организации G* t совпадает с G*. В результате получаем ряд управлений 1, 2,, 11, при которых структура организации имеет соответственно от одного до одиннадцати “управляющих” иерархических уровней.

Таким образом, в данном пункте описана динамика внешней среды. Ниже считаем ее заданной, обозначая через R(l ) результат l -управления, через P(l ) и (l ) – соответственно первую и вторую его части (см. опр. 5.10).

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

Как было отмечено во введении к данной главе, считаем, что затраты на функционирование (первая часть результата управления структурой, см. опр. 5.10) определяются функционалом стоимости P.

Проведем расчеты на примере функционала (I) (см. §2 гл. II), который имеет вид:

P(C(g1),,C(gk )) = [C(g1) + + C(gk ) - max(C(g1),,C(gk ))], где (0;+) – параметр функционала. Считаем, что функция сложности имеет вид C(g) = ( ag C(a)1/ ), где (0,+) – параметр сложности, а C(a) 0 – заданные сложности исполнителей (элементов) a N. Положим C(a) = 1 для любого a N (всех исполнителей считаем однородными, то есть имеющими одинаковую сложность).

Pages:     | 1 |   ...   | 22 | 23 || 25 | 26 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.