Алгоритм методу Мака

1.Позначаємо мінімальний елемент рядка позначкою *. Якщо мінімальних елементів декілька, позначаємо будь-який з них.

2.Дії п. 1 повторюємо для всіх рядків матриці витрат.

3.Якщо рядок має ще один мінімальний елемент, проглядаємо стовпець, до якого цей елемент належить. Можливі випадки:

i) стовпець не має позначених елементів;

ii) стовпець має принаймні один позначений елемент.

4.У випадку i) позначаємо мінімальний елемент рядка позначкою *. Всі інші позначки в цьому рядку знімаються.

У випадку ii) позначаємо мінімальний елемент рядка позначкою ^, якщо елемент цього рядка з позначкою * не є єдиним позначеним елементом у своєму стовпцi.

5.Дії п.п. 3 та 4 повторюємо послідовно для всіх рядків, що мають більше одного мінімального елемента.

6.Якщо кожний стовпець матриці витрат має елемент з позначкою *, тоді задача про оптимальні призначення розв’язана. Iнакше переходимо до наступного пункту.

7.Позначаємо (позначкою &) стовпцi, що мають більше одного позначеного елемента. Вони утворюють множину В, інші стовпцi матриці витрат утворюють множину A.

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

9.Знаходимо для рядка мінімальну різницю між елементами множини A i елементом з позначкою *.

10.Дії п.п. 8 та 9 повторюємо послідовно для всіх рядків, що мають властивості, які вказані в п. 8.

11.Вибираємо найменшу з мінімальних різниць.

12.Додаємо це число до кожного елемента множини В.

13.Повертаємось до п. 3.

Зауваження до методу Мака аналогічні угорському методу.

Задача про максимальний потік.Метод Форда-Фалкерсона

Постановка задачі про максимальний потік в мережі. В мережі, що задається графом (I, U), де I – множина вершин, U – множина дуг з визначеною на ній функцією пропускних здатностей r_ij ((i,j) – дуга з U), зафіксовані дві вершини – i₁ та i_n.

Вершина i₁ (джерело) має інтенсивність d, вершина i_n (стік) – інтенсивність – d, всі інші вершини нейтральні. Треба знайти максимальну інтенсивність джерела d, при якій мережа допускає потік. Потiк, що відповідає такому максимальному значенню інтенсивності d*, називається максимальним потоком, а саме значення d* – величиною цього потоку.

Алгоритм Форда-Фалкерсона застосовується для побудови максимального потоку в мережі із заданої початкової вершини-джерела в задану кінцеву вершину-стiк.

Будемо вважати, що вершиною-джерелом є 1 -а вершина, вершиною-стоком – вершина з номером n.