Вероятности и неприятности. Математика повседневной жизни - Сергей Борисович Самойленко
Лучшее — враг хорошего
Наконец, говоря об очередях и неприятностях, с ними связанных, нельзя не упомянуть о совершенно возмутительном парадоксе Браеса. Этот эффект приводит к тому, что в коммуникационной сети, содержащей очереди, добавление новых простых связей, даже не стохастических, может привести к уменьшению пропускной способности всей сети.
Простейшей моделью, в которой наблюдается этот эффект, может быть дорожная сеть, где два населенных пункта A и B соединены двумя дорогами так, как показано на рис. 7.17. При этом выделяются четыре участка дорог, два из которых, AC и DB, — достаточно широки и свободны, так что среднее время пути по ним занимает известное постоянное время t0. Два других плеча — AD и CB — короче, но имеют склонность к образованию заторов. Дорожный поток и пробка во многом похожи на очередь, и для них тоже работает теорема Литтла, позволяющая связать время пути по загруженному (или узкому) участку с числом машин на дороге. Таким образом, для загруженных участков время пути можно считать пропорциональным числу участников дорожного движения: t=λN. И последнее важное условие: пассажиропоток между городами таков, что t0>λN/2.
Рис. 7.17. Модель дорожной сети
Тут мы впервые вынуждены сделать предположение, которое выходит за рамки темы книги. Оно касается того, как люди принимают решения. Это тоже можно описывать математически с помощью методов теории игр — области знания, которая получила широкое развитие в последние десятилетия. Здесь я не хочу вдаваться в подробности самой теории, а сразу воспользуюсь одним из ее результатов — понятием равновесия Нэша. Поведение людей во многих случаях можно считать оптимизирующим: они пытаются уменьшить потери и увеличить свои преимущества. Но во взаимодействии с такими же оптимизирующими группа игроков может нащупать некое равновесное состояние — не лучшее, но хотя бы удовлетворительное. Применительно к нашим дорогам приход к равновесию Нэша выразится в том, что водители будут стремиться распределиться по обоим плечам дорог ACB и ADB поровну. Так что если обычно из города A в город B ездит N автомобилистов, время в пути можно выразить как λN/2 + t0.
Теперь, стремясь оптимизировать движение в этой сети, мы построим связку CD, причем постараемся сделать ее как можно шире и лучше, чтобы время на ее преодоление было существенно меньше, чем t0 или λN/2 (рис. 7.18). Воспользовавшись ею, автомобилист сможет попасть из пункта A в пункт B за время порядка 2t0 (двигаясь по пути ACDB) либо 2×λN/2 = λN (в случае пути ADCB). Но, правда, только при условии, что он окажется на дороге один. Проблема в том, что, как только люди прознают о новой дороге, естественно, какая-то часть водителей постарается пользоваться только ею. И вот к чему это приведет. В равновесии Нэша часть публики αN предпочтет путь ADCB — как более короткий, так что мы должны получить следующие характерные времена: ACB, ADB — λαN + t0, ADCB — 2λαN, ACDB — 2t0. Подвох в том, что все эти времена превышают прежний средний результат λN/2 + t0 для любого α > 1/2.
Рис. 7.18. Модель дорог с дополнительной связкой
Рассмотрим конкретный пример. Пусть t0 = 30 мин., λ = 1/100 мин./чел., α = 2/3, N = 5000. Это означает, что из пункта A выехало 5000 человек. В отсутствие связки CD среднее время пути от A до B составит 55 минут. Наличие короткого пути приведет к таким вариантам среднего времени: ACB, ADB — 63 минуты, ADCB — 67 минут, ACDB — 60 минут. Иначе говоря, ни по одному из этих путей не удастся добраться из города A в город B быстрее, чем до строительства новой скоростной дороги. Если водители каким-то усилием воли распределятся по обеим дорогам поровну, то все вернется к первоначальному состоянию. Но тогда, выходит, не было смысла строить новую связку CD!
Парадокс Браеса долгое время казался мне не очень интуитивным и ярким: слишком многое нужно принять во внимание, чтобы понять, что же в нем парадоксального. Мое мнение о нем изменилось, когда я увидел физическую модель этого явления… на пружинках. Удлинение пружины пропорционально приложенной к ней силе; это мы изучали в школе, называя законом Гука. Увеличение времени пути пропорционально загруженности трассы; об этом нам говорит теорема Литтла. Можно рассмотреть две схемы соединения пружин, которые будут эквивалентны двум схемам соединения дорогами населенных пунктов, как показано на рис. 7.19. Физическая модель делает разницу между этими двумя схемами очевидной. В первом случае мы имеем параллельное соединение участков с линейной зависимостью (пружин или затрудненных участков дороги), а во втором — последовательное. Для двух одинаковых пружин жесткостью k эффективная жесткость первой (параллельной) схемы будет равна 2k, а для второй (последовательной) — k/2. Таким образом, при одной и той же нагрузке растяжение второй системы больше, чем первой, — при условии, что длина нерастяжимых нитей окажется не меньше длины растянутых пружин. Это условие в точности соответствует требованию t0 > λN/2.
Рис. 7.19. Модель парадокса Браеса на пружинах
Этот парадокс оставался бы на страницах учебников по теории игр, если бы не проявлялся в реальной жизни, и не только в дорожном строительстве. Такое парадоксальное уменьшение пропускной способности сети при добавлении новых соединений встретилось и в механике, и в электрических сетях[31], и в полупроводниковых структурах на микроуровне[32]. А исследования случайных графов, которые важны для анализа социальных сетей и сети интернет, показали, что эффект Браеса почти наверняка проявляется в них начиная с определенного уровня сложности[33]. Применив аналогию с пружинами, нетрудно представить себе сложную сеть, в которой есть как упругие, так и нерастяжимые связи. При перерезании каких-то коротких нитей часть упругих связей начнет работать параллельно, распределив между собой нагрузку, и вся сеть станет более жесткой, менее зависимой от нагрузки.
* * *
