Математика для гиков

В первом шаге алгоритма каждый человек представляет свою функцию плотности вероятности, или ФПВ, судье. (Судья может принимать различные формы: компьютер, старшая сестра, прохожий на улице или родители.) Судья отмечает на торте все места, где ФПВ пересекаются; другими словами, где пересекаются предпочтения каждого человека. Судья назначает порции согласно этим предпочтениям, и если на этом этапе каждый человек получает куски одинакового размера, алгоритм останавливается, и все начинают есть. Например, скажем, что человек А любит шоколадный торт, а человек Б любит ванильный. Если торт поделен пополам двумя разными вкусами, то судья просто может разрезать торт по демаркационной линии и дать каждому человеку кусок, который ему больше нравится. Но если торт разделен не поровну, то человек с большим куском отдает часть своей доли другому человеку, начиная с того места, где степень его предпочтений является наименьшей. Этот процесс продолжается, пока объем порции каждого человека не станет одинаковым.

Помимо метода Брамса – Барбанеля, который помогает двум людям справедливо поделить торт, существует другой, более общий метод, который может помочь неограниченному количеству людей разделить торт на неограниченное количество кусков. Этот метод изобрели Брамс и другой математик, Алан Тейлор, он был опубликован в январе 1995 года в выпуске журнала American Mathematical Monthly. Этот общий метод несколько сложный, но суть в том, что после того, как торт был порезан человеком А, человек Б может обрезать некоторые куски, чтобы сделать их более одинаковыми, если он чувствует, что человек А несправедливо порезал торт. Затем человек В может обрезать куски, потом человек Г и так далее. Кроме того, этот метод обеспечивает наличие лишних кусков торта, поэтому если кто-то почувствует себя обманутым, они всегда смогут выбрать один из оставшихся кусков, который будет такого размера, каким бы его хотели видеть.

Неаддитивная полезность

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

2.10. Эффективная доставка посылок

Математическое понятие: задача коммивояжера

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

В самом сердце операций UPS лежит процесс определения кратчайшего маршрута, который выберет водитель. У UPS есть примерно 96 000 транспортных средств, среди которых можно найти как машины, фургоны, мотоциклы, так и средства с альтернативными видами топлива, и каждый водитель посещает в среднем 150 пунктов назначений каждый день. Увеличение маршрута водителем хотя бы на одну милю будет стоить компании миллионы долларов в год. Поэтому у них есть огромный стимул сделать маршрут как можно короче и эффективнее.

Такая проблема – нахождение лучшего маршрута – хорошо известна математикам, которые называют ее задачей коммивояжера. Название было придумано, когда была распространена торговля «от двери до двери»; коммивояжер должен был посетить определенное количество домов за один день, поэтому ему было необходимо продумать маршрут, который позволит обойти их за наименьшее количество времени. Задача коммивояжера является сложной для решения, так как нужно принимать во внимание огромное количество факторов. Например, если водитель запланировал объехать 25 мест назначений в один день, то количество возможных маршрутов достигает 15 триллионов вариантов. Но благодаря компьютерным алгоритмам – набору инструкций, служащих определенной цели, – UPS может снизить число возможных маршрутов за короткий срок.

Усилия UPS в улучшении алгоритмов дали свои плоды в 2000-х, когда они создали компьютерную программу ORION (комплексная оптимизация и навигация на дороге). Математические вычисления программы ORION сэкономили их водителям миллионы миль в год. Вы можете сделать это и сами, если вам нужно выполнить ряд заданий, мысленно вы продумываете наиболее эффективный маршрут, чтобы минимизировать время и энергозатраты, например, чтобы дважды не возвращаться в одно и то же место или не попасть в пробку в час пик.