Интерпретация метода потенциалов как симплекс-метода

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

Шаг 1 Определяем начальное базисное решение, затем переходим к выполнению второго шага.

Шаг 2 На основании условия оптимальности симплекс-метода среди всех небазисных переменных определяем вводимую в базис. Если все небазисные переменные удовлетворяют условию оптимальности, вычисления заканчиваются; в противном случае переходим к третьему шагу.

Шаг 3 С помощью условия допустимости симплекс-метода среди текущих базисных переменных определяем исключаемую. Затем находим новое базисное решение. Возвращаемся ко второму шагу.

Связь метода потенциалов с симплекс-методом основывается на соотношениях двойственности задач ЛП. Исходя из специальной структуры транспортной задачи (6.1), двойственная ей задача будет записана в следующем виде.

(6.2)

Из соотношений двойственности следует, что коэффициент при переменной х_ij в выражении целевой функции должен быть равен разности между левой и правой частями соответствующего ограничения двойственной задачи, т.е величине u_i +v_j -c_ij. Но мы знаем, эта величина по второй теореме о двойственности для каждой базисной переменной равна нулю. Другими словами, для этих переменных должно выполняться равенство u_i +v_j =c_ij. Имея m+n-1 таких равенств и решая их как систему линейных уравнений (после присвоения какой-либо переменной произвольного значения, например u₁ =0), находим значения потенциалов u_i и v _j. Вычислив значения потенциалов, далее определяем вводимую в базис переменную среди всех небазисных как переменную, имеющую наибольшее положительное значение величины u_i +v_j -c_ij.

Присвоение одной из двойственных переменных произвольного значения (например u₁=0) противоречит представлениям о том, что двойственное решение единственно, ведь оно находится как произведение вектора коэффициентов целевой функции при базисных переменных на обратную матрицу коэффициентов при базисных переменных ограничений (). Но это не так, и можно показать, что значение целевой функции не меняется при замене C _B на С_B+k, что присвоение одной двойственной переменной произвольного значение равносильно прибавлению к коэффициентам целевой функции произвольной константы k ко всем коэффициентам с _ij.

Алгоритм решения транспортной задачи будет проиллюстрирован на следующем примере 6.1

Пример 6.1

Транспортная компания занимается перевозкой зерна специальными зерновозами от трех элеваторов к четырем мельницам. В таблице 6.1 показаны возможности отгрузки зерна (предложения) элеваторами (в зерновозах) и потребности (спрос) мельниц (также в зерновозах), а также стоимости перевозки зерна одним зерновозом от соответствующего элеватора к соответствующей мельнице. Стоимость перевозок с _ij приведена в сотнях тысяч рублей.

Таблица 6.1

В данной задаче требуется определить структуру перевозок между элеваторами и мельницами с минимальной стоимостью. Для этого необходимо найти объемы перевозок x_ij между i -м элеватором и j -й мельницей.