Приклад знаходження максимального потоку методом Форда-Фалкерсона. Метод знаходження максимального потоку

При плануванні раціонального розподілу продукції мережі розподілу необхідно узгоджувати пропускну спроможністьканалів із потребами клієнтів та з потужністю виробничого підприємства. Цей клас завдань вирішується шляхом знаходження максимального потоку.

Розглянемо мережу розподілу (рис. 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. Пари цифр у дужках, показані на дугах графа, означають максимальну пропускну спроможність дуги та рекомендований обсяг постачання товарів у мережу.

Транспортне завдання
Може виникати у фізиці, економіці тощо.
На окремі компоненти транспортної мережі
(Мережа залізничних, автомобільних і т.д.
шляхів; мережу трубопроводів і т.д.) накладено
обмеження – їх максимально допустима
навантаження.
Необхідно визначити максимально
можлива кількість пасажирів, товару,
продукту і т.д., яке можна провезти по цій
мережі та яким чином.
Ми збудуємо графову дискретну модель
цієї транспортної задачі та вирішимо її в цій
моделі.

Математик Джордж Бернард Данциг, з 1941 року
працюючи у відділі статистичного управління Військово-повітряних сил США у Вашингтоні, вперше вирішив
завдання про максимальний потік під час підготовки
повітряний мост під час блокади Західного Берліна.
1951 року Джордж Данциг вперше сформулював
завдання в загальному вигляді. У 1955 році, Лестер Форд і
Делберт Фалкерсон вперше побудували алгоритм,
спеціально призначений для вирішення цього завдання.
Їхній алгоритм отримав назву алгоритм ФордаФалкерсона.
У 2010 році дослідники Джонатан Келнер і
Александер Мондри із МТІ разом зі своїми
колегами Деніелем Спілманом з Єльського
університету та Шень-Хуа Тенем з ПівденноКаліфорнійського університету продемонстрували
чергове вдосконалення алгоритму.

Даний орієнтований граф
(транспортна мережа) G = (V, E), вершина
графа s (джерело) та вершина t (стік).
Кожній дузі (i, j) приписано деяку
пропускна здатність з(i,j) 0 (без
втрати спільності вважаємо її
цілою величиною),
визначальна максимальне значення
потоку, який може протікати по
цій дузі.

потоком
в
мережі
називають
цілісну функцію f(i, j), задану
на безлічі дуг E і володіє
наступними властивостями:
1. Обмеження потоку пропускної
здатністю
Для будь-якої дуги (i, j) E виконується
нерівність f(i, j) c(i, j).

2. Збереження потоку
Для будь-якої вершини q V,
виконується рівність
q s
і
q t
f(i, q) f(q, j)
i V
(i, q) E
j V
(q, j) E
Т. е. сума потоку, що заходить в q, дорівнює
сумі потоку, що виходить із q (потік без
втрат та накопичень)

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

приклад
У компанії Lycky Puck у Ванкувері є фабрика
(джерело s), що виробляє хокейні шайби, а в
Вінніпеге - склад (стік t), де ці шайби зберігаються.
Компанія орендує місця на вантажівках інших фірм
для доставки шайб із фабрики на склад. Оскільки
вантажівки їздять певними маршрутами (ребрами)
між містами (вершинами) та мають обмежену
вантажопідйомність, компанія Lycky Puck може
перевозити не більше c(u,v) ящиків на день між кожною
парою міст u та v. Компанія Lycky Puck не може
вплинути на маршрути та пропускну спроможність. Її
завдання – визначити, яка найбільша кількість
ящиків на день можна відвантажувати, а потім виробляти
саме така кількість, оскільки не має сенсу
робити шайб більше, ніж можна відправити на
склад.

Методи вирішення задачі
Лінійне програмування
Уявити задачу про максимальний потік як задачу
лінійного програмування. Змінними є
потоки по ребрам, а обмеженнями - збереження потоку
та обмеження пропускної спроможності.
Алгоритм Форда-Фалкерсона
Знайти будь-який шлях, що збільшує. Збільшити потік по
всім його ребрам на мінімальну з їх залишкових
пропускних здібностей. Повторювати, поки
збільшує шлях є. Алгоритм працює тільки
для цілих пропускних можливостей.

10.

Приклад 1
Дамо формулювання завдання про максимальне
потоці термінах лінійного програмування.
Нехай ХKM - обсяг перевезень з пункту К пункт М.
К = 0,1,2,3, М = 1,2,3,4, причому перевезення можливі
лише в пункт з великим номером. Значить, всього
є 9 змінних ХKM, а саме, Х01, Х02, Х03, Х12
Х13, Х14, Х23, Х24, Х34.
s=0
t=4

11.

Завдання лінійного програмування,
націлена на максимізацію потоку, має вигляд:
F → max,
Х01 + Х02 + Х03 = F
-Х01 + Х12 + Х13 + Х14 = 0
-Х02 -Х12 + Х23 + Х24 = 0
-Х03-Х13-Х23 + Х34 = 0
-Х14 -Х24 -Х34 = - F
Х01 ≤ 2
Х02 ≤ 3
Х03 ≤ 1
Х12 ≤ 4
Х13 ≤ 1
Х14 ≤ 3
Х23 ≤ 1
Х24 ≤ 2
Х34 ≤ 2
ХКМ ≥ 0, К, М = 0, 1, 2, 3, 4
F≥0.

12.

Розрізом
називають безліч дуг,
видалення яких із мережі призводить до
«розриву» всіх шляхів, що ведуть з s до t.
Пропускна здатність розрізу – це
сумарна пропускна спроможність дуг, його
складових.
!!! Знайти розрізи у прикладі 1

13.

Теорема Л. Форда та Д. Фалкерсона:
Величина кожного потоку з s у t не
перевершує
пропускний
здібності
мінімального розрізу, що поділяє s і t,
причому потік, що досягає цього значення,
Існує.
(Величина
максимального
потоку
в
транспортної
мережі
дорівнює
величині
мінімального розрізу в ній)
!!! Знайти мінімальний розріз у прикладі 1

14.

З алгоритмічної точки зору ця
теорема малопродуктивна.
Генерація всіх підмножин дуг та
перевірка,
є
чи
чергове
підмножина розрізом – «лобове рішення»,
призводить до високої складності алгоритму.
Крім того, цей факт не допомагає
знайти спосіб розподілу максимального
потоку дугами.

15.

Алгоритм Форда-Фалкерсона
«Техніка міток» Л. Форда та Д. Фалкерсона
полягає в послідовному
(ітераційному, пошуком завширшки) побудові
максимального потоку шляхом пошуку на кожному
кроку збільшуючого ланцюга, тобто шляху,
якому можна збільшити потік.
У цьому вузли (вершини графа)
спеціальним чином позначаються. Звідси і
виник термін "мітка".

16.

Алгоритм Форда-Фалкерсона
Що являє собою мітка
вершини?
перша цифра у мітці – це номер
вершини, з якої йде потік у
цю вершину;
друга цифра у мітці – чисельне
значення потоку, який можна
передати на цю вершину.

17.

Алгоритм Форда-Фалкерсона
На кожному кроці алгоритму вершини мережі
можуть бути в одному з трьох станів:
вершина немає мітки;
вершині присвоєно мітку, і вона не
переглянуто, тобто не всі суміжні з нею
вершини оброблені;
вершині присвоєно мітку, і вона
переглянуто.

18.

Алгоритм Форда-Фалкерсона
Як тільки вершина-стік стає
поміченою, це говорить про те, що
черговий ланцюжок, що збільшує потік
знайдено, підсумковий сумарний потік
необхідно збільшити на величину потоку
знайденого ланцюжка, і перейти до
наступний крок алгоритму.

19.

Алгоритм Форда-Фалкерсона
Дуга e=(u, v) мережі є допустимою
дугою з u до v щодо потоку f, якщо
e=(u, v) та f(e) прямі);
e=(v, u) та f(e)>0 (дуги другого типу,
зворотні).
Друга умова говорить про те, що
допустимими є і дуги, що входять до
вершину u, якими «вже пропущено
ненульовий потік».

