Метод Ньютона по праву считается одним из самых мощных и быстро сходящихся алгоритмов в арсенале нелинейного математического программирования. В то время как методы градиентного спуска первого порядка анализируют только "наклон" целевой функции, метод Ньютона привлекает информацию о ее "кривизне", используя вторые производные. Это позволяет алгоритму строить точную параболическую аппроксимацию функции и достигать оптимума с квадратичной скоростью сходимости.

В 1984 году математик Нарендра Кармаркар из AT&T Bell Labs опубликовал алгоритм, который потряс мир математического программирования. До этого момента считалось, что полиномиальные алгоритмы (такие как метод эллипсоидов Хачияна) применимы лишь в теории, а на практике безоговорочно властвует симплекс-метод с его потенциально экспоненциальной сложностью. Алгоритм Кармаркара стал первым методом внутренних точек, который доказал свою полиномиальную сложность $O(n^{3.5} L)$ и при этом на задачах огромной размерности превосходил симплекс-метод по скорости вычислений в десятки раз.

Транспортная задача линейного программирования выделяется специфической структурой матрицы ограничений, что делает применение классического симплекс-метода вычислительно избыточным. Метод потенциалов (метод разрешающих множителей) был разработан Леонидом Канторовичем и Тьяллингом Купмансом как специализированный алгоритм, идеально учитывающий сетевую структуру задачи и позволяющий находить глобальный оптимум транспортных потоков значительно быстрее стандартных симплекс-процедур.