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

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

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

по теме:

«Определение максимального потока в транспортной сети»

Содержание

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

Введение

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

1.1 Основные определения, используемые в задаче о максимальном потоке в сети

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

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

2.1 Общая постановка задачи

2.2 Математическая постановка задачи

2.3 Решение задачи о максимальном потоке

Заключение

Литература

Введение

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

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

Начало этой науке положено выдающимся ученым Леонардом Эйлером при решении знаменитой задачи о «кенигсбергских мостах» в 1736 г. Позднее, в 19 веке, теория графов была применена инженером-электриком Кирхгофом при исследовании электрических цепей, Кэли - в органической химии, Гамильтоном - в картографии, для решения головоломок.

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

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

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

2. Нахождение кротчайшего маршрута между двумя городами по существующей сети дорог.

3. Определение схемы транспортировки нефти от пунктов нефтедобычи к нефтеперерабатывающим заводам с минимальной стоимостью транспортировки.

4. Составление временного графика строительных работ (определение дат начала и завершения отдельных этапов работ).

Решение приведенных задач (как и многих других подобных задач) требует применения различных сетевых алгоритмов:

1. Алгоритм нахождения минимального остовного дерева;

2. Алгоритм нахождения кротчайшего пути;

3. Алгоритм определения максимального потока;

4. Алгоритм минимизации стоимости потока в сети с ограниченной пропускной способностью;

5. Алгоритм нахождения критического пути.

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

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

1.1 Основные определения, используемые в задаче о максимальном потоке в сети

Сеть состоит из множества узлов, связанных дугами (или ребрами). Таким образом, сеть описывается парой множеств (N, A), где N - множество узлов, а A - множество ребер. Например, сеть, показанная на рис. 1 описывается следующим образом:

N = {1, 2, 3, 4, 5},

A = {(1, 3), (1, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)}.

Рис. 1

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

Ребро называется направленным, или ориентированным, если в одном направлении возможен только положительный поток, а в противоположном - только нулевой.

Последовательностью различных ребер, соединяющих два узла, независимо от направления потока в каждом ребре, называется путь. Он формирует цикл, если начальный и конечный узлы совпадают. Например, на рисунке 1 ребра (2, 3), (3, 4) и (4, 2) составляют цикл.

Цикл, в котором все дуги ориентированы в определенном направлении, называется является ориентированным.

Если в сети любые два узла связаны хоть одним путем, то такая сеть называется связной.

На приведенном выше рисунке показан именно такой тип сети.

Алгоритм нахождения минимального остовного дерева.

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

Остовное дерево - это дерево, содержащее все узлы сети. На рис. 2 показаны дерево и остовное дерево для сети из рис. 1.

Дерево Остовное дерево

Рис. 2

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

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

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

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

Для произвольного узла j, получающего поток от узла i, определим метку [i, aj], где aj - величина потока, протекающего от узла j к узлу i. Алгоритм нахождения максимального потока предполагает выполнение следующих действий.

Шаг 1. Для всех ребер (i, j) положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем:

(xij, xji) = (Xij, Xji)

Назначим a1 = ? и пометим узел 1 меткой [-, ?]. Отсюда i = 1.

Шаг 2. Определяем множество Pi как множество узлов j, в которые можно перейти из узла i по ребру с положительной остаточной пропускной способностью (т.е. vij > 0 для всех j Pi). Если Pi ? Ш, выполняем третий шаг, в противном случае переходим к шагу 4.

Шаг 3. Во множестве Pi находим узел k, такой, что

xik = max {vij} (при j Pi)

Пусть ak = cik, тогда пометим узел k меткой [i, ak]. Если последней меткой помечен узел стока (т.е. если k = n), сквозной путь найден, и мы переходим к пятому шагу. В противном случае берем i = k и возвращаемся ко второму шагу.

Шаг 4. (Откат назад). Если i = 1, сквозной путь невозможен, и мы переходим к шагу 6. Если i ? 1, находим помеченный узел r, непосредственно предшествующий узлу i, и удаляем узел i из множества узлов, смежных с узлом r. Полагаем i = r и возвращаемся ко второму шагу. Процесс отката на данном шаге выполняется тогда, когда алгоритм должен «уничтожить» промежуточный узел до момента реализации сквозного пути.

