автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Модели и методы оптимизации структуры иерархических систем обработки информации

На правах рукописи

ГУБКО МИХАИЛ ВЛАДИМИРОВИЧ

МОДЕЛИ И МЕТОДЫ ОПТИМИЗАЦИИ СТРУКТУРЫ ИЕРАРХИЧЕСКИХ СИСТЕМ ОБРАБОТКИ ИНФОРМАЦИИ

Специальность: 05.13.01 - «Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)»

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Ь УсВ 2014

МОСКВА-2014

005544843

005544843

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте проблем управления им. В.А. Трапезникова Российской академии наук

Научный консультант

- член-корреспондент РАН Новиков Д.А., зам. директора Федерального государственного бюджетного учреждения науки Института проблем управления им. В.А. Трапезникова Российской академии наук

Официальные оппоненты

- Горелик Виктор Александрович, доктор физико-математических наук, профессор, ведущий научный сотрудник отдела «Имитационные системы и исследование операций» Федерального государственного бюджетного учреждения науки Вычислительный центр им. А. А. Дородницына Российской академии наук,

- Райгородский Андрей Михайлович, доктор физико-математических наук, профессор кафедры математической статистики и случайных процессов механико-математического факультета Московского государственного университета,

-Токарев Владислав Васильевич, доктор физико-математических наук, профессор, главный научный сотрудник Федерального государственного бюджетного учреждения науки Институт системного анализа Российской академии наук.

Ведущая организация

- Волгоградский государственный университет, Кафедра фундаментальной информатики и оптимального управления.

Защита состоится 17 апреля 2014 г. в 1400 час. на заседании Диссертационного Совета Д 002.226.02 Федерального государственного бюджетного учреждения науки Института проблем управления им. В.А. Трапезникова Российской академии наук: 117997, Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке ИПУ РАН.

Автореферат разослан 27 января 2014 г.

Ученый секретарь

Диссертационного Совета Д 002.226.02

кандидат физико-математических наук

Общая характеристика работы

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

Значительный вклад в разработку математических методов оптимизации иерархических структур внесли М.А. Айзерман, A.A. Воронин, В.Т. Дементьев, А.И. Ерзин, С.А. Косяченко, В.В. Кульба, М.Ш. Левин, С.П.Мишин, Д.А.Новиков, Б.Л. Овсиевич, Г.А. Уголь-ницкий, А.Д. Цвиркун и др. За рубежом исследования в этой и смежных областях проводились Б. Боллобашем, Г. Волковицем, Т. Ван Зандтом, О. Вильямсоном, И. Гутманом, К.С. Дасом, Дж. Куинланом, Т.К. Ландоером, Г. Минцбергом, П. Милгромом, М. Ньюнесом, Р. Раднером, Ф. Рендлом, Д. Стевановичем, Д.Л Фишером, П. Эрдошем и многими другими.

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

Хотя такой абстрактный взгляд типичен для системного анализа, до сих пор в литературе известно не много общих формальных результатов, которые позволяли бы синтезировать иерархические структуры систем различной природы, что связано, в частности, с тем, что задачи этого класса относятся к самым сложным задачам дискретной оптимизации.

Объектом исследования в диссертационной работе являются иерархические системы обработки информации, предметом - методы оптимизации структуры таких систем.

Цель работы - повышение эффективности функционирования иерархических систем обработки информации за счет разработки математических моделей, алгоритмических и аналитических методов оптимизации их структуры в приложении к информационным, организационным и техническим системам. Достижение этой цели требует решения следующих основных задач:

1. Выявление общих характеристик задач оптимизации структуры сложных систем различной природы.

2. Формулировка единой математической модели оптимизации структуры иерархических систем, учитывающей вариативность состава системы, асимметрию иерархии управления и другие особенности частных постановок задач оптимизации структуры иерархических систем обработки информации.

3. Разработка методов оптимизации иерархических структур, в т.ч.:

3.1. исследование непрерывных релаксаций задач оптимизации иерархий для получения верхних и нижних оценок критерия эффективности,

3.2. поиск эффективно проверяемых условий, позволяющих сузить множество потенциально оптимальных иерархий,

3.3. создание и исследование алгоритмов точного и приближенного решения задач поиска оптимальной иерархии.

4. Исследование (с помощью полученных теоретических результатов) прикладных моделей оптимизации структуры иерархических систем обработки информации применительно к информационным, организационным и техническим системам.

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

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

Научная новизна работы состоит в формулировке единого подхода к разработке моделей анализа и синтеза эффективных струк-

тур иерархических систем обработки информации и в разработке

методов оптимизации этих структур применительно к проблемам

управления системами различной природы. А именно:

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

2. Получены общие достаточные условия оптимальности однородных древовидных иерархий, разработаны алгоритмы поиска наилучших однородных деревьев, находящие свое применение во многих задачах синтеза структуры систем. Эти результаты демонстрируют и обосновывают оптимизационную природу принципа самоподобия, - одного из общих законов структуризации сложных систем.

