Алгоритм решения транспортных задач методом потенциала

1. Проверка на разрешимость задачи. Если задача не разрешима, т.е имеет неправильный баланс, то вводится фиксированный поставщик, либо потребитель, с необходимыми запасами, или запросами, при нулевой стоимости перевозок.

2. Построение начального опорного решения (одним из методов). Правильность его построения определяется в количестве занятых клеток, которых должно быть m + n – 1.

3. Построение системы потенциалов, соответствующих опорному решению, по формуле.

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

В случае, когда потенциал v1 известен, применяют:

В случае, когда потенциал u1 известен, применяют:

4. Проверка на выполнение условия оптимальности происходит только для свободных клеток таблицы:

Таким образом вычисляются оценки для всех свободных клеток таблицы.

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

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

Для этого, выбирают наибольшую положительную оценку

И начинают строить цикл, содержащий в себе данную клетку, которая связанна с другими клетками имеющие опорное решение. В клетках образующие цикл постепенно расставляют знаки «+» и «-», причем начинают цикл с наибольшей положительной оценки, и присваивание ей знака «+». Далее, осуществляют сдвиг по циклу на величину 0 = min(X ij). А клетка со знаком «-» остается пустой, так как в ней достигается min(X ij). Минимум может достигаться в нескольких клетках. В таком случае одна из клеток останется пустой, а в остальных проставляем базисные нули.

После завершения данной операции, возвращаемся к пункту 3.