Шаг 5. (Определение остаточной сети). На данном шаге выполняется коррекция пропускных способностей. Обозначим через Np = {1, k1, k2, …, n} множество узлов, через которые проходит p-й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n). Тогда максимальный поток (максимальная пропускная способность), проходящий по этому пути, вычисляется так:

ѓp = min {a1, ak1, ak2, …, an}.

Остаточные пропускные способности ребер, составляющих сквозной путь, уменьшаются на величину ѓp в направлении движения потока и увеличиваются на эту же величину в противоположном направлении. Таким образом, для ребра (i, j), входящего в сквозной путь, текущие остаточные стоимости (xij, xji) изменятся следующим образом:

a) (xij - ѓp, xji + ѓp), если поток идет от узла i к узлу j,

b) (xij + ѓp, xji - ѓp), если поток идет от узла j к узлу i.

Далее восстанавливаем все узлы, удаленные на шаге 4. Полагаем i = 1 и возвращаемся ко второму шагу для поиска нового сквозного пути.

Шаг 6. (Решение).

a) При m найденных сквозных путей максимальный поток вычисляется по формуле

F = ѓ1 + ѓ2 +… + ѓm.

b) Имея значения начальных (Xij, Xji) и конечных (xij, xji) пропускных способностей ребра (i, j), можно вычислить оптимальный поток через это ребро следующим образом. Положим (б, в) = (Xij - xij, Xji - xji). Если б > 0, поток, проходящий через ребро (i, j) равен б. Если же в > 0, поток равен в. (Случай, когда одновременно б > 0 и в > 0, невозможен).

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

2.1 Общая постановка задачи

ОАО мебельному заводу «Золотой ус» необходимо доставить максимально возможное количество своей продукции на склад магазина-реализатора за определенное время. При этом на выбранном маршруте имеется 6 промежуточных складских помещений, между которыми возможна транспортировка мягкой мебели. Пропускные способности всех участков дорог считаются известными.

2.2 Математическая постановка задачи

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

2.3 Решение задачи о максимальном потоке в сети

Итерация 1.

Пропускаем по всей сети первоначальный нулевой поток ѓ0 = 0.

Положим остаточные пропускные способности c (xij, xji) всех ребер равными первоначальным пропускным способностям C (Xij, Xji).

Шаг 1. Назначим aб = ? и пометим узел Sб меткой [- ;?]. Полагаем i = б.

Шаг 2. P1 = [X1, X2, X3] (? Ш).

Шаг 3. k=1, поскольку cб1 = max{cб1, cб2, cб3}= max{6, 5, 7}=7. Вершина X1 получает метку [S+; 6]. Вершина X2 получает метку [S+; 5]. Вершина X3 получает метку [S+; 7]. Полагаем i = 1 и возвращаемся к шагу 2.

Шаг 2. P2 = [X2, X4] (? Ш).

Шаг 3. k=4 и a2 = c12 = max{11, 8}=11. Вершина X4 получает метку [X1+; 6].Полагаем i = 4 и возвращаемся к шагу 2.

Шаг 2. Вершина X1 помечена и просмотрена. Будем просматривать вершину X2. P3 = [X4, X5] (? Ш).

Шаг 3. k=5 и a5 = c25 = max{9, 10}=10. Помечаем узел X5 меткой [X2+; 5]. Полагаем i = 5 и возвращаемся к шагу 2.

Шаг 2. Вершина X2 помечена и просмотрена. Будем просматривать вершину X3. P4 = [X6, X2] (? Ш).

Шаг 3. k=6 и a6= cб6 = max{4, 5}=5. Помечаем узел X6 меткой [X3+; 5]. Полагаем i = 6 и возвращаемся к шагу 2.

Шаг 2. Просмотрим вершину X4. P5 = [X5, tщ] (? Ш).

Шаг 3. k=щ и aщ = c4щ = max{9}=9. Помечаем узел tщ меткой [X4+; 6]. Получен сквозной путь. Переходим к шагу 5.