3. На базе идей алгоритмов Хаффмана и Шеннона-Фано разработаны эффективные алгоритмы поиска приближенно однородных деревьев, а также деревьев, вершины которых имеют заданные степени (число смежных ребер).

4. Показано, что «жадная» эвристика построения дерева «сверху-вниз», нередко используемая при решении частных задач, применима и для поиска оптимального дерева для произвольной секционной функции; разработан общий эвристический алгоритм построения субоптимального дерева, исследована его трудоемкость и получены оценки эффективности.

5. Предложена модель сети, обеспечивающей заданный набор информационных или материальных потоков. Затраты сети сконцентрированы в вершинах и определяются потоками, протекающими через дуги, инцидентные вершине. Предложены нижние оценки затрат сети, основанные на принципе Рэлея-Ритца и результатах спектральной теории графов.

6. Общность и эффективность разработанных методов подтверждена решением с их помощью следующих актуальных задач синтеза структуры систем различной природы.

6.1. К общей модели на базе однородных функций затрат сведены такие разные задачи как дизайн структуры пользовательских меню и формирование организационной структуры компа-

нии.В том числе:

• полученные теоретические результаты впервые позволили

разработать универсальную математическую модель и алгоритмы дизайна структуры пользовательских меню, достаточно эффективные для их реализации в САПР;

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

6.2. К поиску оптимального дерева для секционной функции затрат сведены известные задачи построения дерева принятия решений и балансировки сборочной линии:

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

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

6.3. Предложенная модель связывающей сети позволяет в рамках единой постановки описывать оптимизацию сети поставок, дизайн структуры сетей связи, кластеризацию на графах и многие другие задачи.

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

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

ственного университета и Московского физико-технического института (ГУ).

Личный вклад. Все основные результаты получены автором самостоятельно.

Апробация работы. Основные результаты диссертационной работы докладывались на международных конференциях: Современные сложные системы управления (Старый Оскол 2002); Теория активных систем (Москва 2003, 2005, 2007, 2009, 2011); Game Theory and Management (Санкт-Петербург 2008, 2010, 2012); World Congress of the International Federation of Automatic Control (Сеул 2008, Милан 2011); Международная конференция по проблемам управления (Москва 2009), CAD/CAM/PDM (Москва 2011), Управление развитием крупномасштабных систем (Москва 2013), Networking games and management (Петрозаводск 2012), ACM SIGCHI Symposium on Engineering Interactive Computing Systems (Берлин 2010), Conference of European Chapter of Combinatorial Optimization (Анталия 2012), European Conference on Operational Research (Рим 2013) а также на научных семинарах в ИПУ РАН, ЦЭМИ РАН, ИНХС РАН, МГУ, МФТИ и др.

Публикации. По теме диссертационной работы автором опубликованы 52 научные работы, в т.ч. 5 монографий и глав в монографиях, 19 статей в рецензируемых журналах.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложения с актами о внедрении результатов диссертационной работы. Она содержит 370 страниц текста, список использованной литературы включает 180 наименований.

Содержание работы

Во введении обоснована актуальность темы диссертационной работы, определены цель и задачи исследования, используемые методы, научная новизна и структура работы.

В первой главе проводится обзор и обосновывается актуальность разработки общих математических методов оптимизации иерархических структур в приложении к системам обработки информации.

Сначала задачи оптимизации иерархической структуры позиционируются в комплексе задач кибернетики и системного анализа. На основе структурного подхода системного анализа обосновывается связь задач оптимизации структуры с проблематикой теорией информации. Актуальность этих задач обусловлена тем, что эффективность

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

Общность задач синтеза структуры систем различной природы и целесообразность их рассмотрения с единых позиций обосновывается многочисленными примерами из областей управления техническими, организационными и информационными системами. Все задачи в той или иной мере удалось решить разработанными во второй главе методами, что описывается в главах 3-5.

Приведем общую постановку задачи оптимизации иерархий.

Определение 1. Ациклический граф Н=<1¥\1 М,Е>с множеством дуг Ее (IVи М) х М назовем иерархией над множеством вершин нижнего уровня IV= если множество его началь-

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

Это определение позволяет описывать асимметричные иерархии, множественное подчинение и наличие в иерархии нескольких

терминальных вершин.

Определение 3. Число входящих в вершину дуг называется полустепенью захода или ветвистостью этой вершины.

В самом общем виде задачу поиска оптимальной иерархии можно сформулировать следующим образом. Пусть задано конечное множество вершин нижнего уровня IV, множество допустимых иерархий асСХИО и функция затрат С: П -» [0,+«), которая каждой допустимой иерархии ставит в соответствие неотрицательное число. Необходимо найти допустимую иерархию с минимальными затратами, т.е. найти Н" е А^тт С(Я) .

ЯеП

