Потребности. 
Решение транспортной задачи предприятия

…

Методами решения рассмотренной выше задачи являются все те методы, которые используются для решения задач целочисленного линейного программирования, однако существуют другие методы решения именно этого класса задач, среди которых выделяют:

метод потенциалов;

венгерский метод.

метод потенциалов.

Название метода пошло от того, что при решении транспортной задачи этим методом каждому i-му поставщику (i-й строке) устанавливается потенциал ui, который можно интерпретировать как цену продукта в пункте поставщика, а каждому j-му потребителю (j-му столбцу) устанавливается потенциал vj, который можно принять условно за цену продукта в пункте потребителя. В простейшем случае цена продукта в пункте потребителя равна его цене в пункте поставщика плюс транспортные расходы на его доставку, т. е., (1).

где vj — потенциал каждому j-му потребителю (j-му столбцу);

ui — потенциал каждому j-му потребителю (j-му столбцу);

сij — транспортные расходы.

Алгоритм метода потенциалов для закрытой задачи состоит из следующих этапов:

Этап 1. Составление начального распределения (начального плана перевозок); для реализации этого начального этапа используется ряд методов:

северо-западного угла;

наименьших стоимостей;

аппроксимаций Фогеля и другие.

Этап 2. Построение системы потенциалов на основе равенства (1) и проверка начального плана на оптимальность. В случае его оптимальности вычисляют значение целевой функции, и процесс решения задачи прекращается. Если начальный базисный план не является оптимальным, то переходят к третьему этапу алгоритма.

Этап 3. Реализация циклов перераспределения (корректировка плана прикрепления потребителей к поставщикам), после чего переходят опять ко второму этапу алгоритма.

Совокупность процедур третьего и второго этапов образует одну итерацию, такие итерации повторяются до тех пор, пока план перевозок не станет оптимальным, т. е. его нельзя улучшить.