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

c(s1,,sk ) c(s1,, s ) + c(s1 s, s,...,sk ). (*) j j j +Перестроим иерархию. Непосредственно подчиним сотрудников v1,Е,vj менеджеру m вместо менеджера m1. Менеджера mудалим. Перестроенный фрагмент графа выглядит так, как показано на рисунке 29a). Менеджер m по-прежнему управляет всеми исполнителями. То есть в результате получили иерархию. Группы, подчиненные остальным менеджерам, также не изменились. В построенной иерархии затраты менеджера m (левая часть неравенства (*)) не превышают затрат менеджеров m и m1 в исходной иерархии (правая часть неравенства (*)). Следовательно, построенная иерархия оптимальна.

Построенная иерархия удовлетворяет условиям (i) и (ii) утверждения 1. Однако условие (iii) может нарушиться, так как некоторые из сотрудников v1,Е,vj могут быть подчинены некоторым из сотрудников vj+1,Е,vk. Предположим, что сотрудник vj подчинен сотруднику v, 1 j1 j, j +1 j2 k. Тогда в силу леммы j(страница 20) выполнено s s. В силу леммы 4 (страница 28) j1 jможно удалить лишнее ребро (vj,m) без увеличения затрат С.П. Мишин, иерархии. Сотрудник v при этом будет подчинен высшему меjнеджеру, но не непосредственно, а через сотрудника v. Продолjжая подобные удаления, получим оптимальную иерархию, удовлетворяющую условиям (i), (ii) и (iii).

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

Доказательство следствия (из утверждений 6 и 8). По утверждению 6 для монотонной по группам функции затрат найдется оптимальное дерево. В доказательстве утверждения 8 в качестве начальной иерархии H можно рассмотреть это дерево. По лемме 2 в дереве не пересекаются группы, управляемые непосредственными подчиненными одного менеджера. Поэтому среди групп s1,Е,sk в доказательстве утверждения 8 нет пересекающихся. То есть для перестроения иерархии, описанного в доказательстве утверждения 8, достаточно, чтобы функция затрат была расширяющей на непересекающихся группах. После перестроения получим дерево, поскольку у всех сотрудников, кроме высшего менеджера, ровно один непосредственный начальник. После всех перестроений придем к оптимальной двухуровневой иерархии.

Доказательство утверждения 9. Согласно утверждению для сужающей функции затрат найдется оптимальная 2-иерархия H1. В силу утверждения 1 найдется также оптимальная 2-иерархия H, которая удовлетворяет свойствам (i)-(iii) (страница 28). Ниже в доказательстве будем пользоваться условием (i), согласно которому все сотрудники иерархии управляют различными группами. Из условия (i) следует, что каждый менеджер имеет ровно двух непосредственных подчиненных.

Менеджера назовем неправильным, если ему непосредственно подчинены два других менеджера. Если H не содержит неправильных менеджеров, то каждому менеджеру подчинен хотя бы один исполнитель. То есть H - искомая оптимальная последовательная Оптимальные иерархии управления в экономических системах иерархия. Если в H имеются неправильные менеджеры, то будем уменьшать их количество, перестраивая иерархию без увеличения затрат.

Рассмотрим неправильного менеджера m, которому подчинены только правильные менеджеры. m имеет двух непосредственных подчиненных m1 и m2. Правильные менеджеры m1 и m2 непосредственно управляют хотя бы одним исполнителем. То есть менеджер m1 непосредственно управляет некоторым исполнителем w и сотрудником v. Менеджер m2 непосредственно управляет некото рым исполнителем w и сотрудником v. Соответствующий фрагмент иерархии выглядит так, как показано на рисунке 33a).

Обозначим группы, управляемые менеджерами m1 и m2, через s1=sH(m1) и s2=sH(m2). В силу условия (i) утверждения 1 сотрудник не может управлять исполнителем, поскольку в этом случае v w m1 и v' управляли бы одной и той же группой. То есть sH (v ) = s1 \ {w }. Аналогично sH (v ) = s2 \ {w }.

