Содержание к диссертации
Введение
Глава 1. Ориентированные графы с барьерной достижимостью 9
1.1. Основные понятия и определения 9
1.2. Достижимость на графах с условием барьерного перехода 12
1.3.Случайные процессы на графах с барьерной достижимостью 20
1.3.1. Случайные процессы, классическая постановка 20
1.3.2. Случайные процессы на графах с барьерной достижимостью ...24
1.4. Потоковая задача в сетях с барьерной достижимостью 28
1.4.1. Основные понятия, определения и утверждения 28
1.4.2. Потоки в сетях с барьерной достижимостью 29
Глава 2. Ориентированные графы с биполярной магнитностью 37
2.1. Достижимость на графах с условием биполярной магнитности 37
2.2. Случайные процессы на графах с биполярной магнитностью 49
2.3. Потоковая задача в сетях с биполярной магнитностью 54
Глава 3. Многопродуктовые потоки мультисетях 62
3.1. Постановка задачи 62
3.2. Алгоритм построения максимального потока в многопродуктовой мультисети 64
3.3 Теорема Форда-Фалкерсона для мнопродуктовых мультисетей 78
Приложение 83
Литература
- Достижимость на графах с условием барьерного перехода
- Случайные процессы на графах с барьерной достижимостью
- Случайные процессы на графах с биполярной магнитностью
- Алгоритм построения максимального потока в многопродуктовой мультисети
Введение к работе
Ориентированные графы широко используются для моделирования различных классов объектов и процессов. Наиболее часто на графах рассматриваются задача о достижимости (т.е. существовании пути между двумя вершинами), Марковские процессы (т.е. задача о случайном блуждании частицы на графе с заданными на дугах вероятностями) и задача построения максимального потока в ориентированной сети. В классической постановке все вышеперечисленные задачи хорошо изучено и широко применяются в различных областях. Наиболее существенными в этой области являются работы Басакера Р.Д., Ерусалимского ЯМ., Замбицкого Д.К., Зыкова А.А., Лозовану Д.Д., Кристофидеса Н., Оре О., Саати Т.Л., Свами М., Тхуласирамана К., Фалкерсона Д.Р., Форда Л.Р.([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 = Uп U U+ VJ и Б , причем множества попарно непересекающиеся. Множество Uн - множество нейтральных дуг, т.е. множество, дуги которого подчиняются свойствам стандартной достижимости. Множество U+ - множество дуг, увеличивающих барьерный показатель. Множество U Б - множество дуг барьерного перехода. Для удобства дальнейшего описания ограничений, накладываемых на рассматриваемые пути, будем считать, что по дугам графа движется частица, перемещаясь между вершинами графа. С каждым отрезком [i,j]N{\ i j п) пути J i связана числовая характеристика j Ац\} ]) = 2 i№\т) П сУ+ _ барьерный показатель частицы, m=i тогда если к /-тому шагу путь JU от своего начала накопил величину барьерного показателя (0 большую либо равную к, то становятся допустимыми для прохождения в последующем этим путем дуги из множества UБ. Пути, удовлетворяющие этому условию мы называем путями длины п(пе N) на графе, допускающими барьерный переход уровня к{к 1). Существенное отличие данного вида ограничений на достижимость от рассмотренных ранее в [12],[27] заключается в следующем. В отличие от магнитной и вентильной достижимости в случае барьерной достижимости у множества путей имеется транзитивное свойство, т.е. если существует путь из вершины X в вершину у, допускающий барьерный переход, и существует путь из вершины у в вершину z, допускающий барьерный переход, то существует путь из вершины х в вершину z, допускающий барьерный переход. Кроме этого в условии барьерной достижимости отсутствует директивность при поиске пути, а именно, накопив необходимую для выполнения условия перехода величину барьерного показателя, не обязательно продолжать путь по дугам из множества UБ.
Описан алгоритм перестроения исходного графа, сводящий достижимость вершин исходного графа к достижимости на вспомогательном графе и доказана теорема:
Теорема 1.2.1. Любому пути // на вспомогательном графе С соответствует путь ju, допускающий барьерный переход исходном графе G, и вершина у достижима при условии барьерного перехода уровня к из вершины х на графе G тогда и только тогда, когда на G достижима из х, по крайней мере, одна из вершин множества Vy = {у, у ,..., у }.
В главе 1 также рассмотрена задача о случайном блуждании частицы на графе с условием барьерной достижимости. Ясно, что процесс случайного блуждания на таком графе не является Марковским, так как переходы определяются не только вероятностями переходов, но и значением величины барьерного показателя. Для сведения данного процесса к Марковскому предлагается следующий подход: производится построение вспомогательного графа G\X\U\f ). На вспомогательном графе специальным образом задаются вероятности перехода:
!. Дл, « eeV ) / = 0 : " = ИНі_ llp{Vj)) Vje@+(x)n(UE)
2. Для w e0+(xW): Р(М,) = р(й).
Также в первой главе показано, что потоковая задача в сети с условием барьерного перехода сводится к потоковой задаче на вспомогательной сети со связанными дугами. Уточняется понятие разреза в такой сети и доказывается аналог теоремы Форда-Фалкерсона:
Теорема 1.4.2. Для любой ориентированной сети, допускающей барьерный переход, с источником s и стоком t величина максимального потока равна пропускной способности минимального барьерного разреза.
Во второй главе вводится понятие биполярной магнитности на ориентированном графе, у которого множество дуг
U - U н U (У+ LJ [/_ VJ UM+ U U м_} причем все эти множества попарно
не пересекаются. Множество UH - называется множеством нейтральных дуг, т.е. множеством, дуги которого подчиняются свойствам стандартной достижимости. Множество U+ - называется множеством дуг, увеличивающих положительную магнитность, a U_ - множеством дуг, увеличивающих отрицательную магнитность. Множество UM+ - называется множеством дуг положительной магнитности, a UM_ - множеством дуг отрицательной магнитности. С каждым отрезком [i,j]N(l i j n) пути № связана числовая характеристика накопленной биполярной магнитности, тогда , если к / -тому шагу путь JU от своего начала накопил магнитность лДО большую либо равную к и среди дуг, выходящих из концевой вершины / - той дуги есть хотя бы одна дуга из множества отрицательной магнитности, то следующая (/ +1 - я) дуга биполярного магнитного пути уровня к обязана быть дугой из множества UM_, а если к / - тому шагу путь Ц от своего начала накопил магнитность лДО меньшую либо равную -к и среди дуг, выходящих из концевой вершины / - той дуги есть хотя бы одна дуга из множества положительной магнитности, то следующая (z + 1 - я) дуга биполярного магнитного пути уровня к обязана быть дугой из множества UM+. Такое условие называется условием биполярной магнитности уровня к. Задача о биполярной магнитности является существенным уточнением модели, рассмотренной в [26],[27]. Биполярная магнитность, с нашей точки зрения, является более «физичной», так как в нашей задаче частица, которая движется по дугам графа, накопив положительную магнитность, притягивается дугами с отрицательной магнитностью, а дугами с положительной магнитностью -отталкивается и наоборот.
Описан алгоритм перестроения исходного графа, сводящий достижимость вершин исходного графа к достижимости на вспомогательном графе.
Рассмотрена задача о случайном блуждании частицы на графе с условием биполярной магнитности. Такой процесс случайного блуждания не является Марковским. Для сведения данного процесса к Марковскому предлагается следующий подход: производится построение вспомогательного графа G {Xх,/ ,/ ). На вспомогательном графе специальным образом задаются вероятности перехода.
Также во второй главе показано, что потоковая задача в сети с условием биполярной магнитности сводится к потоковой задаче на вспомогательной сети со связанными дугами. Уточняется понятие разреза в такой сети и доказывается аналог теоремы Форда-Фалкерсона:
Теорема 2.3.1. Для любой ориентированной сети с биполярной магнитностью с источником s и стоком t величина максимального потока равна пропускной способности минимального магнитного разреза.
В третьей главе дается определение многопродуктового потока в сети. В указанных выше работах поток считается однородным (в том смысле, что все частицы (элементы) потока подчиняются одним и тем же ограничениям на достижимость). В данной главе рассматривается задача о многопродуктовых потоках в сетях с нестандартной достижимостью, причем типы достижимости для разных продуктов могут быть различными. Разработан подход к построению максимального потока в многопродуктовой сети, который заключается в согласованном рассмотрении сетей из связанного набора. Помимо понятия связанных дуг вводится понятие связанных сетей. Предложен алгоритм построения набора связанных сетей по исходному графу, сводящий задачу о построении многопродуктового потока к задаче о последовательном построении однопродуктовых потоков на каждой из сетей набора. Показано, что порядок выбора продуктов из набора не оказывает влияния на величину суммарного потока. Также приведена задача о максимальном потоке в многопродуктовой сети с дополнительным условием: величина потока каждого продукта должна быть не меньше некоторой заданной величины. Показано, что в данном случае порядок выбора продукта играет существенную роль.
Достижимость на графах с условием барьерного перехода
Пусть имеем орграф G(X,U,j), Множество U = UH VjU+\jUБу причем множества попарно непересекающиеся. Множество Uп - множество нейтральных дуг, т.е. множество, дуги которого подчиняются свойствам стандартной достижимости. Множество U+ - множество дуг, увеличивающих барьерный показатель. Множество UБ - множество дуг барьерного перехода. Для удобства дальнейшего описания ограничений, накладываемых на рассматриваемые пути, будем считать, что по дугам графа движется частица, перемещаясь между вершинами графа. Пусть М путь длины п. С каждым отрезком [i,j]N(l i j n) пути М свяжем числовую характеристику j m-i равную количеству дуг, увеличивающих барьерный показатель частицы. При этом в указанной сумме каждая дуга считается столько раз, сколько раз она встречается на рассматриваемом отрезке пути. В случае простого пути мы имеем равенство: (i,j) = M([hj]N) U+. Характеристику M(hj) будем называть величиной барьерного показателя отрезка [i,j]N пути JU .
Через АД/) = (0) + (1,/) обозначим величину барьерного показателя на пути JU через / шагов от начала пути. Определим величину -13-AM (0) = 0 (случай, когда (0) Ф 0 будет рассмотрен далее). Будем называть ее величиной начального барьерного показателя пути № .
Определение 1.2.1. Путь JU будем называть путем длины n(neN) на графе G, допускающим барьерный переход уровня к(к 1), если выполняется следующее условие: \fm\ju(m) є UE = ЛМ (т-\) к.
Другими словами, если к /-тому шагу путь Ц от своего начала накопил величину барьерного показателя (0 большую либо равную к, то становятся допустимыми для прохождения в последующем этим путем дуги из множества UБ . Данное условие будем называть условием барьерного перехода уровня к. Пример 1.2.1. Пусть дан граф (рис. 1.2.1.) при к = 2, его дуги Щ,и2,и3,и4,и5 такие, что /(и,) = (1,2), Л«2) = (2,3), /(и,) = (3,1), Д«4) = (3,4) и Ж) = (2,4). Считаем, что U+ = {щ,и2}, UH = {щ,щ} ииБ = {и5} Рассмотрим путь № = {WIJW5/ -14-Путь М не является путем, допускающим барьерный переход уровня 2 , так как он не удовлетворяет условию (/ (2) Є и Б, но \Ч 2). Рассмотрим путь V = \Ul,U2,U3iU5) ш \ \ ) = 2 5 так как УЦ лт = iwi и2 » w3 / , а дуги Wj, w2 Є (У +.
Путь У является путем, допускающим барьерный переход уровня 2 , так как он удовлетворяет условию (И/+) = 5 Є UБ и лу\р) = 2),
Замечание 1.2.1. Существенное отличие данного вида ограничений на достижимость от рассмотренных ранее в [12],[27] заключается в следующем. В отличие от магнитной и вентильной достижимости в случае барьерной достижимости у множества путей имеется транзитивное свойство, т.е. если существует путь из вершины X в вершину У, допускающий барьерный переход, и существует путь из вершины У в вершину z , допускающий барьерный переход, то существует путь из вершины х в вершину Z , допускающий барьерный переход. Кроме этого в условии барьерной достижимости отсутствует директивность при поиске пути, а именно, накопив необходимую для выполнения условия перехода величину барьерного показателя, не обязательно продолжать путь по дугам из множества UБ.
Определение 1.2.2. Граф G(X,U,f), на котором рассматриваются пути, допускающие барьерный переход уровня к, будем называть графом с условием барьерного перехода уровня к.
Таким образом, граф с условием барьерного перехода - это граф, на котором не все пути являются допустимыми. Отсюда следует, что стандартный алгоритм Дейкстры нахождения кратчайшего пути из вершины в вершину не применим, поскольку алгоритм Дейкстры не учитывает наличие условия барьерного перехода.
Подход к решению задачи о достижимости на графах с условием барьерного перехода состоит в построении вспомогательного графа, количество вершин которого больше, чем у исходного, но на котором нет условий барьерного перехода, т.е. все пути являются допустимыми. При этом путь, допускающий барьерный переход на исходном графе можно единственным образом восстановить по пути на вспомогательном графе.
Случайные процессы на графах с барьерной достижимостью
Пусть имеем орграф . На дугах графа G заданы вероятности перехода. Пусть граф G является графом с условием барьерного перехода порядка к . В случае, когда величина барьерного показателя достигает значения к, дуги множества UБ становятся допустимыми. В случае, когда величина барьерного показателя меньше к, вероятности переходов задаются следующим образом: МхеХ \/u\(ue d+(x))8c(uUE) р(и) = р(и) (- ) у/Є0+(х)п( .)
Ясно, что процесе случайного блуждания в сети, допускающей барьерный переход, не является Марковским, так как переходы определяются не только вероятностями переходов, но и значением величины накопленного барьерного показателя.
Для сведения данного процесса к Марковскому предлагается следующий подход:
Производится построение вспомогательного графа G\X\U\f) по указанному выше алгоритму.
Вероятности перехода на вспомогательном графе зависят от барьерного уровня, на котором находится вершина графа:
Для каждой рассматриваемой вершины xw графа G соответствующую ей вершину графа G будем обозначать х. Для каждой рассматриваемой дуги и графа G соответствующую ей дугу графа G будем обозначать и . І.Для и є0+(х(і)) і = 0,к-\: Ж) = РІМ) (- р , ч) і- LP J) VjeQ+(x)n(UB) 2. Для w e0+(/]): р(и ) = р(и)т
На вспомогательном графе за счет увеличения количества состояний случайный процесс зависит только от одного параметра (вероятности перехода по некоторой дуге). После такого перестроения процесс на вспомогательном графе G является Марковским и имеет место
Вероятность перехода из вершины х в вершину у на графе G за t шагов равна сумме вероятностей перехода частицы на графе G из вершины х в каждую из вершин у за / шагов, или, что то же самое она равна вероятности перехода частицы за t шагов из вершины х во множество вершин {У ,у ,...,У } и имеет место формула
Видно, что если рассматривать граф без условия барьерной достижимости, то вероятность перехода из вершины 1 в вершину 4 за 5 шагов равна 0.141, а с условием барьерной достижимости уровня 2 она равна 0.42. Приведем некоторые понятия и определения, необходимые для дальнейшего изложения ([28]). Определение 1.4.1. Сетью будем называть связный граф без петель и кратных дуг.
Рассмотрим сеть G с источником s и стоком /, допускающую барьерный переход. Для любой дуги и є U задан вес с(и) - пропускная способность дуги.
Определение 1.4.2. Пусть X = 7 и Y\YС\ Т= 0,s є Y,t є Г. Разрезом (Y,У) будем называть множество дуг ueU, обладающих свойствами (/?i f){u) є Y, (р2 о f)(u) є 7 , такое, что для любого пути ju(s, t) выполняется fi{s, t) n (Y, Y ) Ф 0.
Другими словами разрезом будем называть множество дуг (начальные вершины которых принадлежат множеству Y, а концевые - множеству У) таких, что любой путь от источника до стока обязательно содержит дугу этого множества.
В классической постановке рассматриваются сети без кратных дуг, поскольку, если существуют дуги щ,...,ик такие, что /(щ) =... = f{uk) = (х,у), то замена их дугой и, такой, что /(и) = (х,у), а к С\Щ = 2_,с(м/) не влияет на решение. В случае сетей с ограничениями на /=1 достижимость кратные дуги могут принадлежать различным подмножествам (дуги допускающие барьерный переход и дуги не допускающие барьерный переход) множества U, поэтому простой заменой кратных дуг одной дугой нельзя свести задачу к классической.
Определение 1.4.5. Рассмотрим всевозможные подмножества дуг разреза (Y,Yr) обладающие следующим свойством: для любой дуги и подмножества разреза существует путь v{s,t), допускающий барьерный переход на исходной сети G, содержащий эту дугу. Подмножество такого вида наибольшей мощности будем называть барьерным разрезом (У, У )м .
Рассмотрим потоковую задачу в сети, допускающей барьерный переход. В данной задаче нельзя применять стандартные алгоритмы построения максимального потока, так как в условиях барьерного перехода в сети не все пути являются допустимыми.
Подход к решению поставленной задачи заключается в построении вспомогательной сети G , по правилам, указанным для графов, допускающих барьерный переход порядка к.
Одного построения вспомогательной сети недостаточно. Необходимо кроме этого существенно модернизировать алгоритм Форда-Фалкерсона.
Действительно, решаем потоковую задачу по аналогии с решением задачи о достижимости, т.е. задаем веса для дуг вспомогательной сети следующим образом:
Обозначим через U = {ut,,..., и\} - множество дуг графа С, порожденное дугой иі і = \,т. Полагаем пропускную способность всех дуг множества U{,) равными пропускной способности дуги и .
Случайные процессы на графах с биполярной магнитностью
Пусть G{X,U,f) - орграф и U = UH u U+ и U_ и UM+ и Uи_ , причем, все эти множества попарно непересекающиеся. Рассмотрим случайный процесс блуждания частицы по вершинам данного графа. Будем считать, что существует два типа магнитности: положительная и отрицательная, а множество дуг, изменяющих величину магнитности блуждающей частицы состоит из двух множеств: U+ и U_. При прохождении по любой дуге множества U+ частица увеличивает абсолютную величину положительной магнитности и уменьшает абсолютную величину отрицательной магнитности, а при прохождении по любой дуге множества U_ - наоборот. Увеличение абсолютных величин происходит до некоторого значения, при достижении которого абсолютная величина магнитности больше не увеличивается. Положим его равным к и будем считать, что частица увеличивает абсолютные величины магнитностей одинаковыми порциями, равными 1. При этом, чем больше величина положительной магнитности, тем больше вероятность следующего перехода по дугам множества UM_ и меньше вероятность следующего перехода по дугам множества U \ UM_; и чем больше величина отрицательной магнитности, тем больше вероятность следующего перехода по дугам множества UM+ и меньше вероятность следующего перехода по дугам множества U \ UM+ .
Если величина положительной магнитности достигла значения к и для данной вершины есть выходящие дуги из множества UM_, вероятность перехода по дугам из множества U \ UM_ становится равной нулю.
Если величина отрицательной магнитности достигла значения к и для данной вершины есть выходящие дуги из множества UM+, вероятность перехода по дугам из множества U \ UM+ становится равной нулю.
Из-за условия магнитности, рассматриваемый процесс не является Марковским, так как следующий переход определяется не только вероятностями перехода по дугам, но и некоторой памятью о проделанном частицей пути. При поставленном условии магнитности вероятность перехода из некоторого состояния меняется в зависимости от величины магнитности частицы, находящейся в данном состоянии.
Для сведения данного процесса к Марковскому предлагается следующий подход:
Производится построение вспомогательного графа G\X\U\f) по указанному выше алгоритму.
Вероятности перехода на вспомогательном графе зависят от магнитного уровня, на котором находится вершина графа:
Для каждой рассматриваемой дуги и еС соответствующую ей дугу исходного графа будем обозначать v.
Рассмотрим путь ju = {ul,u2,u3} (в виде последовательности вершин -1— 2—»3— 1)и рассмотрим вероятности перехода из вершины 1 в начале и конце пути. В начале пути =0 и вероятности перехода из вершины 1 равны: p(U[) - 0,5, р{и5) = 0,5. В конце пути % = 2 и, значит, переход из вершины 1 по дуге и5 невозможен, поскольку дуга и5 є UM+. Следовательно, вероятность перехода по ней (в данный момент) равна нулю
и соответственно вероятность перехода по оставшейся дуге их (є U+) равна единице.
В данном графе вероятность перехода из вершины 1 в вершину 4 за 5 шагов равна 0,225, а при отсутствии условий биполярной магнитности вероятность перехода равна 0,0225, т.е. в десять раз меньше. В графе с условиями биполярной магнитности наряду с увеличением вероятности перехода в некоторые вершины происходит уменьшение вероятности перехода в другие вершины. Например, в исходном графе при отсутствии условий биполярной магнитности вероятность перехода из вершины 1 в вершину 3 за 5 шагов равна 0,2025, а в графе с условиями биполярной магнитности уровня 2 вероятность перехода из вершины 1 в вершину 3 за 5 шагов равна 0.
Определение 2.3.1. Рассмотрим всевозможные подмножества дуг разреза {Y,Y ) обладающие следующим свойством: для любой дуги и подмножества разреза существует биполярный магнитный путь ju(s,t) содержащий эту дугу. Подмножество такого вида наибольшей мощности будем называть магнитным разрезом {Y, У ) .
Рассмотрим потоковую задачу в сети с условием биполярной магнитности. В данной задаче нельзя применять стандартные алгоритмы построения максимального потока, так как в условиях биполярной магнитности не все пути в сети являются допустимыми.
Подход к решению поставленной задачи заключается в построении вспомогательной сети G , по правилам, указанным для графов с биполярной магнитностью уровня к.
Одного построения вспомогательной сети недостаточно. Необходимо кроме этого существенно модернизировать алгоритм Форда-Фалкерсона.
Действительно, решаем потоковую задачу по аналогии с решением задачи о достижимости, т.е. задаем веса для дуг вспомогательной сети следующим образом:
Обозначим через С/ = {ип...,и } - множество дуг графа С, порожденное дугой ut i = \,m. Полагаем пропускную способность всех дуг множества U{,) равными пропускной способности дуги ut .
На G находим поток и переносим его на G следующим образом: суммарный поток, пропущенный по дугам множества U{,), считаем пропущенным по дуге и.{ \/i = \,m. Однако, если искать поток на С стандартными алгоритмами, то может возникнуть ситуация, когда по одной дуге сети G будет пропущен поток, величина которого больше пропускной способности этой дуги.
Алгоритм построения максимального потока в многопродуктовой мультисети
Постановка данной задачи привела к необходимости перейти от сетей со связанными дугами к понятию набора сетей со связанными дугами. Предлагается следующий порядок действий для решения многопродуктовой задачи. Необходимо сделать перестроения сети для каждого продукта. Соответственно мы будем иметь столько новых сетей со связанными дугами, сколько продуктов имеется в нашей задаче. Пусть имеем сеть G и к продуктов, тогда после перестроений получим к новых сетей со связанными дугами: G ... G . Полученный набор сетей следует воспринимать как один объект, в связи с этим введем понятие набора связанных сетей.
Обозначим через к щ \ — U - множество дуг, где Uі множество связанных дуг сети Gl, порожденное дугой ин И. EG i = \,m. Множество всех дуг набора сетей G ... G - U =kUUi J..\JkUUm .
Считаем, что заданы «суммарные» пропускные способности множеств UUi \с\к Uи, )) i = \,m (сумма величин потоков, проходящих по дугам множества, не может превышать величину с( UUj )). Множество {G\G2,---,Gk} будем -называть набором сетей со связанными дугами, порожденных многопродуктовой мультисетью G. Множества и. будем называть связанными дугами набора сетей Gx ... G , порожденных многопродуктовой мультисетью.
Предлагается алгоритм построения максимального многопродуктового потока, основанный на согласованном рассмотрении сетей из связанного набора. Каждому продукту соответствует одна сеть из набора. Допустим, что в условии задачи не оговорен порядок выбора продуктов (другой случай будет рассмотрен далее), поэтому можно начинать процедуру построения максимального потока с любого продукта. Пусть выбирается продукт j. Используя алгоритм «прорыва» необходимо построить максимальный поток
в сети GJ. На величину потока, построенного в сети GJ необходимо уменьшить пропускную способность дуг путей потока и связанных с ними дуг набора сетей {Gl,G2,---,Gk}. Затем, выбирается следующий продукт и т.д. пока максимальный поток не будет построен в каждой сети из набора Максимальным потоком многопродуктовой мультисети G будем называть сумму максимальных потоков сетей из набора {G\G\-,Gk}.
Данную сеть будем насыщать двумя продуктами с двумя видами ограничений на достижимость: магнитная достижимость, описанная в работах [26],[27] и разрешенная достижимость, описанная в дипломной работе автора настоящей диссертации. Приведем определения этих видов достижимости. Пусть имеем орграф G(X, U J).
Множество U — Uн {J Uм , причем множества UH,Uм попарно непересекающиеся. Множество UH -множество нейтральных дуг, т.е. множество, дуги которого подчиняются свойствам стандартной достижимости. Множество м - множество магнитных дуг. Пусть М - путь длины п. С каждым отрезком [i,j]N(\ i j п) пути JU свяжем числовую характеристику j m=i
Определение 3.2.1. Путь JU будем называть магнитно-накопительным путем порядка к{к 1) длины п{п є N) с неубывающей магнитностью на графе G , если выполняется следующее условие: Мт{ (т) к){Є+ ((р2 о / о М)(т)) п UM 0) {М(т + \)eUM). Пусть имеем орграф (j\J(, и, J ) . Множество U = Uн KJ и 3 причем множества н з попарно непересекающиеся. Множество UH -множество нейтральных дуг, т.е. множество, дуги которого подчиняются свойствам стандартной достижимости. Множество Ц? - множество запрещенных дуг. Определение 3.2.2. Путь JU будем называть разрешенным путем длины п{п є JV) на графе G, если выполняется следующее условие: \fm(ju(m) eU3)= {fi{m + \)eUH). -67 I) Для первого продукта запрещенные дуги (1,2), (2,4), (1,3) и (3,4) II) Для второго продукта магнитные дуги (1,2), (1,3), (3,2) и (3,4) Обозначения: 1) Числа на дугах означают соответственно пропускную способность и поток. 2) c(U{p/)) - суммарная пропускная способность множества связанных дуг, порожденных дугой (р, г) исходного графа, где р - начальная вершина дуги в исходном графе, г - конечная вершина дуги в исходном графе. 3) Связанные дуги обозначены двойной чертой. Сделаем перестроения для каждого вида достижимости: I) для случая запрещенных дуг (рис. 3.2.2.)
