Ведущий подход к симплекс-методу, широко используемому методу балансировки сложных логистических ограничений, не может быть лучше. Комментарий Сохранить статью Прочитать позже
Введение
В 1939 году, опоздав на курс статистики в Калифорнийском университете в Беркли, Джордж Данциг, аспирант первого курса, списал с доски две задачи, думая, что это домашнее задание. Позже он вспоминал, что домашнее задание оказалось «труднее обычного», и извинился перед профессором за то, что потратил на него несколько дополнительных дней. Несколько недель спустя профессор сообщил ему, что он решил две знаменитые открытые задачи по статистике. Работа Данцига легла в основу его докторской диссертации, а спустя десятилетия вдохновила на создание фильма «Умница Уилл Хантинг».
Данциг получил докторскую степень в 1946 году, сразу после Второй мировой войны, и вскоре стал математическим консультантом недавно сформированных Военно-воздушных сил США. Как и во всех современных войнах, исход Второй мировой войны зависел от разумного распределения ограниченных ресурсов. Но, в отличие от предыдущих войн, этот конфликт был поистине глобальным по масштабу, и победа в нём была одержана во многом благодаря исключительной промышленной мощи. США могли просто производить больше танков, авианосцев и бомбардировщиков, чем их противники. Зная это, военные активно интересовались проблемами оптимизации, то есть тем, как стратегически распределять ограниченные ресурсы в ситуациях, которые могли включать сотни и тысячи переменных.
Военно-воздушные силы поручили Данцигу найти новые способы решения подобных задач оптимизации. В ответ он изобрёл симплекс-метод – алгоритм, основанный на некоторых математических методах, разработанных им почти десять лет назад при решении школьных задач.
Спустя почти 80 лет симплекс-метод по-прежнему остаётся одним из самых распространённых инструментов, когда необходимо принимать решения в области логистики или цепочки поставок в условиях сложных ограничений. Он эффективен и работает. «Он всегда работал быстро, и никто не видел, чтобы он работал медленно», — сказала Софи Юйбертс из Французского национального центра научных исследований (CNRS).
В то же время существует любопытное свойство, которое долгое время бросало тень на метод Данцига. В 1972 году математики доказали, что время, необходимое для выполнения задачи, может экспоненциально расти с увеличением количества ограничений. Таким образом, независимо от того, насколько быстрым может быть метод на практике, теоретический анализ постоянно предлагал худшие сценарии, которые подразумевали, что он может занять экспоненциально больше времени. Для симплекс-метода «наши традиционные инструменты изучения алгоритмов не работают», — сказал Хьюбертс.
Однако в новой статье, которая будет представлена в декабре на конференции «Основы информатики», Хейбертс и Элеон Бах, докторант Мюнхенского технического университета, похоже, преодолели эту проблему. Они ускорили алгоритм и представили теоретические обоснования того, почему экспоненциальный рост времени выполнения, которого долгое время опасались, не реализуется на практике. По словам Тэна, эта работа, основанная на эпохальном результате Дэниела Шпильмана и Шан-Хуа Тэна, «блестящая [и] прекрасная».
«Это очень впечатляющая техническая работа, которая мастерски объединяет многие идеи, разработанные в предыдущих направлениях исследований, [добавляя] некоторые действительно хорошие новые технические идеи», — сказал Ласло Вег, математик из Боннского университета, который не принимал участия в этом проекте.
Оптимальная геометрия
Симплекс-метод был разработан для решения такого класса задач: предположим, что мебельная компания производит шкафы, кровати и стулья. По совпадению, каждый шкаф в три раза прибыльнее каждого стула, а каждая кровать — в два раза. Если бы мы захотели записать это в виде выражения, используя a, b и c для обозначения объёма произведённой мебели, мы бы сказали, что общая прибыль пропорциональна 3a + 2b + c.
Сколько единиц каждого вида продукции должна производить компания, чтобы максимизировать прибыль? Ответ зависит от ограничений, с которыми она сталкивается. Предположим, что компания может производить не более 50 единиц в месяц, поэтому a + b + c меньше или равно 50. Шкафы изготавливать сложнее — их можно изготовить не более 20, поэтому a меньше или равно 20. Для стульев требуется особая древесина, запасы которой ограничены, поэтому c должно быть меньше 24.
Симплекс-метод превращает подобные ситуации, хотя часто и с участием гораздо большего количества переменных, в геометрическую задачу. Представьте себе графическое отображение наших ограничений для a, b и c в трёхмерном пространстве. Если a меньше или равно 20, мы можем представить себе плоскость на трёхмерном графике, перпендикулярную оси a и пересекающую её в точке a = 20. Мы бы определили, что наше решение должно лежать на этой плоскости или ниже её. Аналогичным образом мы можем создать границы, связанные с другими ограничениями. В совокупности эти границы могут разделить пространство на сложную трёхмерную фигуру, называемую многогранником.
Софи Хьюбертс имеет геометрическую модель задачи оптимизации.
Выполнение симплекс-алгоритма от начала до конца, представленное геометрически, включает в себя поиск пути — скажем, от нижней вершины до самой верхней точки — который требует наименьшего количества шагов или, что эквивалентно, прослеживает наименьшее количество рёбер. Общее количество шагов, в свою очередь, связано со временем выполнения (или «сложностью») алгоритма, при этом цель состоит в том, чтобы решить задачу за минимальное количество шагов. Определение кратчайшего пути снизу вверх на этом рисунке равнозначно определению наиболее эффективной формы, которую может принять такой алгоритм.
Найти быстрый и прямой путь было бы легко, если бы не два обстоятельства: во-первых, исходная форма, вероятно, гораздо сложнее, чем в нашем примере, с гораздо большим количеством граней, вершин и рёбер. Во-вторых, нет карты, которая могла бы помочь вам. Вы не видите весь объект, по которому пытаетесь двигаться. Вместо этого вы начинаете с одной вершины и выбираете, по какому ребру идти первым. Вы делаете то же самое в следующей вершине и так далее, не зная наверняка, куда приведёт вас выбранное вами ребро.
Если вам невероятно не повезёт, вы можете свернуть не туда в каждой вершине и застрять в лабиринте. «Вы можете пройти самый длинный путь из точки А в точку Б, — сказал Бах, — потому что на каждом углу кто-то скажет вам, что нужно идти не в том направлении». Именно такая ситуация может привести к наихудшим сценариям, которые займут экспоненциальное время.
В 2001 году Спилман и Тэн доказали, что даже самая крошечная доля случайности может помочь предотвратить такой исход. Возвращаясь к предыдущему примеру — рискуя сильно упростить аргументацию Спилмана и Тэна — предположим, что на каждом углу, куда вы приходите, есть шесть вариантов выбора. Если вам всегда говорят, в каком наихудшем направлении идти, вы попадете в беду. Однако, если вы вместо этого полагаетесь на бросок кубика, у вас будет пять из шести шансов избежать наихудшего выбора, и катастрофа может быть предотвращена. Введение элемента случайности и неопределенности в процесс разумно, учитывая, что в реальном мире измерения никогда не бывают точными. Спилман и Тэн ввели случайность совершенно другим способом, но они показали, что время выполнения никогда не может быть хуже, чем количество ограничений, возведенных в фиксированную степень — например, n² — что является примером того, что называется полиномиальным временем. Это намного лучше, чем экспоненциальное время, которое имеет форму, скажем, 2n.
Шан-Хуа Тэн (слева) и Дэниел Спилман использовали случайность в своем знаменательном результате 2001 года.
Тем не менее, это не решило проблему полностью. Хьюбертс отметил, что их полиномиальные значения времени всё ещё были довольно высокими — они включали член, возведённый в степень 30, что является довольно большим числом для показателя степени. Таким образом, за последние два десятилетия исследователи добились постепенного прогресса в снижении этого значения.
В своей новой работе Бах и Хьюбертс использовали ещё большую случайность в своём алгоритме, чтобы показать, что время выполнения гарантированно значительно ниже, чем было установлено ранее. Они также показали, что алгоритм, основанный на подходе, предложенном Шпильманом и Тэном, не может работать быстрее полученного ими значения. Это говорит нам, сказал Хьюбертс, «о том, что мы полностью понимаем [эту] модель симплекс-метода».
«Это знаменует собой значительный шаг вперед в нашем понимании [симплексного] алгоритма», — сказал Хайко Рёглин, специалист по информатике из Боннского университета, — «и предлагает первое действительно убедительное объяснение практической эффективности метода».
Тем не менее, Хьюбертс не считает это концом пути. Подход, начатый в 2001 году Шпильманом и Тэном, показал, как время выполнения можно сократить с экспоненциального до полиномиального. Следующий логичный шаг — разработать способ линейного масштабирования в зависимости от количества ограничений. «Это путеводная звезда для всех этих исследований», — сказала она. Но это потребует совершенно новой стратегии. «Мы не рискуем достичь этого в ближайшее время».
Хотя работы Баха и Хьюбертса представляют теоретический интерес для коллег в их области, они не нашли непосредственного практического применения. Тем не менее, они могут помочь развеять некоторые опасения, связанные с использованием современного программного обеспечения, основанного на симплекс-методе. «Хотя практические эксперименты показывают, что эти задачи всегда решаются за полиномиальное время», — сказал Джулиан Холл, преподаватель математики Эдинбургского университета, разрабатывающий программное обеспечение для линейного программирования, Бах и Хьюбертс предоставили более убедительное математическое обоснование этой интуиции. «Таким образом, теперь легче убедить тех, кто боится экспоненциальной сложности».
Источник: www.quantamagazine.org
