автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Новые виды достижимости и математические модели многопродуктовых потоков в мультисетях

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

Петросян Артем Георгиевич

НОВЫЕ ВИДЫ ДОСТИЖИМОСТИ И МАТЕМАТИЧЕСКИЕ МОДЕЛИ МНОГОПРОДУКТОВЫХ ПОТОКОВ В МУЛЬТИСЕТЯХ

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

АВТОРЕФЕРАТ

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

Ростов-на-Дону 2006

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

Научный руководитель

кандидат физико-математических наук, профессор Ерусалимский Яков Михайлович

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

доктор физико-математических наук, профессор Покорный Юлий Витальевич

кандидат физико-математических наук, доцент Степовой Дмитрий Владимирович

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

Калмыцкий государственный университет

Защита диссертации состоится " 28 " сентября 2006 года в часов

на заседании диссертационного совета К 212.208.04 по физико-математическим и техническим наукам в Ростовском Государственном Университете по адресу: 344090, г. Ростов-на-Дону, пр. Стачки 200/1, корпус 2, ЮГИНФО РГУ, к. 206.

С диссертацией можно ознакомиться в Зональной научной библиотеке РГУ по адресу: г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан 2006г.

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

Диссертационного совета, к.ф.м.н., доцент Муратова Г.В.

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

Актуальность темы. Ориентированные графы широко используются в качестве математических моделей различных классов объектов и процессов, например, они применяются для решения таких задач, как маршрутизация в информационных сетях, сетевое планирование и многих других. Наиболее часто на графах: рассматриваются задача о достижимости (т.е. существовании пути между двумя вершинами), Марковские процессы (т.е. задача о случайном блуждании частицы на графе с заданными на дугах вероятностями) и задача построения максимального потока в ориентированной сети. В классической постановке все вышеперечисленные задачи хорошо изучено и широко применяются в различных областях. Наиболее существенными в этой области являются работы Краскала Д., Фалкерсона Д.Р., Форда JI.P, Басакера Р.Д., Зыкова A.A., Лозовану Д.Д., Кристофидеса Н., Ope О., Саати Т.Л., Свами М., Тхуласирамана К. '

. В отличие от классической постановки в работах Басанговой Е.О., Ерусалимского Я.М., Логвинова С.Ю., Скороходова В.А; перечисленные задачи рассматриваются на графах с ограничениями на достижимость. Это такие графы, в которых не все пути являются допустимыми, а, следовательно, известные алгоритмы для решения этих задач неприменимы. Такие графы'мы называем орграфами с нестандартной достижимостью. Такое обобщение классического понятия позволяет расширить область применения графовый моделей и методов, в том числе к задачам маршрутизации в сетях с участками затухания и участками усиления сигнала, к нахождению кратчайших путей выполнения технологических процессов, в которых налагаются ограничения на порядок (последовательность) выполнения некоторых операций или их совместимость, к нахождению вероятностей в задачах случайного блуждания частицы, когда имеются переходы, влияющие на ее свойства.

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

Применимость данных моделей к решению логистических задач делает данную работу актуальной.

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

В работе рассмотрены и решены следующие задачи:

1. Определены и исследованы новые виды достижимости на орграфах.

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

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

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

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

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

1. Определены и изучены два вида условий ограничений на достижимость: барьерная достижимость и достижимость с условием биполярной магнитно-¡сти. ' '

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

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

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

5. Алгоритмы, предложенные в работе, реализованы в виде комплекса программ, приведенного в приложении.

Практическая ценность работы состоит в том, что

1. ■ Введенные и изученные новые виды достижимости на орграфах расширяют

класс возможных приложений;

2. Решенная задача о многопродуктовых потоках в мультисетях мо. ;.т быть применена для решения практических задач планирования перевозок разнотипных грузов, продуктов и т.п.

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

Апробация работы.

1. Результаты диссертации докладывались на конференции «Математические методы в современных и классических моделях экономики и естествознания» (Ростов-на-Дону, 2005 г.)

2. По результатам работы сделан доклад на семинаре «Современные проблемы математического моделирования» (Абрау-Дюрсо, 2005 г.)

3. Результаты работы неоднократно обсуждались на научном семинаре кафедры алгебры и дискретной математики РГУ.

