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

(Задача выбора)

Постановка задачи. Пусть имеется n заказов с номерами и имеются n исполнителей с номерами , т.е. число заказов равно числу исполнителей. Любой заказ м.б. выполнен любым исполнителем., при этом стоимость выполнения i–того заказа j-тым исполнителем равна . Необходимо закрепить заказы за исполнителями так, чтобы все заказы были выполнены, у всех исполнителей был заказ, а суммарная стоимость выполнения заказов была бы минимальной.

Построим ММ задачи.

Пусть

Тогда модель задачи о назначениях запишется в виде:

(1)

(2)

(3)

(4)

Здесь целевая функция (1) выражает суммарную стоимость выполнения заказов, ограничения (2) требуют, чтобы у каждого заказа был исполнитель, а ограничения (3) – чтобы у каждого исполнителя был заказ.

Модель (1)-(4) относится к классу задач линейного целочисленного, а именно булевского, программирования. Решение такого класса задач является очень трудоемким и за приемлемое время можно получить решение лишь для задач небольшой размерности. Однако задача (1)-(4) имеет особенности, которые позволяют свести ее к КТЗ. Для этого условие (4) записывается условно как:

(5).

Тогда задача (1)-(3), (5) является частным случаем КТЗ при m=n, . Пусть эта задача решена методом потенциалов и получено решение . Будет ли это решение являться и решением исходной задачи (1)-(4)? ДА! На основании теоремы о целочисленности решения КТЗ значения целые. Они удовлетворяют ограничениям (2), (3). Но сумма неотрицательных целых чисел очевидно будет равна 1 только тогда, когда слагаемые равны 0 и 1, т.е. . Таким образом выполняется условие (4).

Если число заказов больше или меньше числа исполнителей, то вводят либо фиктивных исполнителей, либо фиктивные заказы.

Примечание. Таким образом, задачу о назначениях можно решить как КТЗ. Однако существуют специальные более эффективные методы. Один из таких алгоритмов известен под названием «Венгерский метод» (см. Таха Х. «Введение в ТПР»).