Ведущий подход к симплекс-методу, широко используемой методике для балансировки сложных логистических ограничений, не может быть лучше.
Иллюстрация: Нэш Вирасекера для журнала QuantaСохранить эту историю Сохранить эту историю
Оригинальная версия этой статьи была опубликована в журнале Quanta Magazine.
В 1939 году, опоздав на свой курс статистики в Калифорнийском университете в Беркли, Джордж Данциг — аспирант первого курса — переписал с доски две задачи, думая, что это домашнее задание. Позже он вспоминал, что домашнее задание оказалось «сложнее обычного», и извинился перед профессором за то, что потратил на его выполнение несколько дополнительных дней. Несколько недель спустя профессор сообщил ему, что он решил две известные нерешенные проблемы в статистике. Работа Данцига легла в основу его докторской диссертации и, десятилетия спустя, послужила вдохновением для фильма «Умница Уилл Хантинг».
Данциг получил докторскую степень в 1946 году, сразу после Второй мировой войны, и вскоре стал математическим советником недавно сформированных ВВС США. Как и во всех современных войнах, исход Второй мировой войны зависел от разумного распределения ограниченных ресурсов. Но в отличие от предыдущих войн, этот конфликт имел поистине глобальный масштаб, и победа в значительной степени была одержана благодаря чистой промышленной мощи. США могли просто производить больше танков, авианосцев и бомбардировщиков, чем их противники. Зная это, военные были крайне заинтересованы в задачах оптимизации — то есть в том, как стратегически распределять ограниченные ресурсы в ситуациях, которые могли включать сотни или тысячи переменных.
Военно-воздушные силы поручили Данцигу разработать новые способы решения подобных задач оптимизации. В ответ он изобрел симплекс-метод — алгоритм, основанный на некоторых математических методах, разработанных им при решении задач на доске почти десять лет назад.
Спустя почти 80 лет симплекс-метод по-прежнему остается одним из наиболее широко используемых инструментов при принятии логистических решений или решений в цепочке поставок в условиях сложных ограничений. Он эффективен и работает. «Он всегда работал быстро, и никто не видел, чтобы он работал медленнее», — сказала Софи Юибертс из Французского национального центра научных исследований (CNRS).
В то же время, существует любопытное свойство, которое долгое время омрачало метод Данцига. В 1972 году математики доказали, что время, необходимое для выполнения задачи, может экспоненциально возрастать с увеличением числа ограничений. Таким образом, независимо от того, насколько быстрым может быть метод на практике, теоретический анализ неизменно показывает наихудшие сценарии, которые подразумевают, что он может занять экспоненциально больше времени. Что касается симплекс-метода, то, по словам Хуибертса, «наши традиционные инструменты для изучения алгоритмов не работают».
Элеон Бах — соавтор нового результата.
Фотография: любезно предоставлена Элеоном Бахом.Однако в новой статье, которая будет представлена в декабре на конференции «Основы информатики», Хуибертс и Элеон Бах, аспирант Мюнхенского технического университета, похоже, преодолели эту проблему. Они ускорили алгоритм, а также представили теоретические объяснения того, почему экспоненциальное увеличение времени выполнения, которого долгое время опасались, на практике не наблюдается. Работа, основанная на знаменательном результате 2001 года Даниэля Шпильмана и Шан-Хуа Тэна, по словам Тэна, «блестящая и прекрасная».
«Это очень впечатляющая техническая работа, которая мастерски сочетает в себе многие идеи, разработанные в предыдущих направлениях исследований, [и добавляет] несколько действительно интересных новых технических решений», — сказал Ласло Вег, математик из Боннского университета, не принимавший участия в этой работе.
Оптимальная геометрия
Симплекс-метод был разработан для решения класса задач, подобных этой: Предположим, мебельная компания производит шкафы, кровати и стулья. По совпадению, каждый шкаф приносит в три раза больше прибыли, чем каждый стул, а каждая кровать — в два раза больше. Если бы мы хотели записать это в виде выражения, используя 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² — что является примером так называемого полиномиального времени. Это намного лучше, чем экспоненциальное время, которое принимает форму, скажем, 2*n*.
Шан-Хуа Тэн.
Фотография: Эмилио Флорес для журнала Quanta.
Дэниел Спилман.
Фотография: Брэндон Шульман.Тем не менее, это не решило проблему полностью. Значения полиномиального времени оставались довольно высокими, отметил Хуибертс, — они включали член, возведенный в степень 30, что является довольно большим числом для показателя степени. Поэтому за последние два десятилетия исследователи постепенно продвигались в снижении этого значения.
В своей новой статье Бах и Хуибертс, опираясь на еще большую долю случайности в своем алгоритме, показали, что время выполнения гарантированно будет значительно меньше, чем было установлено ранее. Они также продемонстрировали, что алгоритм, основанный на подходе, разработанном Шпильманом и Тенгом, не может работать быстрее, чем полученное ими значение. Это говорит нам, сказал Хуибертс, «что мы полностью понимаем [эту] модель симплекс-метода».
«Это знаменует собой значительный шаг вперед в нашем понимании алгоритма [симплекса], — сказал Хайко Рёглин, специалист по информатике из Боннского университета, — предлагая первое действительно убедительное объяснение практической эффективности этого метода».
Тем не менее, Хуибертс не считает это концом пути. Подход, начатый в 2001 году Спилменом и Тенгом, показал, как время выполнения можно сократить с экспоненциального до полиномиального. Следующим логическим шагом является изобретение способа линейного масштабирования в зависимости от количества ограничений. «Это путеводная звезда для всех этих исследований», — сказала она. Но для этого потребуется совершенно новая стратегия. «Мы не рискуем достичь этого в ближайшее время».
Хотя работы Баха и Хуибертса представляют теоретический интерес для коллег в их области, они не нашли немедленного практического применения. Тем не менее, они могут помочь развеять некоторые опасения, связанные с использованием доступного сегодня программного обеспечения, основанного на симплекс-методе. «Хотя практические эксперименты показывают, что эти задачи всегда решаются за полиномиальное время, — сказал Джулиан Холл, преподаватель математики в Эдинбургском университете, занимающийся разработкой программного обеспечения для линейного программирования, — Бах и Хуибертс предоставили более убедительные математические доказательства этой интуиции. Поэтому теперь легче убедить тех, кто опасается экспоненциальной сложности».
Источник: www.wired.com