Цей посібник призначений для студентів, які вивчають курс дискретної математики та (або) теорії графів. За його допомогою Ви опануєте тему "Максимальний потік та мінімальний розріз у мережі". Прямо з цього посібника Ви можете порахувати свій ВДЗ, навіть якщо у Вас немає на комп'ютері MATLAB. Якщо ж у Вас є MATLAB, перейдіть на цю сторінку: там Ви маєте можливість втрутитися в сценарій (програму) обчислень. Тут же завдання про максимальний потік у мережі вирішується шляхом зведення до задачі лінійного програмування.

Введемо позначення:

n=|V| − розмір графа (кількість вершин);
m=|E| − потужність графа (кількість ребер);
A − матриця інцидентності орграфа мережі розміром n× m; кожен її елемент a ik=1, якщо з i-й вершини виходить k-я дуга; a ik=−1, якщо у i-ю вершину входить k-я дуга; і a ik=0 в інших випадках; у кожному стовпці такої матриці рівно одна одиниця, одна мінус одиниця, інші нулі;
s− номер вершини-джерела мережі; з цієї вершини повинні тільки виходити дуги, і будь-яка інша вершина має бути досяжною з джерела;
t− номер вершини-стоку мережі; у цю вершину повинні тільки входити дуги, і з будь-якої іншої вершини має бути досягнуто стік;
a s − s A ; у ній мають бути лише одиниці, т.к. із джерела повинні тільки виходити дуги;
a t − t-я рядок матриці інцидентності орграфа мережі A ; у ній мають бути лише мінус одиниці, т.к. у стік повинні лише входити дуги;
A st− матриця інцидентності орграфа мережі A з викинутими з неї s-й та t-й рядками;
e − вектор-стовпець довжини m; у кожному його елементі e kбуде величина потоку в k-ї дузі;
c − вектор-стовпець довжини m; у кожному його елементі c k≥0 задається пропускна спроможність kї дуги.

