Ханна Фрай - Математика любви. Закономерности, доказательства и поиск идеального решения

Если два гостя не знакомы друг с другом, то их пара получает ноль, а те, которых лучше разделить, – отрицательную оценку. Самый низкий балл получают люди, которых нужно любой ценой держать подальше друг от друга.

Попробуем проверить этот метод на особенно сложном примере свадьбы всего с двумя столами. Имена мы, как обычно, придумали, причем совершенно случайным образом.

В данном случае решение очевидно: посадите Люка, Брюса и Щенка Далматинца за один стол, а тех, кто всегда всем портит настроение – Дарта, Джокера и Круэллу, – за второй.

Глядя на колонку Люка, мы видим, что он получает 20 “очков счастья” за удовольствие сидеть рядом с Брюсом и 60 – за Щенка, что в сумме дает ему 80 баллов.

По аналогичной системе Брюс получает 60 баллов, а Щенок будет абсолютно счастлив со своими новыми друзьями, получив в сумме 100 баллов.

За столом “ворчунов” Дарт получает 45 “очков счастья”, Джокер – 50, Круэлла – 35. По крайней мере, им будет приятно побрюзжать вместе. Если сложить баллы всех гостей, то в целом такой план дает нам 370 баллов. Для начала неплохо.

Но стоит нам поменять местами двух гостей, как разразится катастрофа. Если Щенок Далматинца поменяется с Дартом (и за первым столом окажутся Люк, Брюс и Дарт, а за вторым – Щенок, Джокер и Круэлла), сумма баллов обрушится до 120.

Конечно, это достаточно простой пример, и в данном случае идеальный план рассадки очевиден с самого начала, однако в принципе такой метод подсчета баллов для пар гостей действительно дает возможность рационально рассчитать гораздо более сложные и жизненные планы рассадки на многолюдных торжествах.

Основной принцип будет таким же, и теоретически проверить все возможные комбинации рассадки можно и вручную. Итак, проблема решена… если не считать того, что даже для совсем скромной свадьбы (17 приглашенных, два десятиместных стола) существует 131 702 различных вариантов рассадки!

Ох…

Компьютерная программа, способная обработать один вариант в секунду, будет перебирать все возможные комбинации свыше двух недель. На то, чтобы сделать это с помощью карандаша и бумаги, уйдут десятилетия (не отпугнет ли это одного из будущих супругов?). Чем больше гостей, тем больше нужно времени на вычисления. Свадьба на сто гостей и десять столов имеет 65 триллионов триллионов триллионов триллионов триллионов триллионов триллионов возможных вариантов рассадки. Если вы решите проверить их все в предвидении великого дня – желаю удачи, она вам понадобится…

И вот здесь и начинается собственно оптимизация.

Существует множество остроумных математических методов [13], которые позволяют исключить, не проверяя, огромные массивы ненужных комбинаций. Это означает, что вместо подсчета общего количества баллов для каждого возможного плана рассадки вы можете быстро и эффективно пройтись по комбинациям и определить лучшую – без необходимости проверять все.

В 2012 году Меган Беллоуз и Джей Ди Петерсон использовали эту стратегию, чтобы спланировать свою свадьбу. Они начали с того, что присвоили каждому из своих 107 гостей “оценку счастья”. Осознавая масштаб проблемы, они решили обойтись без карандаша и бумаги и сделали то, что и подобает сделать каждому уважающему себя организатору свадеб: использовали Общую систему алгебраического моделирования ( GAMS ) совместно с пакетом программного обеспечения CPLEX . Компьютер сделал свою работу, и через 36 часов жених и невеста получили оптимальный план рассадки.

Если ваши знания численных методов оптимизации находятся не на самом высоком уровне, вам придется обработать два-три самых “трудных стола” вручную. Либо обратитесь к кому-нибудь из друзей-математиков. Насколько мне известно, они всегда рады помочь.

Нельзя гарантировать, что результат будет идеальным. Программа выдаст настолько подходящий результат, насколько верными будут цифры, которые вы в нее заложите. Но вы получите решение, из которого можно будет исходить, пока вы не покажете план рассадки родителям с обеих сторон – и вот тут-то и начнутся настоящие сражения.