Обычно множество допустимых иерархий настолько широко, что решение задачи перебором невозможно (размер даже самого узкого из рассматриваемых ниже множества последовательных иерархий растет пропорционально (|Щ - 1)!). Для разработки эффективных

подстраиваться под качество нижней оценки для различных групп (в частности, под среднее качество оценки для групп разного размера) -чем точнее оценка, тем меньше значение «($). В частности, «(,?) может настраиваться по результатам пробных запусков алгоритма.

В зависимости от множества допустимых иерархий задача полного перебора разбиений сама может быть довольно трудоемкой (максимальное число разбиений дает т.н. число Белла). В этом случае были предложены (и апробированы на задачах оптимизации пользовательских меню и построения дерева принятия решений) процедуры локального поиска, в т.ч. такие, в которых окрестность разбиения задается с помощью операции объединения пары составляющих разбиение множеств. «Жадный» алгоритм выбора разбиения стартует с максимально детального разбиения, на каждом шаге перебирает «соседние» разбиения и переходит к тому из них, которое доставляет минимум эвристическому критерию, если текущее разбиение хуже. В этом случае доказано, что если вычисление нижней оценки для множества из п листьев требует порядка (/г - 1)^ операций, то алгоритм имеет гарантированную трудоемкость порядка «/?+4.

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

Именно, в хорошей схеме локального поиска пути улучшения решения не должны приводить к локальным оптимумам с существенно худшим качеством. Количество «соседей» текущего решения, переход к одному из которых осуществляется на каждой итерации, не должно быть ни слишком большим, ни слишком малым.

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

локальных изменений - переходов к «соседним» иерархиям.

Такой критерий неоптимальности вершины был предложен для секционных функций. Для произвольной вершины т дерева Я обозначим через Нт поддерево Я, надстроенное над т. Пусть некоторой вершине т в Я подчинены вершины ти ..., тк. Введем величину

где введены обозначения .у := ^¡¡(т), := ^от,), г = к.

Если нижняя оценка затрат иерархии С(-) удовлетворяет техническому условию «монотонности», то Лц(т) неотрицательно. Кроме того, сумма этих величин по всём вершинам дерева Я дает главный критерий неоптимальности иерархии - разницу между затратами С(Я) дерева Я и нижней оценкой С(Щ затрат оптимального дерева.

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

Для каждой иерархии Не О. определяется множество \(Н) с О (возможно, пустое) последователей иерархии Я (обычно оно довольно естественным образом определяется через различные элементарные операции преобразования иерархий). Набор множеств Я е П, определяет ориентированный граф с множеством вершин Г2, а дуга от вершины-иерархии Я к вершине-иерархии Я проводится тогда и только тогда, когда Я е \{Н). Если получившийся граф не содержит циклов (в том числе, петель), то он порождает некоторый строгий частичный порядок -< допустимых иерархий из П

Определение 32. Функция затрат иерархии С(Я) слабо возрастает относительно мастичного порядка -<, если для любой иерархии ЯеП найдется такой последователь Я е ЦЯ), что С(Я) ^ С(Я). Функция затрат иерархии слабо убывает относительно -< , если найдется такой Я е К/7), что С(Н) > С(Я). Заменой нестрогих неравенств на строгие определяется строгое слабое возрастание и убывание.

Минимум слабо убывающей функции затрат достигается на одном из максимальных элементов упорядочения -< , и поиск оптимальных иерархий достаточно вести на множестве максимальных элементов С1, что упрощает задачу, если эти максимальные элементы удобно характеризуются или перечисляются. В частности, можно уточнить

условие сильного сужения для класса только древовидных иерархий-

Утверждение 20. Сужающая на наборах непересекающихся групп функция затрат называется сильно сужающей на наборах непересекающихся групп, если для любых с IV, ~ 0, Ы, Ы ^ 2, выполнено по крайней мере одно из двух неравенств:

а) ыез, => ф1,52)+ф1\{>у},{п'})>ф|\М,52) + с((5ЛМ)и52'Н)'

б) н'елз => ф1(у2)+ф2\М,М)>Ф1^2ЧМ) + Ф1и(^\М),М)-Для такой функции затрат на множестве всех деревьев существует оптимальная последовательная иерархия.

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

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

Пусть временная задержка в одной вершине равна Р(к) > 0, и Д£)/1п к->+ оо при к -> +оо. Необходимо над фиксированным множеством листьев IV= {1, п} надстроить иерархию Н, минимизирующую максимальное время С(Я) передачи данных от листа до корня.

Утверждение 24. Для любого дерева ЯС(Я) > С(п) = А- 1п п, где А - константа, зависящая от вида функции /?(•)• Равенство достигается, если Я-однородная симметричная иерархия. Ее ветвистость также зависит только от вида функции /?(•)•

