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

Актуальность темы

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

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

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

Задача поиска потока максимальной величины и двойственная ей задача поиска минимального разреза — это классические комбинаторные задачи с многочисленными научными и практическими приложениями. Например, определение максимальной интенсивности транспортного потока между двумя пунктами и определение части сети дорог, которая насыщена и образует «узкое место».

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

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

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

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

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

Степень разработанности проблемы. Исследованиями в области теории графов занимались многие ученые как в нашей стране, так и за рубежом. Выдающимся достижением алгоритмической теории графов следует назвать теорию потоков в сетях, созданную JI.P. Фордом и Д. Р. Фалкерсоном [42, 53]. Дальнейшее развитие эта теория получила в работах Е. А. Диница [11, 50], Дж. Р. Эдмондса и P.M. Карпа [51], A.B. Карзанова [65], A.B. Голдберга [59, 61] и многих других. Задачи о нестандартной достижимости рассмотрены в работах.

Я.М. Ерусалимского [14, 15, 19, 26, 31], Е. О. Басанговой [3−5], А. Г. Петросяна [18, 25, 34−36], В. А. Скороходова [13, 17, 22, 24, 39−41] и других.

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

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

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

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

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

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

Основные положения диссертационного исследования, выносимые на защиту:

1. Доказана ЫР-полнота задачи нахождения максимального потока для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к >2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимо сть.

2. Построены полиномиальные алгоритмы нахождения максимального потока для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к = 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями.

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

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

Представление материалов диссертационной работы на конференциях. Основные результаты работы докладывались соискателем на Воронежской весенней математической школе «Понтрягинские чтения» в 2008, 2009 и 2010 годах.

Публикации. Содержание диссертационного исследования и его результаты изложены в публикациях автора. По теме диссертации опубликовано 7 научных работ ([7−10, 12, 20, 21]), 2 работы написаны без соавторов.

Структура диссертационной работы. Диссертация состоит из введения, трех глав, заключения и библиографического списка. Полный объем диссертации составляет 142 страницы, включая 72 рисунка и 3 таблицы.

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

Рассмотрены два варианта задачи о максимальном объеме в сети: вариант при котром поток, имеющий максимальный объем в сети в момент времени t, не продолжаем на все ^ е Z, и вариант, когда полученный поток должен быть продолжаем на все X е Z. Предложены алгоритмы для решения этой задачи. Доказано, что эти алгоритмы находят поток, имеющий максимальный объем.

ЗАКЛЮЧЕНИЕ

.

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

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

Для достижения поставленной цели были решены следующие задачи:

1. Доказана МР-полнота задачи нахождения максимального потока для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к > 2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимость.

2. Построены полиномиальные алгоритмы нахождения максимального потока для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к — 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями.

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

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

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

В диссертационной работе подробно рассмотрен поток в сетях с барьерными ограничениями на достижимость, и проанализирован существовавший ранее алгоритм. Показано, что на некоторых графах (даже без барьерных ограничений) алгоритм «прорыва» [14] может не находить максимального потока. Автором работы построен алгоритм на основе алгоритма Эдмондса-Карпа, который обходит ограничения существовавшего ранее решения (алгоритм 2). Однако построенный пример показывает, что и этот алгоритм не всегда может найти максимальный поток.

Проанализированы причины, по которым алгоритмы, основанные на поиске увеличивающих цепей (такие как алгоритмы Форда-Фалкерсона и Эдмондса-Карпа), могут не находить решения. Рассмотрено обобщение задачи — поток на вспомогательном графе, построенном по исходному графу, в котором все пути разрешены, но некоторые дуги являются связанными. Потребовалось изменить определение величины разреза на таком графе.

Согласно работе [14] часть теоремы Форда-Фалкерсона о том, что максимальный поток ограничен сверху величиной минимального разреза, выполнена и для нового определения разреза. Однако на приведенных в данной работе примерах показано, что другая часть — о том, что существует поток, величина которого достигает величины минимального разреза, не выполнена. На основании этого делается вывод о неприменимости алгоритмов поиска максимального потока, основанных на поиске увеличивающих путей, в сетях с дополнительными ограничениями на достижимость.

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

Автором показано, что задача поиска потока на графах с дополнительными ограничениями на достижимость может быть ЫР-полна для некоторых видов достижимости. Для доказательства этого утверждения построен специальный вид достижимости — ЫР-достижимость.

Решение задачи 3−8АТ сведено к нахождению максимального потока в специально построенном графе с МР-достижимостью. Доказано, что решение задачи о максимальном потоке на графе, построенном в теореме об ИР-полноте, с ИР-достижимостью, эквивалентно задачам на том же графе для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к > 2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимость.

Для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к = 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями построены полиномиальные алгоритмы нахождения максимального потока.

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

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

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

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

Построены алгоритмы решения указанных задач: для первой задачи — алгоритм Эдмондса-Карпа с обратным поискомдля второй — алгоритм 4, доказаны теоремы о том, что эти алгоритмы находят правильное решение.

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

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