Тоді задача про максимальний потік у мережі може бути сформульована як завдання лінійного програмування:

Максимізується загальний потік, що виходить із джерела (1). При цьому в будь-якій проміжній вершині вхідний потік дорівнює виходить (2), а пропускні здібності дуг обмежені (3).

Завдання, двоїсте до завдання про максимальний потік – це завдання про мінімальний розріз. Для побудови мінімального розрізу можна скористатися теоремами подвійності. Потрібно:

видалити з орграфа мережі всі порожні ( e k= 0) та насичені ( e k = c k) дуги;
знайти компоненти зв'язності графа, що залишився;
якщо таких компонентів дві, то викинуті дуги дають мінімальний розріз;
якщо з'явиться більше двох компонент зв'язності, то орграф мережі має кілька мінімальних розрізів (відповідна задача лінійного програмування вироджена).

Для виродженого завдання даній сторінці будується перший, найближчий до джерела мінімальний розріз.

Для правильної роботиз цією сторінкою Ваш браузер повинен підтримувати сценарії Java Script. Увімкніть їх.

Введіть вихідні дані в області введення, що знаходяться нижче. У першій області потрібно (точніше, можна) запровадити координати вершин для малювання орграф мережі. Вони задаються у вигляді матриці n×2: у першому стовпці − x-е координати, у другому - y-е. Числа можна ставити цілі, з десятковою точкою або в експоненційній формі. Числа розділяйте пробілами. Загальна кількість рядків у цій галузі введення визначає розмір орграфа n− кількість вершин. Ці вихідні дані (координати вершин) не є обов'язковими: якщо їх не задати, то орграф мережі буде малюватись у вигляді правильного n-кутника, а кількість вершин визначатиметься максимальним номером вершини в наступній області введення.

У наступній області введення ліва частина обов'язкова для заповнення. У ньому визначається структура орграфа мережі. Кожна дуга в орграфі поєднує дві вершини. Номери цих вершин задаються як матриці m×2 у лівій частині другої області введення. На кожному рядку спочатку задається 1-а вершина (хвіст, джерело) дуги, а потім через пропуск 2-а (вістря, стік) дуги. У цих стовпцях мають бути натуральні числавід 1 до nвключно. Числа розділяйте пробілами. У правій частині задаються пропускні здібності дуг - дійсні позитивні числа. Якщо цей стовпець не заданий, усі пропускні можливості вважаються однаковими (поодинокими). Загальна кількість чисел у кожному з цих стовпців визначає потужність орграфа m− кількість дуг.

Порахувати

Потоки у мережах

Завдання про максимальний потік

Нехай задана мережа, що складається з безлічі вершин Е і безлічі дуг, що з'єднують деякі впорядковані пари вершин, взятих з Е. Припускатимемо, що вона є симетричним графом, тобто якщо дуга () входить в мережу, то в неї входить і симетрична Дуга (), хоча реально такої дуги може і не бути. Для визначеності привласним вершин мережі такі номери: . Кожна вершина характеризується інтенсивністю. Вершини, котрим , назвемо джерелами, вершини, котрим , - стоками, інші - проміжними. Шляхами мережі прямують деякі потоки - однорідна речовина (газ, рідина) або транспорт - із джерел у стоки. Кожній дузі () мережі поставлено у відповідність число, зване пропускною здатністю дуги. Під пропускною спроможністю дуги розуміється максимальний потік, який може пропустити за одиницю часу. Нехай і для інших вершин, тоді - єдине джерело, - єдиний стік, а - проміжні вершини мережі.

