Завдання про максимальний потік (в мережевий постановці)

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

Розглянемо транспортну мережу, що має один пункт виробництва , один пункт споживання і N - 2 перевалочних пунктів. Назвемо потоком з пункту в пункт систему перевезень, що задовольняє наступним умовам:

(4.24)

(4.25)

(4.26)

Величину р назвемо величиною потоку. Ця величина показує, скільки продукту вивозиться з пункту , званого джерелом. Оскільки для всіх перевалочних пунктів існує баланс між кількістю ввезеного і кількістю вивозиться продукту (4.25), то ясно, що весь продукт, що вивозиться з пункту , повинен прибути в пункт , що легко показати і аналітично. Для цього позначимо кількість продукту, що вивозиться з пункту , через . Воно визначається співвідношенням

(4.27)

Складемо останню рівність з усіма равенствами (4.25) і (4.26). Неважко бачити, що ліва частина отриманого рівності звертається в нуль, так як для будь-якого числа , що стоїть зі знаком "плюс", знайдеться це ж число, яке стоїть зі знаком "мінус". Дійсно, будь-яка комунікація виходить рівно з одного пункту і входить рівно в один пункт . Тому одне з рівності (4.25) або (4.26), відповідне пункту , містить в лівій частині доданок , а інше, відповідне пункту , - від'ємник . Таким чином, приходимо до співвідношення

Отже, з пункту вивозиться негативне кількість одиниць продукту (-р), а це і означає, що в нього ввозиться р одиниць, що і стверджувалося.

Пункт P N носить назву "стік".

Завданням про максимальний потік називається задача відшукання потоку найбільшої величини з пункту в пункт або, що те ж саме, завдання знаходження максимуму лінійної функції (4.26) при лінійних обмеженнях (4.25) і (4.24).

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

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

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

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

В цьому випадку під потоком розуміється система перевезень, що задовольняє наступним умовам:

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

Метод рішення задачі про максимальний потік розроблений американськими математиками Фордом і Фулкерсоном [11, 36, 38, 39].