В 1939 году студент Джордж Данциг опоздал на лекцию и принял две задачи на доске за домашнее задание. Не зная, что это нерешенные проблемы статистики, он потратил несколько дней на их решение — и заложил основу для симплекс-метода. Спустя 80 лет этот алгоритм остается одним из самых используемых инструментов для оптимизации логистики и цепочек поставок.
ни не только ускорили алгоритм
Главная проблема метода заключалась в том, что в 1972 году математики доказали: в худшем случае время выполнения может расти экспоненциально с количеством ограничений. Это как блуждание по лабиринту, где на каждом углу вам указывают неправильное направление — теоретически можно идти самым долгим путем от точки А до точки Б.
В 2001 году Дэниел Спилман и Шанг-Хуа Тенг показали, что крошечная доля случайности может предотвратить катастрофический сценарий. Если в каждой точке есть 6 вариантов пути, и вместо следования худшему совету вы бросаете кости, то получите 5 из 6 шансов избежать неудачного выбора. Они доказали, что время выполнения никогда не превысит полиномиальное — например, n² вместо катастрофического 2ⁿ.
Теперь Софи Хьюибертс из Французского национального центра научных исследований и Элеон Бах из Технического университета Мюнхена представят в декабре 2025 года новую работу на конференции Foundations of Computer Science. Они не только улучшили теоретическое понимание алгоритма, но и объяснили теоретически, почему экспоненциальные времена выполнения не материализуются на практике. Всего-то потребовалось 80 лет, чтобы окончательно разобраться с методом, который уже давно работает быстро.
Источник новости и обложки: www.quantamagazine.org