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

Приведенный выше метод северо-западного угла позволяет построить лишь опорный план задачи, однозначно удовлетворяющий условию разрешимости при соблюдении баланса. Однако данный план не является оптимальным. Для построения оптимального плана можно воспользоваться методом потенциалов. Метод состоит из конечного числа шагов, на каждом из которых план проверяется на оптимальность. Если оптимальность оказывается не достигнутой, то строится новый план с меньшим значением суммарных транспортных издержек (2).
Рассмотрим произвольный план задачи X = ||xij||m,n. Элемент матрицы транспортных издержек cij называют x-существенным, если соответствующий xij 0

. Функция W называют потенциалом задачи, если выполняется условие (8) для всех х-существенных элементов плана X:
W (Bj) – W (Ai) ≤ cij (8)
где i = 1, 2,…, m; j = 1,2,…,n;
Для оптимальности плана Х необходима и достаточна его потенциальность [1, с.351]. Пусть задана совокупность Gk всех Xk-существенных элементов матрицы транспортных издержек, то есть таких cij, которым соответствует xij 0. Тогда имеются величины ui и vj, удовлетворяющие системе уравнений (9), для каждого cij € Gk:
center1714500(9)
center119443500Так как значения cij заданы, то система (9) решается при задании одного начального значения ui или vj