4. Результаты работы вошли в отчеты по проектам «Нестандартная достижимость на ориентированных графах» (Грант конкурсного центра Мит нобразования РФ по разделу естественные науки , проект Е02-01-231) и «Графы и сети с нестандартной достижимостью» (Ведомстве/.;:-я программа Минобрнауки РФ «Развитие научного потенциала высшей школы», подпрограмма №3, раздел З.З.- поддержка исследований проводимых молодыми учеными, проект 7857)

Публикации. По материалам диссертации опубликовано 5 работ ПНЯ- Работы [1],[4] выполнены совместно с научным руководителем. В этих работах Ерусалимскому Я.М. принадлежит постановка задачи и определение общих исследования методов, проведение подробных доказательств всех теоретических результатов и разработка алгоритмов принадлежит автору диссертации. . .

Структура и объем работы. Диссертация состоит из введения, трех глав, приложения и списка литературы. Объем диссертационной работы составляет 148 страниц, в работе содержатся 57 рисунков, библиографический список содержит 33 наименования.

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

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

В первой главе вводится понятие барьерной достижимости на ориентированном графе, у которого множество дуг и = причем множества

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

¿/г

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

[', _/]л (1 5) < / £ п) пути Ц длины и связана числовая характеристика

>

О"»]) ~ ^("О ^ 1 - барьерный показатель частицы.

т=!

Определение 1.2.1. Путь № будем называть путем длины " (п € Л^) на графе (7 , допускающим барьерный переход уровня к (А 1), если выполняется следующее условие:

Ут| /фи) е иБ =>Л„(/л -1) > к.

Другими словами, если к / — тому шагу путь Ц от своего начала накопил величину

барьерного показателя Я^ (/) большую либо равную к , то становятся допустимыми для

прохождения в последующем этим путем дуги из множества С/Б. Пути, удовлетворяющие этому условию мы называем путями, допускающими барьерный переход уровня к{к > 1) . Существенное отличие данного вида ограничений на достижимость от рассмотренных ранее заключается в следующем. В отличие от магнитной и вентильной достижимости, изученных в работах Ерусалимского Я.М. и Скороходова В.А., в случае барьерной достижимости у множества путей имеется транзитивное свойство, т.е. если существует путь из вершины X в вершину У, допускающий барьерный переход уровня к. и существует путь из вершины У в вершину 2 , допускающий барьерный переход , то существует путь из вершины X в вершину 2 , допускающий барьерный переход уровня

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

барьерного показателя, не обязательно продолжать путь по дугам из множества иБ.

Описан алгоритм перестроения исходного графа, сводящий достижимость вершин исходного графа к достижимости на вспомогательном графе:

Каждой вершине л графа <? ставится в соответствие к +1 вершина графа С Х,.*"',...,*'*1, а дугам С? ставятся в соответствие дуги С по следующему правилу:

1. Каждой дуге множества 0* (х) Гли н на Ст ставится в соответствие А + 1 дуга М(0),...,М<4) на графе С таких, что

. /Ч"Ш) = (*Ш,У;)),У/ = од.

2. Каждой дуге множества 0+(х)п1/+ на С ставится в соответствие к +1 дуг «<°>,...,а<*> на графе С таких, что

3. Каждой дуге множества 0+(х)п1/г на С? ставится в соответствие дуга и на графе С такая, что /'(") = (У 'ЛУ*1).

' ?

Доказана теорема о связи вспомогательного графа с исходным:

Теорема.1.2,1. Любому пути // на вспомогательном графе С соответствует путь /V, допускающий барьерный переход исходном графе <7 , и вершина у достижима при условии барьерного перехода уровня к из вершины X на графе С тогда и только тогда, когда на С достижима из X, по крайней мере, одна из вершин множества

Уу={у,ут.....у*'}. '

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

Теорема 1.2.2. Кратчайшему пути на вспомогательном графе Сек барьерными уровнями соответствует кратчайший путь, допускающий барьерный переход к -го уровня на графе С? .

Теорема 1.2.3. При указанном построении, на вспомогательном графе кратчайших путей, содержащих более чем п — 1 дуг, не существует, где П - количество вершин исходного графа.

В главе 1 также рассмотрена задача о случайном блуждании частицы на графе с условием барьерной достижимости. Ясно, что процесс случайного блуждания на таком графе не является Марковским, так как переходы определяются не только вероятностями переходов, но и значением величины барьерного показателя. Для сведения данного процесса к Марковскому предлагается следующий подход: производится построение вспомогательного графа ,и', У). На вспомогательном графе специальным образом задаются вероятности перехода:

1. Для «•ев-Ос») / = 0ДГ1: = *»>•<!.

2. Для и'еЭЧ*^): =

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

Теорема 1.3.1. Вероятность перехода из вершины X в вершину у на графе С? за / шагов равна сумме вероятностей перехода частицы на графе С из вершины X в каждую из вершин У'1 за Г шагов, или, что то же самое она равна вероятности перехода частицы

за / шагов из вершины х во множество вершин {.>,<0),.У<,),.-ч.У<')} иимеетместо формула

к ;=0

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

Вводится понятие барьерного разреза:

Определение 1.4.5. Рассмотрим всевозможные подмножества дуг разреза (К, У) обладающие следующим свойством: для любой дуги и подмножества разреза существует путь , допускающий барьерный переход на исходной сети <7, содержащий эту дугу. Подмножество такого вида наибольшей мощности будем называть барьерным разрезом У .

Доказывается аналог теоремы Форда-Фалкерсона:

Теорема 1.4.2. Для любой ориентированной сети, допускающей барьерный переход, с источником 5 и стоком I величина максимального потока равна пропускной способности минимального барьерного разреза.

Во второй главе вводится понятие биполярной магнитности на ориентированном

графе, у которого множество дуг С/ = ин ^ С/+ О С/_ ^ &м+ ^ , причем

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

[Л - называется множеством дуг, увеличивающих положительную магнитность, а - множеством дуг, увеличивающих отрицательную магнит-ность. Множество V- называется множеством дуг положительной магнитности, а и м- - множеством. дуг отрицательной магнитности. С каждым отрезком ['»У1л'(1 ^' 7 —пути М связана числовая характеристика

К(<">Л = £I П и+ I ■- £I Ц{т) П и_ I

- величина накоп-

т=г

ленной биполярной магнитности.

Определение 2.1.1. Путь № будем называть биполярным магнитным путем уровня

1) длины п(п е N) с биполярной магнитностью на графе С, если выполняются следующие условия:

У/»(Д„(ш) > ще+((р2о/ о М)(т))пим, *0)=> (м(т +1) е £/„_) Ут^ (/и) < -*)(©+ ((р2 о / о м)(т)) о им+ (м(т +1) е )

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

I — той дуги есть хотя бы одна дуга из множества отрицательной магнитности, то следующая (1 + 1 - я) дуга биполярного магнитного пути уровня к обязана быть дугой из множества , а если к 2— тому шагу путь /2 от своего начала накопил магнитностъ (') меньшую либо равную —к и среди дуг, выходящих из концевой вершины I — той дуги есть хотя бы одна дуга из множества положительной магнитности, то следующая (2' + 1 - я) дуга биполярного магнитного пути уровня к обязана быть дугой из множества и. Такое условие называется условием биполярной магнитности уровня

к , Задача о биполярной магнитности является существенным уточнением модели, рассмотренной в работе В.А.Скороходова «Случайные блуждания и потоки в сетях с магнитной достижимостью»(в сб. Модели и дискретные структуры. Элиста, 2002. -с. 93-100.). Биполярная магнитностъ, с нашей точки зрения, является более «физичной», так как в нашей задаче частица, которая движется по дугам графа, накопив положительную магнит-юность, притягивается дугами с отрицательной магнитностью, а дугами с положительной магнитностью — отталкивается и наоборот, , .

Описан алгоритм перестроения исходного графа, сводящий достижимость вершин исходного графа к достижимости на вспомогательном графе:

Каждой вершине х графа б ставится в сбответствие 1к +1 вершина графа С

,.(-*> „(И) „ „(1) „(*) гу..............

х - ,х,х ,...,х ' , а дугам О- ставятся в соответствие дуги О по следую-

щему правилу: , ;"■ , . 1 . . ■■ •

1. Каждой дуге множества ©+(-г)Г»£/+ на (7 ставится в соответствие 2к — 1

дуг и на графе О таких, что

г {ии)) =. (х1», у™), V/ = - к+1, * -1. Если ©Ч*)оС/„_=0 ,тодо-

бавляется дуга Г(и1к)) = (хт,у1к)). Если €>+(х)ОII= 0 , то добавля-етсядуга =

2. Каждой дуге множества ©+(х)пС/_ на С ставится в соответствие 2к — 1 дуг и ,...,и на графе Сг таких, что /Ч«0)) = (хи\у0-1}),^ = -к + 1,к-1. Если е*(х)пи,и=0 ,юдо-бавляетсядуга /,(«("*)) = (*<"<>»^("")-Если б'Мпи,,. = 0 , то добавляется дуга /,(и(*>) = (х(4),У*-1)).

3. Каждой дуге множества на б ставится в соответствие 2к дуг «И),...,и(И на графе С таких, что /'("0)) = У0)). У/' = - к -1 .

4. Каждой дуге множества ©+(л:)г\ии_ на й ставится в соответствие 2к дуг и(-М),...,и1*> на графе С таких,что /'(кШ) = (хи),уи)),У/=-к+ 1,к .

5. Каждой дуге множества на й ставится в соответствие 2к — \ дуг и >•••»" на графе С/ таких, что/'(«0)) = (х0>,Ул),У/ = -* + 1Д-1. Если ©*(х)Ш/„_ =0 . то добавляется дуга /'("(1)) = (х(4),У4>). Если ©+(х) П С/м+ = 0 , то добавляется дуга /Ч"("4)) =