Аргументами окрестностной функции затрат помимо групп, подчиненных детям вершины, является группа, подчиненная родителю вершины и ветвистость родителя. Для окрестностных функций, зависящих только от размеров групп листьев, подчиненных детям вершины и от ветвистости ее родителя, в параграфе 2.5.2 предложен точный алгоритм поиска оптимальной древовидной /--иерархии. Его вычислительная сложность - пг, где п - количество листьев. Идея -для каждого п'=\,...,п и />= 1, ...,г рекурсивно вычислить затраты

шенных расстояний между р этими вершинами в сети Н, внутренние вершины которой имеют веса аь ..., ач.1 Тогда

С2(Н)> 5ирЩс2([с2]-\аа))-ат[с'2Г\ат) + ая\Т„КЛп)-

«1.....ач [ш = 1

[Щ^Л - В{а,,...,ач)]к^, где К = ЛЬщ».....,кр).

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

«Прикладные» главы диссертации (3-5) посвящены применению описанных в главе 2 теоретических результатов к решению задач синтеза структуры сложных систем, имеющих различную природу.

В главе 3 исследуются задачи оптимизации иерархической структуры информационных систем.

В разделе 3.1 рассматриваются задачи построения дерева принятия решений. Проблема состоит в том, чтобы по обучающей выборке построить дерево вопросов, ответы на которые позволяют выбрать то или иное решение. Важна предсказательная способность дерева -при поступлении на вход новых, ранее не встречавшихся комбинаций ответов на вопросы принимать в них правильные решения. Для этой №-полной задачи известны эвристические алгоритмы. В диссертации предлагается нижняя оценка стоимости дерева принятия решений, с ее использованием разрабатываются новые эффективные алгоритмы построения деревьев принятия решений.

Пусть задано множество решений £)= {1, ..., о?} и множество атрибутов М= {1, ..., ц}. Мощность множества значений атрибута т обозначим через к{т). Также задано множество примеров Ж с весами Ди»), ы е №. Пример е IV- это уникальный вектор (а»,л)ЯЕ« значений атрибутов и значения класса / е £>. Разные ответы на вопрос «Каково значение атрибута тЪ> порождают разбиение всего множества примеров IV на подмножества ...,БКт){т). В работе рас-

1 Всем д внутренним вершинам сети Н назначим веса а\, ..., ач. Тогда матрица И = (<1тт.) - это рхр-матрица, элемент с1тт- которой равен сумме весов вершин на пути между вершинами мит'в//(в силу древовидности Н путь единственен). В матрицу О входят только расстояния между р вершинами, имеющими инцидентные висячие вершины.

С(Я) > С (IV) := = •

Однако качество этой оценки может быть достаточно низким:

Утверждение 32. Если с„т = с„„ то С(Щ/С(Н) > 2/(п + 1), и для любого е найдется дерево Я такое, что С(Щ1С(Н) = (2 + £•)/«.

Вычисление сводится к решению для каждого примера

№-трудной задачи о покрытии множества, но проведенные вычислительные эксперименты показывают, что в реальных задачах классификации оценка в среднем вычисляется за время О(тхп2). Для ускорения расчета предложено исключать из задач о покрытии существенные вопросы (это понятие было введено О.П. Кузнецовым в 1977).

Нижняя оценка была использована в универсальном эвристическом алгоритме построения дерева, описанном в параграфе 2.4.1. Впоследствии модификации алгоритма были реализованы в виде модуля открытой информационной системы анализа данных \Veka.

Проведенные вычислительные эксперименты на реальных задачах классификации показали, что этот алгоритм и его модификации работают медленнее популярных эвристик типа СБ-ЮЗ, ЮХ и Е02, но строят в среднем более эффективные деревья.

Раздел 3.2 посвящен задаче оптимизации иерархических пользовательских меню, которые до сих пор являются самым популярным методом доступа пользователей к командам и данным. Эффективность меню обычно измеряется средним временем навигации в нем пользователя, а оно существенно зависит от структуры - того, в какие категории группируются функции системы, как эти категории объединяются в метакатегории, и т.д. В результате таких группировок получается древовидная структура, листья которой соответствуют отдельным функциям, а остальные вершины - панелям меню или, что эквивалентно, категориям - группам функций. Оптимизация структуры меню состоит в том, чтобы среди множества допустимых выбрать структуру, минимизирующую среднее время пользовательской сессии.

Пусть IV-множество функций системы, Ди>) - вероятность того, что пользователь ищет функцию н> е IV. Иерархическое меню - это древовидная иерархия с множеством листьев Ш, промежуточные вершины которой соответствуют категориям. Каждая категория при этом характеризуется множеством составляющих ее функций

Допустимые группировки функций определяются заданным набором иерархических классификаций функций системы. Панель меню может содержать группировки только из одной классификации.

Для каждой функции или допустимой категории .у Q Wзадается ярлык l(s) и его семантическое качество ®(/(.v)).

Пусть категории ,уь ...,sk формируют панель меню с ярлыками lu ..., 4 соответственно. Тогда время выбора пользователем /-го пункта меню ti{k,(ov...,cok) = il(k)-CTi{(oх,...,сок), где со, := йЩ функция t,(k)

задает влияние структуры и дизайна меню, а функция а,{соь ...,й)к) описывает влияние семантического качества. Например, для голосового меню ait) - время воспроизведения метки, а г»ь ...,&>/;) = л>i + ... + a>¡. Среднее время, которое пользователь проводит в панели меню,

