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

Алгоритм включает следующие этапы: 1

1. Нахождение опорного плана. 1 Это предварительный план перевозок, который не обязательно должен быть оптимальным. 2
2. Нахождение потенциалов пунктов отправления и назначения. 1
3. Определение числа для каждой свободной клетки. 1 Если среди этих чисел нет положительных, то получен оптимальный план транспортной задачи. 1 Если положительные числа есть, то делается переход к новому опорному плану. 1
4. Выбор максимального среди положительных чисел. 1 Определяется свободная клетка, которую нужно заполнить, и строится цикл пересчёта для выбранной свободной клетки. 1
5. Проверка полученного опорного плана на оптимальность. 1

Если план оптимален, то решение найдено. 2 Если нет — план улучшается столько раз, сколько потребуется, пока не будет найден оптимальный план. 2

Для нахождения опорного плана существуют разные методы, например, метод северо-западного угла или метод наименьшего элемента. 5