Доказана теорема о связи вспомогательного графа с исходным:

Теорема 2.1.1. Любому пути на вспомогательном графе С соответствует биполярный магнитный путь Ц на исходном графе С и вершина у магнитно-достижима при условии биполярной магнитности из вершины X на графе б тогда и только тогда, когда на С достижима из X, по крайней мере, одна из вершин множества

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

Теорема 2.1.2. Кратчайшему пути на вспомогательном графе Сек магнитными уровнями соответствует кратчайший биполярный магнитный путь уровня к на исходном графе С .

Теорема 2.1.3. При указанном построении, на вспомогательном графе кратчайших путей, содержащих более чем п — 1 дуг, не возникает, где п - количество вершин исходного графа.

Рассмотрена задача о случайном блуждании частицы на графе с условием биполярной магнитносТи. Такой процесс случайного блуждания не является Марковским. Для сведения данного процесса к Марковскому предлагается следующий подход: производится построение вспомогательного графа С(Х',и',У) . На вспомогательном графе специальным образом задаются вероятности перехода:

Для каждой рассматриваемой дуги и е С соответствующую ей дугу исходного графа будем обозначать V.

1.Для ие0+(*<о) / = й:

а) Если V 6 0+ О) П им, , тогда -Р(") = ■?(")(! - т> ■

к

Если =0 .то

ДЛЯ

1-

Л€0*(*)г-.(С/„ иИ.иУ.)

в противном случае:

для veQ*(x)n(УнvU+\JU_) Р(и) = Р(«)(1-|).

к

1- X Р(Г) V € © (х)пим_ Р{») - Р(и)--£ р(м)

/'Ев4 (х)пии.

2. Для М£0 (х' 1 = 0: вероятности перехода не изменяются.

3. Для иев+(х0)) г = ~1,-к:

а)Если УбвЧ^пС/^ .тогда =

Если © = 0 , то для

