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

Определению 5.1 можно дать следующую содержательную интерпретацию. Для реорганизации группы g в группу h сначала последовательно исключаем те элементы g, которые не входят в h, а затем последовательно включаем те элементы h, которые не входят в g. Сумма (g,h) всех затрат и будет стоимостью реорганизации g в h. Если положить g =, то получим стоимость организации группы h Ус нуляФ, то есть стоимость включения всех элементов группы. Если положить h =, то получим стоимость деорганизации группы g, то есть стоимость исключения всех элементов группы.

Напомним, что через F обозначено множество групп (см. опр. 1.13), через F {} соответственно обозначено множество F с добавленной пустой УгруппойФ. Под множеством групп ниже будем понимать множество с включенной пустой группой.

Сумму по пустому множеству полагаем равной нулю по определению.

Лемма 5.1. Если для всех a N выполнено (a) > 0 и (a) > 0, то для любых групп g, h F {} выполнена первая аксиома метрики: равенство (g, h) = 0 эквивалентно равенству g = h.

Доказательство. (g, h) = ag\h (a) + ah\g (a) = тогда и только тогда, когда g \ h = и h \ g = (в силу (a) > 0, (a) > 0), что эквивалентно условию g = h. Лемма доказана.

Лемма 5.2. Если для всех a N выполнено (a) = (a) = = (a), то для любых групп g, h F {} выполнена вторая аксиома метрики (симметричность): (g, h) = (h, g).

Доказательство. (g,h) = (a) + (a) = (a)+ (a) = ag\h ah\g ah\g ag\h = (h, g). Лемма доказана.

емма 5.3. Для любых групп f, g, h F {} выполнено неравенство треугольника: ( f, h) ( f, g) + (g, h).

Доказательство.Имеем (*) ( f,h) = af \h (a) +ah\ f (a), (**) ( f, g) + (g,h) = a f \ g (a) + ag \ f (a) + ag \h (a) + + ah\ g (a). Рассмотрим a f \ h. Имеем a f, a h. Слага емое (a) входит в выражение (*). Если a g, то a g \ h. Если a g, то a f \ g. В обоих случаях слагаемое (a) также входит в выражение (**). Рассмотрим a h \ f. Имеем a f, a h.

Слагаемое (a) входит в выражение (*). Если a g, то a g \ f.

Если a g, то a h \ g. В обоих случаях слагаемое (a) также входит в выражение (**). Итак, каждое слагаемое, входящее в левую часть неравенства ( f, h) ( f, g) + (g, h), входит и в правую его часть. Лемма доказана.

Утверждение 5.1. Если для всех a N выполнено (a) = (a) = (a) > 0, то стоимость реорганизации является метрикой на множестве групп F {}.

Доказательство следует из лемм 5.1-5.3. Утверждение доказано.

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

В данном пункте на основании метрики на множестве групп, построенной в пункте 1, строится метрика на множестве наборов групп.

Определение 5.2. Стоимостью реорганизации произвольного набора групп Q11 в набор групп Q2 будем называть величину (Q1,Q2 ) = min i=1,k (gi, hi ), где k = max(Q1, Q2 ), набор меньшей мощности дополнен пустыми группами до мощности k, минимум берется по всевозможным разбиениям наборов Q1 и Qна пары (gi, hi ), i = 1,k. Если Q1 - пустой набор, то величину (,Q2 ) назовем стоимостью организации набора Q2 Ус нуляФ.

Если Q2 - пустой набор, то величину (Q1,) назовем стоимостью деорганизации набора Q1.

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

Поясним определение. Предположим, что необходимо реорганизовать некоторый набор (множество) групп Q1 в набор Q2. Рассмотрим две группы: g Q1 и h Q2. Затраты на деорганизацию g и последующую организацию h Ус нуляФ составят (g,) + (, h). Затраты на непосредственную реорганизацию g в h составят (g,h). Второй способ предпочтительнее в силу неравенства (g, h) (g,) + (, h) (см. лемму 5.3).

