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

В общем случае в данной задаче необходимо распределить среди работников работы таким образом, чтобы суммарные затраты на их выполнение были минимальными.

Пусть имеется n работ и n претендентов на их выполнение, которые могут выполнять любую из имеющихся работ. Известны затраты (производительность) c_i,j (q_i,j) на выполнение i-м работником j-й работы. Цель задачи – найти оптимальное распределение (с минимальными суммарными затратами или максимальной суммарной производительностью) работ среди работников.

Задачу о назначениях n работников на n работ удобно представлять в виде таблицы.

Данная задача имеет следующие ограничения:

- количество работ должно равняться количеству претендентов (равенство можно достичь введением в модель либо фиктивной работы, либо фиктивного работника);

- каждый работник должен быть назначен только на одну работу;

- на каждую работу следует назначить только одного претендента.

Построим математическую модель задачи.

Введем переменные х_i,j:

1, если i-й работник назначен на j-ю работу,

х_i,j =

0, если i-й работник не назначается на j-ю работу.

Требуется минимизировать (максимизировать) выражение

при соблюдении условий

, i = 1, 2, …, n;

, j = 1, 2,..., n.

Данные условия означают, что каждый претендент назначается только на одну работу, а на каждую работу назначается только один работник. Таким образом, матрица X = (х_i,j) назначений – допустимое решение задачи – содержит в каждом столбце и в каждой строке ровно по одной единице, все остальные элементы матрицы – нули.

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

Не нашли, что искали? Воспользуйтесь поиском: