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

Автор работы: Пользователь скрыл имя, 03 Февраля 2014 в 14:52, курсовая работа

Краткое описание

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

Содержание

1. ВВЕДЕНИЕ 3
2. ПОСТАНОВКА ЗАДАЧИ И МЕТОД РЕШЕНИЯ 4
2.1 Общая постановка задачи о максимальном потоке 4
2.2 Математическая модель 4
2.3 Алгоритм Форда-Фалкерсона нахождения максимального потока 4
3. ПРАКТИЧЕСКАЯ ЧАСТЬ 6
4. ЗАКЛЮЧЕНИЕ 14
5. СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 15

Скачать в ZIP архиве (317.57 Кб) Сколько стоит заказать работу?

Вложенные файлы: 1 файл

КУРСОВАЯ И.О..docx

— 325.08 Кб (Скачать файл)

БАЙКАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ЭКОНОМИКИ И ПРАВА

Кафедра информатики и кибернетики

КУРСОВАЯ РАБОТА

ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ

Автор: Якушев Н.А.

группа: ИС-11-1

Руководитель: Доцент кафедры информатики и кибернетики, кандидат физико-математических наук Белых Т.И.

Иркутск

2013

ОГЛАВЛЕНИЕ

1. ВВЕДЕНИЕ 3

2. ПОСТАНОВКА ЗАДАЧИ И МЕТОД РЕШЕНИЯ 4

2.1 Общая постановка задачи о максимальном потоке 4

2.2 Математическая модель 4

2.3 Алгоритм Форда-Фалкерсона нахождения максимального потока 4

3. ПРАКТИЧЕСКАЯ ЧАСТЬ 6

4. ЗАКЛЮЧЕНИЕ 14

5. СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 15

ВВЕДЕНИЕ

Задача о максимальном потоке изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира.

60 лет назад, задача о максимальном потоке решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения этой задачи ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести к фундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push-Relabel метода. Для нахождения максимального потока, он использует предпотоки и метки, изменяемые во время работы алгоритма. Push-Relabel алгоритмы очень эффективны и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных мне алгоритмов.

ПОСТАНОВКА ЗАДАЧИ И МЕТОД РЕШЕНИЯ

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

Общая постановка задачи о максимальном потоке

Рассмотрим двухполюсную сеть S=(N, U) с одним входом (источником) s є N и выходом (стоком) t є N, дуги сети (i, j) є U имеют ограниченную пропускную способность . Задача о максимальном потоке заключается в поиске таких потоков по дугам (i, j) если, что результирующий поток из источника в сток является максимальным. Алгоритм Форда-Фалкерсона нахождения максимального потока

Математическая модель

Математическая модель задачи о максимальном потоке выглядит следующим образом:

найти такие значения j_ij_, при которых

V=å j_sj =å j_sj Þ max;

j j

при ограничениях:

0<= j_ij<=c_ij

å j_ij -åj_ij =0 i є N i¹s i¹t.

j j

Алгоритм Форда-Фалкерсона нахождения максимального потока

Идея данного алгоритма состоит в поиске сквозных путей с положительными потоками от источника к стоку.

Рассмотрим ребро (i,j) с (начальной) пропускной способностью . В процессе выполнения алгоритма части этих пропускных способностей «забираются» потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Сеть, в которой все ребра имеют остаточную пропускную способность. Будем использовать запись для представления остаточных пропускных способностей. Сеть в которой все рёбра имеют остаточную пропускную способность, назовем остаточной.

Для произвольного узла j, получающего поток от узла i, определим метку , где - величина потока, протекающего от узла j к узлу i. Чтобы найти максимальный поток, выполним следующие действия.

