Задача заключается в выборе такого распределения ресурсов по объектам, при котором минимизируется стоимость назначений. Предполагается, что каждый ресурс назначается ровно один раз и каждому объекту приписывается ровно один ресурс.
Возможные применения задачи о назначениях представлены в табл. 26.1.
Матрица стоимостей С имеет вид
Где Cij — затраты, связанные с назначением I-го ресурса на J-й объект, I = J = 
, где П — число объектов или ресурсов.
Обозначим:
Таким образом, решение задачи может быть записано в виде Х = (Xij).
Допустимое решение называется Назначением. Оно строится путем выбора ровно одного элемента в каждой строке матрицы X = (Xij) и ровно одного элемента в каждом столбце этой матрицы.
Элементы Cij матрицы С, соответствующие элементам Xij = 1 матрицы X, будем отмечать кружками:
Математическая постановка задачи:
При ограничениях:
