Задачи оптимизации структуры многоуровневых иерархических систем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I. Многоуровневые иерархические структуры.

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

X. I. Постановка задачи

1.2. Метод решения.

1.3. Частные случаи.

§ 2. Неоднородные иерархические структуры транспортного типа.

2.1. Задача многоуровневого размещения.

2.2. Приближенный алгоритм решения

2.3. Точный алгоритм неявного перебора.

§ 3. Задача двухуровневого размещения.

§ 4. Динамическая задача двухуровневого размещения

ГЛАВА П. Оптимизация иерархических структур на графах

§ 5. Постановка задачи и методы ее решения.

§ 6. Смешанный алгоритм.

§ 7. Наилушее дерево

7.1. Оценки относительной погрешности.

7.2. Случай

7.3. Алгоритм локальной оптимизации.

§ 8. Асимптотический подход к решению задачи.

8.1. Оценка относительной погрешности

8.2. Ограничение на количество висячих вершин в дереве D

8.3. Ограничение на степени вершин графа

§ 9. Задача, на максимум.

9.1. Наилучпее из деревьев Р и в'

9.2. Вероятностный подход к асимптотическому поведению алгоритма "иди в дальний".

В различных сферах человеческой деятельности - в науке об управлении, в экономике, в технике - приходится сталкиваться с задачами построения и функционирования "больших систем". Важным направлением исследования таких систем является рассмотрение их как многоуровневых систем с иерархической структурой. Однако стройной математической теории таких иерархи -ческих систем еще нет. Книга Масаровича М.Д., Мако Д., Така-хара И. [25] является, видимо, первой книгой, в которой более или менее систематически исследуются математические модели иерархических структур управления и анализируются преимущества, которые может дать применение иерархического подхода в различных случаях. Основная ее цель состоит в том, чтобы показать возможности и вскрыть особенности иерархического построения систем управления различными процессами (к таким процессам относятся производственно-технологические, экономические процессы, процессы управления множеством объектов и т.п.). В книге [27] дается современное состояние информационной теории иерархических систем.

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

1. каждый элемент системы принадлежит (хотя бы формально) однои^у из уровней иерархии и может быть соединен только с элементами других уровней;

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

На сегодняшний день наиболее важной задачей является разработка следующих разделов теории иерархических структур (см.

И >=

- моделирование иерархических структур;

- динамические модели принятия решения в иерархических системах;

- модели принятия решения в иерархических системах в условиях неопределенности;

- методы оптимизации иерархических систем;'

- моделирование реальных иерархических систем (приложения).

Настоящая диссертация посвящена моделированию и разработке методов оптимизации структуры иерархических систем (ИС). В работах, относящихся к ИС, как правило, не рассматривается вопрос о построении структуры. Она считается заданной и оптимизируется только функционирование системы. В настоящей диссертации задачи построения структуры ИС являются основными. Значительное внимание уделяется также вопросам построения математических моделей рассматриваемых задач. Математическая постановка и методы решения задач первой главы в работе осуществлены впервые. Задача же второй главы рассматривалась рядом авторов (см. [1-3, 7, 14, 17, 22-24, 28-30, 34]). Так, например, в работе Клетина В.А. приводятся результаты экспериментальной проверки эффективности методов комбинаторного программирования применительно к задаче (2.1). Исследуются: метод ветвей и границ (МВТ), равдомизированные алгоритмы и алгоритмы локальной оптимизации. В работах Лотарева Д.Т. [i, 23, 24j показаны некоторые свойства оптимальных деревьев задачи. Предложено несколько эвристических алгоритмов. Приведены результаты исследования алгоритмов синтеза решения на ЭВМ. Ахпателов Э.А., Табаков Н.В. и Макарова Л.Н. [2-з] предлагают правила отбраковки некоторых деревьев и на их основе разрабатывают метод неявного перебора, типа МВГ. Метод ветвей и границ применяется также в работах Алиева Т.М., Именова К.С., Лотарева Д.Т. [i] и Трубина В.А., Гццояна А.К. [28] . Причем в работе [.28] предлагается находить нижнюю границу и рекорд на каждом шаге МВГ с помощью некоторой двойственной задачи. Злотов А.В. в работе [l4] формулирует ряд утверждений, позволяющих обосновать правила отбраковки и вычисления нижней границы и рекорда в методе неявного перебора. Там же предлагается приближенный алгоритм. Приводятся результаты .численных экспериментов.

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

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

31]). Долгое время единственным способом анализа эффективности методов решения таких задач было численное' экспериментирование. В последние годы возникла необходимость объективного сравнения задач дискретной оптимизации и алгоритмов их решения. В связи с этим стала бурно развиваться теория сложности алгоритмов. Общепринято, в последнее время, измерять сложность алгоритма по количеству арифметических операций и ячеек памяти, необходимых для его реализации. Количество ячеек в запоминающем устройстве ЭВМ, требуемое для хранения необходимой информации при реализации алгоритма, называется его памятью. Количество же арифметических операций, выполняемых алгоритмом, называют его трудоемкостью или временной сложность». Очевидно, что разные алгоритмы имеют различную трудоемкость, и выясне -ние того, какие алгоритмы эффективны, а какие нет, всегда будет зависеть от конкретной задачи. Однако специалисты, разрабатывающие алгоритмы, считают эффективными полиномиальные алгоритмы, т.е. алгоритмы, чья трудоемкость ограничена сверху некоторым полиномом от длины записи исходной информации. Если временную сложность алгоритма нельзя оценить сверху полиномиальной функцией, то такой алгоритм называют экспоненциальным и считают его не эффективным. Различия между полиномиальными экспоненциальным алгоритмами тем заметнее, чем больше размерность задачи. Как правило, алгоритмы экспоненциальной трудоемкости подразумевают полный перебор допустимых решений задачи, в то время как эффективные алгоритмы удается построить только в случае глубокого понимания сути рассматриваемой задачи.

