Вероятности и неприятности. Математика повседневной жизни - [48]

Выходит, нет никаких подлых штучек злодейки-судьбы, а есть только честное случайное блуждание. Правда, если нам не повезло и мы оказались во временно отстающей очереди, то мы в ней проведем больше времени и, согласно закону велосипедиста, у нас будет больше возможностей посетовать на судьбу! А теперь, внимание, хорошие новости: в любой выбранный интервал времени тех, кому повезет попасть в быструю очередь, будет больше, чем невезунчиков, ведь быстрая очередь может пропустить больше людей! Но, увы, это ничуть не утешит того, кто надолго застрял в хвосте.

Теория для заскучавших в коридоре

Тем и хороша математика, что она способна сделать увлекательным даже стояние в очереди. Например, можно прикинуть, сколько еще ждать своей очереди, но для этого, как ни странно, надо посмотреть не вперед, а назад, на растущий хвост. Если подождать какое-то время, скажем 10 минут, и посчитать, сколько человек выстроилось за вами, то, разделив количество людей перед вами на полученное число, вы вычислите среднее время ожидания в десятках минут. Например, пусть за десять минут хвост вырос на пять человек; если в момент подсчета перед вами семь человек, то ожидаемое время ожидания составит 10 × 7/5 = 14 минут. Понятно, что эта оценка будет весьма грубой, но любопытно, что она действительно соответствует среднему времени ожидания. Об этом говорит теорема Литтла — один из самых ранних и самых общих результатов теории очередей, известной в России как теория массового обслуживания.

Теория очередей появилась в самом начале XX века, с первых работ датского математика Агнера Эрланга (1878–1929), который занимался зарождающейся областью телекоммуникаций. За сотню лет результаты исследований Эрланга прочно вошли в нашу жизнь — настолько, что возникает ощущение, будто мы вошли в мир телекоммуникаций. Несколько позже большой вклад в развитие этой науки внес советский математик Александр Яковлевич Хинчин (1894–1959), который вместе с Андреем Николаевичем Колмогоровым (1903–1987) заложил основы современной теории вероятностей. Результаты теории массового обслуживания важны для проектирования магазинов и залов ожидания, оптимального управления операционной системой компьютера и операционным залом банка, для грамотной разработки бюрократической машины, управления дорожной сетью и в оценке рисков страховой компании. В очередях могут стоять люди (покупатели, клиенты, пассажиры), автотранспорт и грузы, задачи и документы; а обрабатывать их — кассиры, операторы, регистраторы, серверы и бюрократы. Чтобы не путаться и не утопать в деталях, будем называть стоящих в очереди клиентами, а того, кто их обслуживает, — оператором.

Представьте себе очередь, в которую люди встают согласно некоторому распределению временных интервалов p_in(t) со средним значением 1/λ. Время, которое оператор тратит на работу с клиентами, подчинено распределению p_out(t) со средним значением 1/μ. На рисунке 7.3 показана очередь, в которой ожидают два клиента под номерами 1 и 2, один с номером 0 обслуживается, а клиент номер 3 готов в нее встать. Ее можно описать как марковский процесс, в котором состояние определяется длиной очереди: состояние 0 — в очереди никого, состояние 1 — один клиент, состояние 2 — два клиента и т. д. В идеальном мире ничто не запрещает очереди стать сколь угодно длинной; значит, мы получаем цепь с бесконечным числом состояний, и для анализа очереди придется иметь дело с матрицей переходов, содержащей бесконечное число строк и столбцов. В предыдущей главе мы уже имели дело с марковскими процессами, и для анализа стационарного состояния цепи нам понадобилось возводить матрицу переходов в бесконечную степень. Так что же, надо вычислить бесконечную матрицу, возведенную в бесконечную степень? Математиков эта задача не испугала, и уже в 1930-е были придуманы методы для таких вычислений. Результатом анализа будут свойства стационарного состояния очереди. Оно не меняется со временем, но все параметры очереди, такие как длина или время ожидания в ней, — случайные величины. Они могут постоянно меняться, но при этом всегда остаются в рамках каких-то распределений, от времени не зависящих. И чего только не придумаешь, скучая в зале ожидания!

Рис. 7.3. Модель очереди

Свойства очереди сильно зависят от соотношения λ и μ. Если λ > μ, хвост будет расти неограниченно, как пробка на дороге, в которую въезжает больше автомобилей, чем может выехать. Она попросту перекрывает поток клиентов, накапливая их в себе. Для λ < μ очередь устойчива. Она может расти или уменьшаться по мере того, как клиенты добавляются и выходят из нее, но клиенты в ней не накапливаются неограниченно: сколько их вошло в зону ожидания, столько же выйдет. Иными словами, устойчивая очередь может затормозить тех, кто в ней стоит, но неспособна изменить интенсивность потока людей, проходящих сквозь нее. И если на входе мы имеем в среднем λ человек в единицу времени, то и на выходе должны получить такой же поток, независимо от скорости работы оператора. Случай λ ≈ μ рассматривается отдельно. Такая метастабильная очередь ведет себя неустойчиво и моделируется процессом случайного блуждания — с той только разницей, что длина очереди не может быть отрицательной. У блуждающей таким образом системы есть непроницаемая стенка снизу, которая, однако, не мешает практически неограниченному росту длины очереди. И хотя рано или поздно она сократится и даже исчезнет, отклонения времени ожидания и времени работы оператора от среднего будут столь велики, что счесть такое обслуживание удовлетворительным никак не получится. Далее мы будем рассматривать только устойчивые очереди. От характера распределений