где у1 _ относительная популярность /-го пункта в панели меню. Среднее время поиска в иерархическом меню Н

теЛ-/

где ¿„(/и), ..., - категории, соответствующие ^ттг) пунктам

панели меню /и, ^(т),...,^/'^'^«) - семантическое качество их

ярлыков, а/л, , ..., <,„».„„, - их популярности.

Задача поиска оптимальной структуры меню - из допустимых категорий построить структуру меню Я, в которой Т(Н) минимально.

Если все ярлыки имеют одинаковое семантическое качество ю, то формула (1) дает нижнюю оценку среднего времени навигации:

Решение этой задачи минимизации дает ветвистость г и соотношение ..., хг между популярностями пунктов панелей идеального меню.

Для поиска оптимального меню с учетом семантического качества был применен универсальный алгоритма из параграфа 2.4.1 со следующим локальным критерием оценки разбиения категории 5 на подкатегории Я], ..., як с относительными популярностями уи ...,>>* и семантическим качеством а>\,..., о)к:

Ку„..„ук,о\,...,сок) = ^у^{к)аХ(о,.....

T(W ,<у) = ^In^-E/'W^^W

\

/

21.Губко М.В., Коргин Н.А., Новиков Д.А. Классификация моделей анализа и синтеза организационных структур // Управление большими системами. 2004. №6. С. 5-21.

22. Губко М.В. Теоретико-игровая модель, формирования торговой сети // Управление большими системами. 2004. № 6. С. 56-83.

23. Губко М.В. Рыночное равновесие в задаче формирования торговой сети // Управление большими системами. 2004. № 7. С. 17-32.

24. Губко М.В. Сбалансированные деревья // Управление большими системами. 2004. №9. С. 103-114.

25. Губко М.В. Однородные функции затрат менеджеров и оптимальная организационная структура // Управление большими системами. 2006. № 15. С. 103-116.

26. Goubko M.V., Mishin S.P. Optimal Hierarchies in Firms: a Theoretical Model / Contributions to Game Theory and Management. Vol. II. Collected papers presented on the Second International Conference Game Theory and Management [Ed. by L. Petrosjan and N. Zenkevich]. SPb: Graduate School of Management SPbU, 2009. P. 124-136.

Монографии

27. Губко М.В. Управление организационными системами с коалиционным взаимодействием участников. М.: ИПУ РАН, 2003.

28. Губко М.В. Математические модели оптимизации иерархических структур. М.: ЛЕНАНД, 2006.

29. Воронин А.А., Губко М.В., Мишин С.П., Новиков Д.А. Математические модели организаций: учебное пособие. М.: ЛЕНАНД, 2008.

30. Губко М.В., Мишин С.П. Механизмы формирования оптимальных структур управления [Текст] / Бурков В.Н. // Введение в теорию управления организационными системами: Учебник / [Под ред. Д.А. Новикова.] М.: Книжный дом «ЛИБРОКОМ», 2009. Глава 6. С. 193-257.

31.Burkov V., Goubko М., Kondrat'ev V., Korgin N., Novikov D. Mechanism Design and Management: Mathematical Methods for Smart Organizations (for managers, academics and students). New York: Nova Publishers, 2013.

Доклады на конференциях

32. Губко М.В., Мишин С.П. Оптимальная структура системы управления технологическими связями / Материалы международной научной конференции «Современные сложные системы управления». Старый Оскол: СТИ, 2002. С. 50-54.

33. Губко М.В., Коргин Н.А. Теоретико-игровая модель управления структурой организации / Труды Международной научно-практической конференции "Теория активных систем". М.: ИПУ РАН, 2003. Том 1. С. 34-35.

34. Губко М.В. Формирование бизнес-схем в транснациональных корпорациях / Теория активных систем. Труды международной научно-практической конференции. Том 1. -М.: ИПУ РАН, 2003. С. 26-28.

2008. P. 2962-2967.

48. Goubko M.V. Models of Network Formation Game Control / Game Theory and Management. Collected abstracts of papers, presented in the IV International Conference "Game Theory and Management", SPb: Gradual School of Management, SPbU. 2010. P. 64-67.

49. *Goubko M.V., Danilenko A.I. An automated routine for menu structure optimization / Proceedings of the 2nd ACM SIGCHI symposium on Engineering interactive computing systems, Berlin, Germany, June 19-23. 2010. P. 67-76.

50. *Goubko M.V. Lower-bound Estimate for Cost-sensitive Decision Trees / Preprints of the 18th IFAC World Congress, Milano (Italy), August 28-September 2. 2011. P. 9005-9010.

51. Goubko M. Heuristic algorithm for optimal tree search / Abstracts of the 25th Conference of European Chapter of Combinatorial Optimization (ECCO'2012), 26-69 April. 2012. P. 24-25.

52. Goubko M.V. On Communication Network Topology Problem with Node Costs // Abstracts of 26th European Conference on Operational Research, July 1-4, Rome, Italy. 2013. P. 14.

Личный вклад автора в работах, опубликованных в соавторстве, заключается в следующем: в [1] - постановка задачи и исследование кооперативной игры менеджеров матричной структуры, в [6, 15, 16] -разработка и исследование математической модели оптимизации организационной структуры, в [И, 13, 40, 42, 49] - разработка математической модели навигации пользователя в меню, постановка задачи оптимизации и разработка алгоритмов ее решения, в [12, 14, 17, 18, 31] - описание механизмов управления структурой организационной системы, в [21 ] - участие в разработке системы классификаций моделей оптимизации организационных структур, в [26, 46, 47] - участие в создании и исследовании математической модели, в [30] - обзор математических моделей формирования рациональных организационных структур, а также методы поиска оптимальных деревьев для однородных функций затрат, в [32] - разработка модели иерархии управления технологическими связями, в [33] - описание теоретико-игровой модели многоуровневой иерархии, в [37] - разработка математической модели оптимизации структуры сборки, в [39] - описание методики опроса и статистическое исследование его результатов, в [43] - описание оптимизационных моделей управления структурой сложных систем.

Научное издание

Губко Михаил Владимирович

Модели и методы оптимизации структуры иерархических систем обработки информации

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

В печать от 16.01.2014 Формат 60x90/16 Уч.-изд. л. 2,3 Тираж 100. Заказ 6

117997, Москва, Профсоюзная, 65 Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова Российской академии наук

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова Российской академии наук

УДК 519.176

На правах рукописи

0520145091*5

ГУБКО МИХАИЛ ВЛАДИМИРОВИЧ

МОДЕЛИ И МЕТОДЫ ОПТИМИЗАЦИИ СТРУКТУРЫ ИЕРАРХИЧЕСКИХ СИСТЕМ ОБРАБОТКИ ИНФОРМАЦИИ

Специальность: 05.13.01 - «Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)»

Диссертация на соискание ученой степени доктора физико-математических наук

МОСКВА-2014

СОДЕРЖАНИЕ

Содержание..........................................................................................................................2

Введение...............................................................................................................................б

Глава 1. Проблемы оптимизации структуры иерархических систем обработки информации........................................................................................................................11

1.1. Задачи оптимизации структуры иерархических систем.......................................11

1.1.1. Управление структурой с позиций системного анализа......................................11

1.1.2. Задачи оптимизации иерархической структуры информационных систем.......15

1.1.3.Задачи оптимизации иерархической структуры организационных систем.......22

1.1.4. Задачи оптимизации иерархической структуры технических систем................27

1.2. Общая постановка задачи оптимизации иерархических структур......................31

1.2.1. Определение иерархии.............................................................................................32

1.2.2. Секционные функции затрат...................................................................................37

1.2.3. Функции затрат, зависящие от мер.........................................................................43

1.2.4. Функции затрат по контролю потоков...................................................................47

1.2.5. Общие свойства секционных функций затрат.......................................................51

1.2.6. Расширение концепции секционных функций......................................................57

1.3. Задачи, подходы и методы теории оптимизации иерархических структур.......59

1.3.1.Классификация задач оптимизации иерархических структур.............................61

1.3.2.Методы решения задач оптимизации иерархических структур..........................63

1.3.3.Степень исследованности задач оптимизации иерархических структур...........65

1.3.4.Подходы к решению задач оптимизации иерархических структур....................67

Глава 2. Методы оптимизации иерархических структур...............................................70

2.1. Однородные функции затрат...................................................................................70

2.1.1. Нижняя оценка затрат иерархии для однородных функций................................73

2.1.1.1. Численный алгоритм поиска оптимального дерева.......................................73

2.1.1.2. Однородные деревья и их затраты...................................................................75

2.1.1.3. Нижняя оценка затрат оптимального дерева..................................................82

2.1.1.4. Поиск наилучших однородных деревьев........................................................87

2.1.2. Качество нижней оценки и приближенно оптимальные иерархии.....................93

2.1.2.1. Скорость роста нижней оценки затрат иерархии...........................................94

2.1.2.2. Случай степени однородности, не меньшей единицы...................................96

2.1.2.3. Случай степени однородности, меньшей единицы......................................106

2.1.3. Последовательные иерархии и граничные решения...........................................111

2.2. Функции затрат, зависящие от мер.......................................................................115

2.2.1. Затраты, представимые в виде суммы однородных функций............................115

2.2.2. Кусочно-однородные функции затрат..................................................................123

2.2.3. Аддитивные функции затрат.................................................................................129

2.2.4. Достаточные условия оптимальности последовательной иерархии.................140

2.3. Оптимальные иерархии по контролю потоков....................................................145

2.4. Секционные функции затрат.................................................................................150

2.4.1 .Алгоритм поиска приближенно оптимальной древовидной иерархии.............152

2.4.2.Интерактивная методика оптимизации древовидных иерархий.......................155

2.4.3.Частичные упорядочения иерархий и локальный поиск....................................160

2.5. Расширения модели секционных функций затрат..............................................168

2.5.1. Минимизация максимального пути......................................................................169

2.5.2. Окрестностные функции затрат............................................................................171

2.5.3.Задача о связывающей сети...................................................................................172

2.5.3.1. Постановка задачи о связывающей сети.......................................................173

2.5.3.2. Аддитивная функция затрат по контролю потоков......................................175

2.5.3.3. Нижняя оценка затрат оптимальной сети для аддитивной функции..........176

2.5.3.4. Нижние оценки для функции затрат, зависящей от степени вершин.........179

2.5.3.5. Оптимальные сети для функции затрат, зависящей от потока, протекающего через вершину........................................................................................181

2.5.3.6. Нижние оценки для функции затрат,

зависящей от потока, протекающего через вершину..................................................183

2.6. Выводы по главе 2..................................................................................................190

Глава 3. Модели и методы оптимизации

иерархической структуры информационных систем...................................................191

3.1. Оптимальные вопросники и деревья принятия решений...................................191

3.1.1. Постановка задачи..................................................................................................191

3.1.2. Сведение задачи к минимизации секционной функции.....................................195

3.1.3. Нижняя оценка затрат дерева принятия решений...............................................198

3.1.4. Алгоритмы поиска оптимальных деревьев решений..........................................208

3.2. Иерархические пользовательские меню..............................................................215

3.2.1.Обзор литературы...................................................................................................218

3.2.2.Модель оптимизации среднего времени навигации в меню..............................221

3.2.3.Учет семантического качества в модели навигации по меню...........................224

3.2.4. Алгоритмы оптимизации структуры меню..........................................................227

3.2.4.1. Поиск разбиения функций..............................................................................228

3.2.4.2. Сортировка вариантов в панели меню...........................................................231

3.2.4.3. Локальный критерий оптимизации................................................................231

3.2.4.4. Шаги алгоритма...............................................................................................232

3.2.4.5. Оценка качества алгоритма............................................................................233

3.2.5. Примеры оптимизации пользовательских меню.................................................233

3.3. Оптимизация структуры алгоритмов...................................................................238

3.3.1. Структуры алгоритмов и оптимальные иерархии...............................................238

3.3.2. Оптимизация иерархии ветвлений.......................................................................238

3.3.3.Оптимизация дихотомического представления функций..................................241

Глава 4. Модели и методы оптимизации

иерархической структуры организационных систем...................................................247

4.1. Организационная структура фирмы.....................................................................247

4.2. Обзор литературы...................................................................................................250

4.2.1. Историческая ретроспектива.................................................................................250

4.2.2. Классификация моделей........................................................................................251

4.2.3.Многоуровневые симметричные иерархии.........................................................253

4.2.4. Иерархии знаний....................................................................................................256

4.2.5.Многоуровневые иерархии обработки информации..........................................257

4.2.6. Иерархии и теория команд....................................................................................259

4.2.7. Иерархии принятия решений................................................................................260

4.2.8. Игры и иерархии.....................................................................................................262

4.3. Приложения однородных функций затрат...........................................................264

4.3.1. Однородные функции затрат менеджера.............................................................264

4.3.2.Модель делегирования решения проблем...........................................................266

4.3.3. Исполнение приказов и детализация планов.......................................................276

4.3.4. Скорость роста функции затрат иерархии...........................................................285

4.3.5.Идентификация функции затрат на содержание менеджеров...........................288

4.4. Модель совместной оптимизации иерархии и объема выпуска........................294

4.5. Оптимизация иерархии контроля исполнения бизнес-процессов.....................307

4.6. Оптимизация сети поставок..................................................................................312

4.6.1. Оптимизация структуры сети поставок...............................................................313

4.6.2. Задача среднесрочного планирования товарных потоков..................................323

Глава 5. Модели и методы оптимизации

ирархической структуры технических систем..............................................................328

5.1. Иерархическая структура сетей мобильной связи..............................................328

5.2. Модели проектирования структуры сборочного производства........................330

5.2. ¡.Постановка задачи..................................................................................................330

5.2.2. Алгоритмы оптимизации схем сборки.................................................................336

5.2.3.Модель с учетом транспортных расходов...........................................................339

5.3. Структура иерархий сбора информации..............................................................343

5.3.1.Минимизация времени сбора информации.........................................................345

5.3.2.Иерархическая структура мультиагентной системы..........................................348

Заключение.......................................................................................................................354

Список литературы..........................................................................................................361

Приложение. Акты и справки о внедрении

результатов диссертационной работы...........................................................................371

ВВЕДЕНИЕ

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

Значительный вклад в разработку математических методов оптимизации иерархических структур внесли М.А. Айзерман, A.A. Воронин, В.Т. Дементьев, А.И. Ерзин, С.А. Косяченко, В.В. Кульба, М.Ш. Левин, С.П. Мишин, Д.А. Новиков, Б.Л. Овсиевич, Г.А. Угольницкий, А.Д. Цвиркун и др. За рубежом исследования в этой и смежных областях проводились Б. Боллобашем, Г. Волковицем, Т. Ван Зандтом, О. Вильямсо-ном, И. Гутманом, К.С. Дасом, Дж. Куинланом, Т.К. Ландоером, Г. Минцбергом, П. Милгромом, М. Ньюнесом, Р. Раднером, Ф. Рендлом, Д. Стевановичем, Д.Л Фишером, П. Эрдошем и многими другими.

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

Хотя такой абстрактный взгляд типичен для системного анализа, до сих пор в литературе известно не много общих формальных результатов, которые позволяли бы синтезировать иерархические структуры систем различной природы, что связано, в частности, с тем, что задачи этого класса относятся к самым сложным задачам дискретной оптимизации.

Объектом исследования в диссертационной работе являются иерархические системы обработки информации, предметом - методы оптимизации структуры таких систем.

Цель работы - повышение эффективности функционирования иерархических систем обработки информации за счет разработки математических моделей, алгоритмических и аналитических методов оптимизации их структуры в приложении к информационным, организационным и техническим системам. Достижение этой цели требует решения следующих основных задач:

1. Выявление общих характеристик задач оптимизации структуры сложных систем различной природы.

2. Формулировка единой математической модели оптимизации структуры иерархических систем, учитывающей вариативность состава системы, асимметрию иерархии управления и другие особенности частных постановок задач оптимизации структуры иерархических систем обработки информации.

3. Разработка методов оптимизации иерархических структур, в т.ч.:

a. исследование непрерывных релаксаций математических задач оптимизации

иерархий для получения верхних и нижних оценок критерия эффективности,

b. поиск эффективно проверяемых условий, позволяющих сузить множество потен-

циально оптимальных иерархий,

c. создание и исследование алгоритмов точного и приближенного решения задач

поиска оптимальной иерархии.

4. Исследование (с помощью полученных теоретических результатов) прикладных моделей оптимизации структуры иерархических систем обработки информации применительно к информационным, организационным и техническим системам.

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

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

Научная новизна работы состоит в формулировке единого подхода к разработке моделей анализа и синтеза эффективных структур иерархических систем обработки информации, и в разработке методов оптимизации этих структур применительно к проблемам управления системами различной природы. А именно:

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

2. Получены общие достаточные условия оптимальности однородных древовидных иерархий, разработаны алгоритмы поиска наилучших однородных деревьев, находящие свое применение во многих задачах синтеза структуры систем. Эти результаты демонстрируют и обосновывают оптимизационную природу принципа самоподобия, - одного из общих законов структуризации сложных систем.

3. На базе идей алгоритмов Хаффмана и Шеннона-Фано разработаны эффективные алгоритмы поиска приближенно однородных деревьев, а также деревьев, вершины которых имеют заданные степени (число смежных ребер).

4. Показано, что «жадная» эвристика построения дерева «сверху-вниз», нередко используемая при решении частных задач, применима и для поиска оптимального дерева для произвольной секционной функции; разработан общий эвристический алгоритм построения субоптимального дерева, исследована его трудоемкость и получены оценки эффективности.

5. Предложена модель сети, обеспечивающей заданный набор информационных или материальных потоков. Затраты сети сконцентрированы в вершинах и определяются потоками, протекающими через дуги, инцидентные вершине. Предложены нижние оценки затрат сети, основанные на принципе Рэлея-Ритца и результатах спектральной теории графов.

6. Общность и эффективность разработанных методов подтверждена решением с их помощью следующих актуальных задач синтеза структуры систем различной природы.

6.1. К общей модели на базе однородных функций затрат сведены такие разные задачи как дизайн структуры пользовательских меню и формирование организационной структуры компании. В том числе:

• полученные теоретические результаты впервые позволили разработать универсальную математическую модель и алгоритмы дизайна структуры пользовательских меню, достаточно эффективные для их реализации в САПР;

• для ряда моделей формирования организационной структуры компании удалось получить аналитические выражения, связывающие параметры модели (квалификацию менеджеров и исполнителей, степень стандартизации процессов и др.) с формой оптимальной иерар