Пример нахождения максимального потока методом Форда—Фалкерсона. Максимальный поток
При планировании рационального распределения продукции в сети распределения необходимо согласовывать пропускную способность каналов с потребностями клиентов и с мощностью производственного предприятия. Данный класс задач решается методом нахождения максимального потока.
Рассмотрим сеть распределения (рис. 4.21), в которой выделены пункты 0 (вход, например, склад готовой продукции производителя) и п (выход, распределительные центры, склады оптовых и розничных организаций, потребитель) и каждой дуге (отрезку), связывающей пункты i и j, сопоставлено число dij > 0, называемое пропускной способностью дуги. Величина пропускной способности характеризует максимальное допустимое количество материального потока, которое может проходить по соответствующей дуге в единицу времени.
Рис. 4.21.
Количество продукции, проходящее по дуге от i до j , будем называть потоком по дуге (i ,j ) и обозначать через . Очевидно, что
Если учесть, что весь материальный поток, вошедший в промежуточный пункт сети, должен полностью выйти из него, получим
Из естественного требования равенства потоков на входе и на выходе имеем
Величину Z назовем величиной потока в сети и поставим задачу максимизации Z при соблюдении обозначенных выше условий.
Поиск максимального потока сводится к поиску пропускной способности минимального разреза.
Рассмотрим универсальный алгоритм поиска в матричной форме.
Начальный этап алгоритма состоит в построении матрицы D 0, в которую заносятся значения пропускных способностей (для неориентированной дуги берем симметричные значения элементов матрицы ).
Основные шаги алгоритма состоят в поиске некоторого пути и коррекции потока на этом пути.
При поиске пути используем процесс отмечаний. Метим символом * нулевые строку и столбец матрицы (вход сети). В 0-й строке отыскиваем , метим соответствующие столбцы индексами
и переносим метки столбцов на строки. Затем берем ί-ю отмеченную строку, ищем в ней непомеченный столбец с , которому сопоставляем метки-индексы
Метки столбцов переносим на строки, и этот процесс продолжаем до тех пор, пока не будет отмечен п-й столбец.
Затем "обратным ходом" по индексам выясняем путь, приведший к η-й вершине, уменьшаем пропускные способности дуг пути (элементы матрицы) на V n и увеличиваем симметричные элементы на эту же величину.
Такая процедура продолжается до тех пор, пока отмечание n -й вершины не станет невозможным.
Максимальный поток может быть найден вычитанием из исходной матрицы D 0, получаемой после приведенной выше корректуры матрицы пропускных способностей:
Пример 4.4
Производство размещено в Москве. Для распределения продукции предприятие привлекает посредников, которые работают с предприятием через распределительные центры различных уровней. В европейской части России работает оптовое предприятие 1, обслуживаемое центральным распределительным центром. Оптовое предприятие 2 работает в ближайшем зарубежье (Украина, Белоруссия) и обслуживается региональным распределительным центром. Есть у предприятия на местном рынке (Москва и Московская область) свои клиенты – ритейлеры, которые получают продукцию с городского распределительного центра. Запасы регионального и городского распределительных центров пополняются с центрального распределительного центра.
Выделим фрагмент распределительной сети:
- склад готовой продукции производственного предприятия;
- центральный распределительный центр;
- региональный распределительный центр;
- городской распределительный центр;
- два оптовых предприятия;
- розничная точка, принадлежащая компании;
- потребители.
Рис. 4.22.
Каждое звено сети распределения обозначим цифрой, а над дугами проставим пропускную способность. Пропускная способность в зависимости от вида звена может быть выражена через объем производственной мощности, плановую потребность (спрос) потребителей и емкость рынка.
Граф сети распределения продукции представлен на рис. 4.23. Построим матрицу D 0, в которую занесем значения пропускных способностей звеньев распределительной сети (рис. 4.24).
Рис. 4.23.
Рис. 4.24.
Из нулевой строки отметим вершины (строки-столбцы) 1, 2 и 3 индексами μ = 0 и V, равными 30,10 и 10.
Из помеченной строки 1 отметим вершины 4 и 5 индексами μ = 1 и V4 = min (30,15) = 15, V5 = min (30,10) = 10.
Из строки 3 отметим вершину 6 и, наконец, из строки 4 – вершину 7 (рис. 4.25).
Рис. 4.25.
Обратным ходом по μ обнаруживаем путь: к вершине 7 от 4, к вершине 4 от 1, к вершине 1 от 0; корректируем элементы D 0 на величину потока V7 = 15.
Очередной шаг дает путь с потоком 5 (рис. 4.26).
Рис. 4.26.
Последующий шаг дает результат, представленный на рис. 4.27.
Рис. 4.27.
Дальнейшее отмечание невозможно. Отсюда получаем матрицу максимального потока (рис. 4.28).
Рис. 4.28.
В результате применения алгоритма нахождения максимального потока в сети получены результаты, представленные на рис. 4.29. Пары цифр в скобках, показанные на дугах графа, означают максимальную пропускную способность дуги и рекомендуемый объем поставки товаров в сеть.
Гамильтоновы циклы
Граф задан в форме матрицы, где в ячейках задана стоимость передвижения между пунктами. На главной диагонали ставится символ ∞, чтобы исключить бессмысленный путь в сам себя.
Т.к. в полученной матрице оказался столбец без нулевых элементов, то найдем в нем минимальный элемент и вычтем его из всех элементов этого столбца.
| A | B | C | D | |
| A | ∞ | |||
| B | ∞ | |||
| C | ∞ | |||
| D | ∞ |
Просуммируем все вычтенные элементы и получим нижнюю границу цикла в= 2+2+3+2+1=10
1.2. Проведём оценку всех нулевых элементов матрицы.
Оценку нулей удобно представлять в таблице.
| A | B | C | D | |
| A | ||||
| B | ||||
| C | ||||
| D |
θ=max γ=γ А C =2
1.3. Множество путей разобьём на два подмножества:QAC – пути, содержащие дугу (AC) и QAC – пути, не содержащие дугу (АC). Для второго подмножества нижней границей будет: в / =в+ θ =10+2=12.
Чтобы вычислить границу для первого подмножества, перейдём к матрице на порядок ниже, вычеркнув A-строку и C-столбец. В новой матрице для исключения обратного пути (CA) в соответствующую клетку поставим знак ∞.
Вычислим границу полученной матрицы 2+0=2
и добавим её к нижней границе цикла. Эта сумма в // =10+2=12 и будет границей для первого подмножества.
1.4. Сравним границы всех висячих вершин и выберем вершину с наименьшей границей. Если этих вершин две, выбираем любую из них. Это вершина QAC , нижняя граница которой =12.
Выберем максимальную из оценок θ=max γ=γ BD =3
в / =12+3=15.
1.6. Все последующие пункты выполняем аналогично предыдущим.
Выберем максимальную из оценок θ=max γ=γ С B = ∞
в / =в+ θ=∞
| A | |
| D |
Все строки и столбцы этой матрицы содержат нули. Следовательно, граница остается равной 12.
ЗАДАЧА. Найти величину максимального потока на транспортной сети.
ПОСТАНОВКА ЗАДАЧИ.
Рассмотрим транспортную задачу на сети (I,D,G ) с заданными пропускными способностями дуг c(i,j).
Выделим две фиксированные вершины: s - источник и t – сток. Потоком на сети s→t назовем числовую функцию f , определенную на множестве дуг и удовлетворяющую следующим линейным уравнениям и неравенствам:
0≤ f(i,j) ≤c(i,j) для любых (i,j)
Требуется максимизировать переменную x
Разрезом L
в сети, отделяющим вершины s t
называется множество дуг 
Любой путь s→t содержит по крайней мере одну дугу разреза.
КРИТЕРИЙ ОПТИМАЛЬНОСТИ: на реальной сети величина произвольного потока не превосходит пропускной способности разреза, а величина максимального потока равна минимальной пропускной способности разреза.
ПРИМЕР 3.12.
М 9 К
М 8 К
ПРИМЕР 3.13.
М 2 К
РЕШЕНИЕ:
Пропускная способность исходящей дуги (Т,В) превышает суммарную пропускную способность входящих в соответствующую вершину дуг. Для того, чтобы сеть стала реальной, заменим с(Т,В)=5.
Найдем и вычислим значение пропускных способностей всех разрезов. (К,В) – (Т,В) разрез с минимальной пропускной способностью =6. Следовательно, максимальный поток =6.
Сеть, имеющую несколько источников и стоков можно свести к сети с одним источником и стоком.
ПРИМЕР. Пусть имеется несколько источников S и стоков T (транспортная задача). Расширим сеть, добавив два узла s* , t* и все дуги (s*, S) , (T,t*). Доопределим функцию пропускной способности, положив
МЕТОД РАССТАНОВКИ ПОМЕТОК.
1. Начальный поток f(i,j) = 0.
Припишем вершинам данной сети пометки, которые будут иметь вид (i+, ε)
или
(i - , ε).
Источник пометим (-, ∞),
т.е. ε(s)=
∞.
2. Для любой помеченной вершины i
выберем все непомеченные вершины j
для которых f(i,j)
Эту операцию повторяем до тех пор, пока не окажется помеченным сток. Если сток остался непомеченным, то найденный поток - максимальный, а множество дуг, связывающих помеченные вершины с непомеченными, образуют минимальный разрез.
3. Пусть сток имеет пометку (j+, ε(t)) , тогда f(j,t) заменяем на f(j,t)+ε(t) . Если же сток имеет пометку (j-, ε(t)) , то f(j,t) заменяем на f(j,t)-ε(t) . Переходим к вершине j . Если j имеет пометку (i+, ε(j)) , то заменяем f(i,j) на f(i,j)+ε(t) , а если (i-, ε(j)) , f(j,i) заменяем на f(j,i)-ε(t) . Переходим к вершине i . Эту операцию повторяем до тех пор, пока не достигнем источника s . Изменение потока прекращается, стираются все пометки и переходим к п.2
ПРИМЕР 3.14.
М 4 К
| 1 шаг | А → (-, ∞) М → (А+,8) Р → (А+,3) К → (Р+,3) Т → (Р+,3) В → (Т+,3) | f(Т,В)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(А,М)=0 f(М,Р)=0 f(М,К)=0 f(М,Т)=0 f(К,Т)=0 f(К,В)=0 |
| 2 шаг | А → (-, ∞) М → (А+,8) Р → (М+,1) К → (М+,4) Т → (М+,2) | f(К,В)=3 f(М,К)=3 f(А,М)=3 f(Т,В)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(М,Т)=0 f(М,Р)=0 f(К,Т)=0 |
| 3 шаг | А → (-, ∞) М → (А+,5) Р → (М+,1) К → (М+,1) Т → (М+,2) В → (Т+,2) | f(Т,В)=5 f(М,Т)=2 f(А,М)=5 f(К,В)=3 f(М,К)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(М,Р)=0 f(К,Т)=0 |
| 4 шаг | А → (-, ∞) М → (А+,3) Р → (М+,1) К → (М+,1) Т → (Р+,1) В → (Т+,1) | f(А,М)=6 f(Т,В)=6 f(Р,Т)=4 f(М,Р)=1 f(М,Т)=2 f(К,В)=3 f(М,К)=3 f(А,Р)=3 f(Р,К)=0 f(К,Т)=0 |
| 5 шаг | А → (-, ∞) М → (А+,2) Р → (М-,1) К → (М+,1) Т → (К+,1) В → (Т+,1) | f(А,М)=7 f(М,К)=4 f(К,Т)=1 f(Т,В)=7 f(Р,Т)=4 f(М,Р)=1 f(М,Т)=2 f(К,В)=3 f(А,Р)=3 f(Р,К)=0 |
| 6 шаг | А → (-, ∞) М → (А+,1) | Поток оптимален f=10 Минимальный разрез:М →Т-М →Р-М →К |
ЗАДАЧА. Найти наибольший поток на сети
АЛГОРИТМ
Обозначим вершину s= х 0 . Все остальные – х i .
1 этап.
1. Выбираем любой путь, все дуги которого не насыщены.
2. Увеличиваем величину потока по этому пути на единицу до тех пор, пока в нем не будет насыщенной дуги.
Процесс увеличения потока продолжаем до тех пор, пока не будет построен полный поток, т.е. любой путь будет содержать хотя бы одну насыщенную дугу.
2 этап.
2. Если х i уже помеченная вершина, то помечаем (+i) все непомеченные вершины, в которые идут не насыщенные дуги из х i , и индексом (–i) все непомеченные вершины, из которых идут дуги с ненулевым потоком в х i .
3. Если в результате этого процесса окажется помеченной вершина t , то между s и t найдется путь, все вершины которого помечены номерами предыдущих вершин. Поток во всех дугах этого пути увеличиваем на единицу, если при движении отs к t ориентация дуги совпадает с направлением движения, и уменьшаем на единицу, если дуга имеет противоположную ориентацию. Переходим к п.1.
4. Когда вершину t невозможно пометить процесс прекращается и полученный поток является наибольшим потоком сети.
ПРИМЕЧАНИЕ. Перейти к 2 этапу можно, не завершая первого этапа (см. пример 3.16).
ПРИМЕР 3.15.
9
РЕШЕНИЕ:
На заданной транспортной сети найден полный поток. Насыщенные дуги выделены
В этой сети также можно пометить конечную вершину, причем результат разметки окажется тем же самым. Изменив поток, получим сеть, в которой конечную вершину пометить невозможно, поэтому поток в ней является наибольшим и равен 10.
ПРИМЕР 3.16.
8 2 1
На заданной транспортной сети найден неполный поток
Пометим сеть и увеличим в ней поток согласно алгоритму. Получим
В этой сети также можно пометить конечную вершину, причем результат разметки окажется тем же самым. Изменив поток, получим сеть, в которой конечную вершину пометить невозможно, поэтому поток в ней является наибольшим и равен 6.
Раздел IV. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.
Динамическое программирование служит для поиска оптимальных многоэтапных решений. Например, долгосрочное планирование замены оборудования; деятельность отрасли промышленности в течение ряда лет. Оно использует принцип оптимальности, согласно которому всякое новое частичное решение должно быть оптимальным относительно достигнутого состояния.
Лучше много раз решить одну простую задачу, чем один раз сложную.
ЗАДАЧА 1. О наивыгоднейшем пути между двумя пунктами.
Требуется соорудить путь, соединяющий два пункта А и В, из которых второй лежит к северо-востоку от первого. Для простоты допустим, что прокладка пути состоит из ряда шагов, и на каждом шаге мы можем двигаться либо строго на север, либо строго на восток. Тогда любой путь представляет собой ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей. Затраты на сооружение каждого из таких отрезков известны.
ПРИМЕР 4.1. Найти минимальный путь от А до В.
Последний шаг – достижение т.В. Перед последним шагом мы могли находиться в точках, откуда за один шаг можно достичь т.В. Таких точки две (система могла находиться в одном из двух состояний). Для каждой из них существует единственный вариант достижения т.В: для одной – двигаться на восток; для другой – на север. Запишем затраты 4 и 3 в каждом случае.
4
Теперь оптимизируем предпоследний шаг. После предыдущего шага мы могли оказаться в одной из трех точек: С 1 , С 2 , С 3 .
Для т. С 1 существует единственное управление (пометим его стрелкой) – двигаться на восток, при этом затраты составят 2(на данном шаге)+4(на следующем шаге)=6. Аналогично для т. С 3 затраты составят 2+3=5. Для т.С 2 существует два управления: идти на восток или на север. В первом случае затраты составят 3+3=6, а во втором случае – 1+4=5. Значит условное оптимальное управление – идти на север. Пометим его стрелкой и занесем соответствующие затраты.
| |
| |
| |
| ЗАДАЧА 2. О загрузке машины (о рюкзаке). Имеется N предметов. Известны вес a i и ценность φ i каждого предмета. Требуется заполнить рюкзак, способный вместить вес ≤ R , таким набором предметов, который обладал бы наибольшей ценностью.
Процесс загрузки рюкзака можно разбить на N шагов. На каждом шаге мы решаем вопрос: брать данный предмет или не брать? На каждом шаге имеется всего 2 управления: управление =1, если мы берем данный предмет; и 0 – если не берем. Состояние системы перед очередным шагом характеризуется весом S, который еще остался в нашем распоряжении до конца полной загрузки после того, как предыдущие шаги выполнены (какие-то предметы уже загружены), т.е. количеством свободного пространства в рюкзаке. АЛГОРИТМ. 1. Начнем с последнего шага. Сделаем различные предположения о свободном пространстве в рюкзаке: S=0,1,…R. Положим последний предмет в рюкзак, если в нем сводного пространства достаточно. 2. На каждом предыдущем шаге для всех возможных состояний S рассмотрим 2 варианта: брать или не брать предмет. Найдем выигрыш в каждом случае, как сумму выигрышей на текущем шаге и на следующем уже оптимизированном шаге. Результаты занесем во вспомогательную таблицу. 3. На первом шаге рассмотрим только единственно возможное состояние S=R. 4. Найдем решение, «пятясь назад», т.е. взяв оптимальное управление на первом шаге, изменим состояние системы на втором шаге: S=R–x 1 a 1 и выберем оптимальное управление х 2 для этого состояния. И т.д. ПРИМЕР 4.2. Исходные данные
Основная таблица
Вспомогательная таблица.
Ответ: x 4 =0; x 3 =1; x 2 =0; x 1 =1; W=15 ЗАДАЧА 3. О распределении ресурсов. Имеется N предприятий П 1 , П 2 ,… П N , каждое из которого дает доход φ k (x), если ему выделен ресурс в количестве x. Требуется имеющийся в количестве А ресурс распределить между объектами так, чтобы суммарный доход был максимальным. Пусть x k – количество ресурса, выделенное k-ому предприятию. Тогда рассматриваемая задача сводится к обычной задаче нелинейного программирования.
Сформулируем задачу, как задачу динамического программирования. За первый шаг примем вложение средств в предприятие П 1 , за второй – в П 2 и т.д. Управляемая система в данном случае – средства, которые распределяются. Состояние системы перед каждым шагом характеризуется одним параметром – наличным запасом еще не вложенных средств. В этой задаче шаговыми управлениями являются средства, выделяемые предприятиям. Требуется найти оптимальное управление (х 1 , х 2 ,…х N), при котором суммарный доход максимален: | 1,1 0,5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=3 | 0,1 0,5 | 1,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=4 | 0,1 0,5 | 2,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=5 | 0,1 0,5 2,5 | 3,1 2,5 2,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| i=1 S=5 | 0,5 1,5 | 3,1 1,1 | 3,1 3,5 2,1 2,6 |
Ответ: x 1 =1; x 3 =0; x 3 =4; W=3,5
ОБОБЩЕННЫЙ АЛГОРИТМ
1. Описать систему. Т.е выяснить, какими параметрами характеризуется состояние управляемой системы перед каждым шагом. Важно уметь правильно и “скромно” поставить задачу, не переобременяя ее лишними подробностями, упрощая сколько возможно описание управляемой системы.
2. Расчленить операцию на шаги (этапы). Здесь должны быть учтены все разумные ограничения, накладываемые на управление. Шаг должен быть достаточно мелким для того, чтобы процедура оптимизации шагового управления была достаточно проста; и шаг, в то же время должен быть не слишком мелким, чтобы не производить излишних расчетов, усложняющих процедуру поиска оптимального решения, но не приводящих к существенному изменению оптимума целевой функции.
3. Выяснить набор шаговых управлений x i для каждого шага и налагаемые на них ограничения.
4. Определить, какой выигрыш приносит на i-шаге управление x i , если перед этим система была в состоянии S, т.е. записать функции выигрыша:
w i =f i (S, x i)
5. Определить, как изменяется состояние системы под влиянием управления x i на I-м шаге, т.е. записать функции изменения состояния.
S / =φ i (S, x i)
6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш через уже известную функцию
W i (S)= max{f i (S,x i)+W i+1 (φ i (S, x i))}
7. Произвести условную оптимизацию последнего шага, делая различные предположения о том, чем кончился предпоследний шаг, и для каждого из этих предположений найти условное (выбирается исходя из условия, что шаг закончился тем-то) оптимальное управление на последнем шаге.
W m (S)= max{f m (S, x m)}
8. Произвести условную оптимизацию, начиная с предпоследнего и кончая первым шагом(пятясь назад).
9. Произвести безусловную оптимизацию управления, «читая» соответствующие рекомендации на каждом шаге: взять найденное оптимальное управление на первом шаге и изменить состояние системы, для найденного состояния найти оптимальное управление на втором шаге и т.д. до последнего шага.
ПРИНЦИП ОПТИМАЛЬНОСТИ. Каково бы ни было состояние системы перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.
Принцип динамического программирования не предполагает, что каждый шаг оптимизируется отдельно, независимо от других. Что толку выбирать управление, эффективность которого максимальна на одном конкретном шаге, если этот шаг лишит нас возможности хорошо выиграть на последующих шагах?
На практике встречаются случаи, когда планировать операцию приходится на неопределенно долгий промежуток времени. Моделью такого случая является бесконечношаговый управляемый процесс, где все шаги равноправны. Здесь функция выигрыша и функция изменения состояния не зависят от номера шага.
Раздел V. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ
Идея этого алгоритма состоит в поиске сквозных путей с положительными потоками от источника к стоку.
Рассмотрим ребро (i, j) с (начальной) пропускной способностью. В процессе выполнения алгоритма части этих пропускных способностей «забираются» потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Запись - остаточная пропускная способность. Сеть в которой все ребра имеют остаточную пропускную способность, назовем остаточной.
Для произвольного узла j, получающего поток из узла i, определим метку, где - величина потока, протекающего от j узла к узлу i. Чтобы найти максимальный поток, выполняем следующие действия.
Для всех ребер положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем =. Назначим и пометим узел 1 меткой. Полагаем i=1.
Множество узлов j, в которые можно перейти из узла I по ребру с положительной остаточной пропускной способностью >0 для всех j. Если, выполняем 3 этап, в противном случае переходим к 4.
В находим узел k, такой, что. Положим и пометим узел k меткой. Если k=n, сквозной путь найден, и переходим к 5 этапу, в противном случае полагаем i=k и возвращаемся к 2 этапу.
Откат назад. Если i=1, сквозной путь не возможен, и переходим к 6. Если, находим помеченный узел r, непосредственно предшествующий узлу i, и удаляем его из множества узлов, смежных с узлом r. Полагаем i=r и возвращаемся ко 2 этапу.
Определение остаточной сети. Обозначим через множество узлов, через которые проходит p_й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n).тогда максимальный поток, проходящий по этому пути
Остаточные пропускные способности ребер, составляющих сквозной путь, уменьшаются на величину в направлении движения потока и увеличиваются на эту же величину в противоположном направлении.
Т.о. для ребра (i, j), входящего в сквозной путь, текущие остаточные пропускные способности изменяются:
1) , если поток идет от узла i к j,
2) , если поток идет от узла j к i.
а) при m найденных сквозных путях максимальный поток выражается
б) Имея значения начальных и конечных пропускных способностей ребра (i, j), можно вычислить оптимальный поток через это ребро следующим образом. Положим. Если >0, поток, проходящий через ребро (i, j) равен. Если >0, тогда поток равен. (случай, когда одновременно >0 и >0, невозможен).
Пример 1. Найти максимальный поток в сети рис. 1
Итерация 1. =
3) k=3, так как. Назначаем и помечаем узел 3 меткой. i=3 и возвращаемся к 2)
5) k=5 и. Помечаем узел 5 меткой. Получаем сквозной путь.
6) сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1: . и. Вычисляем остаточные пропускные способности вдоль пути:
Итерация 2.
1) и помечаем узел 1 меткой. i=1
2») (, поэтому узел 5 не включается в
3») k=4, и помечаем узел 4 меткой. i=4 и возвращаемся к 2)
2""") (так как узлы 1 и 3 помечены, они не включаются в)
3""") k=5 и. Помечаем узел 5 меткой. Получен сквозной путь. Переходим к 5)
Итерация 3.
1) и помечаем узел 1 меткой. i=1
3) k=2, и помечаем узел 2 меткой. i=2 и возвращаемся к 2)
3") k=3 и. Помечаем узел 3 меткой. i=3 и возвращаемся к 2)
2») (так как) переходим к 4)
4) метка узла 3 показывает номер предшествующего узла. На этой итерации узел 3 в дальнейшем во внимание не принимается, его метку вычеркиваем. и возвращаемся к 2)
2""") (так как узел 3 удален из возможного сквозного пути)
3""") и. Помечаем узел 5 меткой. Получен сквозной путь. Переходим к 5)
5) и. Вычисляем остаточные пропускные способности вдоль пути:
Итерация 4. на этой итерации получен путь с
Итерация 5. на этой итерации получен путь с
Итерация 6. новые сквозные пути невозможны, поскольку все ребра, исходящие из узла 1, имеют нулевые остаточные пропускные способности. Переходим к 6) для определения решения
6) максимальный объем потока в сети равен единиц.
Значения потоков по различным ребрам вычисляются путем вычитания последних значений остаточных пропускных способностей из первоначальных значений пропускных способностей.
Результаты вычислений: табл. 1
|
Величина потока |
направление |
||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(30,0) - (0,30)=(30, - 30) |
|||
|
(10,0) - (0,10)=(10, - 10) |
|||
|
(40,0) - (40,0)=(0,0) |
|||
|
(30,0) - (10,20)=(20, - 20) |
|||
|
(10,5) - (0,15)=(10, - 10) |
|||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(20,0) - (0,20)=(20, - 20) |
Графическое последовательное выполнение алгоритма нахождения максимального потока (пример 1)
д) е) Сквозных путей нет
Рис.
Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 2, можно также задать таблицей (табл. 2).
Табл.2. Исходные данные к задаче о максимальном потоке
Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3. Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4. Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы. Решение можно представить в виде таблицы (табл. 3)
Табл.3. Решение задачи о максимальном потоке
|
Пункт отправления |
Пункт назначения |
План перевозок |
Пропускная способность |
Задача линейного программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х KM - объем перевозок из пункта К в пункт М. Согласно рис. 2 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных Х KM, а именно, Х 01, Х 02, Х 03, Х 12, Х 13, Х 14, Х 23, Х 24, Х 34. Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:
Х 01 + Х 02 + Х 03 = F (0)
Х 01 + Х 12 + Х 13 + Х 14 = 0 (1)
Х 02 - Х 12 + Х 23 + Х 24 = 0 (2)
Х 03 - Х 13 - Х 23 + Х 34 = 0 (3)
Х 14 - Х 24 - Х 34 = - F (4)
Х КМ? 0, К, М = 0, 1, 2, 3, 4
Здесь F - целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не «рождаются» в ней. Условие (4) - это условие «выхода» грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом («вход» равен «выходу»). Следующие девять неравенств задают ограничения на пропускную способность отдельных «веток» транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию - через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом «не знает»).
Пусть задан ориентированный граф G=
Обозначим через x(v) величину потока, движущегося по дуге v . Очевидно, что
0£ x(v) £ d(v) , vÎV . (6. 1)
В каждой вершине iÎE\{t,s} объем потока входящего равен объему потока выходящего, т.е. справедливо равенство
{x(v )|i Î V + (i)}= {x(v)| iÎ V - (i)}
{x(v)| iÎV + (i)} - {x(v)| iÎV - (i)}=0. (6.2)
Для вершины t
{x(v)| iÎV + (i)} -{x(v)¦ iÎV - (i)}=-Q, (6.3)
для вершины s
{x(v)| iÎ V + (i)} -{x(v)¦ i Î V - (i)}= Q. (6.4)
Величина Q является величиной потока, который выходит из вершины t и входит в вершину s .
Требуется определить
Q ® max (6.5)
при ограничениях (6.1-6.4).
Величины Q, x(v) , vÎV, удовлетворяющие ограничениям (6.1-6.4) будем называть потоком в сети, и если они максимизируют величину Q , то максимальным потоком. Нетрудно видеть, что значения Q=0, x(v)=0, vÎV , являются потоком в сети.
Задача (6.1-6.5) является задачей линейного программирования и ее можно решить алгоритмами симплекс-метода.
Разобьем множество вершины Е на две непересекающиеся части Е1 и Е2 таким образом, чтобы tÎE1, sÎE2 . Разрезом V(E1,E2) , разделяющим t и s будем называть множество V(E1,E2)ÌV такое, что для каждой дуги v Î V(E1,E2) либо h1(v)ÎE1 и h2(v)ÎE2 , либо h1(v)ÎE2 и h2(v)ÎE1 .
Разобьем множество V(E1,E2) на две части V(E1,E2,+),V(E1,E2,-) следующим образом:
V(E1,E2,+)={vÎV(E1,E2)| h1(v)ÎE1 и h2(v)ÎE2}
V(E1,E2,-)= { vÎV(E1,E2)| h2(v)ÎE1 и h1(v)ÎE2}
Пропускной способностью разреза будем называть
Q(E1,E2) = {x(v)| vÎV(E1,E2,+)}-{x(v)| vÎV(E1,E2,-)}
Справедлива следующая
Теорема 1 . (О максимальном потоке и минимальном разрезе).
В любой сети величина максимального потока из источника t в сток s равна минимальной пропускной способности Q(E1,E2) среди всех разрезов V(E1,E2) , разделяющих вершины t и s .
Заметим, что в максимальном потоке
x(v)=d(v) , vÎV(E1,E2,+),
x(v)=0 , vÎV(E1,E2,-).
Пусть Q, x(v), vÎV, - некоторый поток в сети, последовательность
t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,
является цепью, соединяющих вершины t и s . Зададим на этой цепи направление движения от вершины t к s . Дуга v(j) из этой цепи называется прямой, если ее направление совпадает с направлением движения от t к s , и обратной в противном случае. Эту цепь будем называть путем увеличения потока , если для прямых дуг v цепи x(v) < d(v) и для обратных x(v) > 0 . По этой цепи можно пропустить дополнительный поток q из t к s величиной q = min (q1,q2), где q1=min (d(v) -x(v)) , минимум берется по всем прямым дугам цепи, q1=min (x(v)) , минимум берется по всем обратным дугам цепи.
Теорема 2 .
Поток Q, x(v) , vÎV , максимальный тогда и только тогда, когда не существует пути увеличения потока.
Предлагаемый алгоритм решения задачи о максимальном потоке в сети, основан на поиске пути увеличения потока из t в s , который в свою очередь основан на процессе расстановки пометок вершин. Будем говорить, что
вершина i помечена пометкой q(i)>0 , а также известна дуга прямая дуга v(i) , через которую поступил этот поток, либо помечена пометкой , если до нее дошел некоторый дополнительный поток величиной q(i)>0 , а также известна обратная дуга v(i) , через которую поступил этот поток;
вершина i просмотрена, если помечены все соседние с ней вершины.
Если помечена вершина s, то найден путь увеличения потока величиной q , который пропускается по этому пути. Для описания алгоритма нам понадобится также массив SPW , в который помещаются номера помеченных вершин в порядке их пометки. С1 - номер в массиве SPW просматриваемой вершины, С2 - номер последней помеченной вершины в этом массиве.
