Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4).
Алгоритм метода Мака.
1. Помечаем минимальный элемент строки отметкой *. Если минимальных элементов несколько, помечаем любой из них.
2. Действия п. 1 повторяем для всех строк матрицы расходов.
3. Если строка имеет еще один минимальный элемент, просматриваем столбец, к которому этот элемент принадлежит. Возможные случаи:
i) Столбец не имеет обозначенных элементов;
ii) Столбец имеет по крайней мере один обозначенный элемент.
4. В случае i) помечаем минимальный элемент строки отметкой *. Все другие отметки в этой строке снимаются. В случае ii) помечаем минимальный элемент строки отметкой ^, если элемент этой строки с отметкой * не является единственным обозначенным элементом в своем столбце.
5. Действия п.п. 3 и 4 повторяем последовательно для всех строк, которые имеют больше одного минимального элемента.