13.3.2. Особые случаи задачи о назначениях
МАКСИМИЗАЦИЯ ЦЕЛЕВОЙ ФУНКЦИИ
Алгоритм решения задачи о назначениях предполагает минимизацию ее целевой функции. Если имеется задача о назначениях, целевую функцию которой нужно максимизировать, то поступают таким же образом, как и в алгоритме решения транспортной задачи: после окончания формирования первой таблицы все ее элементы умножаются на 
Пример 13.8. В распоряжении некоторой компании имеется 6 торговых точек и 6 продавцов. Из прошлого опыта известно, что эффективность работы продавцов в различных торговых точках неодинакова. Коммерческий директор компании произвел оценку деятельности каждого продавца в каждой торговой точке. Результаты этой оценки представлены в табл. 13.38.
Таблица 13.38. Объемы продаж в различных торговых точках для различных продавцов
Как коммерческий директор должен осуществить назначение продавцов по торговым точкам, чтобы достичь максимального объема продаж?
Решение.
Все элементы исходной таблицы умножаются на 
Таблица 13.39. Модификация исходных данных и выявление минимальных элементов
Минимальный (наибольший по абсолютной величине) элемент вычитается из всех элементов соответствующей строки.
Таблица 13.40. Вычитание минимального элемента по строкам и выявление минимальных элементов по столбцам
Минимальный элемент вычитается из всех элементов соответствующего столбца.
Таблица 13.41. Вычитание минимального элемента по столбцам
Дальнейший поиск оптимального решения осуществляется в соответствии с обычным алгоритмом (см. пример 13.9).
НЕДОПУСТИМЫЕ НАЗНАЧЕНИЯ
Данную проблему можно решить так же, как и транспортную задачу. Если по той или иной причине некоторое назначение является недопустимым, то в соответствующей клетке проставляется значение стоимости, которое заведомо больше любого другого значения. После этого в ходе реализации алгоритма мы сможем избежать данного назначения автоматически.
НЕСООТВЕТСТВИЕ ЧИСЛА ПУНКТОВ ПРОИЗВОДСТВА И НАЗНАЧЕНИЯ
Если исходная таблица не является квадратной, в нее следует включить дополнительные фиктивные строки и столбцы, необходимые для приведения ее к квадратной форме. Значения стоимости, соответствующие фиктивным клеткам, как правило, равны нулю.
Назначения, размещаемые в клетках фиктивных строк, фактически не существуют. Назначения, соответствующие фиктивным столбцам, на деле представляют собой те единицы, которые не подлежат распределению.