Поэтому для реорганизации Q1 в Q2 разбиваем эти наборы на пары (g, h) Q1 Q2 и реорганизуем g в h. Если Q1 < Q2, то оставшиеся после разбиения на пары группы набора Qорганизуем Ус нуляФ. А если Q1 > Q2, то оставшиеся группы Набор групп Q - некоторое множество групп, в частности пустое. Q - количество групп в наборе (мощность). В наборе могут быть одинаковые (повторяющиеся) группы.

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

Разбиение на пары производим таким образом, чтобы стоимость реорганизации была минимальна. Если Q1 - пустой набор, то получим стоимость организации набора Q2 Ус нуляФ (или сумму стоимостей организации всех групп набора Ус нуляФ), если Q2 - пустой набор, то получим стоимость деорганизации набора Q(или сумму стоимостей деорганизации всех групп набора).

емма 5.4. Добавление к любому из наборов групп Q1, Qпроизвольного числа пустых множеств не меняет значения (Q1,Q2 ).

Доказательство. Обозначим k1 = Q1, k2 = Q2, k = max(k1,k2).

При вычислении (Q1,Q2 ) к Q1 добавляется k - k1 пустых множеств, к Q2 добавляется k - k2 пустых множеств. Обозначим полученные после добавления наборы через Q1 и Q2. Далее выбираются пары (gi,hi ) Q1 Q2, i = 1,k так, чтобы i=1,k (gi, hi ) была минимальна.

Добавим к одному из наборов Q1, Q2 пустые множества.

Обозначим мощность полученного набора через k. Если k k, то при вычислении (Q1,Q2 ) снова получим наборы Q1 и Q2, то есть не изменим (Q1,Q2 ).

Если k > k, то при вычислении (Q1,Q2 ) получим наборы j Q1 и Q2, где Q получается из Qj добавлением k - k пустых множеств, j = 1, 2. Наборы Q1 и Q2 можно разбить на пары следующим образом: сохраним разбиение наборов Q1 и Q2, оставшиеся пары состоят из пустых множеств. Учитывая (,) = 0, получим, что (Q1,Q2 ) (Q1,Q2 ) = (Q1,Q2 ).

Рассмотрим разбиение наборов Q1 и Q2 на пары (gi,hi ) Q1 Q2, i = 1,k, при котором (Q1,Q2 ) = i=1,k (gi, hi ). Если в нем есть две пары вида (g,), (, h), g, h, то переформируем их в пары (g,h), (,). При таком разбиении снова получим (Q1,Q2), так как сумма не увеличилась в силу (g, h) (g,) + (, h) (см. лемму 5.3), (,) = 0. Повторяя такие действия, получим в результате разбиение, в котором нет двух пар вида (g,), (, h).

Такое разбиение может быть получено из некоторого разбиения наборов Q1 и Q2 добавлением пар, состоящих из пустых множеств. Таким образом, (Q1,Q2 ) = (Q1,Q2 ) (Q1,Q2 ). То есть (Q1,Q2 ) = (Q1,Q2 ). Лемма доказана.

емма 5.5. Если для любых групп f и g выполнена первая аксиома метрики, то и для любых наборов непустых групп Q1 и Qтакже выполнена первая аксиома метрики: равенство (Q1,Q2 ) = эквивалентно равенству Q1 = Q2.

Доказательство. (Q1,Q2 ) = 0 тогда и только тогда, когда Q1 = Q2 = k, так как иначе добавляются пустые множества, а (g,) > 0 и (, h) > 0 для любых непустых групп g и h. Далее имеем (Q1,Q2 ) = min i=1,k (gi, hi ) = 0 тогда и только тогда, когда наборы Q1 и Q2 разбиваются на пары (gi, hi ), для которых (gi,hi ) = 0, то есть на пары одинаковых множеств, что возможно лишь при Q1 = Q2. Лемма доказана.

емма 5.6. Если для любых групп выполнена вторая аксиома метрики, то и для любых наборов групп Q1 и Q2 также выполнена вторая аксиома метрики (симметричность): (Q1,Q2 ) = (Q2,Q1).

