Транспортные сети. Задача о максимальном потоке в сети

Изучение поперечных сечений сети и нахождение ограниченного поперечного сечения. Сущность понятия "поток сети". Характеристика теоремы Форда-Фалкерсона и ее решение. Особенности построения орграфа приращений и максимального потока для транспортной сети.

Рубрика Физика и энергетика
Вид курсовая работа
Язык русский
Дата добавления 10.03.2014
Размер файла 84,0 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Московский Государственный Институт Делового Администрирования

Курсовая работа

На тему: «Транспортные сети. Задача о максимальном потоке в сети»

Работу выполнила: Болотина Юлия

Работу проверил: Аллавердиев А.М

Москва 2003

Содержание

Введение

Теоретическая часть

Теорема Форда-Фалкерсона

Алгоритм решения

Поток в транспортной сети

Орграф приращений

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

Практическая часть

Заключение

Список используемой литературы

Введение

В своей курсовой работе я рассматриваю тему «Транспортные сети». Моя курсовая работа состоит из следующих разделов:

* Транспортные сети;

* Поток в транспортной сети;

* Орграф приращений;

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

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

Теоретическая часть

Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c(), называемое пропускной способностью дуги, и существует:

1) ровно одна вершина , в которую не заходит ни одна дуга, называемая источником или началом сети;

2) ровно одна вершина , из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.

Потоком сети называется неотрицательная функция f(1) такая, что f(e) меньше или равно c(e). (Поток не может превышать пропускную способность дуги.)

Дуга

транспортная сеть максимальный поток

называется насыщенной потоком f, если

(Поток называется полным, если содержит насыщенную дугу

f(e)=c(e).)

Разрезом L сети G(V,E) называется множество насыщенных дуг, отделяющих источник s от стока t.

Теорема Форда-Фалкерсона

Пусть D - транспортная сеть, - допустимый поток в этой сети, - множество вершин таких, что длина минимального пути из в в орграфе приращений равна нулю. Тогда, если , то - максимальный поток, величина которого равна .

Пусть . Тогда выполняется равенство

(1)

Если , так как в противном случае, используя

Имеем , а следовательно, в силу существует путь нулевой длины из в , что противоречит условию . Но тогда из (1) получаем

Следствие 1. Используя теорему Форда-Фалкерсона получаем, что величина максимального потока в транспортной сети равна пропускной способности минимального разреза.

Следствие 2. Пусть - допустимый поток в транспортной сети D. Тогда, если длина минимального пути из v1 в vn в орграфе приращений равна бесконечности, то - максимальный поток.

Алгоритм решения

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

Две основные процедуры (операции алгоритма):

операция расстановки пометок;

операция изменения потока.

Рассмотрим первую процедуру. Для каждой вершины данной сети нужно приписать пометку, которая имеет следующий вид: или где , а - натуральное число или бесконечность. Вообще возможны три состояния вершины:

1) не помечена;

2) помечена, но не просмотрена;

3) помечена и просмотрена.

Расставлять пометки начнем с источника S. Он получит пометку Источник помечен, но не просмотрен. Остальные вершины не помечены. Чтобы источник S был помечен и просмотрен, надо поместить все вершины, смежные с S.

Вершина получит пометку , где

.

Теперь все вершины смежные с S, помечены, но не просмотрены. А вершина S помечена и просмотрена. Начнём просматривать ту из вершин , которая имеет наименьший индекс. Для этого нужно расставить пометки вершинам, смежным с . Если для вершины выполняется следующее условие , то она получит метку , где

.

Если же для вершины выполняется условие , то получает метку , где

.

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

процедуре 2.

Рассмотрим процедуру изменения потока. Если вершина имеет пометку , то заменяем на

,

если же вершина имеет пометку , то заменяем на

Переходим к следующей вершине и так до тех пор, пока не достигнем источника S. Здесь изменение потока прекращается. Далее переходим к процедуре 1 и так до тех пор, пока величину потока уже нельзя изменить.

Рассмотрим конкретную задачу о нахождении максимального потока в сети.

Дана сеть G(V,E) (рис. 11) с источником S и стоком t. Пропускные способности дуг указаны. Найти максимальный поток из S в t.

Поток в транспортной сети

Функция , определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если:

*для любой дуги величина , называемая потоком по дуге , удовлетворяет условию ;

*для любой промежуточной вершины v выполняется равенство

т.е. сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v.

Размещено на http://www.allbest.ru/

Пример. На рисунке показан допустимый поток в транспортной сети. При каждой дуге указана величина потока по ней. Очевидно, что выполняются все условия, перечисленные в определении допустимого потока (проверяем выполнение второго условия для промежуточных вершин ).

Для любого допустимого потока в транспортной сети D выполняется равенство:

