Способ задания задачи о назначениях и ее анализ
Как видно из математической модели (1)-(4) задача о назначениях является транспортной задачей с квадратной матрицей 
, в которой для всех i и j, 
, поэтому, чтобы задать задачу о назначениях достаточно только задать квадратную матрицу С.
Заметим, что задача о назначениях является транспортной задачей, если ограничение (2) заменить ограничением 
. Возникает вопрос, если исправленную задачу решить методом потенциалов, то будет ли решение удовлетворять ограничению (2).
Однако известно, что транспортная задача с целыми правыми частями имеет целочисленное решение. Правые части задачи о назначениях равны единице, то есть целые числа, значит и все 
также целые числа, при этом из (2)-(3) следует, что все 
, следовательно, они могут принимать значения только ноль и единица.
Отсюда любое допустимое решение задачи о назначениях может быть представлено в виде квадратной матрицы Х, в которой в каждом столбце и каждой строке имеется по одной единице. Все остальные элементы матрицы равны нулю. Например, матрица Х может иметь вид (рис. 1).
| Х= | ||||
Рис. 1.
То есть матрица Х имеет ровно n ненулевых элементов. Если решать задачу методом потенциалов, то базисное решение х должно иметь (2n-1) базисную компоненту и так как число единиц равно n, то базисное решение должно быть дополнено (n-1) нулем. Отсюда следует, что базисное решение является сильно вырожденным, а это является существенной помехой для использования метода потенциалов ( 
часто будет равно нулю). Поэтому для решения задачи о назначениях может быть предложен другой метод, существенно использующий тот факт, что ненулевые компоненты решения равны единице. В этом случае матрицу Х можно вообще не задавать, а на матрице С пометить (крышкой) элементы, которым соответствуют единичные компоненты матрицы Х. Тогда значение целевой функции будет равно
.
Рассмотрим свойства матрицы С.
Свойство 1. Если из всех элементов одной строки или одного столбца матрицы С вычесть одно и тоже число 
, то оптимальное решение новой задачи будет совпадать с оптимальным решением исходной задачи, а оптимальное значение целевой функции новой задачи уменьшится по сравнению с оптимальным значением целевой функции исходной задачи на величину :
.
Доказательство Св.1: Так как в задаче меняется только целевая функция, то допустимое множество исходной и новой задачи одинаково.
Пусть число вычитается из первой строки матрицы С:
.
Свойство 2. Без ограничения общности мы можем считать, что 
.
Доказательство Св.2: Если в матрице С существует 
, то к строке 
можно прибавить , тогда , а все остальные элементы этой строки увеличатся на . Таким образам можно убрать все отрицательные элементы.
Свойство 3. Пусть все и существуют 
, тогда, если удается найти допустимое решение 
такое, что все 
соответствуют , то полученное допустимое решение оптимально.
Доказательство Св.3: Из формулы (4) следует, что если все и х – допустимое решение, то для любого допустимого решения х 
, но 
, то есть - оптимальное решение.
Определение 1. Пусть все элементы матрицы С больше или равны нулю и существуют . Нули матрицы С называются независимыми, если они стоят в разных строках и столбцах матрицы С.
Так как любое допустимое решение задачи о назначениях имеет n единиц, стоящих в разных строках и столбцах, то, как следует из Свойства 3, для того, чтобы могло быть найдено оптимальное решение задачи о назначениях, надо чтобы матрица С имела n независимых нулей. Отсюда следует, что для нахождения оптимального решения необходимо воспользовавшись Свойством 1, путем вычитания из строк и столбцов некоторых чисел, получить новую матрицу С, имеющую n независимых нулей. Этот метод называется Венгерским методом.