Шаг 5. Сквозной путь определяем по меткам, начиная с узла tщ и заканчивая узлом Sб:

tщ - [X4+; 6] - X4 - [X1+; 6] - X1 - [S+; 6] - Sб.

Таким образом, N1 = {Sб, X1, X4, tщ}; ѓ1 = min{aб, a1, a4, aщ} = {?, 6, 6, 6} = 6.

Вычислим остаточные пропускные способности вдоль пути N1:

с (Sб, X 1; X 1 Sб) = (6-6; 0+6) = (0; 6)

с (X 1, X 4; X 4 X 1) = (11-6; 0+6) = (5; 6)

с (X 4, tщ; tщ X 4) = (9-6; 0+6) = (3; 6)

Итерация 2.

Получаем остаточные пропускные способности всех ребер путем внесения изменений в пропускные способности тех ребер, которые находятся на маршруте N1, в соответствии с проходящим через них потоком ѓ1.

Шаг 1. Назначим aб = ? и пометим узел Sб меткой [-; ?]. Полагаем i = б.

Шаг 2. P1 = [X1, X2, X3] (? Ш).

Шаг 3. k=2, поскольку cб2 = max{cб2, cб3}= max{7, 5}= 7. Вершина X2 получает метку [S+; 5]. Вершина X3 получает метку [S+; 7]. Полагаем i = 2 и возвращаемся к шагу 2.



Шаг 2. P2 = [X 4, X 5] (? Ш).

Шаг 3. k=4 и a4 = c14 = max{9, 10}= 10. Вершина X4 получает пометку [X2+; 5]. Вершина X5 получает метку [X2+; 5]. Полагаем i = 4 и возвращаемся к шагу 2.

Шаг 2. P3 = [X 6] (? Ш).

Шаг 3. k=6 и a6 = c36 = max{5}= 5. Помечаем узел V6 меткой [X3+; 5]. Полагаем i = 6.

Шаг 4. Просмотрим вершину X4. Из нее можно перейти к вершине X1, которая получает пометку [X4-; 5]. Так как f(X1;X4) > 0, то cб1 = min {c14, f(X1;X4)} = 5. Переходим к шагу 2.

Шаг 2. P4 = [X5, tщ] (? Ш).

Шаг 3. k=щ и aщ = c4щ = max{9}=9. Помечаем узел tщ меткой [X4+; 3]. Получен сквозной путь. Переходим к шагу 5.

Шаг 5. Сквозной путь определяем по меткам, начиная с узла tщ и заканчивая узлом Sб:

tщ - [X4+; 3] - X4 - [X2+; 5] - X2 - [S+; 5] - Sб.

Таким образом, N1 = {Sб, X2, X4, tщ}; ѓ1 = min{aб, a2, a4, aщ} = {?, 5, 5, 3} = 3.

Вычислим остаточные пропускные способности вдоль пути N1:

с (Sб, X 2; X 2 Sб) = (5-3; 0+3) = (2; 3)

с (X 2, X 4; X 4 X 2) = (9-3; 0+3) = (6; 3)

с (X 4, tщ; tщ X 4) = (3-3; 6+3) = (0; 9)

Итерация 3.

Получаем остаточные пропускные способности всех ребер путем внесения изменений в пропускные способности тех ребер, которые находятся на маршруте N2, в соответствии с проходящим через них потоком ѓ2.

Шаг 1. Назначим aб = ? и пометим узел Sб меткой [-; ?]. Полагаем i = б.

Шаг 2. P1 = [X1, X2, X3] (? Ш).

Шаг 3. k=2, поскольку cб2 = max{cб2, cб3}= max{7, 5}= 7. Вершина X2 получает метку [S+; 2]. Вершина X3 получает метку [S+; 7]. Полагаем i = 2 и возвращаемся к шагу 2.

Шаг 2. P2 = [X 4, X 5] (? Ш).

Шаг 3. Вершина X4 получает пометку [X2+; 2]. Вершина X5 получает метку [X2+; 2]. Полагаем i = 4 и возвращаемся к шагу 2.

Шаг 2. Просмотрим вершину X5. P3 = [X5, tщ] (? Ш).

