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

1. Записываются уравнения задачи.

2. Определяется каким-либо способом допустимое базисное решение.

3. С помощью уравнений для базисных клеток находятся потенциалы a_i и b_j всех пунктов отправления и назначения.

4. Определяется сумма стоимости по циклам пересчета g_ij = c_ij – (a_i + b_j) для всех свободных переменных. Выбирается свободная переменная x_i0j0, для которой g_i0j0 отрицательна и является наибольшей по абсолютной величине. Если таких нет, то это означает, что данное базисное решение оптимально.

5. Для выбранной переменной x_i0j0 строится цикл пересчета и осуществляется сдвиг на величину наименьшего значения базисной переменной в отрицательных вершинах.

6. Далее операции 2 – 5 повторяются, пока не будет получено оптимальное решение, т. е. пока все g_ij не станут положительными.

7. Вычисляется общая стоимость перевозок, соответствующая оптимальному решению.

Рассмотрим пример определения потенциалов. Данные задачи и одно из допустимых базисных решений приведены в таблице.

Составим систему уравнений для определения потенциалов пунктов отправления и назначения:

Число уравнений равно числу базисных переменных.

Примем в качестве свободной неизвестной a₁, положим a₁ =0.

В первой строке таблицы имеется две базисные неизвестные x₁₁, x₁₂, им соответствуют уравнения a₁ +b₁ =2 и a₁ +b₂ =3. Из этих уравнений находим b₁=2, b₂ =3.

В первом столбце таблицы содержится одна базисная неизвестная x₁₁, соответствующее ей уравнение уже было использовано.

Во втором столбце кроме x₁₂ содержится базисная переменная x₂₂. Ей соответствует уравнение a₂ +b₂ =2. Т. к. b₂ =3, значит a₂ =2 – b₂ = –1.

Во второй строке кроме рассмотренной x₂₂ имеется базисная неизвестная x₂₃. Из соответствующего ей уравнения a₂ +b₃ =5 при условии a₂ = –1 следует, что b₃ =5 – a₂ =6.

В третьем столбце кроме базисной x₂₃ есть x₃₃. Из уравнения a₃ +b₃ =2 по известному значению b₃ находим a₂ = –4.

И, наконец, из уравнения для базисной неизвестной x₃₄ a₃ +b₄ =6 определяем b₄ =6 – a₃ =10.

Теперь можно найти алгебраическую сумму стоимостей по циклу пересчета свободных переменных. Так, для свободной переменной x₁₃ имеем g₁₃ = с₁₃ – – (a₁ +b₃) =2 – (0+6) = - 4. Аналогично находим

g₁₄ = -6, g₂₁ =2, g₂₄ = - 8, g₃₁ =6, g₃₂ =4.

Далее выбирается свободная неизвестная, для которой g_ij отрицательна и имеет наибольшую абсолютную величину (в нашем случае это g₂₄ = - 8, и для нее будет x₂₄). Для выбранной переменной определяется цикл пересчета и осуществляется сдвиг по циклу на наименьшее значение базисной неизвестной в отрицательной вершине.

Далее повторяются предыдущие вычисления вплоть до получения оптимального значения, когда все g_ij будут положительны.