Модификации задачи о назначениях

1. В ряде случаев представляется целесообразным решать задачу о назначениях не на максимум суммы n независимых элементов, а на ее минимум. В этом случае алгоритм венгерского метода отличается только подготовительным этапом. Для решения задачи на минимум достаточно в квадратной матрице производительностей A = {d_ij} заменить у элементов d_ij знаки на обратные, т.е. матрица будет иметь вид A = {-d_ij}. В остальном алгоритм остается без изменения. Поэтому от задачи максимизации всегда можно перейти к задаче минимизации.

2. Иногда в задаче о назначении матрица эффективностей не является квадратной: число исполнителей m не равно числу работ n. Допустим, m>n. Построим тогда квадратную матрицу эффективностей введением (m-n) фиктивных работ, которые выполняются всеми лицами с одинаковой эффективностью, равной нулю. Решение видоизмененной задачи дает некоторое решение исходной задачи. Лицо, назначенное на фиктивную работу, остается без назначения.

В случае m<n достраиваем матрицу эффективностей до квадратной введением (n-m) фиктивных исполнителей, имеющих нулевую эффективность на всех работах. Матрица эффективностей становится квадратной.

3. В ряде случаев допускается, чтобы i-исполнитель (например, узел связи c_i) мог выполнять две работы (например, обслуживать два населенных пункта из множества населенных пунктов B_i, i = 1,n). Для решения этой задачи условно представим i-исполнитель в виде двух самостоятельных исполнителей А_i^’ и A_i^”. Исходные данные для исполнителей А_i^’ и A_i^” должны быть одинаковы с данными для исполнителей A_i. В этом случае формально происходит увеличение числа исполнителей и может потребоваться увеличение числа фиктивных работ. Изложенный подход позволяет существенно расширять возможности практического использования задачи о назначениях.

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

Задача о наименьшем покрытии