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

Рассмотрим ситуацию, когда требуется распределить m работ (или исполнителей) по n станкам. Работа i (i = 1, ..., m), выполняемая на станке j (j = 1, ..., n), связана с затратами c_ij. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат.

Эту задачу можно рассматривать как частный случай транспортной задачи. Здесь работы представляют «исходные пункты», а станки – «пункты назначения». Предложение в каждом исходном пункте равно 1, т.е. a_i = 1 для всех i. Аналогично спрос в каждом пункте назначения равен 1, т.е. b_j = 1 для всех j. Стоимость «перевозки» (прикрепления) работы i к станку j равна c_ij. Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость c_ij берется равной очень большому числу. Матрица стоимостей C определяется следующим образом:

станки

виды работ

Прежде чем решать такую задачу, необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m = n.

Пусть x_ij = 0, если j-я работа не выполняется на i-м станке,

x_ij = 1, если j-я работа выполняется на i-м станке.

Таким образом, решение задачи может быть записано в виде двумерного массива X = (x_ij). Допустимое решение называется назначением. Допустимое решение строится путем выбора одного элемента в каждой строке матрицы X = (x_ij) и одного элемента в каждом столбце этой матрицы. Для заданного значения n существует n! допустимых решений.

Теперь задача будет формулироваться следующим образом:

;

;

;

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

Для иллюстрации задачи о назначениях рассмотрим таблицу с тремя работами и тремя станками.

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

Примечание. Оптимальное решение задачи не изменится, если из любой строки или столбца матрицы стоимостей вычесть произвольную постоянную величину.

Приведенное замечание показывает, что если можно построить новую матрицу с нулевыми элементами и эти нулевые элементы или их подмножество соответствуют допустимому решению, то такое решение будет оптимальным:

С Þ Þ = .

0 0 2

Оптимальное назначение:

остальные ,

5 + 12 + 13 = 30.

К сожалению, не всегда удается определить решение так просто.