Симплекс-метод: непревзойдённое решение для комплексных логистических задач
В 1939 году аспирант Джордж Данциг, опоздав на лекцию по статистике в Беркли, переписал две задачи с доски, принимая их за домашнее задание. По его признанию, они оказались «намеренно сложнее привычного», и он извинялся перед профессором за затянувшееся решение. Спустя недели преподаватель сообщил, что эти задачи были нерешёнными проблемами статистики. Работа Данцига положила начало его докторской диссертации и вдохновила сценаристов фильма «Умница Уилл Хантинг».
В 1946 году, сразу после окончания Второй мировой, Данциг получил степень PhD и стал консультантом вновь созданных ВВС США. В тот период эффективность военных операций всё больше зависела от оптимального распределения ограниченных ресурсов на глобальных масштабах – от производства самолётов до снаряжения. Военные требовали алгоритма, способного обрабатывать сотни и тысячи переменных.
В ответ Данциг предложил симплекс-метод: алгоритм, базирующийся на математических принципах, которые он развивал почти десять лет, решая те самые «домашние» задачи.
Спустя почти восемьдесят лет симплекс-метод по-прежнему лидирует в оптимизации цепочек поставок и логистики с жёсткими ограничениями: он надёжен, быстр и понятен на практике. «Он неизменно работает быстро, и никто не наблюдал его замедления», — отмечает Софи Хубертс из CNRS [сайт].
Однако теоретики давно указывали на редкий, но возможный сценарий экспоненциального роста времени работы алгоритма с увеличением числа ограничений. Как подчёркивает Хубертс, «традиционные методы анализа алгоритмической сложности здесь бессильны».
В статье arXiv:2504.04197, представленной в декабре на конференции FOCS, Хубертс вместе с доктором наук Элеоном Бахом из Технического университета Мюнхена предложили ускоренный вариант симплекс-метода и доказали, почему на практике экспоненциальная сложность никогда не проявляется. Их работа опирается на классический результат Спилмана и Тенга 2001 года [cs/0111050]. По словам Шан-Хуа Тенга, это «гениальное и элегантное» развитие идеи.
«Авторы мастерски объединили классические подходы и привнесли свежие технические идеи», — замечает Ласло Вег из Боннского университета [профиль].
Геометрическая интуиция
Идея проста: представить задачу выбора производства шкафов, кроватей и стульев в виде многогранника в пространстве переменных a, b и c. Целевая функция 3a + 2b + c задаёт прибыль, а ограничения формируют грани этой фигуры. Симплекс-метод ведёт по рёбрам многогранника от одной вершины к другой, стремясь к максимальной прибыли за минимальное число шагов.
Сложности возникают из-за огромного числа ребер и невозможности «увидеть» весь многогранник сразу. На каждом перекрёстке алгоритм должен выбрать направление, не зная, куда оно приведёт. В худшем случае это может быть экспоненциально длинный путь.
Спилман и Тенг в 2001 году доказали, что добавление случайности в правило выбора рёбер ограничивает время работы полиномиальной оценкой (скажем, n²) вместо экспоненциальной 2^n. Они продемонстрировали, что при малейшей рандомизации алгоритма вероятность застревания стремится к нулю.
Тем не менее оценки Спилмана и Тенга предусматривали высокую степень полинома (до n^30). Последние двадцать лет учёные постепенно снижали эти показатели. Бах и Хубертс в новой работе внедрили ещё более интенсивную рандомизацию и добились гарантии существенно меньшего полинома, а также доказали, что дальше ускорить алгоритм без кардинально нового подхода невозможно.
«Эта статья – первый убедительный ответ на вопрос о практической эффективности симплекс-метода», — подчёркивает Хайко Рёглин из Боннского университета [сайт].
Следующая цель – вывести оценку времени в линейной зависимости от числа ограничений. «Это путеводная звезда для всех нас, но пока до неё ещё далеко», — признаёт Хубертс.
Хотя новый результат носит теоретический характер и не изменит мгновенно инструменты оптимизации, он укрепляет доверие к существующим программным решениям. «Будет легче убедить скептиков, что реальные задачи решаются полиномиально», — говорит Джулиан Холл из Эдинбургского университета [профиль].
