Венгерский метод решения задачи о назначениях

Венгерский  метод решения  задачи о назначениях 

Алгоритм:

1. В каждом столбце матрицы эффективности найти максимальный элемент и вычесть от него все остальные элементы столбца. В результате появится новая матрица, в каждом столбце которой хотя бы по одному нулю.
2. В каждой строке новой матрицы найти минимальный элемент и вычесть его из всех элементов соответствующей строки. В результате получим матрицу, в каждой строке которой хотя бы по одному нулю.
3. Находим строку или столбец, в котором расположено меньше всего нулей. Выделяем один из них звездочкой и зачеркиваем все нули, находящиеся с ним в одной строке или столбце. По такому же принципу отмечаем звездочкой другие нули. Если в результате в каждой строке и столбце окажется выделенный нуль, то задача решена. В этом случае переходим к п. 6 и записываем ответ.
4. Отмечаем столбцы, в которых находятся нули со звездочками. Затем просматриваем каждый невыделенный столбец, ищем в нем все нули и отмечаем соответствующие им строки. Если в отмеченной строке есть нуль со звездочкой, то убираем выделение столбца, в котором присутствует этот нуль. Так проделываем со всеми невыделенными столбцами.
5. Среди элементов невыделенных строк и столбцов ищем минимальный. Отнимаем этот элемент из всех невыделенных строк и прибавляем ко всем выделенным столбцам. Получим новую матрицу. Переходим к п. 3 предложенного алгоритма.
6. Ответ. Нулям со звездочками соответствует максимальная суммарная эффективность (производительность).

     Пример.

     Решить  задачу о назначениях при следующей матрице эффективности:

     Решение. 

     Шаг 1. (п.1)

     Шаг 2. (п. 2)

     Шаг 3. (п. 3)

     Шаг 4. (п. 4)

     Шаг 5. (п. 3)

      . 

     Шаг 6. (п. 6)

     Ответ: , .