1в противном случае: для V е 0+ (х) о (ин Р(и) = Р(и)(\ - .

1- ^Р(Г)

^ / ч тт Г>Г„\ - Р/..\ гевФ<,*)г*(Ц\ии.)

да.Убв (*)Л£/М+ Р(и) = Р(и)~-

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

Теорема 2.2.1. Вероятность перехода из вершины X в вершину у на графе С? за / шагов равна сумме вероятностей перехода частицы на графе С из вершины х в каждую из вершин за t шагов, или, что то же самое она равна вероятности перехода частицы

за I шагов из вершины X во множество вершин {>"' и

имеет место формула

к

рф,х,У, 0= 5><<у,*о>('\о

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

Определение 2.3.1. Рассмотрим всевозможные подмножества дуг разреза (У, У) обладающие следующим свойством: для любой дуги и подмножества разреза существует биполярный магнитный путь //(5,?) содержащий эту дугу. Подмножество такого вида наибольшей мощности будем называть магнитным разрезом .

Доказывается аналог теоремы Форда-Фалкерсона:

Теорема 2.3.1. Для любой ориентированной сети с биполярной магнитностью с источником 5 и стоком / величина максимального потока равна пропускной способности минимального магнитного разреза.

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

Вводится понятие мультиразреза:' Определение 3.3.1. Рассмотрим всевозможные подмножества дуг разреза (У,У) обладающие следующим свойством: для любой дуги и подмножества разреза существует хотя бы одно / (/ = 1 ,к), такое что для /-го продукта существует допустимый путь /^(■^»0. содержащий эту дугу. Подмножество такого вида наибольшей мощности будем называть мультиразрезом

Доказывается аналог теоремы Форда-Фалкерсона:

Теорема 3.3.1. Для любой многопродуктовой мультисети с источником 5 истоком t величина максимального потока равна пропускной способности минимального мультиразреза.

В приложении приведены листинги программы и описание работы программного комплекса.

Положения, выносимые на защиту

1. Определены и изучены два новых вида нестандартной достижимости на ориентированных графах: барьерная достижимость и достижимость с условием биполярной магнитности.

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

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

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

5. Построена модель сетей с различными продуктами с различными видами ограничений на достижимость.

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

7. Доказан аналог теоремы Форда-Фалкерсона для мнопродуктовых мультисетей.

Список работ, опубликованных по теме диссертации

1. Ерусалимский Я.М., Петросян А.Г. Многопродуктовые потоки в сетях с нестандартной достижимостью.//Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2005, №6, с. 8-16.

2. Петросян А.Г. Многопродуктовые потоки в сетях с ограничениями на дости-жимость//в сб. Математические методы в современных и классических моделях экономики и естествознания. Ростов-на-Дону, 2005, с.136-138.

3. Петросян А.Г. Потоковая задача в многопродуктовых сетях с нестандартной достижимостьюУ/в сб. Современные проблемы математического моделирования. Ростов-на-Дону, 2005, с.334-340,

4. Ерусалимский Я.М., Петросян А.Г. Случайные процессы в сетях с биполярной магнитностью.//Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2005, Xsl 1, с. 10-16.

5. Петросян А.Г. Потоки в сетях с биполярной достижимосп>ю.//Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2006, №3, с.32-37.

Издательство ООО «ЦВВР». Лицензия ЛР № 66-36 от 0S.08.99 г. Сдано в набор 21.08.06 г. Подписано в печать 21.08.06 г. Формат 60*84 1/ 16 Заказ № 742. Бумага офсетная. Гарнитура «Тайме». Оперативная печать. Тираж 100 экз. Печ. Лист 1,0. Усл.печл. 1,0. Типография: Издательско-полиграфический комплекс « Биос» РГУ 344091, г. Ростов-на-Дону, ул. Зорге, 28/2, корп. 5 «В», тел (863) 247-80-51. Лицензия на полиграфическую деятельность № 65-125 от 09-02.98 г.

Содержание.

Введение.

Глава 1. Ориентированные графы с барьерной достижимостью.

1.1. Основные понятия и определения.

1.2.Достижимость на графах с условием барьерного перехода.

1.3.Случайные процессы на графах с барьерной достижимостью.

1.3.1. Случайные процессы, классическая постановка.

1.3.2. Случайные процессы на графах с барьерной достижимостью.

1.4. Потоковая задача в сетях с барьерной достижимостью.

1.4.1. Основные понятия, определения и утверждения.

1.4.2. Потоки в сетях с барьерной достижимостью.

Глава 2. Ориентированные графы с биполярной магнитностью.

2.1. Достижимость на графах с условием биполярной магнитности.

2.2. Случайные процессы на графах с биполярной магнитностью.

2.3. Потоковая задача в сетях с биполярной магнитностью.

Глава 3. Многопродуктовые потоки мультисетях.

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

3.2. Алгоритм построения максимального потока в многопродуктовой мультисети.

3.3 Теорема Форда-Фалкерсона для мнопродуктовых мультисетей.

Ориентированные графы широко используются для моделирования различных классов объектов и процессов. Наиболее часто на графах рассматриваются задача о достижимости (т.е. существовании пути между двумя вершинами), Марковские процессы (т.е. задача о случайном блуждании частицы на графе с заданными на дугах вероятностями) и задача построения максимального потока в ориентированной сети. В классической постановке все вышеперечисленные задачи хорошо изучено и широко применяются в различных областях. Наиболее существенными в этой области являются работы Басакера Р.Д., Ерусалимского Я.М., Замбицкого Д.К., Зыкова А.А., Лозовану Д.Д., Кристофидеса Н., Оре О., Саати Т.Л., Свами М., Тхуласирамана К., Фалкерсона Д.Р., Форда Л.Р.([1],[7],[15],[16],[17],[19],[21],[25],[28]).

В отличии от классической постановки в работах [2]-[5],[8],[9],[12]-[14], [26], [27] перечисленные задачи рассматриваются на графах с ограничениями на достижимость. Это такие графы, в которых не все пути являются допустимыми, а, следовательно, известные алгоритмы для решения этих задач неприменимы. Такие графы мы называем орграфами с нестандартной достижимостью. Такое обобщение классического понятия позволяет расширить область применения графовых моделей и методов, в том числе к задачам маршрутизации в сетях с участками затухания и участками усиления сигнала, к нахождению кратчайших путей выполнения технологических процессов, в которых имеются ограничения на порядок (последовательность) выполнения некоторых операций или их совместимость, к нахождению вероятностей в задачах случайного блуждания частицы, когда имеются переходы, влияющие на ее свойства.

Впервые графы с ограничениями на достижимость рассматривались в работах Басанговой Е.О. и Ерусалимского Я.М. ([2]-[5]). Подход к решению подобных задач очень подробно описан в работах Я.М. и Скороходова В.А. ([12]-[14],[26],[27]), который заключается в построении вспомогательного графа, который взаимнооднозначно связан с исходным, но при этом на нем нет ограничений на достижимость. Алгоритм построения вспомогательного графа определяется конкретным видом ограничений на достижимость. Дальнейшее решение задач ведется на этом вспомогательном графе. Следует отметить, что в результате перестроения на вспомогательном графе возникают так называемые «связанные дуги», в результате чего для построения максимального потока в сети необходимо было существенно модернизировать алгоритм Форда-Фалкерсона. Полученный алгоритм (алгоритм «Прорыва») подробно описан в дипломной работе автора.

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

В первой главе вводится понятие барьерной достижимости на ориентированном графе, у которого множество дуг U = Un U VJ , причем множества попарно непересекающиеся. Множество Uи

- множество нейтральных дуг, т.е. множество, дуги которого подчиняются свойствам стандартной достижимости. Множество U+ - множество дуг, увеличивающих барьерный показатель. Множество UE - множество дуг барьерного перехода. Для удобства дальнейшего описания ограничений, накладываемых на рассматриваемые пути, будем считать, что по дугам графа движется частица, перемещаясь между вершинами графа. С каждым отрезком [i,j]N(\<i< j < п) пути Ц связана числовая характеристика j fi j) = M(m) П t/+ барьерный показатель частицы, m=i тогда если к /-тому шагу путь Ц от своего начала накопил величину барьерного показателя большую либо равную к, то становятся допустимыми для прохождения в последующем этим путем дуги из множества UБ. Пути, удовлетворяющие этому условию мы называем путями длины n(ns N) на графе, допускающими барьерный переход уровня к(к > 1) Существенное отличие данного вида ограничений на достижимость от рассмотренных ранее в [12],[27] заключается в следующем. В отличие от магнитной и вентильной достижимости в случае барьерной достижимости у множества путей имеется транзитивное свойство, т.е. если существует путь из вершины X в вершину у, допускающий барьерный переход, и существует путь из вершины у в вершину Z, допускающий барьерный переход, то существует путь из вершины х в вершину z, допускающий барьерный переход. Кроме этого в условии барьерной достижимости отсутствует директивность при поиске пути, а именно, накопив необходимую для выполнения условия перехода величину барьерного показателя, не обязательно продолжать путь по дугам из множества UБ.

Описан алгоритм перестроения исходного графа, сводящий достижимость вершин исходного графа к достижимости на вспомогательном графе и доказана теорема:

Теорема 1.2.1. Любому пути // на вспомогательном графе G' соответствует путь //, допускающий барьерный переход исходном графе G, и вершина у достижима при условии барьерного перехода уровня к из вершины х на графе G тогда и только тогда, когда на G' достижима из х, по крайней мере, одна из вершин множества Vy = {y,yw•у{к)}.

В главе 1 также рассмотрена задача о случайном блуждании частицы на графе с условием барьерной достижимости. Ясно, что процесс случайного блуждания на таком графе не является Марковским, так как переходы определяются не только вероятностями переходов, но и значением величины барьерного показателя. Для сведения данного процесса к Марковскому предлагается следующий подход: производится построение вспомогательного графа G\X\U\f%). На вспомогательном графе специальным образом задаются вероятности перехода: и • Р(и') = Р(и)<~1-^ , ч)

1. Для wet) (xwj i = 0,k-l: 1- \p(vj)

VjeQ+(x)n(Uc)

2. Для м'е0+(х№): p(u') = p(u).

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

Теорема 1.4.2. Для любой ориентированной сети, допускающей барьерный переход, с источником s и стоком t величина максимального потока равна пропускной способности минимального барьерного разреза.

Во второй главе вводится понятие биполярной магнитности на ориентированном графе, у которого множество дуг yjU m+\jU м , причем все эти множества попарно не пересекаются. Множество Uн - называется множеством нейтральных дуг, т.е. множеством, дуги которого подчиняются свойствам стандартной достижимости. Множество U+ - называется множеством дуг, увеличивающих положительную магнитность, a U - множеством дуг, увеличивающих отрицательную магнитность. Множество Uи+ - называется множеством дуг положительной магнитности, a UM - множеством дуг отрицательной магнитности. С каждым отрезком [i,j]N(l<i< j<n) пути /л связана числовая характеристика яди)=Zi n u+i" Ei ^ w n 1 величина m=i m=i накопленной биполярной магнитности, тогда , если к / - тому шагу путь // от своего начала накопил магнитность ЯД/) большую либо равную к и среди дуг, выходящих из концевой вершины / - той дуги есть хотя бы одна дуга из множества отрицательной магнитности, то следующая (/ +1 - я) дуга биполярного магнитного пути уровня к обязана быть дугой из множества UM, а если к i - тому шагу путь Ц от своего начала накопил магнитность ЯД0 меньшую либо равную -к и среди дуг, выходящих из концевой вершины / - той дуги есть хотя бы одна дуга из множества положительной магнитности, то следующая (/ + 1 - я) дуга биполярного магнитного пути уровня к обязана быть дугой из множества Uм+. Такое условие называется условием биполярной магнитности уровня к. Задача о биполярной магнитности является существенным уточнением модели, рассмотренной в [26],[27]. Биполярная магнитность, с нашей точки зрения, является более «физичной», так как в нашей задаче частица, которая движется по дугам графа, накопив положительную магнитность, притягивается дугами с отрицательной магнитностью, а дугами с положительной магнитностью -отталкивается и наоборот.

