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

Матричная формулировка задачи

Задача о назначениях может быть сформулирована следующим образом: необходимо наилучшим образом назначить N работников { C₁, C₂,, C_N } на N работ {B_1, B_2,, B_N }. Наилучшим назначением считается такое, которое обеспечивает максимальную выработку суммарной продукции (или минимальные затраты). Необходимая информация для решения задачи о назначениях содержится в квадратной матрице производительностей А={a_ij}, где a_ij – производительность i-го работника (машины) при выполнении j-ой работы. В случае минимизации затрат коэффициент a_ij означает затраты при выполнении i-ым работником (машиной) j-ой работы.

Должно выполняться дополнительное условие: на каждую работу назначается только один работник и все работы должны быть выполнены.