Непрерывная релаксация не чудодейственное средство: она по-прежнему не предлагает нам эффективный способ приблизиться к действительно оптимальным решениям, а только лишь к их приближенным значениям. Но получить в два раза больше писем или внедрить в два раза больше пожарных расчетов будет гораздо лучше, чем использовать неоптимизированные альтернативы.
Штраф за превышение скорости: Лагранжева релаксация
Виззини: Непостижимо.
Иниго Монтойя: Ты постоянно используешь это слово. Не думаю, что оно означает то, что ты думаешь, что оно означает.
Фильм «Принцесса-невеста»
Однажды в детстве Брайан полдня жаловался матери на все, что ему приходилось делать: уроки, работу по дому… «С юридической точки зрения ты не обязан ничего делать, – ответила ему мать. – Ты не обязан слушаться учителей. Ты не обязан слушаться меня. Ты не обязан даже подчиняться закону. Но у любого поступка есть последствия, и только тебе решать, когда ты захочешь с этими последствиями столкнуться».
Детский мозг Брайана взорвался. Это был мощный посыл, пробуждающий ощущение силы, ответственность, моральные суждения. Но было это также и кое-что другое: эффективная методика вычислений под названием Лагранжева релаксация. Идея Лагранжевой релаксации проста. Задача оптимизации состоит из двух частей: правила и оценка производительности. В рамках Лагранжевой релаксации мы берем некоторые из ограничивающих условий задачи и внедряем их в систему количественных показателей. Таким образом, мы превращаем невозможное в затратное. (В задаче со свадебной рассадкой, к примеру, мы можем убрать ограничение, что за каждым столом может сидеть максимум 10 человек, и допустить «перенаселение» за столами с вероятностью слегка потолкаться локтями.) Когда условие задачи оптимизации гласит «Делай только так, а не то…», Лагранжева релаксация вопрошает: «А не то что?» Однажды мы позволяем себе выйти за границы (хотя бы чуть-чуть, пусть даже за счет высоких расходов) – и вот уже задачи становятся разрешимыми.
Лагранжевы релаксации занимают огромную часть во всей теоретической литературе, посвященной задаче коммивояжера и другим сложным задачам в области информатики. Кроме того, они служат важным инструментом для ряда практических случаев. Вспомним, к примеру, Майкла Трика из Университета Карнеги – Меллон, который, как мы помним из главы 3, отвечал за расписание Главной лиги бейсбола и ряд конференций Национальной ассоциации студенческого спорта. О чем мы не упоминали, так это о том, как он это делает. Составление расписания на каждый год представляет собой гигантскую задачу дискретной оптимизации, слишком сложную для того, чтобы компьютер мог решить ее методом перебора. Поэтому каждый год Трик и его коллеги из группы спортивного планирования прибегают к помощи Лагранжевой релаксации. Каждый раз, когда вы включаете телевизор или занимаете место на трибуне стадиона, помните, благодаря чему состоялась встреча этих двух команд на этой площадке в этот конкретный вечер. Ну хорошо, необязательно это будет оптимальный спортивный матч. Но близко к тому. И поблагодарить за это нам стоит не только Майкла Трика, но и французского математика XVIII века Жозефа Луи Лагранжа.