Правило Феодалов и построение оптиммальной иерархии - Губко М.В
..pdf«ПРАВИЛО ФЕОДАЛОВ» И ПОСТРОЕНИЕ ОПТИМАЛЬНОЙ ИЕРАРХИИ
М.В. Губко Институт проблем управления им. В.А. Трапезникова
Задачи построения различного рода иерархий – это широкий спектр задач построения организационных структур, организации компьютерных сетей, построения систем сбора информации, создания систем кодирования. В то же время, несмотря на идейное сходство многих из этих задач, аппарат, позволяющий с единых позиций взглянуть на проблему синтеза оптимальных в некотором смысле иерархий, в настоящее время развит недостаточно. Важная работа в этом направлении проведена в работах А.А. Воронина, С.П. Мишина (см., например, [1, 2]) – поставлена задача, доказан ряд результатов о виде оптимальных иерархий (организаций – в терминологии [1]), разработаны численные алгоритмы поиска оптимальной организации.
Данный доклад содержит один общий результат относительно вида оптимальных иерархий.
Иерархия на множестве элементов V – это конечный ациклический граф <V , E V ×V > (V – множество вершин, E – множество дуг). Множество всех иерархий обозначим Ξ . На множестве иерархий определим функционал стоимости иерархии P : Ξ → [0,+∞) . Для произвольной иерархии G Ξ P(G) – ее стоимость.
Задача синтеза оптимальной иерархии – это задача поиска графа минимальной стоимости из некоторого подкласса иерархий Ω Ξ .
Исследовать столь общо поставленную задачу, конечно, невозможно – необходимо вводить ограничения на P и Ω . Одно из таких ограничений
рассматривается ниже. |
|
|
Множество дуг E можно рассматривать, как бинарное |
отношение на |
V и |
определить его транзитивное замыкание по формуле E ∞ = E U E 2 |
∞ |
|
U E 3 U ... = U E k |
[3]. |
|
|
k =1 |
|
В некоторых случаях исследование транзитивных замыканий более удобно, чем самих графов (отношений), поэтому важен вопрос о том, какие графы можно однозначно восстановить по их транзитивному замыканию.
Остовом транзитивного отношения E ∞ назовем граф E':= ϕ(E ∞ ) = E ∞ \ E ∞ E ∞ . E ∞ является транзитивным замыканием остова E' . Функция ϕ(.) взаимно однозначна.
Содержательно ограничения на класс остовов описываются известным еще с феодальных времен правилом: «вассал моего вассала – не мой вассал».
Лемма. Если Ω вместе с любым транзитивным отношением E ∞ содержит и все графы с таким транзитивным замыканием, а удаление из произвольного графа G Ω любой связи удешевляет граф, то граф минимальной стоимости является остовом. ∙
Во многих частных задач условия этой леммы выполнены, что позволяет сузить
множество потенциально оптимальных графов до множества остовов и использовать для решения задачи как сами графы, так и их транзитивные замыкания.
Литература
1.А.А. Воронин, С.П. Мишин. Модель оптимального управления структурными изменениями организационной системы. // Автоматика и телемеханика, №8. с. 136-150, 2002.
2.С.П. Мишин. Оптимизация иерархических структур. // Сборник трудов международной научно-технической конференции "Современные сложные системы управления". Старый Оскол, 27-29 ноября 2002.
3.С.А. Орловский. Проблемы принятия решения при нечеткой исходной информации. – М.: Наука. 1981.