По определению допустимого потока имеем:

Заметим, что для каждой дуги где , величина входит в левую часть равенства лишь один раз и при этом со знаком плюс. Аналогично для каждой дуги , величина входит в левую часть равенства (2) лишь один раз и при этом со знаком минус. С другой стороны, для каждой дуги

величина входит в левую часть равенства (2) один раз со знаком плюс (при ) и один раз со знаком минус (при ), что в сумме даёт нулевой вклад в левую часть равенства (2). Учитывая сказанное, заключаем, что из равенства (2) следует справедливость равенства (1).

Величиной потока в транспортной сети D называется величина , равная сумме потоков по всем дугам, заходящим в , или, что то же самое - величина, равная сумме потоков по всем дугам, исходящим из

Пусть - допустимый поток в транспортной сети D. Дуга называется насыщенной, если поток по ней равен её пропускной способности, т.е. если . Поток называется полным, если любой путь в D из содержит, по крайней мере, одну насыщенную дугу.

Поток называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D.

Очевидно, что максимальный поток обязательно является полным (т.к. в противном случае в D существует некоторая простая цепь из V1 в Vn, не содержащая насыщенных дуг, а следовательно, можно увеличить на единицу потоки по всем дугам из и тем самым увеличить на единицу , что противоречит условию максимальности потока). Обратная же, вообще говоря, неверно. Существуют полные потоки, не являющиеся максимальными. Тем на менее полный поток можно рассматривать как некоторое приближение к максимальному потоку.

Орграф приращений

Введем для заданной транспортной сети D и допустимого потока в этой сети орграф приращений , имеющий те же вершины, что и сеть D. Каждой дуге транспортной сети D в орграфе приращений соответствует две дуги: и - дуга, противоположная по направлению дуге . Припишем дугам орграфа приращений длину :

т.е. орграф является нагруженным. При этом очевидно, что длина любого пути из в в орграфе равна либо 0, либо бесконечности.

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

Важным следствием теоремы Форда-Фалкерсона является Алгоритм построения максимального потока в транспортной сети.

Алгоритм:

Шаг 1. Полагаем i=0. Пусть - любой допустимый поток в транспортной сети D (например, полный, можно начинать с нулевого потока: ).

Шаг 2. По сети D и потоку строим орграф приращений .

Шаг 3. Находим простую цепь , являющуюся минимальным путем из в в нагруженном орграфе . Если длина этой цепи равна бесконечности, то поток максимален, и работа алгоритма закончена. В противном случае увеличиваем поток ввдоль цепи на максимально допустимую величину , такую, что при этом сохраняется условие 1 допустимого потока (для любой дуги величина , называемая потоком по дуге х, удовлетворяет условию ). В силу , используя

,

получаем, что указанная величина существует. В результате меняется поток в транспортной сети D, т.е. от потока мы перешли к потоку , и при этом . Присваеваем и переходим к шагу 2.

Практическая часть

Задача о максимальном потоке

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

Этап 1

Начнём с процедуры расстановки пометок. Пометка источника S Далее рассмотрим те вершины, которые соединены с источником дугой. Это V, V, V . Пропустим по всей сети первоначальный нулевой поток

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

Просмотрим вершину S, для этого пометим вершиныV , V , V .

Просмотрим вершину V , ставим метки . Просмотрим , ставим метки .

Изменение потока:

Поэтому заменим величину первоначального потока:

на

на ,

Размещено на http://www.allbest.ru/

Этап 2

Просмотрим вершину V1, вершины V4 и V2 получают метки . И просмотрим V3, V2 уже просмотрена, . Просмотрим V2, V4 уже помечена,

Изменение потока:

Вносим изменения потока. Дуга (V2, t) стала насыщенной.

Размещено на http://www.allbest.ru/

Этап 3

Просмотрим вершину V1.

Просмотрим V3, V2 уже помечена, просмотрим V2, V4 уже помечена, просмотрим V4.

Изменение потока:

Вносим изменения потока. Дуга (V3,V2) стала насыщенной.

Размещено на http://www.allbest.ru/

Этап 4

Просмотрим вершину V3 и V3.

Вносим изменения потока. Дуга (V3, V2) стала насыщенной.

Размещено на http://www.allbest.ru/

Этап 5

Просмотрим вершину V3.

Просмотрим V6

Изменение потока:

Вносим изменения потока. Дуга (S,V3) стала насыщенной.

Размещено на http://www.allbest.ru/

Поток f=21 является максимальным, а множество дуг составляют минимальный разрез сети. Минимальный разрез на рисунке обозначен волнистой линией.

Заключение

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

Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c(), называемое пропускной способностью дуги, и существует:

1) ровно одна вершина , в которую не заходит ни одна дуга, называемая источником или началом сети;

