Метод потенциалов. 
Транспортные задачи

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj — числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij — стоимости перевозки единицы продукции между пунктами Аi и Вj: vj[k] - ui[k] Cij, i 1, …, m; j 1, ., п. Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

Определение оптимального и опорного плана транспортной задачи

Как и при решении задачи линейного программирования, симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана.

Число переменных Xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах равно n+m. Так как мы предполагаем, что выполняется условие.

то число линейно независимых уравнений равно n+m-1 отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонентов равно в точности n+m-1, то план является не выраженным, а если меньше — то выраженным. Для определения опорного плана существует несколько методов. Три из них — метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля.

При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Обычно рассмотренный метод используется при вычислениях с помощью ЭВМ. Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения и коэффициенты при неизвестных равны единице для определения оптимального плана транспортной задачи разработаны специальные методы. Два из них — метод потенциалов и Венгерский метод.