ЗАДАЧА О НАЗНАЧЕНИЯХ

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

Задачу о назначениях можно сформулировать следующим образом. Необходимо выполнить N различных работ. Для их выполнения можно привлечь N рабочих. Каждый рабочий за определенную плату готов выполнить любую работу. Выполнение любой работы следует поручить одному рабочему. Любой рабочий может выполнить только одну работу. Требуется так распределить работы между рабочими, чтобы общие затраты на выполнение всех работ были минимальными.

Задача о назначениях в стандартной форме. При рассмотрении задачи о назначениях в стандартной форме предполагается, что количество рабочих равно количеству работ.

Обозначения:

с_ij — показатель эффективности назначения i-го рабочего на j-ую работу, например издержки выполнения i-м рабочим j-й работы;

x_ij — переменная модели (х_ij = 1, если i-й рабочий используется на j-й работе, и x_ij = 0 в противном случае).

Модель задачи о назначениях:

(1)

(2а)

(2б)

(3)

Здесь (1) — целевая функция (минимум издержек на выполнение всех работ);

(2) — система ограничений, отражающая следующие условия:

а) каждая работа должна быть выполнена одним рабочим;

б) каждый рабочий может быть привлечен к одной работе;

(3) — условия двоичности переменных.

При решении задачи о назначениях исходной информацией является таблица задачи о назначениях с={с_ij}, элементами которой служат показатели эффективности назначений. Для задачи о назначениях, записанной в стандартной форме, количество строк этой таблицы совпадает с количеством столбцов:

Результатом решения задачи о назначениях (1)—(3) является вектор х*={ }, компоненты которого — целые числа.

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

В комбинаторной интерпретации задача о назначениях заключается в определении такой перестановки исполнителей {1,2,…,n}, которая обеспечивает минимальную суммарную стоимость назначений. Очевидно, что решение такой задачи может быть получено перебором, однако существует ряд эффективных алгоритмов.

Введем необходимые определения.

Матрицей весов (или матрицей назначений) называется матрица вида C = {c_ij}_n*n, где n – число вершин одной доли графа, в которой элементу c_ij присваивается значение веса соответствующего ребра двудольного графа.

Матрица C называется приведенной, если в каждом ее столбце и в каждой строке есть хотя бы один нуль.

Нулевые элементы матрицы C называются независимыми нулями, если для любого i, для которого выполняется условие 1<=i<=k, строка и столбец, на пересечении которых расположен элемент x_i, не содержит другие нули x_j для всех j k.

Для решения задачи о назначениях будем применять Венгерский алгоритм (алгоритм Куна) представленный в матричной форме.