Эквивалентное преобразование, идея метода

Теорема: две задачи оптимизации эквивалентны, если у них одинаковые планы.

Теорема. Прибавление к элементам некоторой строки матрицы С, либо ко всем элементам столбца константы есть преобразование эквивалентное.

Доказательство. Прибавим к элементам i -ой строки константу d_i, а к элементам j -ого столбца константу l_j. В результате получим задачу о назначении с матрицей С^k, у которой .

Посчитаем целевую функцию:

Так как константа не влияет на оптимальный план, то обе задачи эквивалентны.