Выбор короткой очереди

Выбор оптималь­ного вари­анта действий — одна из глав­ных задач в современ­ной жизни, кото­рая ста­но­вится всё более слож­ной и динамич­ной. Среди рекомен­даций, пред­лага­емых матема­ти­че­скими моде­лями, есть при­ёмы, для понима­ния кото­рых доста­точно школь­ных пред­став­ле­ний о тео­рии веро­ят­но­стей и ком­би­на­то­рике.

Метод «выбора из двух» — при­мер соеди­не­ния эффек­тив­но­сти и про­стоты. Область при­ме­не­ния — задачи о балан­си­ровке нагрузки из раз­дела матема­тики с акту­ально зву­чащим назва­нием: тео­рия оче­ре­дей.

Реаль­ная оче­редь может состо­ять как из людей в кассы супермар­кета, так и из запро­сов к сер­ве­рам поис­ко­вой системы. В супермар­кете посе­ти­тель выби­рает оче­редь по её длине и коли­че­ству това­ров в кор­зи­нах покупа­те­лей. Поступающий в поис­ко­вую систему запрос тоже хочется напра­вить к сер­веру с корот­кой оче­ре­дью. Однако, если сер­ве­ров очень много, то непре­рыв­ный опрос всех о длине оче­реди сде­лает систему нера­бо­то­спо­соб­ной.

Выбор короткой очереди // Математическая составляющая

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

Про­де­мон­стри­руем метод «выбор из двух» на при­ме­рах. Если самая длин­ная оче­редь только одна, то при выборе из двух попа­да­ние в неё исклю­ча­ется.

Если сер­ве­ров много, а самых загружен­ных — пятая часть, то веро­ят­ность попа­да­ния в «плохую» оче­редь не исклю­ча­ется, но мала и при­мерно равна про­из­ве­де­нию веро­ят­но­стей $\frac15\cdot \frac15=\frac1{25}$. Ана­логично, если самых сво­бод­ных сер­ве­ров тоже пятая часть, то веро­ят­ность попасть в «хорошую» оче­редь равна $\frac9{25}$.

Несмотря на про­стоту идеи, осно­ван­ные на ней методы полу­чили рас­про­стра­не­ние и раз­ви­тие только в недав­нее время. А вы, чита­тель, ока­завшись в супермар­кете с десят­ками касс, выби­райте наугад пару оче­ре­дей и направ­ляй­тесь к более корот­кой, меньшему из двух зол!

Разворот книги

Книга «Математическая составляющая»
Книга «Математическая составляющая»

Лите­ра­тура

Райго­род­ский А., Лит­вак Н. Кому нужна матема­тика?: Понят­ная книга о том, как устроен циф­ро­вой мир. — М.: МИФ, 2017.