Доказательство. Добавим пустые множества так, чтобы наборы Q1 и Q2 содержали одинаковое количество k множеств.

Тогда имеем (Q1,Q2) = min i=1,k (gi, hi ) = mini=1,k (hi, gi ) = = (Q2,Q1). Лемма доказана.

емма 5.7. Для произвольных наборов групп Q1, Q2, Qвыполнено неравенство треугольника: (Q1,Q3) (Q1,Q2) + (Q2,Q3).

Доказательство. Обозначим k = max(Q1, Q2, Q3 ). Добавим к Q1, Q2, Q3 пустые множества так, чтобы k = Q1 = Q2 = Q3. По лемме 5.4 это не изменит величин (Q1,Q3), (Q1,Q2 ), (Q2,Q3).

Предположим, что ( fi, gi ), i = 1, k - разбиение множеств Q1 и Qна пары, которое соответствует значению (Q1,Q2 ), а (gi,hi ), i = 1,k - разбиение множеств Q2 и Q3 на пары, которое соответствует значению (Q2,Q3), тогда имеем: (Q1,Q2)+ (Q2,Q3) = = i=1,k[ ( fi, gi ) + (gi,hi )] i=1,k ( fi,hi ) (Q1,Q3), где последнее неравенство выполнено в силу того, что (Q1,Q3) соответствует разбиению наборов групп Q1 и Q3 на пары с минимальной суммарной стоимостью реорганизации. Лемма доказана.

Утверждение 5.2. Если для всех a N выполнено (a) = (a) = (a) > 0, то стоимость реорганизации является метрикой наборах непустых групп.

Доказательство. По утверждению 5.1 стоимость реорганизации любых групп удовлетворяет первой и второй аксиомам метрики и неравенству треугольника. По леммам 5.5-5.этого достаточно для того, чтобы те же свойства выполнялись для любых наборов непустых групп. Утверждение доказано.

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

Определение 5.3. Для произвольных ориентированных графов G1 = (V1, E1) и G2 = (V2, E2 ), вершины которых являются группами (V1,V2 F {}), стоимостью реорганизации G1 в Gназовем величину (G1,G2 ) = min i=1,k (QG1 (gi ),QG2 (hi )),1 где k = max(V1, V2 ), множество вершин меньшей мощности дополнено изолированными вершинами до мощности k, минимум берется по всевозможным разбиениям множеств V1 и V2 на пары (gi, hi ), i = 1, k. Если G1 = (,) - пустой граф, то величину (,G2 ) назовем стоимостью организации графа G2 Ус нуляФ. Если G2 = (,) - пустой граф, то величину (G1,) назовем стоимостью деорганизации графа G1.

Через QG (g) обозначено множество (набор) вершин, которые непосредственно подчинены g, то есть из которых идут ребра в g в графе G1. Аналогично QG (h) - вершины, непосредственно подчиненные h в G2.

Задача о поиске разбиения на пары минимальной суммарной стоимости является задачей о назначениях (см., например, [7]).

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

Поясним определение. Пусть G1 = (V1, E1) O(N) и G2 = (V2, E2 ) O(N) - графы организации над некоторым множеством элементов N (см. опр. 1.19). Предположим, что G1 необходимо реорганизовать в G2. Рассмотрим вершины g V1 \ NG1 и h V2 \ NG2. Они организуются из наборов подгрупп QG1 (g) и QG2 (h) соответственно. Необходимо некоторым образом УперестроитьФ звено ZG1 (g) в звено ZG2 (h).1 Для подгрупп h1 QG1 (g) и h2 QG2 (h) проделаем следующее: освободим (деорганизуем) элементы из h1 \ h2 от участия в группе g, а затем привлечем (организуем) элементы из h2 \ h1 к участию в группе h. Аналогично поступаем и с другими парами групп из QG1 (g) QG2 (h).

