Кінцевий пункт
Рис. 3.5. Приклад задачі про максимальний потік
У вихідному рішенні величина потоку в мережі дорівнює двом одиницям. Існує кілька варіантів реалізації розглянутого алгоритму. Простежте за ходом варіанта, що нижче викладається, роблячи легкі позначки олівцем на рисунку.
1)
Переглянути
вузол
0: поставити знак + на дугах (0, 4) і (0, 5) і
позначити вузли 4 і 5 знаком
.
Поставити знак
біля вузла 0.
2) Переглянути вузол 5: поставити знак – на дузі (3, 5) і позначити вузол 1 знаком . Поставити знак біля вузла 5.
3) Переглянути вузол 3: поставити знак – на дузі (1, 3) і позначити вузол 3 знаком . Поставити знак біля вузла 3.
4) Переглянути вузол 1: поставити знак + на дузі (1, 2) і позначити вузол 2 знаком . Поставити знак біля вузла 1.
5) Переглянути вузол 2: поставити знак + на дузі (2, 6) і позначити вузол 6 знаком . Шлях, що збільшує потік, виявлений.
Читачеві пропонується зіставити отримані результати з рис. 3.6. Таким чином, рішення поліпшується, якщо:
1) додати одиничний потік по дугах (2, 6) і (1, 2);
2) зменшити на одиницю потік по дугах (1, 3) і (3, 5);
3) додати одиничний потік по дузі (0, 5).
Нове рішення приведене на рис. 3.7. Повторивши всі кроки алгоритму, покажіть, що тепер потік максимальний. Послідовність вузлів, що перегля-даються, включає вузли 0, 4 і 5. Жоден інший вузол позначити вже неможливо.
Джерело
Потік
= 2
Одна
одиниця:
Одна
одиниця:
Рис. 3.6. Процес перегляду мережі
Потік
= 3
Одна
одиниця:
Одна
одиниця:
Одна
одиниця:
Рис. 3.7. Рішення задачі про максимальний потік
Щоб зняти обмеження (3.7) на пропускну здатність дуг, в алгоритм вносяться наступні зміни. При перегляді мережі на кожній вихідній ненасиченій дузі, тобто дузі, пропускна здатність якої перевищує величину дугового потоку, ставиться знак +. Надалі, коли шлях, що збільшує потік, виявляється, цим шляхом направляється максимально припустимий потік з урахуванням величини недовикористаної пропускної здатності кожної дуги, позначеної знаком +, і поточної величини дугових потоків по кожній дузі, позначеної знаком –. Таким чином, при рішенні задачі про максимальний потік (3.12) – (3.16) робота алгоритму закінчується у відповідності з наступним правилом останова.
Правило останова. Потік по дузі, що виходить з переглянутого вузла і входить у позначений вузол, дорівнює її пропускній здатності, а потік по дузі, що виходить з непоміченого вузла і входить у переглянутий вузол, дорівнює нулю.
На кожній ітерації виконання кроку 3 приводить або до збільшення потоку в мережі на одну або більше одиниць, або до останову. Внаслідок цього алгоритм сходиться за кінцеве число ітерацій, тому що максимальний допустимий потік обмежений зверху. Тепер залишається тільки показати, що при завершенні симплекс-процедури рішення дійсно є оптимальним. З цією метою розіб’ємо усі вузли мережі на дві непересічні підмножини, наприклад, С0 і Сp+1. Вузол 0 включимо в підмножину С0, а вузол – у підмножину Сp+1. Така розбивка називається розрізом. Пропускну здатність розрізу визначимо як суму пропускних здатностей uij усіх дуг, таких, що вузол i належить підмножині С0, вузол j – підмножині Cp+1.
Пропускна здатність розрізу при будь-якій розбивці вузлів на зазначені підмножини визначає верхню границю максимально можливої величини потоку в мережі. (Якщо пропускна здатність розрізу дорівнює нулеві, то вузол 0 у буквальному значенні відділений від вузла і потік з джерела на вихід виявляється неможливим.) Отже, якщо припустимий потік дорівнює пропускної здатності будь-якого розрізу, то він повинний бути оптимальним. Крім того, у силу обмежень (3.13), (3.14) і (3.15), що визначає умови збереження потоку, значення F у будь-якому припустимому рішенні повинне бути дорівнює сумі потоків по всіх дугах (i, j) мінус сума всіх потоків по дугах (j, i), де вузол i утримується в підмножині С0, вузол j – у підмножині Сp+1.
З огляду на всі ці зауваження, легко довести оптимальність. Розглянемо деяке допустиме рішення при зупинці алгоритму. Визначимо С0 як підмножина всіх переглянутих вузлів, а Cp+1 як підмножину всіх інших вузлів. Відповідно до правила останова потік з будь-якого вузла, що належить підмножині Cp+1, у будь-який вузол, що належить підмножині С0, дорівнює нулю. Тому загальна величина потоку в мережі дорівнює сумі потоків по всіх дугах, що виходять з підмножини С0 і входять у підмножину Cp+1. Усім цим дугам відповідають потоки, що дорівнюють їх пропускним здатностям. Отже, загальна величина потоку в знайденому рішенні дорівнює пропускної здатності розрізу, і подальше збільшення потоку виявляється вже неможливим.
Приведені міркування резюмуються у виді наступної важливої теореми.
Теорема про максимальний потік / мінімальний розріз.
Максимальна величина потоку F у будь-якій мережі при умовах (3.13) – (3.16) дорівнює мінімальній пропускній здатності розрізу, що відокремлює джерело від виходу.
З цієї теореми походить, що алгоритм дає цілочисельні значення усіх величин хij.