Описан алгоритм перестроения исходного графа, сводящий достижимость вершин исходного графа к достижимости на вспомогательном графе.

Рассмотрена задача о случайном блуждании частицы на графе с условием биполярной магнитности. Такой процесс случайного блуждания не является Марковским. Для сведения данного процесса к Марковскому предлагается следующий подход: производится построение вспомогательного графа G' (X' ,£/',/'). На вспомогательном графе специальным образом задаются вероятности перехода.

Также во второй главе показано, что потоковая задача в сети с условием биполярной магнитности сводится к потоковой задаче на вспомогательной сети со связанными дугами. Уточняется понятие разреза в такой сети и доказывается аналог теоремы Форда-Фалкерсона:

Теорема 2.3.1. Для любой ориентированной сети с биполярной магнитностью с источником s и стоком t величина максимального потока равна пропускной способности минимального магнитного разреза.

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

1. Басакер Р.Д., Саати Т.Л. Конечные графы и сети: Пер. с анг. -М.: Наука, 1974. -366с.

2. Басангова Е.О., Ерусалимский Я.М. Смешанная достижимость на частично ориентированных графах.//в сб. Вычислительные системы и алгоритмы. Ростов-на-Дону, РГУ. 1983.-е. 135-140.

3. Басангова Е.О., Ерусалимский Я.М. Различные виды смешанной достижимости .//в сб. Алгебра и дискретная математика. Элиста, КГУ. 1985. -с.70-75.

