Метод потенциалов

Если допустимое решение транспортной задачи Х = (ij), I – 1,2….m; j = 1,2….n; является оптимальным, то существуют потенциалы (числа) поставщиков u1, i = 1,2…..m и потребителей v1, j = 1,2…..n. удовлетворяющие следующим условиям.

Данная группа равенств используются для нахождения потенциалов.

Эта система уравнений имеет вид m + n неизвестных u1, I = 1,2…..m, j = 1,2….n;

Группа неравенств используются для проверки оптимальности опорного решения.

Эти неравенства удобнее представить в следующем виде.

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