Метод потенциалов. 
Элементы линейного программирования

Значения переменных можно расставить произвольно, например, методом максимального элемента или методом Фогеля. Для вычисления потенциалов необходимо, чтобы число базисных переменных было равно. Поэтому в число базисных переменных введем базисных нулей. Последние должны быть расставлены так, чтобы базисные элементы матрицы X не образовывали циклов.

Вычисляются потенциалы, затем для небазисных пар индексов.

Определяются оценки по формуле:

г бвс.

Если все оценки неотрицательны (г), то процесс окончен: =1 соответствуют оптимальному варианту назначения. Если имеются отрицательные оценки (г < 0), необходимо выбрать разрешающую клетку (пусть она соответствует наименьшей отрицательной оценке), построить цикл пересчета, поставить в разрешающую клетку знак +, присвоить ей номер () и в дальнейшем разрешающую клетку считать четной вершиной, определить величину с и внести изменения в цикле: переменные которые находятся в нечетных вершинах, уменьшить на величину с, а переменные в четных вершинах увеличить на эту же величину.

Венгерский метод.

Пусть С =.

— матрица эффективностей задачи о назначениях. В соответствии с постановкой этой задачи, решить ее — значит, иными словами, выбрать в матрице C n элементов, по одному из каждой строки и каждого столбца так, чтобы сумма выбранных элементов, равная общей эффективности, соответствующей данному выбору, была наибольшей по сравнению с ее значениями при всех других таких выборах. Эту задачу можно свести к выбору n нулевых элементов по одному в каждом столбце и каждой строке, в некоторой матрице с неотрицательными элементами, у которой в каждой строке и каждом столбце есть нули.

Определение. Две матрицы C и D назовем здесь эквивалентными, если одна из них получается из другой прибавлением к элементам каждой строки одного и того же числа (для разных строк эти числа могут быть разными) и прибавлением к элементам каждого столбца одного и того же числа (для разных столбцов эти числа могут быть различны).