2) ровно одна вершина , из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.

Список используемой литературы

1. А.М. Аллавердиев, И.В. Платонова «Прикладная математика. Элементы теории графов» М.2000

2. Лекции по прикладной математике И.В. Платоновой

3. В.Н. Нефедов, В.А. Осипова «Курс дискретной математики» М. 1992

4. С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики» М. 2002

Размещено на Allbest.ru

...

Подобные документы

  • Особенности выбора рациональной схемы и номинального напряжения сети. Анализ технико-экономических показателей районной сети. Значение напряжения в узловых точках в максимальном режиме, его регулирование в электрической сети в послеаварийном режиме.

    курсовая работа [568,3 K], добавлен 20.06.2010

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

    контрольная работа [616,0 K], добавлен 16.03.2012

  • Составление балансов активных и реактивных мощностей. Выбор числа и мощности силовых трансформаторов, сечений проводников. Конструктивное исполнение электрической сети. Расчет максимального и послеаварийного режимов. Регулирование напряжения в сети.

    курсовая работа [242,4 K], добавлен 17.06.2015

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

    курсовая работа [694,7 K], добавлен 04.10.2015

  • Выбор схемы соединения линий электрической сети. Определение сечений проводов линий электропередачи. Расчёт максимального режима сети. Выявление перегруженных элементов сети. Регулирование напряжения на подстанциях. Выбор трансформаторов на подстанциях.

    курсовая работа [5,0 M], добавлен 14.03.2009

  • Оптимальная схема развития районной электрической сети. Выбор номинальных напряжений и оптимальной конструкции сети. Расчет сечений проводов, мощности компенсирующих устройств. Выбор оборудования подстанций. Расчет максимального режима энергосистемы.

    курсовая работа [202,3 K], добавлен 24.03.2012

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

    курсовая работа [1,9 M], добавлен 13.05.2013

  • Определение сечения проводов сети 0,4 кВ по допустимым потерям. Выбор количества и мощности трансформаторов подстанции. Расчет потерь мощности и электрической энергии в элементах сети. Сравнительная эффективность вариантов развития электрической сети.

    курсовая работа [413,9 K], добавлен 25.10.2012

  • Схема районной электрической сети. Определение потока мощности на головных участках сети. Расчет потерь напряжения в местной сети. Расчет номинальных токов плавких вставок предохранителей. Коэффициент для промышленных предприятий и силовых установок.

    контрольная работа [126,5 K], добавлен 06.06.2009

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

    дипломная работа [1,1 M], добавлен 20.08.2014

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

    курсовая работа [188,4 K], добавлен 17.04.2014

  • Разработка проекта электрической сети с учетом существующей линии 110 кВ. Исследование пяти вариантов развития сети. Расчет напряжения, сечений ЛЭП, трансформаторов на понижающих подстанциях и схемы распределительных устройств для каждого варианта.

    курсовая работа [2,4 M], добавлен 24.10.2012

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

    курсовая работа [1,6 M], добавлен 24.11.2013

  • Составление баланса активной и реактивной мощностей. Схемы соединений сети. Выбор номинального напряжения и сечений проводов, трансформаторов на подстанциях. Расчет потерь электроэнергии в элементах сети. Определение ущерба от перерыва в электроснабжении.

    курсовая работа [164,2 K], добавлен 05.09.2013

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

    курсовая работа [956,8 K], добавлен 14.05.2013

  • Построение вариантов схемы электрической сети. Предварительный расчет потоков мощности. Выбор номинальных напряжений для кольцевой сети. Определение сопротивлений и проводимостей линий электропередачи. Проверка сечений по техническим ограничениям.

    курсовая работа [515,7 K], добавлен 29.03.2015

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

    курсовая работа [1,0 M], добавлен 16.10.2014

  • Характеристика электрифицируемого района и потребителей электроэнергии. Составление и обоснование вариантов схемы электрической сети. Баланс реактивной мощности и выбор компенсирующих устройств. Выбор номинального напряжения и сечений проводов сети.

    курсовая работа [89,3 K], добавлен 13.04.2012

  • Этапы и методы проектирования районной электрической сети. Анализ нагрузок, выбор оптимального напряжения сети, типа и мощности силовых трансформаторов. Электрический расчёт варианта сети при максимальных нагрузках. Способы регулирования напряжения.

    методичка [271,9 K], добавлен 27.04.2010

  • Выбор вариантов развития существующей сети. Выбор номинальных напряжений сооружаемых воздушных линий радиального варианта сети. Определение сечений проводов сооружаемых линий радиального варианта сети. Выбор понижающих трансформаторов на подстанции.

    курсовая работа [2,9 M], добавлен 22.07.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.