4. Басангова Е.О., Ерусалимский Я.М. Смешанная достижимость на частично ориентированных графах.//Деп в ВИНИТИ., 1982, №5892-82.

5. Басангова Е.О., Ерусалимский Я.М. Алгоритм нахождения максимальногопотока в частично ориентированной сети .//Дискретные структуры и их приложения. Элиста, КГУ, 1988. -с. 23-28.

6. Дейтел Х.М., Дейтел П.Дж. Как программировать на С+4-: Пер. с англ. -М.: ЗАО «Издательство БИНОМ», 2000г. 1024 е.: ил.

7. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. -М.: Вузовская книга. 2001. -279с.

8. Ерусалимский Я.М. Эйлеровость графов со смешанной достижимостью.//сб. Модели, графы и алгебраические структуры. Элиста, 1989. -с. 45-48.

9. Ерусалимский Я.М., Логвинов С.Ю. Некоторые задачи достижимости на графах с ограничениями.//Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 1996, №2, -с. 14-17.

10. Ерусалимский Я.М., Петросян А.Г. Многопродуктовые потоки в сетях с нестандартной достижимостью.//Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2005, №6, -с. 8-16.

11. Ерусалимский Я.М., Петросян А.Г. Случайные процессы в сетях с биполярной магнитностью.//Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2005, №11, -с. 10-16.