Если для групп s1 и s2 выполнено условие a) определения 11, то без увеличения затрат можно нанять нового менеджера m3 и непосредственно подчинить ему сотрудников v и m2. А менеджеру m непосредственно подчинить исполнителя w и менеджера m3. На рисунке 33b) изображен результат перестроения.

Новый менеджер управляет группой (s1 \{w }) s2. До перестроения затраты менеджера m составляли c(s1,s2). В новой иерархии изменились только затраты менеджера m и добавились затраты m3. Таким образом, разница затрат старой и новой иерархии равна c(s1, s2 ) - c(s1 \{w }, s2 ) - c((s1 \ {w }) s2,{w }) 0. Следовательно, затраты не увеличились и полученная иерархия оптимальна.

Если для групп s1 и s2 выполнено условие b) определения 11, то можно перестроить иерархию аналогичным образом, непосред ственно подчинив менеджеру m исполнителя w. На рисунке 33с) изображен результат перестроения.

Итак, в случае сильно сужающей функции можно построить оптимальную 2-иерархию, в которой менеджер m будет правильным. В построенной иерархии может нарушаться условие (i) утверждения 1, поскольку менеджер m3 может управлять той же С.П. Мишин, группой, что и некоторый менеджер m. В этом случае менеджеру m можно непосредственно подчинить менеджера m вместо m3, а менеджера m3 удалить73. Иерархия при этом останется оптимальной, будет выполнено условие (i), менеджер m останется правильным.

Если менеджер m3 был удален или m3 - правильный менеджер, то построена иерархия, в которой на одного неправильного менеджера меньше, чем в исходной иерархии H. Предположим, что в полученной иерархии остался неправильный менеджер m3. В этом случае ему подчинена меньшая группа, чем менеджеру m. То есть вместо неправильного менеджера m появился неправильный менеджер m3, которому подчинена меньшая группа. Можно повторить перестроение, рассматривая менеджера m3 вместо m. Поскольку число исполнителей, подчиненных неправильному менеджеру, постоянно уменьшается, придем в итоге к оптимальной иерархии, в которой на одного неправильного менеджера меньше, чем в исходной иерархии H.

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

После определения 10 указано, что утверждение 1 справедливо и для последовательных иерархий. Следовательно, найдется последовательная иерархия H*, которая удовлетворяет условиям (i)(iii) утверждения 1 (страница 28). Причем затраты H*, не превышают затрат H2. То есть найдена оптимальная последовательная иерархия H*, имеющая вид, приведенный на рисунке 32.

Доказательство утверждения 10. Рассмотрим некоторый набор групп s1,Е,sk, k 3. Обозначим через z1 левую, через z2 - правую часть в неравенствах (35) и (36) (см. раздел 3.3), которые соответствуют сужающей и расширяющей функции (см. определение 9 на странице 104).

По построению m - единственный непосредственный начальник менеджера m3.

Поэтому такое перестроение не изменит групп, которыми управляют менеджеры, оставшиеся в иерархии, и не изменит их затраты.

Оптимальные иерархии управления в экономических системах Пусть 1. Для произвольного количества сотрудников 1 < j < k и любой перестановки (i1,Е,ik) докажем неравенство (36):

c(s1,,sk ) c(si,, si ) + c(si si, si,...,si ). Введем сле1 j 1 j j +1 k дующие обозначения: x1 = (si ),Е, x = (si ), x =max(x1,Е,xj), j 1 j x=x1+Е+xj, y = (si ), y = (si ),Е, yk = (si ), j+1 j+j +1 j + 2 k y =max(yj+1,Е,yk), y=yj+1+Е+yk, s = si si. Тогда левую и 1 j правую части неравенства (36) можно переписать:

z1 = (x + y - max(x, y )), z2 = (x - x ) + ((s) + y - max(y, (s) )).

В силу неравенства (38) с учетом 1 имеем z2 (x + y + (s) - x - max( y,(s))). Тогда для доказательства неравенства (36) ( z2 z1 ) достаточно доказать:

x + y - max(x, y ) x + y + (s) - x - max(y, (s) ).

Перепишем это неравенство: x + max(y, (s) ) (s) + max(x, y ).

При y (s) неравенство имеет вид x max(x, y ). То есть неравенство выполнено. При y > (s) неравенство имеет вид x + y (s) + max(x, y ). Имеем y max(x, y ), x (s), поскольку s = si si. То есть неравенство (36) выполнено.

1 j Следовательно, при 1 функция (I) - расширяющая.

Пусть 1. Считаем, что (s1) = max((s1),, (sk )) (иначе можно изменить нумерацию групп s1,Е,sk). Рассмотрим две группы s1 и s2 (j=2) и перестановку (1,2,Е,k). Докажем для них неравенство (35): c(s1,,sk ) c(s1, s2 ) + c(s1 s2, s3,...,sk ). Левую и правую части неравенства (35) можно переписать:

z1 = ((s2 ) + + (sk ) ), z2 = (s2 ) + ((s3 ) + + (sk ) ).

В силу неравенства (37) с учетом 1 имеем z1 z2. То есть неравенство (35) выполнено. Следовательно, при 1 функция (I) - сужающая.

Пусть кроме 1 выполнено условие 1. Докажем, что в этой области параметров функция (I) - сильно сужающая (см.

С.П. Мишин, определение 11 на странице 116). Для этого рассмотрим произвольные группы s1 и s2 из двух или более исполнителей. Рассмотрим случай (s1) (s2 ). Обозначим через z1 левую, через z2 - правую часть в неравенстве a) определения 11:

z1 = c(s1, s2 ), z2 = c(s1 \{w},s2 ) + c((s1 \ {w}) s2,{w}), где w - произвольный исполнитель группы s1. Обозначим x = (s1), y = (s1 \{w}), z = ({w}). Тогда z1 = x, z2 = y + z. Заметим, что x=y+z. Тогда неравенство a) определения 11 ( z1 z2 ) имеет вид ( y + z) y + z. В силу неравенства (37) с учетом 1 имеем z1 z2.

Если выполнено (s1) (s2 ), то неравенство b) определения 11 доказывается аналогично с точностью до замены s1 на s2.

Следовательно, при 1 и 1 функция (I) - сильно сужающая.

Доказательство утверждения 11. Рассмотрим некоторый набор групп s1,Е,sk, k 3. Обозначим через z1 левую, через z2 - правую часть в неравенстве (36) (см. страницу 106), которое соответствует расширяющей функции (см. определение 9).

Для произвольного 1 < j < k и любой перестановки (i1,Е,ik) докажем неравенство (36):

c(s1,, sk ) c(si,, si ) + c(si si, si,...,si ).

1 j 1 j j +1 k Введем следующие обозначения s = si si, 1 j x = (si ) + + (si ), y = (si ) + + (si ). Тогда левую и 1 j j +1 k правую части неравенства (36) можно переписать: z1 = (x + y), z2 = x + ((s) + y).

При 1 в силу неравенства (38) выполнено z1 x + y z2. То есть неравенство (36) выполнено. Следовательно, при 1 функция (II) - расширяющая.

Если среди s1,Е,sk нет пересекающихся групп, то можно записать (s) = (si ) + + (si ). При 1 в силу неравенства 1 j Оптимальные иерархии управления в экономических системах (37) выполнено (s) (si ) + + (si ) = x. Тогда имеем 1 j z2 (x + y) = z1. То есть неравенство (36) выполнено. Следовательно, при > 1 и 1 функция (II) - расширяющая на непересекающихся группах.

Заметим, что если группы пересекаются, то неравенство (36) может не выполняться. Пусть, например, s1={w1,w2}, s2={w1,w3},Е, sk-1={w1,wk}, sk={wk+1}, (w1) = (wk +1) = 1, (w2 ) = = (wk ) = 0.

