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

Имеется n работников, которых требуется назначить на n работ. Известно, что j-ю работу i-й работник будет выполнять с эффективностью c_ij. Требуется так распределить работников, чтобы максимизировать суммарную эффективность.

Положим x_ij=1, если i-й работник назначен на j-ю работу;

x_ij=0, в противном случае, i, j= .

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

® max.

ЦФ представляет суммарную эффективность.

Ограничения имеют вид:

, j= , (1)

, i= , (2)

x_ij равно либо 0, либо 1.

Условия (1) означают, что каждый работник назначается только на одну работу.

Условия (2) означают, что один работник выполняет только одну работу.

Данная задача является задачей линейного булева программирования.

Дата добавления: 2015-07-14