Задача о назначениях. Алгоритмы

математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.
В наиболее общей форме задача формулируется следующим образом:
Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.
Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях. Обычно, если говорят о задаче о назначениях без дополнительных условий, имеют в виду линейную задачу о назначениях.

.
( 2 4 1 3 3)
( 1 5 4 1 2 )
A = ( 3 5 2 2 4 )
( 1 4 3 1 4 )
( 3 2 5 3 5 )
РЕШЕНИЕ. Поскольку не указано, будем решать задачу на минимум (стандартная постановка). Решение будем искать венгерским методом.
Составляем исходную таблицу (матрицу):

таблице) и отнимаем от всех элементов строки. Получим:

Теперь проводим аналогичную процедуру для всех столбцов: ищем наименьший элемент по столбцу и отнимаем его из всех элементов столбца. Получим:

стоимостью.
Этап 2. Выбираем строку с одним нулем (строка №1), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №3).
Выбираем строку с одним нулевым значением (строка №5), выделяем нуль.
Выбираем строку с одним нулем (строка №3), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №4).
Выбираем строку с одним нулем (строка №4), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №1). Выбираем строку с одним нулевым значением (строка №2), выделяем нуль.

Получаем оптимальную матрицу назначений:

Минимальное значение целевой функции: 1+2+2+1+2=8.

Карп (а также Томидзава независимо от них) показали, что его можно модифицировать так, чтобы достичь времени выполнения O(n^3).

задание, второму – 1 задание, третьему – 3 задание, четвертому – 4 задание. Стоимость работы составит 13 единиц.

Метод исчерпывающего перебора