льний повторюваний крок
Загальний крок виконується в такій послідовності.
1. З позитивних різниць d ij знаходимо найбільшу різницю d i0j0 :
d iojo = mах (v j - u i - a ij > 0).
Нехай цей максимум має місце для клітини ( i 0 , j 0 ). Включаємо цю клітку в набір Х -відмічених ( k + l - 1) клітин. Клітин стає ( k + l ), а для такої їх кількості завжди можна побудувати цикл. Цей цикл буде в даній ситуації єдиним.
Дійсно, набір Х -відмічених клітин є ациклічним. Додамо до нього одну клітку і припустимо, що для неї можна побудувати два циклу. У цьому випадку завжди можна виділити цикл з вершинами, належними початкового набору, що суперечить умові його ациклічності. Тому такий цикл існує тільки один і завдання полягає в його виділенні.
2. Означивающей цикл, тобто розставляємо знаки в його вершинах. У вихідній клітці (включається в набір) ставимо плюс. Рухаємося по ходу або проти ходу годинникової стрілки і ставимо знаки поперемінно мінус, плюс, - Поки не прийдемо до вихідної вершині. Оскільки кількість вершин у циклі парне, напрямок руху байдуже. В результаті отримаємо так званий окреслений цикл, клітини якого діляться порівну на клітини позитивної полуцепі і клітини негативною полуцепі.
3. Вибираємо найменше значення перевезення в клітинах негативною полуцепі ( x ij ) - . Нехай воно одно Q:
В
min ( x ij ) - = Q.
Якщо таких значень декілька, беремо одне з них, байдуже яке.
4. З перевезень кожної клітини негативною полуцепі віднімаємо Q, а до перевезень кожної клітини позитивної полуцепі додаємо Q. Ця операція називається зрушенням по циклу на величину Q.
Процес зсуву змінює план, але план залишається допустимим.
Дійсно, допустимий план забезпечує баланс в рядках і стовпцях; всякий план, що не порушує цей баланс, буде допустимим. Будь-який цикл, за яким здійснюється зсув, містить в кожному ряду (рядку, стовпці) по дві вершини. В одну клітку додаємо Q, а з іншої віднімаємо Q, і баланс не порушується. Отже, план, знайдений в результаті зсуву, залишиться допустимим. p> Після зсуву в клітці негативною полуцепі з мінімальною перевезенням стоятиме нуль, а в клітці ( i 0 , j 0 ), включеної в набір, виявиться число Q. Першу клітку з плану виключаємо, а другу включаємо; план залишається як і раніше ациклічним, так як єдиний наявний цикл порушується винятком клітини.
Отриманий після зсуву план можна записати наступним чином:
В
5. для отриманого після зсуву плану складаємо нову систему потенціалів. Ці нові потенціали можна обчислити так само, як це робилося в попередньому кроці, а можна знайти виправленням вже наявної системи....