Шаг 3. k=щ и aщ = c5щ = max{10}=10. Помечаем узел tщ меткой [X5+; 2]. Получен сквозной путь. Переходим к шагу 5.

Шаг 5. Сквозной путь определяем по меткам, начиная с узла tщ и заканчивая узлом Sб:

tщ - [X5+; 2] - X5 - [X2+; 2] - X2 - [S+; 2] - Sб.

Таким образом, N1 = {Sб, X2, X5, tщ}; ѓ1 = min{aб, a2, a5, aщ} = {?, 2, 2, 2} = 2.

Вычислим остаточные пропускные способности вдоль пути N1:

с (Sб, X 2; X 2 Sб) = (2-2; 3+2) = (0; 5)

с (X 2, X 5; X 5 X 2) = (10-2; 0+2) = (8; 2)

с (X 5, tщ; tщ X 5) = (12-2; 0+2) = (10; 2)

Итерация 4.

Получаем остаточные пропускные способности всех ребер путем внесения изменений в пропускные способности тех ребер, которые находятся на маршруте N3, в соответствии с проходящим через них потоком ѓ3.

Шаг 1. Назначим aб = ? и пометим узел Sб меткой [-; ?]. Полагаем i = б.

Шаг 2. P1 = [X1, X2, X3] (? Ш).

Шаг 3. Вершины X1 и X2 помечены и просмотрены. Будем просматривать вершину X3. k=2, поскольку cб2 = max{cб2, cб3}= max{7, 5}= 7. Вершина X3 получает метку [S+; 7]. Полагаем i = 7 и возвращаемся к шагу 2.

Шаг 2. P2 = [X 2, X 6] (? Ш).

Шаг 3. Вершина X2 получает пометку [X3+; 4]. Вершина X6 получает метку [X3+; 5]. Полагаем i = 5 и возвращаемся к шагу 2.

Шаг 2. Просмотрим вершину X2. P3 = [X4, X5] (? Ш).

Шаг 3. k=5 и a5 = c25 = max{9;10}=9. Помечаем узел X5 меткой [X2+; 4]. Полагаем i = 4 и возвращаемся к шагу 2.

Шаг 2. Просмотрим вершину X5. P3 = [X5, tщ] (? Ш).

Шаг 3. k=щ и aщ = c5щ = max{10}=10. Помечаем узел tщ меткой [X5+; 4]. Получен сквозной путь. Переходим к шагу 5.

Шаг 5. Сквозной путь определяем по меткам, начиная с узла tщ и заканчивая узлом Sб:

tщ - [X5+; 4] - X5 - [X2+; 4] - X2 - [X3+; 4] - X3 - [S+; 7] - Sб.

Таким образом, N1 = {Sб, X3, X2, X5, tщ}; ѓ1 = min{aб, a3, a2, a5, aщ} = {?, 7, 4, 4, 4} = 4.

Вычислим остаточные пропускные способности вдоль пути N1:

с (Sб, X 3; X 3 Sб) = (7-4; 0+4) = (3; 4)

с (X 3, X 2; X 2 X 3) = (4-4; 0+4) = (0; 4)

с (X 2, X 5; X 5 X 2) = (8-4; 2+4) = (4; 6)

с (X 5, tщ; tщ X 5) = (10-4; 2+4) = (6; 6)

Итерация 5.

Получаем остаточные пропускные способности всех ребер путем внесения изменений в пропускные способности тех ребер, которые находятся на маршруте N4, в соответствии с проходящим через них потоком ѓ4.

Шаг 1. Назначим aб = ? и пометим узел Sб меткой [-; ?]. Полагаем i = б.

Шаг 2. P1 = [X1, X2, X3] (? Ш).

Шаг 3. Вершины X1 и X2 помечены и просмотрены. Будем просматривать вершину X3. k=2, поскольку cб2 = max{cб2, cб3}= max{7, 5}= 7. Вершина X3 получает метку [S+; 3]. Полагаем i = 3 и возвращаемся к шагу 2.

Шаг 2. P2 = [X 2, X 6] (? Ш).