Для всех ребер (i, j) Положим остаточную пропускную способность равную первоначальной пропускной способности, т.е. приравняем = . Назначим и пометим узел 1 меткой . Полагаем i=1 и переходим ко второму этапу.
Определим множество как множество узлов j, в которые можно перейти из узла i по ребру с положительной остаточной пропускной способностью (т.е. для всех ). Если , выполняем третий этап, в противном случае переходим к шагу 4.
В множестве находим узел , такой, что Положим и пометим узел меткой . Если последней меткой помечен узел стока (т.е. если ), сквозной путь найден, и мы переходим к пятому этапу. В противном случае полагаем и возвращаемся к шагу 2.
Откат назад. Если , сквозной путь невозможен, и мы переходим к шагу 6. Если , находим помеченный узел , непосредственно предшествующий узлу i, и удаляем узел i из множества узлов, смежных с узлом r. Полагаем i=r и возвращаемся ко второму этапу.
Определение остаточной сети. Обозначим через множество узлов, через которые проходит p-й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n). Тогда максимальный поток, проходящий по этому пути, вычисляется как Остаточные пропускные способности ребер, составляющих сквозной путь, уменьшаются на величину в направлении движения потока и увеличиваются на эту же величину в противоположном направлении. Таким образом, для ребра (i,j), входящего в сквозной путь, текущие остаточные пропускные способности () изменятся следующим образом: a) (), если поток идет от узла i к узлу j, b) (), если поток идет от узла j к узлу i. Далее восстанавливаем все узлы, удаленные в шаге 4. Полагаем i=1 и возвращаемся ко второму этапу для поиска нового сквозного пути.
Решение. a) При m найденных сквозных путях максимальный поток вычисляется по формуле . b) Имея значения начальных и конечных пропускных способностей ребра (i,j), можно вычислить оптимальный поток через это ребро следующим образом. Положим . Если , поток, проходящий через ребро (i,j), равен . Если же , тогда поток равен . (Случай, когда одновременно , невозможен.)

Процесс отката назад на четвертом этапе выполняется тогда, когда алгоритм должен «убить» промежуточный узел до момента реализации сквозного пути. Коррекцию пропускных способностей, выполняемых в п. 5, можно пояснить на примере простой сети, показанной на рис. 6.30. На рис. 6.30. а найден первый сквозной путь N₁={1,2,3,4} с максимальным потоком f₁=5. После этого остаточные пропускные способности ребер (1,2), (2,3) и (3,4) изменяется соответственно с (5,0) на (0,5). На рис. 6.30, в, где уже невозможно построить сквозной путь N₂={1,2,3,4} с максимальным потоком f₂=5. После коррекции пропускных путей получаем сеть, показанную на рис. 6,30, в, где уже невозможно построить сквозной путь. При вычислении остаточных пропускных способностей в п. 5 при переходе от сети б к сети в невозможна организация потока в направлении 2→3. Получается, что алгоритм как бы помнит что поток в направлении 2→3 уже был в предыдущих сквозных путях, и поэтому снова (на пятом этапе) изменяет пропускную способность с 0 до 5 в направлении от узла 3 к узлу 2. /1/

ПРАКТИЧЕСКАЯ ЧАСТЬ

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

Фермы

Зернохранилища

Таблица 1

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

b) Существует ли при данных условиях схема транспортировки, обеспечивающая весь спрос птицеводческих ферм.

Решим как задачу о нахождении максимального потока:

1 - Исток

2 - З1 зернохранилище

3 - З2 зернохранилище

4 - З3 зернохранилище

5 - Ф1 ферма

6 - Ф2 ферма

7 - Ф3 ферма

8 - Ф4 ферма

9 - Cток

200

100

200

100

Рисунок 1

Итерация 1:

Рисунок 2

200

100

200

100

Назначаем а₁=∞, и помечаем узел 1 меткой [∞,−]. Полагаем i=1.
S₁={2,3,4} ≠{Ø}
k=4, c₁₄=max{c₁₂,c₁₃,c₁₄}=max{20,20,200}=200. Назначаем а₄=c₁₄=200 и помечаем узел 4 меткой [100,1]. Полагаем i=4 и возвращаемся к шагу 2.
S₂={5,6,7,8} ≠{Ø}
k=5, c₄₅=max{ c_45,c₄₆,c_47, c₄₈}=max{100,40,30,40}=40. Назначаем а₅=c₄₅=100 и помечаем узел 5 меткой [100,4]. Полагаем i=5 и возвращаемся к шагу 2.
k=9, c₅₉=max{c₅₉}=max{200}=200. Назначаем а₅=c₅₉=200 и помечаем узел 9 меткой [200,5]. Полагаем i=9 и переходим к шагу 7.
N₁={а₁,а₄,а_5, а₉} f₁ = min{∞, 200, 100, 200} = 100

