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

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

Каждой строке с номером i в матрице перевозок приписывается числовое значение _i, а каждому столбцу с номером j значение _j.

, называются потенциалами, если для каждой заполненной клетки (i; j) выполняется условие:

, (2.16)

где c_ij - тариф перевозки.

Определение. Сумма потенциалов для свободных клеток называется косвенными тарифами .

. (2.17)

Соотношение между косвенными тарифами свободных клеток базисного решения и их истинными (заданными тарифами) служат критериями оптимальности решения.

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

Если есть свободные клетки, для которых , то рассматриваемый план перевозок не является оптимальным и может быть улучшен пересчетом по циклу, соответствующему одной из клеток, в которых (лучше, если разность будет максимальной).