Автор:  Губко М.В.
Название:  Модели и методы оптимизации иерархической структуры систем обработки информации
Статус:  опубликовано
Издательство (для книг и брошюр):  ИПУ РАН
Год:  2014
Тип публикации:  брошюра
Полная библиографическая ссылка:  Губко М.В. Модели и методы оптимизации иерархической структуры систем обработки информации. Дисс. на соискание степени д.ф.-м.н. - М: ИПУ РАН, 2014. - 370 с.
Аннотация:  Эффективность систем управления во многом определяется их структурой (совокупностью связей различной природы между ее элементами). Сложные системы управления зачастую имеют иерархическую структуру, что обычно связано с необходимостью декомпозиции задачи управления и координации частных решений посредством обмена информацией между компонентами системы.
Основной подход настоящей работы основан на том, что, с математической точки зрения, возникающие в различных прикладных областях задачи оптимизации иерархий имеют много общего: задаются некоторое множество элементов нижнего уровня (над которыми необходимо надстроить иерархию), множество допустимых иерархий (из которых необходимо выбрать оптимальное подмножество или одну оптимальную иерархию) и критерий эффективности, позволяющий сравнивать различные иерархии.
Научная новизна работы состоит в формулировке единого подхода к разработке моделей анализа и синтеза эффективных структур иерархических систем обработки информации и в разработке методов оптимизации этих структур применительно к проблемам управления системами различной природы. А именно:
1. Введена система классификаций задач синтеза оптимальных иерархических структур обработки информации. Многие ранее исследовавшиеся независимо задачи синтеза структуры информационных, организационных и технических систем впервые сведены к общей постановке – поиску иерархии над заданным множеством вершин нижнего уровня, минимизирующей т.н. секционную функцию затрат.
2. Получены общие достаточные условия оптимальности однородных древовидных иерархий, разработаны алгоритмы поиска наилучших однородных деревьев, находящие свое применение во многих задачах синтеза структуры систем. Эти результаты демонстрируют и обосновывают оптимизационную природу принципа самоподобия, – одного из общих законов структуризации сложных систем.
3. На базе идей алгоритмов Хаффмана и Шеннона-Фано разработаны эффективные алгоритмы поиска приближенно однородных деревьев, а также деревьев, вершины которых имеют заданные степени (число смежных ребер).
4. Показано, что «жадная» эвристика построения дерева «сверху-вниз», нередко используемая при решении частных задач, применима и для поиска оптимального дерева для произвольной секционной функции; разработан общий эвристический алгоритм по-строения субоптимального дерева, исследована его трудоемкость и получены оценки эффективности.
5. Предложена модель сети, обеспечивающей заданный набор информационных или материальных потоков. Затраты сети сконцентрированы в вершинах и определяются потоками, протекающими через дуги, инцидентные вершине. Предложены нижние оценки затрат сети, основанные на принципе Рэлея-Ритца и результатах спектральной теории графов.
6. Общность и эффективность разработанных методов подтверждена решением с их помощью следующих актуальных задач синтеза структуры систем различной природы.
6.1. К общей модели на базе однородных функций затрат сведены такие разные задачи как дизайн структуры пользовательских меню и формирование организационной структуры компании.
6.2. К поиску оптимального дерева для секционной функции затрат сведены известные задачи построения дерева принятия решений и балансировки сборочной линии.
6.3. Модель связывающей сети позволяет в рамках единой постановки описывать оптимизацию сети поставок, дизайн структуры сетей связи, кластеризацию на графах и многие другие задачи.

Полный текст: Скачать ()
Полный текст: Скачать (pdf)
Полный текст: Скачать (pdf)

Просмотров: 4977, загрузок: 3358, за месяц: 25.

Назад