Создан заказ №427840
16 января 2015
Потоки в сетях
Как заказчик описал требования к работе:
Предмет:дискретная математика. Методичка во вложении. Тема №3. Презентационную часть делать не нужно.
Фрагмент выполненной работы:
Введение.
В настоящее время, в связи с широким развитием транспортных коммуникаций разных типов , построением информационных каналов, каналов связи, сетей ЭВМ и других систем большое практическое значение приобретают специальные методы математического моделирования сетей и разнообразных потоков в ней. Эта наука зародилась в 50 х годах 20 века в трудах американских ученых, так как именно в это время в развитых странах началось бурное развитие трубопроводных и информационных сетевых систем. (работа была выполнена специалистами Автор 24) К таким видным ученым относились, в частности такие специалисты как Л.Форд, Д.Фалкерсон, которые внесли большой вклад в математическую теорию потоков, доказав основополагающую теорему о связи максимального потока и минимального разреза в сети, а также разработавших первые эффективные алгоритмы нахождения оптимальных потоков в сетях. Анализу изложению этих важных результатов посвящена данная работа. В работе имеется три главы, введение и заключение. Во введении кратко освящена история вопроса. В первой, вспомогательной главе даны основные сведения по теории сетей и графов. Вторая глава является основной, в ней подробно разобрано доказательство теоремы Форда-Фалкерсона о максимальном потоке и минимальном разрезе. В третьей главе излагается и демонстрируется на примере знаменитый алгоритм Форда Фалкерсона для нахождении максимального потока в сети в современной трактовке с использованием понятия остаточного графа. В пятой главе кратко демонстрируются возможности применения теории максимальных потоков на практике. В заключении сжато формулируются основные результаты работы. Библиографический список насчитывает 15 названий.
Краткие теоретические положения.
Орграф это пара , где - множество вершин графа и - множество ребер графа, где каждое ребро - является упорядоченным кортежем двух своих концевых вершин. Вершины графа, соединенные ребром называются смежными, ребро и любая из его концевых вершин называются инцидентными.
Транспортная сеть- это шестерка объектов , где множество вершин сети, - множество дуг, - функция пропускных способностей дуг, - функция удельных стоимостей(цен) передачи потока по каждой дуге, заданная начальная вершина(исток), заданная конечная вершина(сток).
Допустимый поток в транспортной сети это функция , задающая отдельный поток на каждой дуге в отдельности, удовлетворяющая условиям
А) , т.е. поток по дуге неотрицателен и не превосходит пропускной способности дуги;
Б) , т.е. во всех внутренних узлах, т.е. узлах отличных от начального и конечного должен выполняться баланс потока, т.е. суммарный поток по выходящим из узла дугам должен равняться потоку по входящим дугам.
Величина допустимого потока находится как , т.е. как сумма потоков по дугам, выходящим из источника.
Поток называется максимальным, если он допустим и имеет максимальную величину среди всех допустимых потоков.
Стоимостью допустимого потока заданной величины называется величина , т.е. суммарная стоимость передачи потока по отдельным дугам, при условии, что , т.е. если поток имеет заданную величину.
Поток заданной величины называется наименьшим, если он имеет наименьшую стоимость среди всех потоков заданной величины.
Постановка задачи о нахождении наименьшего потока включает в себя выбор величины передаваемого потока, удовлетворяющей условию , и последующего решения оптимизационной задачи поиска потока наименьшей стоимости среди потоков заданной величины.
Пусть в транспортной сети задан допустимый поток .
Дуга называется насыщенной или закрытой, если выполняется условие , т.е. поток по данной дуге равен ее пропускной способности.
Пусть в транспортной сети задан допустимый поток . Путь в сети, ведущий из источника к стоку называется увеличивающим, если он состоит из ненасыщенных дуг.
Если в транспортной сети имеется увеличивающий путь , то поток в сети можно увеличить на величину , наращивая на эту величину потоки в дугах, входящих в состав увеличивающего пути, где , т.е. на минимум резервов дуг, входящих в состав пути .
Цепь , т.е. последовательность смежных дуг несогласованного направления, соединяющая источник и сток, называется аугментальной или увеличивающей, если дуги прямого направления имеют резерв, а дуги обратного направления- ненулевой поток.
Если в транспортной сети имеется аугментальная сеть, то поток можно увеличить на величину , наращивая на эту величину отдельные потоки на прямых дугах, входящих в состав цепи и уменьшая на такую же величину потоки на обратных дугах, где - минимум резервов прямых дуг и потоков на обратных дугах, входящих в состав аугментальной цепи.
Критерий максимальности потока- это недостижимость конечной вершины из начальной по аугментальным цепям сети. Факт недостижимости проверяется расчетным путем методом маркировки вершин сети, начиная от начальной вдоль строящихся последовательно аугментальных цепей. Недостижимость конечной вершины означает отсутствие метки у конечной вершины при такой маркировке.
Задача о потоке минимальной стоимости это задача нахождения допустимого потока заданной величины, имеющего минимальную цену среди всех допустимых потоков, имеющих заданную величину в сети вида , где - источник и сток, - множество вершин графа сети, - множество ориентированных ребер (дуг) графа сети, - неотрицательная целочисленная функция пропускных способностей дуг, - неотрицательная целочисленная функция ценовых коэффициентов дуг на единицу проходящего потока и цена допустимого потока определяется по формуле: .
Остаточным графом (аугментальной, т.е. увеличивающей сетью) относительно данного потока называется взвешенный орграф на том же множестве вершин, что и исходный граф и для каждого ребра исходного графа имеющего два ребра с теми же концевыми вершинами: прямого ребра, идущего в том же направлении, что и исходное ребро и обратного ребра, идущего в обратном направлении. При этом пропускная способность прямого ребра, равна остаточной пропускной способности исходного ребра, относительно текущего потока, т.е. ресурсу исходного ребра, а пропускная способность обратного ребра равна запасу исходного ребра, т.е. величине потока, проходящего по данному ребру. Ценовой коэффициент прямого ребра равен ценовому коэффициенту исходного ребра, т.е. положительной величине, а ценовой коэффициент обратного ребра равен той же величине, взятой с обратным знаком, т.е. отрицательной величине.
Поясним отрицательный знак коэффициента обратной дуги. Дело в том, что проведение единиц потока по обратной дуге остаточного графа- это условное алгоритмическое действие, которое реально означает уменьшение величины потока по соответствующей дуге исходного графа с перераспределением его на другие дуги, т.е. такое уменьшение потока по реальной дуге означает уменьшение ее вклада в величину суммарных затрат на величину .
На языке формул имеем - аугментальная сеть, где и , . При этомПосмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
500 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик воспользовался гарантией для внесения правок на основе комментариев преподавателя
19 января 2015
Заказ завершен, заказчик получил финальный файл с работой
5
Потоки в сетях.docx
2017-06-06 13:56
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
Все понравилось, сделали в срок, ввели Доп. Требования) ещё не сдавали, но думаю все будет хорошо
Хочешь такую же работу?
300 ₽
