Метод потенциалов решения транспортной задачи

Для транспортной задачи (ТЗ), как и для любой ЗЛП, существует двойственная к ней задача.

Исходная задача:

; (6.6)

; (6.7)

; (6.8)

. (6.9)

Обозначим двойственные переменные для каждого ограничения вида (6.7) через U_i (i = 1,...,m) и вида (6.8) – V_j (j = 1,...,n), тогда двойственная задача имеет вид

; (6.10)

. (6.11)

Переменные задачи, двойственной к транспортнoй, U_i и V_j называют потенциалами.

Теорема 3. Для оптимальности плана X = (X_ij)_m*n ТЗ необходимо и достаточно существования чисел (потенциалов) V₁, V₂,..., V_n и U₁, U₂,..., U_m, таких, что:

для i = 1,...,m, j = 1,..., n,;

, если X_ij>0.

Из теоремы следует: для того чтобы опорный план был оптимальным, необходимо выполнение следующих условий:

а) для каждой занятой клетки (отличного от нуля элемента матрицы Х) сумма потенциалов должна быть равна стоимости перевозки единицы груза

; (6.12)

б) для каждой незанятой клетки (X_ij = 0) сумма потенциалов должна быть меньше или равна стоимости перевозки единицы груза

. (6.13)

Таким образом, для проверки плана на оптимальность необходимо сначала построить систему потенциалов. Для построения системы потенциалов используем условие

, X_ij>0.

Систему потенциалов можно построить только для невырожденного опорного плана. Такой план содержит m + n – 1 занятых клеток, поэтому для него можно составить систему из m + n – 1 линейно-независимых уравнений вида (6.12) с неизвестными U_i и V_j. Уравнений на одно меньше, чем переменных, поэтому система является неопределенной и одному неизвестному (обычно U_i) придают нулевое значение. После этого остальные потенциалы определяются однозначно.