Диссертация (1173083), страница 14
Текст из файла (страница 14)
Принимаем, что:а) в сети есть две выделенные вершины – исток (только исходящие дуги)и сток (только входящие дуги);б) любая вершина лежит на каком-нибудь пути из истока в сток.76Поток в сети – это нагрузка на дуги, обладающая следующимисвойствами: 1) поток по дуге не может превышать пропускной способностидуги и всегда неотрицателен; 2) для любой вершины (кроме истока и стока)количество втекающего потока равно количеству вытекающего потока.В нашем случае интерпретация потока – это количество груза северногозавоза определенного вида, которое транспортируется по участкам сети,представляемым в модели соответствующими дугами.2.2.2 Формальное определение потока в сетиПусть задана сеть с множеством вершин V.
Для вершин u и v зададимфункцию f(u,v) нагрузки, обладающую следующими свойствами:а) f(u,v)c(u,v) – поток не превышает пропускной способности дуги;б) f(u, v) = –f (v,u) – поток по дуге из вершины v в вершину u равен повеличине потоку из вершины u в вершину v и противоположен по знаку;в) для любой вершины (u), кроме истока и стока, выполняетсяследующее условие:∑ f (u, v) = 0 ;u ⊂Vг) если между вершинами u,v отсутствует дуга, то принимается: f(u,v) = 0.Рассмотрим пример, приведенный на рисунке 2.2Рисунок 2.2 – Пример нагруженной сети [6]77На каждой дуге сети на рисунке 2.2 указана текущая нагрузка на каждойдуге (первая цифра) и пропускная способность дуги (вторая цифра).
Еслиуказана одна цифра, – это пропускная способность дуги.На рисунке (2.2): f(S, 3) = 8; f(3, 2) = –4; f(1, 3) = –1.На рисунке 2.2 дуги (1,2), (4,2), (4,t) исчерпали свою пропускнуюспособность.2.2.3 Остаточная пропускная способность сетиДля дуг нагруженного ориентированного графа вводится понятие«остаточная пропускная способность», которая понимается как разностьмежду пропускной способностью дуги и текущей нагрузкой. Например, длядуги (u,v) остаточная пропускная способность c f (u, v) определится изуравнения:cf =(u, v) c(u, v) − f (u, v) .(2.1)Для дуги (3,4) на рисунке 2.2 пропускная способность c(3, 4) = 14 ,нагрузка на дугу (3,4) f (3, 4) = 11.
Тогда величина остаточной пропускнойспособности c f (3, 4) , в соответствии с уравнением (2.1) равна:c f (3, 4) = c(3, 4) − f (3, 4) = 14 − 11 = 3 .(2.2)Для нагруженной сети вводится понятие «Остаточной сети».Правила построения остаточной сетиДля заданного потока f(u, v) в сети с пропускной способностью реберc(u, v) остаточная сеть строится по правилу r(u, v) = c(u, v) – f(u, v). Такимобразом, пропускная способность каждой дуги в остаточной сети равнаразности пропускной способности дуги и нагрузки на дугу. Если в исходнойсети для какой-либо дуги пропускная способность и нагрузка совпадают, то востаточной сети данная дуга будет иметь нулевую пропускную способность;следовательно, такая дуга из остаточной сети должна быть удалена.
Важноотметить, что для всех дуг остаточной сети нагрузка равна нулю,78следовательно, для дуг отражается только их остаточная пропускнаяспособность.Определение минимального разрезаПусть в сети G задан разрез (S, T). Пропускная способность разреза c(S,T) – это сумма пропускных способностей ребер, пересекающих разрез внаправлении от истока к стоку. Разрез называется минимальным, если онимеет минимальную пропускную способность из всех возможных разрезов.Если в сети G задан поток, то для данного разреза c(S, T) можнорассматривать поток через разрез как алгебраическую сумму потоков f(S, T)по ребрам, пересекающим разрез. При этом знак каждого слагаемого зависитот направления дуги, попавшей в разрез.2.2.4 Теорема Форда-Фалкерсона о максимальном потоке и минимальномразрезе и ее использование для определения максимальнойпропускной способности транспортно-технологической системысеверного завозаЕсли в сети G задан разрез (S, T) и поток f, то следующие утвержденияравносильны [270, 271]:1.
Поток f максимален.2. В остаточной сети Gf нет дополняющих путей.3. Поток f равен пропускной способности минимального разреза в сети.Проверим утверждение теоремы на примере сети, показанной нарисунке 2.2. Как видно из рисунка, суммарный поток из источника S в сток tравен 19. Покажем, что данный поток максимальный. Для этого построим поуказанным выше правилам остаточную сеть для данной сети.
На рисунке(2.3) показан результат построения остаточной сети.79Рисунок 2.3 – Пример остаточной сети [6]Как видим, несмотря на то, что часть дуг графа имеет остаточнуюпропускную способность, построить путь от источника до стока, используядуги остаточной сети, невозможно. Следовательно, поток в сети, показаннойна рисунке 2.2, максимальный. Минимальный разрез при этом проходит подугам (1,2), (2,3), (4,2), (4,t).
Поток на дугах минимального разреза равеналгебраической сумме потоков, входящих в указанный минимальный разрез.Эта сумма равна: 12 – 4 + 7 + 4 =19.1. Обоснование возможности решения задачи для каждого вида грузаотдельноРассмотрим задачу определения максимальной пропускной способностисистемы на примере перевозки твердого и жидкого топлива. Данные видытоплива не конкурируют за ресурсы транспортной системы, поскольку дляперевозки каждого из этих грузов используется специализированныйподвижной состав, а в узловых точках системы для перемещения груза содного вида транспорта на другой используются разные технологическиеплощадки и оборудование. Из этого следует, что определять максимальнуюпропускную способность системы можно для каждого вида груза отдельно.Крометого, необходиморассматриватьтранспортно-технологическуюсистему в зависимости от сезона, поскольку временные маршруты движениягрузовых транспортных средств изменяются [15].802.Представлениетранспортно-технологическойсистемыввидевзвешенного ориентированного графаДля решения задачи определения пропускной способности транспортнотехнологической системы с использованием теоремы Форда-Фалкерсона еенеобходимо представить для каждого вида груза в виде взвешенногоориентированного графа, то есть в виде множества вершин и дуг, гдевершинами графа обозначают пункт отправки/доставки груза, а дугамиобозначают маршрут перевозки между соответствующими пунктами.
Вескаждой дуги в нашей задаче будет означать пропускную способность участкамаршрута по виду груза. Кроме того, поскольку транспортная сетьмультимодальная, для того, чтобы отразить пропускную способностьузловых точек маршрута, необходимо пункты, где происходит передача грузас одного вида транспорта на другой, представить в виде двух узлов сети:один узел для прибывающего груза на одном виде транспорта, другой узелдля отправляемого груза на другом виде транспорта [41].В теореме Форда-Фалкерсона рассматривается транспортная сеть содним истоком и одним стоком.
В транспортно-технологической системесеверного завоза участвуют несколько разных, территориально разобщенныхпоставщиков груза. Для того, чтобы привести модель системы к виду,необходимому для использования положений теоремы Форда-Фалкерсрна,следует добавить единый (фиктивный) исток (S), от которого идут дуги сбесконечной пропускной способностью к узлам, моделирующим реальныеобъекты поставки груза, и далее к единственному стоку (t).2.2.5 Определение максимальной пропускной способности дуг графатранспортно-технологической системы доставки грузов северногозавоза на примере Иркутской областиПоскольку твердые и жидкие виду топлива могут перевозиться всемивидаминаземноготранспорта,модельтранспортно-технологическойсистемы в виде графа будет иметь одинаковый вид как для твердого, так идля жидкого топлива (далее мы рассматриваем построение графа и81определение максимальной пропускной способности дуг графа на примереодного вида груза).
На рисунке 2.4 представлен граф транспортнотехнологической системы северного завоза для летнего сезона. Узлы (5), (9);(6), (10); (7), (11) моделируют технологические процессы перевалки груза содного вида транспорта на другой. Нагрузка С159 на дугу (5),(9) показываетпропускную способность перевалки грузов с железнодорожного транспортана речной в узлах (5) и (9), нагрузка С259 на дугу (5),(9) показываетпропускную способность перевалки грузов с автомобильного транспорта наречной в узлах (5) и (9). Аналогичное значение имеют величины С1610, С2610,С1711.Рисунок 2.4 – Граф транспортно-технологической системы северного завозадля летнего сезона, адаптированный для применения теоремы ФордаФалкерсонаНа рисунке 2.5 представлен граф транспортно-технологической системысеверного завоза для зимнего сезона.82Рисунок 2.5 – Граф транспортно-технологической системы северного завозадля зимнего сезона, адаптированный для применения теоремы ФордаФалкерсона2.2.6 Определение максимальной пропускной способности дуг графа,соответствующих временным участкам маршрутов доставкигрузов северного завозаОт точности определения максимальной пропускной способностимаршрутов доставки грузов северного завоза зависит точность решениязадачи планирования.На первом этапе необходимо оценить максимальную пропускнуюспособность каждого участка транспортной сети.Необходимо решать данную задачу отдельно для каждого сезона,рассматриваякаждыйучастоктранспортно-технологическойсистемыотдельно.
Наиболее изменчивыми являются участки, соответствующиевременным транспортным маршрутам [250, 254, 258].Рассмотрим решение задачи на примере летнего периода эксплуатации.В летний период основной фактор, от которого зависит использование83северных рек для перевозки грузов, – продолжительность навигации, то естьпериод времени, в течение которого по северным рекам на соответствующихучастках могут перевозиться грузы.Следовательно, оценку максимальной пропускной способности участковсистемы необходимо начинать с временных участков транспортной сети,которая зависит от сроков навигации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