12. Ерусалимский Я.М., Скороходов В. А. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях.//Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2003, №2, -с. 35.

13. Ерусалимский Я.М., Скороходов В.А. Потоки в сетях со связанными дугами.//Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2003, №8, -с. 3-8.

14. Ерусалимский Я.М., Скороходов В.А. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость.//Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2003, №8, -с. 9-12.

15. Замбицкий Д.К., Лозовану Д.Д. Алгоритмы решения оптимизационных задач на сетях. -Кишинев: Штиинца, 1983. -171с.

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

17. Зыков А.А. Основы теории графов. -М: Наука, 1987. -384с.

18. Климов Г.П. Теория вероятностей и математическая статистика. -М.: МГУ, 1983. -394с.

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

20. Круглински Д., Уингоу С., Шеферд Дж. Программирование на Microsoft Visual С++ 6.0 для профессионалов. Пер. с англ. СПб: Питер; М.: Издательско-торговый дом «Русская Редакция», 2001. 864с.: ил.

21. Оре О. Теория графов. Пер. с англ. -М: Наука, 1980. -334с.

22. Петросян А.Г. Многопродуктовые потоки в сетях с ограничениями на достижимость//в сб. Математические методы в современных и классических моделях экономики и естествознания. Ростов-на-Дону, 2005, -с.136-138.

23. Петросян А.Г. Потоковая задача в многопродуктовых сетях с нестандартной достижимостью.//в сб. Современные проблемы математического моделирования. Ростов-на-Дону, 2005, -с.334-340.

24. Петросян А.Г. Потоки в сетях с биполярной достижимостью.//Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2006, №3, -с.32-37.

25. Свами М., Тхуласираман К. Графы, сети и алгоритмы. Пер. с англ. -М.: Мир, 1984, -454с.

26. Скороходов В.А. Случайные блуждания и потоки в сетях с магнитной достижимостью.//в сб. Модели и дискретные структуры. Элиста, 2002. -с. 93-100.

27. Скороходов В.А. Графы с магнитной достижимостью. Марковские процессы и потоки в сетях.//Деп в ВИНИТИ., 2003, №410-В2003.

28. Форд JI.P., Фалкерсон Д.Р. Потоки в сетях. Пер. с англ. -М.: Мир, 1996. -334с.

29. Феллер В. Введение в теорию вероятностей и её приложения, тт. 1,2.-М.: Мир, 1967.

30. Харари Ф. Теория графов. Пер. с англ. -М.: Мир, 1973. -300с.

31. Харари Ф., Палмер Е. Перечисление графов. Пер. с англ. -М.: Мир, 1977. -324с.

32. Цой С., Цхай С.М. Прикладная теория графов. -Алма-Ата: Наука, 1971. -500с.

33. Яблонский С.В. Введение в дискретную математику. -М.: Наука, 1979. -272с.