Правило Феодалов и построение оптиммальной иерархии - Губко М.В.

«ПРАВИЛО ФЕОДАЛОВ» И ПОСТРОЕНИЕ ОПТИМАЛЬНОЙ ИЕРАРХИИ

М.В. Губко Институт проблем управления им. В.А. Трапезникова

Задачи построения различного рода иерархий – это широкий спектр задач построения организационных структур, организации компьютерных сетей, построения систем сбора информации, создания систем кодирования. В то же время, несмотря на идейное сходство многих из этих задач, аппарат, позволяющий с единых позиций взглянуть на проблему синтеза оптимальных в некотором смысле иерархий, в настоящее время развит недостаточно. Важная работа в этом направлении проведена в работах А.А. Воронина, С.П. Мишина (см., например, [1, 2]) – поставлена задача, доказан ряд результатов о виде оптимальных иерархий (организаций – в терминологии [1]), разработаны численные алгоритмы поиска оптимальной организации.

Данный доклад содержит один общий результат относительно вида оптимальных иерархий.

Иерархия на множестве элементов V – это конечный ациклический граф <V , E V ×V > (V – множество вершин, E – множество дуг). Множество всех иерархий обозначим Ξ . На множестве иерархий определим функционал стоимости иерархии P : Ξ → [0,+∞) . Для произвольной иерархии G Ξ P(G) – ее стоимость.

Задача синтеза оптимальной иерархии – это задача поиска графа минимальной стоимости из некоторого подкласса иерархий Ω Ξ .

Исследовать столь общо поставленную задачу, конечно, невозможно – необходимо вводить ограничения на P и Ω . Одно из таких ограничений

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

Остовом транзитивного отношения E ∞ назовем граф E':= ϕ(E ∞ ) = E ∞ \ E ∞ E ∞ . E ∞ является транзитивным замыканием остова E' . Функция ϕ(.) взаимно однозначна.

Содержательно ограничения на класс остовов описываются известным еще с феодальных времен правилом: «вассал моего вассала – не мой вассал».

Лемма. Если Ω вместе с любым транзитивным отношением E ∞ содержит и все графы с таким транзитивным замыканием, а удаление из произвольного графа G Ω любой связи удешевляет граф, то граф минимальной стоимости является остовом. ∙

Во многих частных задач условия этой леммы выполнены, что позволяет сузить

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

Литература

1.А.А. Воронин, С.П. Мишин. Модель оптимального управления структурными изменениями организационной системы. // Автоматика и телемеханика, №8. с. 136-150, 2002.

2.С.П. Мишин. Оптимизация иерархических структур. // Сборник трудов международной научно-технической конференции "Современные сложные системы управления". Старый Оскол, 27-29 ноября 2002.

3.С.А. Орловский. Проблемы принятия решения при нечеткой исходной информации. – М.: Наука. 1981.