Биномиальное распределение описывает вероятность успеха в серии независимых испытаний Бернулли с фиксированным числом попыток n и вероятностью успеха p. Эта модель лежит в основе многих статистических приложений, от контроля качества до финансового моделирования. Формула вероятности P(X=k) = C(n,k) * p^k * (1-p)^(n-k) позволяет точно рассчитывать шансы на k успехов.

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

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

Дробно-линейное программирование — это задача оптимизации, где целевая функция представляет собой отношение двух линейных функций, а ограничения остаются линейными. Подобные задачи часто возникают в экономике, когда необходимо максимизировать эффективность (например, отношение прибыли к затратам) при линейных ресурсных ограничениях. Несмотря на нелинейный вид функции, задача может быть сведена к линейному программированию.