zabika.ru 1

Алгоритм венгерского метода

Шаг 1. Проводим предварительные преобразования матрицы C (получаем эквивалентную матрицу).
Формулы предварительных преобразований:
1) Преобразование в столбцах:

2) Преобразование в строках:
Шаг 2. Рассматривая столбцы матрицы сверху вниз поочередно, помечают звездочками нули таким образом, чтобы они не лежали в одной строке или одном столбце (отмечается первый попавшийся [но в соответствии с алгоритмом] в столбце ноль). Если количество поставленных звездочек равно m, то оптимальное решение найдено, и процесс решения закончен.
Шаг 3.

а) столбцы, в которых есть нули со звездочками, помечают сверху знаком «+», и далее эти столбцы считают занятыми;

б) просматривая строки матрицы слева направо, ищут незанятые нули. Незанятый ноль помечается знаком штрих, строку, в которой он находится, справа помечают знаком «+», и далее эту строку считают занятой. Если в строке нуля со штрихом есть ноль со звездочкой, то снимают знак занятости «+» со столбца, где находится ноль со звездочкой. Если в строке 0’ нет нуля со звездочкой, переходят к шагу 5. Если в процессе поиска незанятых нулей оказалось, что незанятых нулей больше нет, а решение при этом не менялось, то переходят к шагу 4.
Шаг 4. Выбирается минимальный незанятый элемент (h). Число (h) вычитается из всех незанятых строк, и прибавляется ко всем занятым столбцам. Таким образом, получаем следующую эквивалентную матрицу. В новой матрице все пометки сохраняются. После этого повторяют выполнение шага 3 в части «б».

Шаг 5. Производим построение цепочки из нулей. Начиная от последнего отмеченного 0’, двигаясь по столбцу к 0*, далее по строке к 0’, и так далее, пока это возможно. Внутри цепочки знаки * снимаются, а вместо штрихов ставятся звездочки. После этого все знаки, кроме *, снимаются (штрихи, плюсы), и возвращаются к шагу 2.