А лгоритм решения:

1) из всех элементов каждой строки и каждого столбца матрицы C= c_ij вычитаем наименьший элемент соответствующей строки p_i (или столбца q_j).

2) проводим поиск допустимого решения, единичные элементы которого соответствуют нулевым коэффициентам модифицированной матрицы.

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

Если такое допустимое решение существует, то оно оптимальное, в противном случае матрица C модифицируется еще один раз, но уже другим способом.

Алгоритм состоит из трех шагов:

1) редукция (сокращение) строк и столбцов

2) попытка определения назначения

3) модификация редуцированной матрицы

Шаг 1. Цель шага – получить максимально возможное число нулей в матрице C путем вычитания из элементов каждой строки и каждого столбца наименьших элементов соответствующих строк и столбцов.

Шаг 2. Если после редукции можно выбрать в каждой строке и в каждом столбце по одному нулевому элементу так, что соответствующее этим элементам решение будет допустимым, то данное назначение оптимальное. Если нет, то переходим к шагу 3.

Шаг 3. Если нулевых элементов недостаточно, то получить необходжимые новые нулевые элементы можно следующим образом. Для этого определим минимальное множество строк и столбцов редуцированной матрицы, содержащей все нулевые элементы, и найдем минимальный элемент матрицы вне множества элементов, составляющих совокупность выбранных строк и столбцов. Если значение найденного элемента вычесть из других элементов матрицы C, то получим отрицательные величины, и по крайней мере один элемент, не принадлежащий множеству элементов, входящих в выделенные строки и столбцы, будет равен 0.

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

Пример:

q₃=2

(1,1) (2,3) (3,2) – оптимальное назначение.

На самом деле стоимость будет равна Z = p₁+p₂+p₃+q₃

Но, к сожалению, не всегда удается определить допустимое назначение таким образом. Поэтому рассмотрим следующий пример:

Оптимальное назначение: (1, 1) (2, 3) (3, 2) (4, 4)

53