Файл: И.А. Кузнецов Сетевые модели. Методические указания к практическим занятиям.pdf

12

Расчет показывает, что наиболее выгодным с точки зрения возможности беспрепятственного проезда является путь 1 - 6 - 7 - 10 - 9. Полная вероятность беспрепятственного проезда по нему составляет 0,56• 0,93• 0,7• 0,88=0,3208. Длина этого пути составляет 12 км. Кратчайшим же является путь 1 - 2 - 5 - 8 - 9 (длина - 11 км), однако вероятность беспрепятственного проезда по нему равна

0,74• 0,69• 0,8• 0,61=0,2492.

Практическое занятие № 4 ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ

Цель работы

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

Задание

1. Для заданной модели транспортной сети с указанными величинами пропускных способностей дуг отыскать цепь, поток по которой будет максимальным.

13

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

Исходные данные: ГТС с указанными величинами пропускных способностей дуг.

Методические указания

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

Через f (x, y) будем обозначать количество единиц потока, прошедших по дуге (x, y) . Для любого потока из s в t количество единиц,

где Х - множество всех вершин рассматриваемого графа. Кроме того,

где А - множество всех дуг рассматриваемого графа.

Наконец, суммарное число единиц потока, выходящих из источника, должно быть равно суммарному числу единиц потока, входящих в сток. Если указанное число обозначить через v, то это условие можно

(x, y) А , для которого выполняются эти четыре условия, то такой на-

бор представляет собой поток из источника s в сток t.

Задача о максимальном потоке состоит в поиске потока, удовлетворяющего условиям (1) - (4), для которого величина v максимальна.

14

Задача о максимальном потоке является задачей линейного программирования и может быть решена симплексным методом. Однако существует более простой алгоритм решения этой задачи - так называемый алгоритм Форда - Фалкерсона.

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

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

Если количество единиц потока, которое может проходить по дуге (x, y) , ограничено, то говорят, что дуга (x, y) имеет ограниченную пропускную способность. Максимальную величину пропускной способности будем обозначать через c(x, y) . Кроме того, через a(x, y) будем обозначать стоимость перемещения единицы потока по дуге (x, y) .

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

f (x, y) . Очевидно, 0 ≤ f (x, y) ≤ c( x, y) . Дуги графа можно отнести к трем

различным категориям:

1) дуги, в которых поток не может не увеличиваться, не уменьшаться (множество таких дуг обозначим через N);

2) дуги, в которых поток может увеличиваться (множество таких дуг обозначим через I)

3) дуги, в которых поток может уменьшаться (множество таких дуг обозначим через R).

Множеству N, например, должны принадлежать дуги, имеющие нулевую пропускную способность или значительную стоимость прохо-

15

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

Обозначим через i(x, y) максимальную величину, на которую может быть увеличен поток в дуге. Очевидно, что i(x, y) = c( x, y) - f( x, y) .

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

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

Шаг 1. Определить состав множеств N, I и R. Дуги множества N из дальнейшего рассмотрения исключить (поскольку в них поток увеличиваться не может).

Шаг 2. Окрашивать дуги и вершины в соответствии с приведенными ниже правилами до тех пор, пока либо не будет окрашена вершина t, либо окраска новых вершин станет невозможной.

Правила окрашивания вершины у и дуги (x, y) при уже окрашенной вершине х:

а) если (x, y) I , то окрашивают вершину у и дугу (x, y) ; б) если (x, y) R , то окрашивают вершину у и дугу (y, x) ;

в) в противном случае окрашивание вершины у и дуги (x, y) не

производится.

В случае окрашивания вершины t действие алгоритма прекращается: в сети находится единственная увеличивающая цепь. В противном

16

случае, когда вершина t не окрашена, а окрасить новые вершины и дуги уже невозможно, в сети отсутствуют увеличивающие цепи из s в t.

Формальное описание алгоритма выглядит следующим образом. Шаг 1. Выбрать любой начальный поток из вершины s (источник)

в вершину t (сток), т.е. любой набор величин f (x, y) , удовлетворяющий соотношениям (1) - (4). Если ни один из начальных потоков из s в t неизвестен, задать начальный поток, положив для всех (x, y) f( x, y) = 0 .

Шаг 2. Сформировать множества дуг I и R согласно правилам, приведенным в алгоритме поиска увеличивающей цепи.

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

2.

Пример. Решим задачу о максимальном потоке для ГТС, изображенного на рис. 1. Источником является вершина 11, стоком - вершина 9. Будем считать, что цифры возле дуг - их пропускные способности c(x, y) . Общее количество единиц потока, которое необходимо переслать, v=7 (т.к. пересылка большего количества из вершины 11 невозможна).

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

2-й шаг. Ищем по тому же принципу увеличивающую цепь. Это цепь 11 - 1 - 6 - 7 - 10 - 9, по ней можно переслать 2 единицы потока. Во множество N переходят дуги (1 - 6) и (6 - 7). Остается переслать 2 единицы потока.

3-й шаг. Ищем новую увеличивающую цепь. Единственный возможный вариант - цепь 11 - 1 - 2 - 5 - 8 - 9, по ней возможно переслать 1 единицу потока (т.к. 3 единицы уже пересылаются по первой цепи, а с(1,2)=4). После этого дуга (1 - 2) также переходит во множество N, и выполнение алгоритма заканчивается (из вершины 1 больше нельзя выслать ни одной единицы потока).