16. Задача о назначениях, особые случаи задачи о назначениях.

Задача о назначениях – одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.

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

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

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

Особые случаи задачи о назначениях

МАКСИМИЗАЦИЯ ЦЕЛЕВОЙ ФУНКЦИИ

Алгоритм решения задачи о назначениях предполагает минимизацию ее целевой функции. Если имеется задача о назначениях, целевую функцию которой нужно максимизировать, то поступают таким же образом, как и в алгоритме решения транспортной задачи: после

окончания формирования первой таблицы все ее элементы умножаются на 

Пример 13.8. В распоряжении некоторой компании имеется 6 торговых точек и 6 продавцов. Из прошлого опыта известно, что эффективность работы продавцов в различных торговых точках неодинакова. Коммерческий директор компании произвел оценку деятельности каждого продавца в каждой торговой точке. Результаты этой оценки представлены в табл. 13.38.

Таблица 13.38. Объемы продаж в различных торговых точках для различных продавцов

Как коммерческий директор должен осуществить назначение продавцов по торговым точкам, чтобы достичь максимального объема продаж?

Решение.

Все элементы исходной таблицы умножаются на 

Таблица 13.39. Модификация исходных данных и выявление минимальных элементов

Минимальный (наибольший по абсолютной величине) элемент вычитается из всех элементов соответствующей строки.

Таблица 13.40. Вычитание минимального элемента по строкам и выявление минимальных элементов по столбцам

Минимальный элемент вычитается из всех элементов соответствующего столбца.

Таблица 13.41. Вычитание минимального элемента по столбцам

Дальнейший поиск оптимального решения осуществляется в соответствии с обычным алгоритмом (см. пример 13.9).