Войти в мой кабинет
Регистрация
ГОТОВЫЕ РАБОТЫ / КУРСОВАЯ РАБОТА, ТРАНСПОРТНЫЕ СРЕДСТВА

Транспортная сеть, нахождение полного, максимального потоков (Форд-Фалкерсон)

cool_lady 372 руб. КУПИТЬ ЭТУ РАБОТУ
Страниц: 31 Заказ написания работы может стоить дешевле
Оригинальность: неизвестно После покупки вы можете повысить уникальность этой работы до 80-100% с помощью сервиса
Размещено: 10.04.2021
В данной работе была рассмотрена теоретическая часть, касающаяся темы курсовой работы. Были решены примеры. В заключении курсовой работы был сделан вывод о значимости и практическом применении метода Форда-Фалкерсона
Введение

Тема моей курсовой работы “Транспортная сеть, нахождение полного, максимального потоков (Форд-Фалкерсон)”Прежде всего, нужно заметить, что тематика задач о максимальном потеке в сети изучается уже больше 60 лет. Для решения задач подобного типа использовался simplex метод Линейного Программирования, что было не очень эффективно, тогда Форд и Фалкерсон решили рассматривать для решения задачи о максимальном потоке ориентированную сеть и решение искать с помощью итерационного алгоритма. Практическое применение этого метода можно реализовать при моделировании различных процессов физики, химии, решения задач теории графов,алгоритм Форд-Фалкерсона может помочь решить проблему максимизации потока нефти по нефтепроводу При решении задач на нахождение максимального потока главную роль играет изучение поперечных сечений сети, так же нужно найти ограниченное поперечное сечение, которое будет узким местом. Такие узкие места определяют пропускную способность системы.
Содержание

Введение …………………………………………………………………………..5 1 Теоретическая база…………………………………………………………....6 1.1 Постановка задачи максимального потока ………………..……………..…6 1.2 Нахождение максимального пропускного потока…………..….……….….7 1.3 Пропускная способность и поток………………………………...……...…..8 1.4 Сводимость некоторых задач о максимальном потоке в сети к рассматриваемой………………………………………………………………......8 2 Пример потока …………………………………………..…..……….…..….11 2.1 Величина потока. Максимальный поток………………………………..…14 2.2 Теорема Форда-Фалкерсона.Задача о максимальном потоке……….…..15 2.3 Задача о максимальном потоке ….………………………….………….…..18 2.4 Остаточная сеть…………………………………………………...……..…..20 2.5 Лемма об остаточной сети………………………………….…………..…....6 3 Алгоритм Форда-Фалкерсона……………………………………….………12 3.1 Анализ алгоритма максимальный поток равен минимальному разрезу…………………………………………………………………………....12 2.2 Поиск цепи в остаточной сети………………………………..……......15 3.3 Пример 1…………………………………………………..…..……….…….15 3.4 Пример 2…………………………………………………….………………16 3.5 Пример 3………………………………………………………………..…..16 3.6 Использование метода Форда-Фалкерсона для повышения интегрированности действий звеньев логической сети поставок…………..17 Список использованной литературы …………………………………….…….26
Список литературы

1. А.М. Аллавердиев, И.В. Платонова «Прикладная математика. Элементы теории графов» М.2000 2. Лекции по прикладной математике И.В. Платоновой 3. В.Н. Нефедов, В.А. Осипова «Курс дискретной математики» М. 1992 4. С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики» М. 2002 5.Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. 6.Андерсон Дж. Дискретная математика и комбинаторика. М.: «Вильямс», С
Отрывок из работы