Рассмотрим число сотрудников j=kЦ1 и тождественную переста новку (1,Е,k). Тогда x=kЦ1, y=1, (s) = 1. Имеем z1 = k, z2 = (k -1) + 2. Неравенство (36) имеет вид z1 - z2 0 или k - (k -1) 2. При любом > 1 левая часть возрастает по k.

При достаточно большом k неравенство (36) нарушается. Следовательно, при > 1 и 1 функция (II) не является расширяющей, но является расширяющей на непересекающихся группах.

Осталось показать, что при > 1 и < 1 функция (II) - ни расширяющая, ни сужающая. Покажем, что это выполнено даже на наборах непересекающихся групп.

Рассмотрим набор групп s1={w1},s2={w2},Е,sk={wk}, (w1) = = (wk ) = 1, где k 1 - четное число. Рассмотрим число сотрудников j=k/2 и тождественную перестановку (1,Е,k).

Тогда x=k/2, y=k/2, (s) = (k / 2). Имеем z1 = k, z2 = (k / 2) + ((k / 2) + k / 2). Неравенство (36) имеет вид z2 z 1 1 или + + 1. При < 1 левая часть неравенства 2 2 k1- убывает при увеличении k. При достаточно большом k ее можно сделать сколь угодно близкой к величине 1/ 2 -1. При > 1 эта величина меньше 1. То есть при достаточно большом k неравенство (36) нарушается. Следовательно, при > 1 и < 1 функция (II) не является расширяющей даже на непересекающихся группах.

Рассмотрим набор групп s1={w1}, s2={w2}, s3={w3}, (w1) = (w2 ) = 1, (w3) = 0. Докажем, что для произвольного количества сотрудников 1 < j < 3 (то есть j=2) и любой перестановС.П. Мишин, ки (i1,i2,i3) не выполнено неравенство (35) c(s1,,sk ) c(si,, si ) + c(si si, si,...,si ). Если переста1 j 1 j j +1 k новка имеет вид (1,2,3) или (2,1,3), то неравенство перепишется в виде 2 2 + 2. При всех остальных перестановках неравенство имеет вид 2 1+ 2. Таким образом, не существует 1 < j < 3 и перестановки (i1,i2,i3), для которой выполнено неравенство (35).

Следовательно, функция (II) не является сужающей даже на непересекающихся группах.

Доказательство утверждения 12. Сначала докажем, что при 1 функция (III) - сужающая. Рассмотрим некоторый набор групп s1,Е,sk, k 3. Обозначим через z1 левую, через z2 - правую часть в неравенстве (35) (см. страницу 105), которое соответствуют сужающей функции (см. определение 9). Считаем, что (s1) = max((s1),, (sk )) (иначе можно изменить нумерацию групп s1,Е,sk). Рассмотрим две группы s1 и s2 (j=2) и тождественную перестановку (1,2,Е,k). Докажем для них неравенство (35):

c(s1,,sk ) c(s1, s2 ) + c(s1 s2, s3,...,sk ).

Обозначим x = (s1 sk ), y = (s1 s2 ), z = (s1).

Выполнено z y x. Левую и правую части неравенства (35) можно переписать: z1 = (x / z -1), z2 = (y / z -1) + (x / y -1).74 В силу неравенства (37) с учетом 1 имеем z2 ( y / z -1+ x / y -1). С учетом этой оценки для доказательства неравенства (35) (z2 z1 ) достаточно показать, что x / z -1- y / z +1- x / y +1 0. Преобразовывая левую часть, получим:

(xy + yz - y2 - xz) / yz = (x - y)(y - z) / yz 0.

То есть неравенство (35) выполнено. Следовательно, при функция (III) - сужающая.

При z=0 имеем z1 = +, следовательно, выполнено неравенство.

z1 zДалее считаем.

z > Оптимальные иерархии управления в экономических системах Теперь покажем, что при 1 функция (III) - сильно сужающая (см. определение 11 на странице 116). Для этого рассмотрим произвольные группы s1 и s2 из двух или более исполнителей.

Рассмотрим случай (s1) (s2 ). Обозначим через z1 левую, через z2 - правую часть в неравенстве a) определения 11 (страница 116):

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