Минимальная стоимость таких перестроений составит (QG1 (g),QG2 (h)) (см. опр. 5.2). Стоимость освобождения всех элементов от участия в g и привлечения к участию в h составит (QG1 (g),) + (,QG2 (h)), что не меньше (QG1 (g),QG2 (h)) в силу неравенства треугольника (см. лемму 5.7).

Таким образом, для реорганизации G1 в G2 разобьем множества V1 и V2 на пары (g,h) V1 V2 и реорганизуем QG1 (g) в QG2 (h). Если V1 < V2, то оставшиеся после разбиения на пары группы V2 организуем Ус нуляФ из соответствующих подгрупп. А если V1 > V2, то для оставшихся групп V1 УразрушимФ их организацию из подгрупп. Таким образом, одно из множеств Vили V2 дополняем изолированными вершинами до достижения мощности другого. Разбивая полученные множества вершин на пары и суммируя стоимость реорганизации соответствующих наборов подгрупп, получим стоимость реорганизации графа G1 в Звено состоит из вершины-центра, непосредственно подчиненных ей вершин и ребер, соответствующих этим подчинением (см. опр. 1.5).

граф G2. Разбиение на пары производим таким образом, чтобы стоимость реорганизации была минимальна.

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

емма 5.8. При добавлении к любому из графов G1 = (V1, E1) и G2 = (V2, E2 ) любого числа изолированных вершин стоимость реорганизации (G1,G2 ) не изменится.

Доказательство. Обозначим k1 = V1, k2 = V2, k = max(k1,k2 ).

При вычислении (G1,G2 ) к V1 добавляется k - k1 изолированных вершин, к V2 добавляется k - k2 изолированных вершин. Обозна чим полученные множества вершин через V1 и V2. Далее выбира ются пары (gi,hi )V1V2, i =1,k так, чтобы i=1,k (QG1(gi ),QG2 (hi )) была минимальна. Добавим к одному из множеств V1 или Vизолированные вершины. Обозначим мощность полученного множества вершин через k, а соответствующие графы через G3 и G4. Если k k, то при вычислении (G3,G4 ) снова получим множества вершин V1 и V2, то есть (G3,G4 ) = (G1,G2 ).

Если k > k, то при вычислении (G3,G4 ) получим множества вершин V1 и V2, где Vj образуется из Vj добавлением k - k изолированных вершин, j = 1,2. Множества V1 и V2 можно разбить на пары следующим образом: сохраним разбиение для V1, V2, оставшиеся пары (g,h) состоят из изолированных вершин, следовательно (QG3 (g),QG4 (h)) = (,) = 0. Таким образом, (G3,G4 ) (G1,G2 ). Рассмотрим разбиение множеств V1 и V на пары (gi,hi ) V1 V2, i = 1,k, при котором (G3,G4) = = i=1,k (QG3 (gi ),QG4 (hi )). Если в нем имеются две пары вида (Q(g),) и (,Q(h)), где Q(g) и Q(h), то переформируем их в пары (Q(g),Q(h)) и (,). При таком разбиении снова получим (G3,G4 ), так как сумма не увеличилась в силу неравенства треугольника (см. лемму 5.7) (Q(g),Q(h)) (Q(g),) + + (,Q(h)) и равенства (,) = 0. Повторяя такие действия, получим в результате разбиение, в котором нет двух пар вида (Q(g),) и (,Q(h)). Такое разбиение может быть получено из некоторого разбиения множеств V1 и V2 добавлением пар (g,h), состоящих из изолированных вершин, для которых (Q(g),Q(h)) = = (,) = 0. Таким образом, (G1,G2) (G3,G4). То есть (G1,G2 ) = (G3,G4 ). Лемма доказана.

емма 5.9. Если для любых наборов непустых групп выполнена первая аксиома метрики, то и для любых графов организации G1 = (V1,E1)O(N) и G2 = (V2,E2)O(N) без изолированных вершин также выполнена первая аксиома метрики: равенство (G1,G2) = 0 эквивалентно равенству G1 = G2 (V1 =V2 и E1 = E2).

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