(с₁₄,с₄₁)=(200-100,0+100)=(100,100)

(с₄₅,с₅₄)=(100-100,0+100)=(0,100)

(с₅₉,с₉₅)=(200-100,0+100)=(100,100)

Итерация 2:

100

Рисунок 3

Назначаем а₁=∞, и помечаем узел 1 меткой [∞,−]. Полагаем i=1.
S₁={2,3,4} ≠{Ø}
k=4, c₁₄=max{c₁₂,c₁₃,c₁₄}=max{20,20,100}=100. Назначаем а₄=c₁₄=100 и помечаем узел 4 меткой [100,1]. Полагаем i=4 и возвращаемся к шагу 2.
S₂={6,7,8} ≠{Ø}
k=6, c₄₆=max{c₄₆,c_47, c₄₈}=max{40,30,40}=40. Назначаем а₆=c₄₆=40 и помечаем узел 6 меткой [40,4]. Полагаем i=6 и возвращаемся к шагу 2.
k=9, c₆₉=max{c₆₉}=max{10}=10. Назначаем а₅=c₆₉=10 и помечаем узел 9 меткой [10,6]. Полагаем i=9 и переходим к шагу 7.
N₁={а₁,а₄,а_6, а₉} f₁ = min{∞, 100, 40, 10} = 10

(с₁₄,с₄₁)=(100-10,100+10)=(90,110)

(с₄₆,с₆₄)=(40-10,0+10)=(30,10)

(с₆₉,с₉₆)=(10-10,0+10)=(0,10)

Итерация 3:

100

110

100

Рисунок 4

Назначаем а₁=∞, и помечаем узел 1 меткой [∞,−]. Полагаем i=1.
S₁={2,3,4} ≠{Ø}
k=4, c₁₄=max{c₁₂,c₁₃,c₁₄}=max{20,20,90}=90. Назначаем а₄=c₁₄=90 и помечаем узел 4 меткой [90,1]. Полагаем i=4 и возвращаемся к шагу 2.
S₂={6,7,8} ≠{Ø}
k=8, c₄₈=max{c₄₆,c_47, c₄₈}=max{30,30,40}=40. Назначаем а₈=c₄₈=40 и помечаем узел 8 меткой [40,4]. Полагаем i=8 и возвращаемся к шагу 2.
k=9, c₈₉=max{c₈₉}=max{20}=20. Назначаем а₈=c₈₉=20 и помечаем узел 9 меткой [20,8]. Полагаем i=9 и переходим к шагу 7.
N₁={а₁,а₄,а_8, а₉} f₁ = min{∞, 90, 40, 20} = 20

(с₁₄,с₄₁)=(90-20,110+20)=(70,130)

(с₄₈,с₈₄)=(40-20,0+20)=(20,20)

(с₈₉,с₉₈)=(20-20,0+20)=(0,20)

Итерация 4:

100

130

100

Рисунок 5

Назначаем а₁=∞, и помечаем узел 1 меткой [∞,−]. Полагаем i=1.
S₁={2,3,4} ≠{Ø}
k=4, c₁₄=max{c₁₂,c₁₃,c₁₄}=max{20,20,70}=70. Назначаем а₄=c₁₄=70 и помечаем узел 4 меткой [70,1]. Полагаем i=4 и возвращаемся к шагу 2.
S₂={6,7,8} ≠{Ø}
k=7, c₄₇=max{c₄₆,c_47, c₄₈}=max{30,30,20}=30. Назначаем а₇=c₄₇=30 и помечаем узел 7 меткой [30,4]. Полагаем i=7 и возвращаемся к шагу 2.
k=9, c₇₉=max{c₇₉}=max{30}=30. Назначаем а₇=c₇₉=30 и помечаем узел 9 меткой [30,7]. Полагаем i=9 и переходим к шагу 7.
N₁={а₁,а₄,а_7, а₉} f₁ = min{∞, 70, 30, 60} = 30

Информация о работе Задача о максимальном потоке