Метод потенциалов для оценки Δij в т-задаче

Свойство цикла: всякий цикл содержит пару загруженных клеток какой-либо строки или столбца матрицы ||х_ij|| с противоположными знаками. Отсюда следует, что изменение элементов строки или столбца матрицы стоимостей на любое число не меняет оценки Δ_ij свободной клетки, так как разности при этом сохраняются. Это значит, что сохраняются и назначения, т.е. решение задачи не меняется.

Пусть план поставок задан, т.е. фиксированы назначения.

Определение. Числа, прибавляемые к элементам строк и столбцов матрицы стоимостей так, что стоимости в загруженных клетках оказываются равными нулю, называются потенциалами строк и столбцов.

Лемма 3. Первый потенциал (любой) может быть задан произвольно (например, равным нулю). Остальные определяются однозначно.

Лемма 4. Оценка свободной клетки Δ_ij определяется как сумма ее стоимости и потенциалов и не зависит от способа выбора потенциалов.

Пример. Для прежних исходных данных построим опорный план «по минимальному элементу». Суть метода в том, что в качестве очередной загружаемой клетки матрицы ||х_ij|| выбирается клетка с минимальной стоимостью в образовавшейся прямоугольной подматрице матрицы ||с_ij||. В результате получим план:

На матрице стоимостей ||с_ij|| строим потенциалы (см. определение и лемму 3) для загруженных клеток:

Определяем оценки (см. лемму 4) для незагруженных (свободных) клеток:

Заключение. Все Δ_ij > 0, следовательно, план оптимальный.