Ставиться завдання визначити для заданої мережі максимальну величину потоку із джерела в стік. Під потоком в мережі з джерела в стік будемо розуміти сукупність потоків () по всіх дугах мережі, де - потік по дузі (), , що дорівнює кількості переміщуваної по ній субстанції в одиницю часу. Математично завдання про максимальний потік формулюється наступним чином: знайти невід'ємні значення для всіх, що максимізують

(3.9)

при обмеженнях:

(3.11)

Умова (3.9) відображає величину максимального потоку, який дорівнює кількості речовини, що витікає з джерела, або тече в стік. Умови (3.10) означають, що потік за кожною дугою повинен бути невід'ємним і не перевищувати її пропускну здатність; з умови (3.11) випливає, що кількість речовини, що притікає до будь-якої проміжної вершини, дорівнює кількості речовини, що випливає з неї.

Досі ми розглядали мережі з єдиним джерелом та стоком. Насправді, однак, кількість джерел і стоків може бути довільним. Покажемо, що за допомогою незначних змін топології завдання такого типу можуть бути зведені до розглянутих.

Проілюструємо це з прикладу.

Розглянемо мережу, що складається з трьох джерел та двох стоків (Рис. 3.10). Нехай, для певності, дана мережаописує таке завдання.

Місця видобутку нафти розташовані у географічних пунктах. З місць видобутку нафту транспортують на нафтопереробні заводи через деякі проміжні пункти. Сукупність пунктів з транспортними магістралями, що з'єднують їх, зобразимо у вигляді мережі на Рис. 3.10 дуги відповідають транспортним магістралям, а вершини - окремим пунктам (місцям видобутку, заводам, станціям перекачування або залізничним станціям). Пропускні можливості транспортних магістралей приписані дугам мережі. Щоб визначити, яке максимальна кількістьнафти можна транспортувати з місць видобутку на нафтопереробні заводи, необхідно розширити мережу, додавши одне фіктивне джерело та один фіктивний стік (фіктивні дуги малюнку нанесені штриховими лініями).

Очевидно, що величину потоку як вихідної мережі, так і в розширеній мережі визначають пропускні здатності дуг вихідної мережі. Таким чином, задача про максимальний потік з безлічі джерел у безліч стоків рівнозначна задачі про максимальний потік з єдиного джерела в єдиний стік.

Рис. 3.10. Введення фіктивного джерела та стоку

приклад 3.

Наведемо приклад розв'язання задачі про максимальний потік в Excel. Розглянемо деяку транспортну мережу (Рис. 3.11). Припустимо, що транспортні потоки можуть йти в обох напрямках деяких дуг (очевидно, цей випадок є більш загальним і складним для вирішення, ніж випадок односторонніх транспортних потоків). На малюнку позначені максимальні пропускні здібності в обох напрямках: наприклад з пункту 3 пункт 6 може бути транспортований потік інтенсивністю 4 одиниці, і такий же потік - з пункту 6 пункт 3 (нулі у закінчень деяких дуг означають неможливість транспортування у відповідному напрямку). Потрібно визначити максимальну пропускну спроможність мережі загалом, тобто. максимальне значення потоку.

Рис. 3.11. Мережевий графікПриклад 3.

Рішення.

Так як передбачається, що для кожного проміжного вузла мережі повний вхідний потік повинен дорівнювати повному вихідному потоку, то завдання може бути сформульована наступним чином:

Максимізувати за обмежень:

Введемо дані на робочий лист відповідно до Мал. 3.12.

Рис. 3.12. Дані для вирішення задачі про максимальний потік

Діапазон осередків A6: Q6 відведемо під розрахункові значення змінних. У комірки A8:A14, а також у цільову комірку F13 введемо такі формули




	C6+D6+I6-E6-H6-J6


	G6+N6+H6+K6-L6-I6-M6-P6

F13 (цільова)

Після запуску Пошуку рішення введемо такі обмеження:

У вікні діалогу Пошуку рішення для діапазону змінних осередків вкажемо A6:Q6.

В результаті рішення отримаємо відповідь: ; потоки в дугах представлені нижче

Пункти (вузли)		Пункти (вузли)

Слід зазначити, що це завдання має єдине оптимальне рішення, тобто при максимальному потоці 17 одиниць може бути різне розподіл потоків по дугах.