Венгерский алгоритм

1.В каждой строке матрицы T находим минимальный элемент и уменьшаем элементы строки на его величину. Получаем матрицу T1.

2.В каждом столбце матрицы T1

находим минимальный элемент и уменьшаем на его величину элементы столбца. Получаем матрицу T2.

11

3. Вычеркиваем все нули матрицы T2

минимально возможным числом линий

(вертикальных и/или горизонтальных). Если количество вычеркивающих линий совпадает с размерностью матрицы, то среди нулей матрицы находим n линейно независимых. Позиции этих определяют решение.

В противном случае, если количество вычеркивающих линий не совпадает с

размерностью матрицы, – шаг 4.

12

4.В матрице имеются элементы:

невычеркнутые, вычеркнутые и перечеркнутые.

Среди невычеркнутых находим минимальный элемент. Обозначим его f.

Элементы

невычеркнутые – уменьшаем на f;

вычеркнутые – оставляем без изменения; перечеркнутые – увеличиваем на f.

5.Переходим к шагу 3.

13