1.Теоретическя база Граф Дано: где , – дуга, e2 = (1, 2) и – неориентированные ребра. Рисунок 1-Граф G Постановка задачи максимального потока. Теперь поговорим непосредственно о теме курсовой работы. Если говорить о наглядности, то можно представить железную дорогу с путями , стрелками и точками отправления. Предположим, что нам дана огромная железная дорога. Но у этой дороги, есть начало так называемый источник и только один конец ,он называется -сток. Можно вообразить рельсы, по которым движение возможно(дуга сети).Стрелочные перегоны-это пункты, в которых можно сменить направление, такие пункты называются вершинами Поезд, движущийся по этим рельсам может перевозить строго определенное количество чего либо, ограниченное весом ли или местом заполнения. В нашем случае ограничение по весу, что означает - числа поставленные в соответствии дугам-пропускная способность. Если предположить, что из А в Б происходит беспрерывная поставка груза( то есть в каждый момент времени составы локомотива заполнены грузами, отправляющимися из А в б и находящимися в пути),то нужно рассмотреть несколько важных вопросов. 1) Какой лимит веса может перевезти поезд из начала в конец, за отведенное время и каким образом требуется распределить грузы между направлениями. 2)Как именно нужно увеличить пропускную способность в графе , что бы обеспечить максимально объемную доставку груза 1.1Нахождение максимального пропускного потока. Я хочу заметить, что подобные задачи-это задания линейного программирования, следовательно решать можно и simplex методом, но делать мы этого, конечно, не будем. Можно добавить, что теорема максимальном потоке, а так же минимальном разрез-это есть теорема двойственности для задачи ЛНП Метод Форма-Фалкерсона—это алгоритм , по своей сути- simplex метод для конкретной ситуации. Алгоритму требуется достаточно много итераций. Для начала найдем хоть какой-нибудь поток, при условии, что он будет не нулевого веса. А если говорить точнее, то я должен найти путь из в ,лучше конечно, что бы с максимальным весом, для этого можно еще использовать алгоритм Дийкстры После чего на каждом шаге требуется наблюдать, можно ли модифицировать поток так, что бы вес стал больше. Если преобразовать поток не получается, значит найдено то, что нужно- максимальный поток. Как же работает модификация и что она из себя представляет? Начинаем работу с того, что прибавляем к потоку новый. Для выполнения этой задачи рассматриваем новый граф ,но с теми же вершинами, с новыми пропускными способностями ребер, если пропускная способность ребра от A до Bравна С, а в нашем потоке по этому же ребру пущено x,то в новом графе будет ребро от A к B c пропускной способностью с-x и ребро от B к A с пропускной способностьюx.Иначе говоря, можно увеличить поток по ребру на максимум c- x или уменьшить на x. Потом в уже новом графе ищем поток из истока в сток, при условии ненулевого веса. Если же такого не оказалось, то повезло, имеющийся поток- максимальный .Если не повезло и такой поток есть- складываем эти 2 потока, получаем новый , с небольшим весом, повторяем процесс. Алгоритм не дает гарантий на то, что время работы сильно уменьшится. 1.3Пропускная способность и поток Теперь мы отложим абстрактное мышление и перейти к конкретике. Мы будем рассматривать только те сети, в которых будет возможно: 1)Только один источник и только один сток 2)Любую из вершин можно достигнуть из источника из любой вершины достижим сток. В рассматриваемой работе числа будем рассматривать, как пропускную способность дуги Теперь требуется записать различную терминологию, что бы работа была более Функция ,заданная на дугах сети ,называется потоком. Когда выполняются определенные условия, а именно : 1)Для всякой дуги выполняется неравенство ; 2)Выполняется условие сбалансированности потока, то есть для любой вершины сети, отличной от источника и стока, сумма значений потока на входящих дугах равна сумме сети значений потока на исходящих дугах Рис. 2 Потоковая сеть с источником s и стоком t 1.4Сводимость некоторых задач о максимальном потоке в сети к рассматриваемой Почти все разнообразные сети и условия существования потока в этих сетях которые могут возникнуть при рассмотрении разных задач и все они сводятся к поиску максимального потока в ориентированной сети С одним источником и одним стоком и верхними границами пропускных способностей дуг сети. В пример приведу наиболее распространенные частные случаи 1.5 Случай нескольких источников и стоков Когда в задаче имеется несколько источников и стоков - все узлы в сети будут делиться на 3 разные группы: S- это множестве источников, а T –это множество стоков.F - это множество помеж. узлов. Рассмотрим случай, когда поток может следовать из любого источника к любому стоку. Модифицируем сеть: Добавим новую вершину пусть будет вершина S* соединим ее дугами со всеми вершинами из множества S. Вершина S*называется суперисточником. Теперь требуется добавить новую вершину T*и соединить ее дугами со всеми вершинами из множества T. Вершина T*называется суперстоком. Зададим пропускную способность всех новых равную ?. Ясно,что поиск максимального потока из вершин множества S в вершины множества T равносилен поиску максимального потока из S*в T*. Случай ограниченной пропускной способности вершин. Если пропускные способности наряду с дугами имеют и узлы сети, то каждую вершину v, имеющую пропускную способность c(v), следует заменить двумя ( и ), соединенными дугой ( ) и c( и ) = c(v). Случай существования нижних границ пропускных способностей дуг. Когда рассматривается случай с задачей, когда поток, проходящий по дуге u, может принимать значения l(u) ? f(u) ? c(u), то функция l(u) рассматривается как уже имеющийся в сети поток и поиск максимального потока следует начинать не с нулевого потока, а с потока l(u). Случай неориентированных и смешанных сетей. Поток по неориентированной дуге (v, w) должен удовлетворять следующим условиям: f(v, w) ? c(v, w) f(w, v) ? c(v, w) f(v, w)*f(w, v) = 0 В этом случае замена неориентированной дуги двумя противоположно направленными ориентированными дугами с одинаковой пропускной способностью c(c, w) сведет задачу к эквивалентной задаче на орграфе. Аналогично ориентированные сети сводятся к неориентированным. (Кроме сетей с единичными пропускными способностями). Пропускные способности различных типов. Различаются случаи целочисленных, вещественных и единичных пропускных способностей. Предполагается, что приводимые далее алгоритмы рассматриваются на сетях с вещественными пропускными способностями, кроме специально оговоренных случаев 2.Пример потока Теперь зададим пример потока в виде рисунка. Когда поток изображается на рисунках, то рядом с каждой дугой указывают два числа, обозначаемые .Первое число обозначает пропускную способность дуги. Число в свою очередь обозначает значение потока на дуге( поток вдоль дуги). Рисунок 3 Поток в сети 2.1 Величина потока. Максимальный поток Величиной потока называется сумма потоков вдоль дуг, которые исходят из начала железной дороги(истока) . Поток называют максимальным, когда его величина максимальна среди всех потоков в данной сети Лемма о величине потока Сумма потоков в любой сети вдоль дуг, исходящих из источника, будет равна сумме потоков вдоль всех дуг, которые входят в сток Разрез в сети. Минимальный разрез Теперь требуется дать определение таким понятиям, как “ разрез в сети” и “минимальный разрез” Разрез сети –это множество дуг, разрывая которые мы уничтожаем поток между истоком и стоком .Так же нужно упомянуть свойства. 1)В заданном орграфе не должно быть цепей 2)Если любую из дуг добавить к орграфу,то в полученном орграфе мы найдем цепь К примеру множество всех дуг, которые исходят из источника является разрезом сети. Можно так же привести наглядный пример разреза вести на примере случайно простроенного графа Рисунок 4 Разрез в сети Известно,что вариаций разрезов может быть множество.Каждый из таких разрезов соответственно будет иметь разную пропускную способность.А сумма всех пропускных способностей дуг разреза будет характеризовать разрез.Среди всех разрезов стоит выделить один особенный.Разрез .Почему его? Потому,что он имеет наименьшую пропускную способность и для него даказана теорема Форда-Фалкерсона,о ней чуть позже. Теперь дадим определение пропускной способности разреза. Сумма пропускных способностей дуг,которые входят в разрес и есть пропускная способность разреза Минимальным же называется разрез, если пропускная способность разреза минимальна среди пропускных способностей всех сетей 2.2 Теорема Форда-Фалкерсона.Задача о максимальном потоке. Вот мы и начали подбираться к самому главному в курсовой работе. Теорема Форда-Фалкерсона: В любой сети величина максимального потока равна пропускной способности минимального разреза. Опираюсь на с теорему Форда-Фалкерсона можно сказть,что минимальный разрез являтся ничем иным,как “узким местом” сети.Если увеличить пропускную способнсть любой дуги,входящией в минимальный разрез сети, увеличивается поток в сети 2.3Задача о максимальном потоке. В заданной сети требуется отыскать минимальный поток и минимальный разрез. Прежде всего для того,что бы построить максимаьный поток нужно понять,как можно величить уже имеющийся на данный момент поток. Самое интересное в том,что для увеличения потока может потребоваться уменьшиить поток вдоль каких-то дуг. В качесте примера хочу рассмотреть несколько рисунков. Рис 5 не максимальный поток Рис 4 максимальный поток Поток на рсунке слева не будет максимальным.Но если мы хотим все же его увеличить,пустив поток вдоль дуги ,тогда вершина будет переполнена,потому что из исходит одна дуга, пропускная способность которой равна 1. По этому требуется уменьшить поток вдоль другой дуги . Перенаправим его вдоль дуги . В результате этих интересных манпуляций получается поток,в этот раз, максимальный для данной сети 2.4 Остаточная сеть Для того,что бы находить возможности увеличения потока существуют алгоритмы,вот один из них. Сеть называется остаточной, она получена из сети с заданным потоком применением двух преобразований: 1)Для пары вершин таких,что и добавить к орграфу G дугу пропускной способности 0; 2)Для дуги такой ,что ,уменьшить пропускную способность дуги ,уменьшить пропускную сособность дуги на и увеличить пропускную способность дуги на Вот так выглядит остаточная сеть предыдущих рисунков Рис 6 Остаточная сеть Красным на Рис 6 выделены добавленные дуги.В этой сети есть цепь 2.5 Лемма об остаточной сети Определение: Минимум из пропускных способностей входящих в нее дуг называется пропускной способнстю Лемма: Если в остаточной сети существуют простая цепь пропускной способности ,то величину потока в сети можно увеличть на Доказательсво: Пусть С- цепь. Можно изменить значения потока на дугах сети по правилам: 1) ; 2) ; 3) в остальных случаях Докажем, что –это поток и .Так как для любоц дуги , то по определению остаточной сети для правила(1) имеем ,а для правила (2),соответственно .Учитывая то,что -это поток, получаем,что функция Проверим выполнение условия сбалансированности потока для Так как это условие выполнено для , равенство выполнено для любой вершины отличной от s и t. Если v не входит в цепь C, то поток вдоль дуг, инцидентных v, не изменится и равенство сохранится. В противном случае в C есть пара дуг . При изменении потока вдоль дуги по правилу (1) левая часть равенства увеличивается на , а при изменении по правилу (2) правая часть уменьшается на . Аналогично, при изменении потока вдоль либо правая часть увеличивается на , либо левая часть уменьшается на то же самое ; в любом случае, равенство будет восстановлено, т. е. условие сбалансированности выполнено. Итак, — поток по определению. Поскольку С- простая цепь, в ней только одна дуга, которая исходи из s и нет дуг, которые бы входили в s.Увеличение потока вдоль дуги, исходящей из s ,происходит согласно правилу (1). Следовательно: (1) Теперь можно доказанную лемму применить к примеру. Возьмем в остаточной сети на рис 3 цепь ,увеличим на 1 поток вдоль дуг(s,y) и (x,t),уменьшим на единицу поток вдоль(x,y) , в результате получим максимальный поток в исходной сети. 3. Алгоритм Форда-Фалкерсона Докажем,что выходом алгоритма Форда-Фалкерсона являются именно макимальный поток и минимальный разрез.Можно увидеть ,что , потому что в противном случае алгоритм перейдет ко второму шагу вместо шага 4 следовательно ? Пусть Пусть , и ,то В то же время ,для каждой из дуг множества R,так как в остаточной сети эти дуги имеют нулевую пропускную способность. Следовательно для любой дуги из вершины v достижим сток t Действительно а значит (v,t) цепь вдоль всех дуг которой поток положителен .Исходя из вышесказанного ,в этой цепи нет вершин из S.В итоге R- разрез по определению 3.1 Анализ алгоритма : максимальный поток равен минимальному разрезу Обозначим f поток, он возвращается алгоритмом Форда-Фалкерсона. От нас требуется доказать, что f имеет максимальную возможную величину среди потоков в G; для этого воспользуемся определенным агоритмом,: предоставим разрез s-t (A*, B*), для которого v(f) = c(A*, B*). Этой процедурой устанавливается то , что f имеет максимальную величину среди всех потоков ,а так же (A*, B*) имеет минимальную пропускную способность по всем разрезам s-t. Алгоритм Форда-Фалкерсона завершается тогда , когда поток f не имеет пути s-t в остаточном графе Gf. Как выясняется, это единственное свойство, необходимое для доказательства его максимальности. Если f — такой поток s-t, для которого не существует пути s-t в остаточном графе Gf, то в G существует разрез s-t (A*, B*), для которого v(f) = c(A*, B*). Соответственно f имеет максимальную величину среди всех потоков в G, а (A*, B*) имеет минимальную емкость по всем разрезам s-t в G. Доказательство. Это утверждение заявляет задуматься о существовании разреза, обладающего неким желательным свойством; теперь нужно найти такой разрез. Обозначим A* ,как множество всех узлов v в G, для которых в Gf существует путь s-v. Множество всех остальных узлов обозначается B*: B* = V - A*. Для начала требуется установить, что (A*, B*) действительно является разрезом s-t. Безусловно, это разбиение V. Источник s принадлежит A*, потому что путь из s в s всегда существует. Кроме того, t ? A* по предположению об отсутствии пути s-t в остаточном графе; следовательно, t ? B*, как и требуется. Затем предположим, что e = (u, v) является ребром в G, для которого u ? A* и v ? B* как показано на рис.7 Можно утверждать, что f(e) = ce. Если бы это было не так, то e было бы прямым ребром в остаточном графе Gf, а поскольку u ? A*, в Gf существует путь s-u; присоединяя eе к этому пути, мы получаем путь s-v в Gf, что противоречит предположению о v ? B*. Рис. 7 Разрез (A*, B*) Теперь предположим, что e' = (u', v') является ребром в G, для которого u' ? B* а v' ? A*. Можно утверждать, что f(e') = 0. Если бы это было не так, то ребро e' породило бы обратное ребро e" = (v', u') в остаточном графе Gf, а поскольку v' ? A* в Gf существует путь s-v'; присоединяя e" к этому пути, мы получаем путь s-u' в Gf, что противоречит предположению о u' ? B*. Итак, все ребра из A* полностью насыщены потоком, а все ребра, направленные в A*, совершенно не используются. Так как алгоритм Форда-Фалкерсона завершается при отсутствии пути s-t в остаточном графе, следует его оптимальность. Поток f возвращаемый алгоритмом Форда-Фалкерсона, является максимальным. Также заметим, что наш алгоритм легко расширяется для вычисления минимального разреза s-t (A*, B*). Для заданного потока f с максимальной величиной разрез s-t с минимальной пропускной способностью вычисляется за время O(m). Доказательство. Просто последуем за построением доказательства Мы строим остаточный граф Gf и проводим поиск в ширину или поиск в глубину для определения множества A* всех узлов, доступных из s. После этого мы определяем B* = V - A* и возвращаем разрез (A*, B*). ¦ Обратите внимание: в графе G может быть много разрезов с минимальной пропускной способностью; процедура в доказательстве просто находит один из этих разрезов, начиная с максимального потока f. Дополнительно анализ алгоритма выявил следующий поразительный факт: В каждой потоковой сети существует поток f и разрез (A,B), для которых (v f) = c(A, B). Суть в том, что f должен быть максимальным потоком s-t; если бы существовал поток f с большей величиной, то значение f превысило бы пропускную способность (A, B).Аналогичным образом можно сделать вывод о том, что (A,B) является минимальным разрезом (никакой другой разрез не может иметь меньшую пропускную способность), потому что если бы существовал разрез (A',B') с меньшей пропускной способностью, он был бы меньше величины f.Из-за этих следствий утверждение часто называется ”теоремой о максимальном потоке и минимальном разрезе” и формулируется следующим образом.).В любой потоковой сети максимальная величина потока s-t равна минимальной пропускной способности разреза s-t. 3.2 Поиск цепи в остаточной сети Одним из важнейши условий реализации алгоритма- проверка 3 условияА именно поиска остаточной сети -цепи ненулевой пропускной способности.После чего другая операия находит самую короткую по числу дуг цепь с нужными свойствами.Для всех вершин v вычисляется (пропускная способность) найденой цепи и предшествующая вершина в этой цепи. Теперь рассмотрим процедуры поиска цепи не нулевой пропускной способности. Шаг 1) Предположим,что для остальных вершин,а так же ? для каждой вершины создадим очередь из одной вершины s Шаг 2) Пока наша очередь заполнена нужно повторять операции: а)Извлечь первый элемент из очереди(пусть будет v) б)Для всех дуг такой, что и , ; если же ,нужно прекратить работу, в противном случае поместить w в конец очереди. После выполнения всех операций, если работа завершилась по условию w=t ,что определяют цепь с пропускной способностью Возможен другой исход, когда процедура завершена из-за окончания очереди, в таком случае цепи не будет существовать, а вершины с условием положительности образуют множество, которое требуется на 4 этапе работы с алгоритмом Форда-Фалкерсона 3.3 Пример 1 За основу возьмем рисунок 1.Найдем максимальный поток и минимальный разрез. Такая же сеть с нулевым потоком изображена на рис 4.статочную сеть рисовать не будем. Запишем 2 правила 1) Можно двигаться по дугам и против стрелок. 2) Пропускная способности дуги в противоположном направлении равняется числу в скобке, а при движении в направлении стрелки разности первого и второго числа Рисунок 8 –Поток в сети Протокол работы В итоге работы была найдена цепь пропускной способности 3.4 Пример 2 В этот раз увеличим поток вдоль дуг и на .Все действия выполняются в соответствии с правилом 1 (увеличения потока).На рис. 9 показан полученный поток. Рис 9- Поток Протокол работы цепь, которую мы нашли содержит обратную дугу из этого следует, что поток вдоль дуги требуется уменьшить на 3,в соответствии с правилом 2(увеличения потока).А в свою очередь поток вдоль дуг и требуется увеличить на 3 в соответствии с правилом 1 3.5 Пример 3 Итак, протокол работы поиска цепи в новой остаточной сети показывает, что нет цепей ненулевой пропускной способности. И находит множество И наконец на четвертом этапе мы находим разрез Рис 10 Поток ………………….Протокол работы (красный цвет) Пропускная способность = 10.Величина максимального потока ( ) =10 3.6 Ипользование метода Форда-Фалкерсона для повышения интегрированности действий звеньев логической сети поставок У цепи поставок в логических системах есть преимущества, но как же они определяются? Они определяются при помощи потенциала возможностей связи ценности выпускаемого продукции с покупателем. В такой связи очень важно правильно расставить приоритеты.
Не смогли найти подходящую работу?
Вы можете заказать учебную работу от 100 рублей у наших авторов.
Оформите заказ и авторы начнут откликаться уже через 5 мин!
Похожие работы
Курсовая работа, Транспортные средства, 29 страниц
600 руб.
Курсовая работа, Транспортные средства, 23 страницы
300 руб.
Курсовая работа, Транспортные средства, 18 страниц
310 руб.
Курсовая работа, Транспортные средства, 43 страницы
340 руб.
Служба поддержки сервиса
+7(499)346-70-08
Принимаем к оплате
Способы оплаты
© «Препод24»

Все права защищены

Разработка движка сайта

/slider/1.jpg /slider/2.jpg /slider/3.jpg /slider/4.jpg /slider/5.jpg