Шаг 3. Вершина X2 помечена и просмотрена. Будем рассматривать вершину X6. Вершина X6 получает метку [X3+; 3]. Полагаем i = 3 и возвращаемся к шагу 2.

Шаг 2. Просмотрим вершину X6. P3 = [ tщ] (? Ш).

Шаг 3. k=щ и aщ = c6щ = max{7}=7. Помечаем узел tщ меткой [X6+; 3]. Получен сквозной путь. Переходим к шагу 5.

Шаг 5. Сквозной путь определяем по меткам, начиная с узла tщ и заканчивая узлом Sб:

tщ - [X6+; 3] - X6 - [X3+; 3] - X3 - [S+; 3] - Sб.

Таким образом, N1 = {Sб, X3, X6, tщ}; ѓ1 = min{aб, a3, a6, aщ} = {?, 3, 3, 3} = 3.

Вычислим остаточные пропускные способности вдоль пути N1:

с (Sб, X 3; X 3 Sб) = (3-3; 4+3) = (0; 7)

с (X 3, X 6; X 6 X 3) = (5-3; 0+3) = (2; 3)

с (X 6, tщ; tщ X 6) = (7-3; 0+3) = (4; 3)

Итерация 6.

Получаем остаточные пропускные способности всех ребер путем внесения изменений в пропускные способности тех ребер, которые находятся на маршруте N8, в соответствии с проходящим через них потоком ѓ8.



Новые сквозные пути невозможны, поскольку все ребра, исходящие из Sщ, имеют нулевые выпускные способности. Переходим к шагу 6 для определения решения.

Шаг 6. Максимальный объем потока в сети равен:

F = ѓ0 + ѓ1 + ѓ2 + ѓ3 + ѓ4 + ѓ5 = 0+6+3+2+4+3= 18 единиц.

Значение потоков по различным ребрам вычисляются путем вычитания последних значений остаточных пропускных способностей (т.е.(xij; xji)6) из первоначальных значений пропускных способностей (Xij; Xji).

Результаты вычислений приведены в следующей таблице:

Таблица 1.

Ребро	(Xij; Xji) - (xij; xji)6	Величина потока	Направление
(Sб; X1)	(6; 0) - (0; 6) = (6; -6)	6	б - 1
(Sб; X2)	(5; 0) - (2; 1) = (3; -1)	1	б - 2
(Sб; X3)	(7; 0) - (0; 7) = (7; -7)	5	б - 3
(X1; X2)	(8; 0) - (8; 0) = (0; 0)	0	-
(X1; X4)	(11; 0) - (6;-6) = (1; -1)	1	1 - 4
(X2; X4)	(9; 0) - (6; 3) = (3; -3)	3	2 - 4
(X2; X5)	(10; 0) - (4; 6) = (6; -6)	6	2 - 5
(X3; X2)	(4; 0) - (0; 4) = (4; -4)	4	3 - 2
(X3; X6)	(5; 0) - (2; 3) = (3; -3)	3	3 - 6
(X4; X5)	(12; 0) - (12; 0) = (0; 0)	0	-
(X4; tщ)	(9; 0) - (0; 9) = (1; -1)	1	4 - щ
(X5; X6)	(6; 0) - (6; 0) = (0; 0)	0	-
(X5; tщ)	(10; 0) - (6; 6) = (4; -6)	2	5 - щ
(X6; tщ)	(7; 0) - (4; 3) = (3; -3)	3	6 - щ

Поток f = 18 является максимальным, а множество дуг (S;X1); (S;X2); (S;X3) составляют минимальный разрез сети.

Проверка:

min L: (S;X1); (S;X2); (S;X3).

c(S;X1); c(S;X2); c(S;X3)= F

6+5+7 = 18

18 = 18

Ответ: верно.

Заключение.

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

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

Литература

1. Платонова И.В. Лекционный материал. М.:МГИДА, 2005

2. Таха Хемди А. Введение в исследование операций, 6-е издание.: Пер. с англ. -М.: Издательский дом «Вильямс», 2001

3. Аллавердиев А.М., Платонова И.В. «Прикладная математика». Методические указания по дисциплине. М.: МГИДА, 2000

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