Необходимость теоретически оценивать сложность различных классов задач, дала толчок для развития теории Д/Р -полных проблем. Понятие н /VP -полнота", введенное С.Куком и Р.Кар-пом, стало символом больших трудностей, с которыми математикам, занимающимся разработкой алгоритмов, все чаще приходится сталкиваться в своей работе. В работах Кука С. , Карпа Р. и Левина Л. jj&J введены такие основные понятия как класс Д/Р всех задач, разрешимых недетерминированными алгоритмами, и класс Р задач, разрешимых за полиномиальное время. В классе /VP найдены, так называемые, /VP -полные задачи, к которым полиномиально сводится любая задача из /VP. Следовательно, вопрос о равенстве Р = А/Р был бы решен, если бы удалось показать, что хотя бы одна А(Р -полная задача принадлежит классу Р . Однако большой практический опыт решения дискретных задач дает основания считать, что Р Ф А/Р , хотя в строгом смысле, до сих пор, это неравенство не доказано (см. [l2] ). Надежда же на то, что класс УР -полных проблем невелик, неоправдана. Многочисленные и разнообразные задачи, встречающиеся в самых различных областях математики, оказались /\/р -полными и количество таких задач растет с каждым днем.

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

Если же удалось установить, что рассматриваемая задача является MP -полной, или NP -трудной (т.е. если трудоемкость ее решения не меньше, чем трудоемкость решения какой-то MP -полной задачи), то в этом случае общепринято поступать следующим образом. Во-первых,необходимо выделить множество подзадач, рассматриваемого класса задач, которые решаются за полиномиальное время. Во-вторых, можно разработать методы неявного перебора, типа МВГ (см. [2lJ ). И, в-третьих, надо разработать приближенные полиномиальные алгоритмы и попробовать оценить точность получаемого решения. Примером такого подхода к решению задач стандартизации может служить книга Береснева В.Л., Гимади Э.Х., Дементьева В.Т. [ .

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

В последнее время широкое распространение нашел другой подход, который принято называть "анализ наихудшего случая". При таком подходе устанавливается такая величина £ , что для каждой конкретной максимизационной (минимизационной) задачи из некоторого класса. Здесь W(x) - значение целевой функции на решении, построенном с помощью приближенного алгоритма, a W*- оптимальное значение целевой функции. Если для некоторой конкретной задачи из рассматриваемого класса соотношение (I) выполняется как равенство, то величина £ называется достижимой оценкой. Если £ не зависит от входных параметров задачи, то ее обычно называют гарантированной оценкой приближенного алгоритма. Приближенные алгоритмы, для которых удается определить величину гарантированной оценки £ , до реализации алгоритма, называются субоптимальными, или £.-оптимальными. Субоптимальные алгоритмы можно построить не для всех задач. Для многих задач построение таких алгоритмов означало бы построение точных эффективных алгоритмов их решения (см[12] ).

Другой интересный подход к решению задачи приближенными методами - это построение асимптотически точного решения (или статистически асимптотически точного решения (см.^6,11,15, 26] ). В этих случаях решение, построенное приближенным алгоритмом, приближается к оптимальному при неограниченном росте размерности задачи. Так, в работах Гимади Э.Х., Глебова Н.И. и Перепелицы В.А. [9, ю] было введено понятие статистически эффективного алгоритма, гарантирующего построение с вероятностью, близкой к единице, асимптотически оптимального решения, на некотором классе задач с введенной на нем вероятностной мерой.

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

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

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

Первая глава посвящена построению оптимальной структуры многоуровневой ИС.

В § I рассматривается задача оптимизации однородной ИС. Предлагается алгоритм полиномиальной трудоёмкости решения ее в общем виде и рассматриваются частные случаи, когда удается выписать решение в аналитическом виде.

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

В § 3. Рассматривается задача построения структуры ИС в случае трех уровней иерархии с дополнительным ограничением на капитальные вложения. Для нее предлагается метод точного решения.

§ 4 посвящен динамической задаче двухуровневого размещения или построению структуры ИС для трех уровней с учетом временного периода Т . Предлагается метод нахождения точного решения с полиномиальной трудоемкостью.

Вторая глава посвящена построению оптимальной структуры ИС в форме дерева на заданном неориентированном взвешенном графе. Показано, что рассматриваемая задача является MP -трудной.

В § 5 приводится математическая постановка задачи, вводятся основные определения и находятся оценки относительной погрешности решений, построенных алгоритмами Прима и Дейкстра.

В § 6 предлагается смешанный алгоритм решения задачи и для построенного им решения находятся оценки относительной погрешности.

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

В § 8 исследуется асимптотическое поведение приближенного решения.- Устанавливаются условия, когда приближенный алгоритм будет асимптотически точным.

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

В заключении коротко формулируются основные результаты диссертации.

Документы приложения подтверждают внедрение результатов работы.

Основные результаты диссертации опубликованы в работах 41-43 и докладывались на У Всесоюзной конференции по проблемам теоретической кибернетики (Новосибирск, 1980 г.), на П Всесоюзном совещании по методам и программам решения оптимизационных задач на графах и сетях (Улан-Удэ, 1982 г.), на У1 Всесоюзной крнференции по теоретическим проблемам кибернетики (Саратов, 1983 г.), на XXII и Ш Областных научно-технических конференциях, посвященных Дню радио (Новосибирск, 1979 г., 1982 г.), на Региональной научно-технической конференции "Вычислительная техника и дискретная математика" (Новосибирск, 1983 г.), на семинарах Института математики СО Ж СССР и Вычислительного центра СО АН СССР.

Автор выражает искреннюю признательность научному руководителю В.Т.Дементьеву за постоянное внимание и всестороннюю поддержку.

103 ЗАКЛЮЧЕНИЕ

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

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

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

1. Альев Т.М., Иманов К.С., Лотарев Д.Т. Некоторые принципы формирования иерархических структур. - В кн.: Вопросы нефтяной технической кибернетики, Баку, 1976, с.16-25.

2. Ахпателов Э.А., Табаков Н.В., Об одной задаче построения сети с нелинейной функцией стоимости на ребрах. В кн.: Проблемы нефти и газа Тюмени, Тюмень, 1980, вып. 47, с.53-58.

3. Беллман Р. Динамическое программирование. -М.: Изд-во иностр. лит., I960. 400 с.

4. Береснев В.Л. Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. М.: Наука, 1978. - 333 с.

5. Боровков А.А. К вероятностной постановке двух экономических задач. ДАН СССР, 1962, 146, вып. 5, с.983-986.

6. Васильева Е.М., Левит Б.Ю., Лившиц В.Н. Нелинейные транспортные задачи на сетях. М.: Финансы и статистика, 198I, -104 с.

7. Гимади Э.Х., Глебов Н.И., Дементьев В.Т. Об одном методе построения нижней оценки и приближенного решения с апостериорной оценкой точности для задачи стандартизации. В кн.: Управляемые системы, Новосибирск, 1974, № 13, с.26-31.

8. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценкой для задач дискретной оптимизации. В кн.: Проблемы кибернетики, вып. 31, М., Наука, 1976, с.35-45.

9. Гимади Э.Х., Перепелица В.А. Асимптотический подход к решению задачи коммивояжера. В кн.: Управляемые системы, Новосибирск, 1974, № 12, с. 35-45.

10. Гимади Э.Х., Перепелица В.А. Статистически эффективный алгоритм выделения гамильтонова контура (цикла). В кн.: Дискретный анализ, Новосибирск, 1973, вып. 22, с.15-28.

11. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. М.: Мир, 1982. - 416 с.

12. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации. В кн.: Проблемы кибернетики, вып.33 -М.: Наука, 1978, с.5-68.

13. Злотов А.В. Об одном комбинаторном алгоритме построения сети с разрывной функцией стоимости на ребрах. В кн.: Экономика и математические методы, 1978, т. 14, № 4, с."583-787.

14. Зыков А.А. Теория конечных графов, I. Наука, Новоси- . бирск, 1969. - 543 с.

15. Карманов В.Г. Математическое программирование. М.: Наука, 1975, 272 с.

16. Клетин В.А. Анализ эффективности комбинаторных алгоритмов поиска экстремальных деревьев на взвешенных орграфах. В кн.: Автоматика и телемеханика, 1979, № II, с. I34-I4I.

17. Ковалев М.М., Котов В.М. Субоптимальные алгоритмы решения задачи коммивояжера. Ред. ж. "Вести, Белорус, ун-та, Сер. I. $из., мат. и мех.", Минск, 1982. Деп. в ВИНИТИ 12 мая 1982г., № 240382. - 31 с.

18. Котов В.М. Алгоритм решенич задачи коммивояжера на максимум. В кн.: Оптимизационные задачи в автоматизированной системе планирования расчетов НИИ ЭМП, Минск, 1982.

19. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978. 432 с.

20. Корбут А.А., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368 с.

21. Лотарев Д.Т. Задача Штейнера для транспортной сети на поверхности заданной цифровой моделью. В кн.: Автоматика и телемеханика, № 10, с.104-115.

22. Лотарев Д.Т. Цифровая модель местности для синтеза сети на неоднородной территории. Труды ВНИИБТ, вып. 54, Оптимизация и проектирование буровых процессов, с.44-50.

23. МесаровичМ., Мако Д., Такахара И., Теория иерархических многоуровневых систем. М.: Мир, 1973. - 344 с.

24. Перепелица В.А., Гимади Э.Х. К задаче нахождения минимального гамильтонова контура на графе со взвешенными дугами. -В кн.: Дискретный анализ, Новосибирск, 1969, вып.15, с.57-65.

25. Современное состояние теории исследования операций., под ред. Моисеева Н.Н. М.: Наука, 1979. - 463 с.

26. Трубин В.А., Гндоян А.К. Алгоритм и свойства задачи синтеза сетей с одним источником. В кн.: Теория оптимальных решений, Киев, 1980, с.82-87.

27. Ху Т. Целочисленное программирование и потоки в сетях. -М.: Мир, 1974. 519 с.

28. Шаген С.Д., Каган Я.М., Горбатиков В.А., Ройзрах В.Б. Оптимизация систем обустройства нефтяных месторождений. -Свердловск, Средне-уральское кн.изд-во, 1976. 105 с.

29. Яблонский С.В. Об алгоритмических трудностях синтеза минимальных контактных схем. В кн.: Проблемы кибернетики. М.:

30. Физматгиз, 1959, с.75-122.

31. Cook£.A.~T\<i. cowfiiexitj of theotiLM -ptoi/Lk£ pboctdule.b. P*"C. Ъ lA AhVl. ACM ОИ TUoy Сомf>u{Гид f Asbouaii'oH Joi. CoiMj>wti4<j Afa^iue-vj, А/eu/ Yolk , />. ifl-iss.

32. Dte^us S.E., tymnet I^.^.Tlae f>to££e.w L'h gxtfis. A/eiv</otkz , 1 , 13?2 , \9S.34. &atlo &., Saudi С., Wirn С. А и l> \м -fot iM t H\via concave. cos.i fbu/ ^oiirnvi . . Djbet . Res. . 9 , Ц9 N^k , f>. 14&-25~£-.

33. Graity H.R.y Jotiuson D.S.TUe MiLhcl pboiPtM CS МР~с.о*ирЬЬц-Ъ{№ J.Aftl .Matb 3Z, 1m ,/>. 2z6 -2ъЧ.

34. G-оЫг» #.L, BoJin L.D. , T. , S-Uwtvtb W.R. Appio/f-mtx-te -{lav/tit vig $.а£е*>мс\и . 1320 , 2.8 7634 -711 .

35. На Icimi S.L- S,i<ii\Ael's. ptolieM Схл gtqjoliS, аи/ i'h 1*л\>ксс{ 1:о\лС. . MeiwozlcS, \ f 1, 1371 9 p . 113 ,

36. Koi^R./Ч. deJuciliftiy аилоьд

37. I R.E. M;t£ei W J W. TUtcU*. Co^^riij of CowpuUt

38. CompuUkoH* f Pte-hunr, Pteis ? /tfj^ , 19 72 ?p. tt-IOZ.

39. Le.viH L.A. .Oil zolii'vij ptolfjLMi, Pyot&mij pciecIqci 3, 13 ?3> p. 1jS~116.

40. Yqhj YY, Wt'ng 0. Suio/>t,-MOii atflottilw* Jot л nsi"te.pto-ticun , I Тгй1л£., CT* —13 13 ?2. 3 p • .

41. Дементьев В.Т., Ерзин А.И., Семенов М.Ф. Оптимизация структуры многоуровневых иерархических систем (некоторые модели и задачи). В кн.: Тез. докл. У Всесоюзн.конф. по проблемам теоретической кибернетики, Новосибирск, 1980, с.57-58.

42. Дементьев В.Т., Ерзин А.И. Две задачи оптимизации иерархических структур. В кн.: Тез.докл. XXII Обл. научно-техн. конф. "Вычислительные устройства и системы". Новосибирск, 1979, с. 102-103.

43. Дементьев В.Т., Ерзин А.И. Об одной задаче многоуровневого размещения. В кн.: Тез.докл. Ш Обл. научко-техн.конф. "Вычислительная техникаыи системный анализ". Новосибирск, 1982, с.77-79.

44. Ерзин А.И. Асимптотический подход к решению задачи Штейнера с вогнутой функцией стоимости потока: Препринт № 4. Новосибирск, 1983. - 12 с. - В надзаг.: Ин-т математики СО АН СССР.

45. Ерзин А.И. Некоторые математические методы оптимизации структуры метрологической службы. В кн.: Системное моделирование. Новосибирск, 1981, № 6, с. 3-22.

46. Ерзин А.И., Семенов М.Ф. Некоторые модели оптимизации сетей связи. В кн.: Тез.докл. II Всесоюзн.совещания по методам и программам решения оптимизационных задач на графах и сетях. Улан-Удэ, 1982, с. 69-72.

47. Ерзин А.И. К одной задаче построения оптимального дерева. Вкн.: Тез.докл. Региональная научно-техн. конф. "Вычислив тельная техника и дискретная математика". Новосибирск, 1983,с. 41-42.

48. Ерзин А.И., Мордвинова Т.Б. Одна задача построения оптимального дерева. В кн.: Управляемые системы, Новосибирск, 1983, № 23, с. 44-54.