Задача о назначениях

области математической оптимизации или исследовании операций. Задача состоит в поиске

минимальной суммы дуг во взвешенном двудольном графе.

В наиболее общей форме задача формулируется следующим образом:

Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.

Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях. Обычно, если говорят о задаче о назначениях без дополнительных условий, имеют в виду линейную задачу о назначениях.

A .
( 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).

2 задание, второму – 1 задание, третьему – 3 задание,

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

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

должен назначить рабочих для выполнения различных производственных операций, распределить ряд

производственных заданий по различным машинам (которые могут эти задания выполнить с различной эффективностью) или решить, какого торгового агента в какую область послать для продвижения продукции фирмы. Это распределение или назначение должно быть сделано из соображений либо наибольшей эффективности, либо наименьших затрат.
 
Задача детектирования движущихся объектов по снимкам: было произведено два снимка, по итогам которых было получено два набор координат. Требуется соотнести объекты на первом и втором снимке, т.е. определить для каждой точки второго снимка, какой точке первого снимка она соответствовала. При этом требуется минимизировать сумму расстояний между сопоставленными точками (т.е. мы ищем решение, в котором объекты суммарно прошли наименьший путь).

Раскраска дерева. Дано дерево, в котором каждая вершина, кроме листьев, имеет ровно сыновей. Требуется выбрать для каждой вершины некоторый цвет из цветов так, чтобы никакие две смежные вершины не имели одинакового цвета. Кроме того, для каждой вершины и каждого цвета известна стоимость покраски этой вершины в этот цвет, и требуется минимизировать суммарную стоимость.