книги / Прикладная теория систем массового обслуживания

УДК 681.513: 681.518.3 Ю17

Рецензенты:

д-р техн. наук, профессор А.В. Частиков (кафедра радиоэлектронных средств Вятского государственного университета)

канд. техн. наук С.Л. Макаренко (директор ИТЦСТ ОАО «МОРИОН»)

Южаков А.А.

Ю17 Прикладная теория систем массового обслуживания: Учеб, пособие / Перм. гос. техн. ун-т. - Пермь, 2004. - 121 с.

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

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

Предназначено для студентов специальностей 200900 «Сети связи и системы коммутации», 210100 «Управление и информатика в технических системах», 210200 «Автоматизация технологических процессов и производств», 200800 «Проектирование и технология радиоэлектронных устройств», изучающих курсы «Прикладная теория систем массового обслуживания», «Передача данных», «Проектирование информационно-управляющих систем», «Сети связи», «Теория телетрафика».

УДК 681.513:681.518.3

ISBN 5-88151-456-4

© Пермский государственный технический университет, 2004

ВВЕДЕНИЕ

Теория массового обслуживания в настоящее время стала одной из наиболее интенсивно развивающихся ветвей теории вероятностей, т.е. опирается на ее аппарат, и в то же время является самостоятельной наукой.

Настоящее учебное пособие посвящено изложению некоторых раз­ делов теории систем массового обслуживания, объединенных единой ме­ тодологической основой - математическим моделированием, т.е. построе­ нием и изучением поведения абстрактных моделей систем массового об­ служивания.

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

Глава 2 посвящена углубленному изложению ряда фундаментальных понятий и факторов теории систем массового обслуживания, введению не­ обходимой терминологии и обозначений. Эти вопросы играют большую роль при описании объектов в терминах систем массового обслуживания.

Действующая система не нуждается в доказательстве ее существова­ ния. Единственное, что требуется, - найти способ ее описания. Вопросом первостепенной важности является нахождение численных решений, вы­ бор математического аппарата, необходимого для их получения. В посо­ бии этому вопросу уделяется особое внимание; при изложении материала имеется в виду прежде всего его полезность.

Системы массового обслуживания так велики и они настолько раз­ нообразны и сложны, что невозможно дать их исчерпывающее описание. Даже в теории информационно-вычислительных сетей существуют облас­ ти, исследование которых выходит за рамки пособия. Поэтому в главе 3 рассматриваются общие экспоненциальные системы массового обслужи­ вания с отказами. Для мультипликативных систем получены явные резуль­ таты, в том числе рекуррентные соотношения для расчета емкостно­ временных характеристик. В главе 4 рассматриваются системы массового обслуживания с ожиданием. В этой главе представлен необходимый мате­ матический аппарат для анализа систем массового обслуживания с конеч­ ной и бесконечной очередью на основе приближенных методов. Возраста­ ние реализма аналитических моделей неизбежно приводит к немультипли­ кативным системам, которым посвящена глава 5. Для рассматриваемых в этой главе систем массового обслуживания с различными ограничениями получены явные выражения, позволяющие рассчитывать основные вероят­ ностные характеристики.

Таким образом, не претендуя на полноту, учебное пособие в целом дает определенное представление о применяемых в теории систем массо­ вого обслуживания моделях.

В заключение считаю своим приятным долгом выразить благодар­ ность Л.Н. Гурко и И.В. Жуковой за помощь в подготовке и оформлении рукописи.

1.ОСНОВЫ ТЕОРИИ СЛУЧАЙНЫХ ПРОЦЕССОВ

Впрактике научных исследований и технических разработок слу­ чайные процессы в настоящее время занимают столь большое место, что без создания эффективных методов их описания и изучения нельзя гово­ рить о дальнейшем научно-техническом прогрессе.

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

Выбор целесообразного уровня строгости описания случайных про­ цессов при решении прикладных задач в значительной степени определяет качество получаемых результатов [1]. Вместе с тем уровень строгости опи­ сания должен соответствовать уровню представлений и характеру решае­ мых задач.

1.1.Семейства случайных величин

Сточки зрения практических приложений [2] любая меняющаяся система, находящаяся под влиянием случайных факторов, представляет собой случайный процесс. В соответствии со сказанным случайный про­ цесс может быть охарактеризован как процесс, мгновенное значение кото­ рого в произвольный момент времени представляет собой случайную ве­ личину [1].

Рассмотрим простой случай, когда состояние системы достаточно хорошо определяется одной количественной характеристикой. Эта вели­

чина £(г) в каждый фиксированный момент t не является однозначно опре­ деленной, как в случае детерминированных систем, а зависит от случай­ ных факторов, которые влияли на систему до момента t. При построении математической модели этого процесса естественно рассматривать £(г) в каждый фиксированный момент t как случайную величину, определенную на некотором вероятностном пространстве (Q, F, Р). Когда t меняется в рассматриваемом промежутке времени, получаем семейство случайных величин £(*), зависящих от параметра t и определенных на одном и том же вероятностном пространстве. Элементарными событиями © в этом вероят­ ностном пространстве будут возможные исходы случайного эксперимента, который определяет поведение системы в целом.

Пусть (Q, F, P) - некоторое вероятностное пространство, T - множе­ ство значений параметра. Случайным процессом называется конечная ве­ щественная функция £(/, со), которая при каждом фиксированном t e Т яв­ ляется измеримой функцией от со € Q.

Легко получить обобщенную форму этого определения в случае, ко­ гда для полного описания состояния системы при каждом фиксированном

= {£i(f, со), ..., £„(/, со)}, то семейство случайных векторов, получающееся при изменении t на множестве Г, будет определять векторный случайный процесс.

Итак, Ç(f) - случайный процесс. При каждом фиксированном t = t\ случайная величина Ç(/i) = (fb со) имеет определенное распределение веро­ ятностей, функцию распределения которой обозначим Р\х, t\) = F{Ç(/i) < <*}.

Пусть tu - , tn- произвольное конечное множество значений t. Соот­ ветствующие случайные величины £(/j), ..., Ç(f„) имеют совместную функ­ цию распределения

возможных значений tj называется семейством конечномерных распреде­ лений процесса £(/). Это одно из основных понятий теории, и многие су­ щественные свойства случайного процесса определяются свойствами се­ мейства его конечномерных распределений. Конечномерные распределе­ ния случайного процесса должны удовлетворять условиям симметрии и согласованности.

Условие симметрии требует, чтобы w-мерные функции распределе­ ния, введенные выше, были симметричными по всем параметрам (*у, tj), т.е. чтобы эти функции распределения не менялись при одновременной перестановке ху и Гу.

Условие согласованности выражается соотношением

lim F(x ,...,х„;tb ..., tn)= F(x„. . . , tu tnA\ xn-+*

которое следует из очевидного факта: со - множество, определенное нера­ венствами

£('0 £хи ЗДн) £x„.|, k(*n) ^ хП9

при хп->со приближается к множеству

{(0, Ç(r,) <хи Ç(r„.,)

Два случайных процесса £(0 и ц(/) называются эквивалентными, ес­ ли при каждом фиксированном t множества значений параметра !;(/) и r|(f) являются эквивалентными случайными величинами, так что £(/) = rj(f) с вероятностью единица. Очевидно, семейства конечномерных распределе­ ний у эквивалентных процессов совпадают.

1.2. Выборочные функции

Случайный процесс может быть определен математически как функ­ ция двух переменных t и со, области изменения которых приведены в § 1.1. Причем, с одной стороны, Ç(t, со) при каждом фиксированном / является измеримой функцией элементарного события со, т.е. случайной величи­ ной.

С другой стороны, Ç(t, со) для каждого фиксированного элементарно­ го события со в данном вероятностном пространстве становится функцией от /, определенной для всех t G Т. Иначе говоря, каждому со или каждому возможному исходу случайного эксперимента соответствует некоторая однозначно определенная функция от t. Эта функция ijj) = Ç(f, со) с фик­ сированным со описывает эволюцию (во времени, в пространстве или в ка­ ком-нибудь ином смысле) меняющейся системы в случае, когда элемен­ тарное событие со явилось результатом рассматриваемого случайного экс­ перимента. В соответствии с этим каждая функция Ç(f) называется реали­ зацией, или траекторией, или выборочной функцией случайного процесса.

На рис. 1.1 показано по одной реализации четырех различных слу­ чайных процессов [3].

Реализация Ifj) может рассматриваться как «точка» в пространстве х всех конечных вещественных функций x(t) переменного t е Т. Пространст­ во х называется пространством выборочных функций или просто выбороч­ ным пространством случайного процесса.

Случайный процесс со) определяет функцию, переводящую каж­ дую точку со вероятностного пространства (Q, F, Р) в некоторую точку пространства выборочных функций х. Эта функция индуцирует некоторое распределение вероятности в х. Множество А1 из х является множеством функций от t. Отсюда, каждое множество функций А1 имеет прообразом некоторое ©-множество А, состоящее из всех точек ©, таких, что соответ­ ствующие функции £(/) = !;(/, ©) принадлежат А1. Индуцированная вероят­ ностная мера Р] в х определяется для всех А] е F соотношением Р1(А]) = = Р(А). Тройка (х, F1, Р1) представляет собой новое вероятностное про­ странство, соответствующее индуцированному распределению.

Рис. 1.1. Наблюдаемые значения случайных процессов: а - зами­ рание интенсивности (А.) радиосигналов; б - пульсация темпера­ туры (Т) воздуха в точке атмосферы; в - пульсация разности ско­ ростей (АУ) ветра в двух точках атмосферы, находящихся на рас­ стоянии 8 см друг от друга; г - изменение диаметра (Ad) ткацкой

нити вдоль длины нити

На вероятностном языке РХ(АХ) означает вероятность того, что реали­ зация £(/) случайного процесса будет принадлежать множеству А1 про­ странства всех выборочных функций х. Поэтому 4(0 можно рассматривать как случайную функцию, принимающую различные «значения» в х в соот­ ветствии с вероятностной мерой р \ а х).

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

зации данного процесса обладают тем или иным свойством, т.е. принадле­ жат некоторому определенному множеству А 1функционального простран­ ства X.

В связи с этим возникает вопрос: в какой степени распределение ве­ роятностей в выборочном пространстве х, индуцированное данным про­ цессом, определяется семейством конечномерных распределений этого процесса? Кроме того, если на множестве значений параметра Т задано не­ которое семейство конечномерных распределений, то при каких условиях существует случайный процесс, имеющий эти распределения?

Ответ на эти вопросы содержится в теореме Колмогорова, которая будет представлена в следующем разделе.

1.3. Теорема Колмогорова

Введем несколько вспомогательных понятий, связанных с функцио­ нальным х.

Открытым интервалом в х называется множество всех конечных ве­ щественных функций х(/), которые удовлетворяют конечному числу нера­ венств вида

бесконечные вещественные числа.

Замкнутым интервалом называется множество всех x(f), удовлетво­ ряющих системе аналогичных неравенств, в которых aj и bj - конечные числа и знак < заменяется на <.

Множество всех x(f), определенное неравенствами того же вида, в которых могут стоять оба знака (< или <), будет называться просто интер­

валомОснованием интервала (1.1) называется «-мерный интервал в под­

пространстве Rn, состоящий из всех точек с координатами х(^),..., х(гл), ко­ торые удовлетворяют тем же неравенствам.

Открытый интервал является топологической окрестностью для ка­ ждой из своих точек. В топологии, индуцированной этими окрестностями, последовательность точек хп в X сходится к пределу х, если для каждого фиксированного t е Т последовательность вещественных чисел х„(/) стре­ мится в обычном смысле к пределу х(/). В этой топологии открытый ин­ тервал Является открытым множеством, а замкнутый интервал - замкну­

тым Множеством.

Bçe конечное суммы интервалов образуют поле множеств В0 в х. НаиМеныиее 5-поле, содержащее В0, будет обозначаться В и может рас­ сматриваться как обобщение класса борелевских множеств [2] в Rn.

Если дан случайный процесс £(/, со), то из определения процесса (см. §1.1) следует, что все со - множества вида

{©; Qj < Щ; со) < bj9 У = 1,2,..., п)

измеримы. Это утверждение остается справедливым, если некоторые из знаков < заменить на <. Таким образом, каждый интервал в пространстве выборочном функций X измерим, и, следовательно, измеримо каждое мно­ жество поля BQ и наименьшего 6-поля В, содержащего В0. Поэтому вероятностностная мера в X, индуцированная функцией £(г, со), однозначно оп­ ределима для всех множеств из В и В е F1, где F 1есть 6-поле множеств в X.

Функция £(/, со) определяет семейство конечномерных распределе­ ний процесса; а w-мерная совместная функция распределения величин £(г,, со), j = 1, ..., п, - вероятностную меру любого интервала, определенного неравенствами указанного выше типа, для значений /, равных /ь tn. Из свойства конечной аддитивности вытекает, что конечномерные распреде­ ления определяют вероятностную меру любого множества из поля BQ. Ра­ нее было отмечено, что функция Ç(f, со) индуцирует вероятностную меру в X, которая однозначно определена для всех множеств из В, значит, заве­ домо для всех множеств из BQ, где она, очевидно, должна совпадать с веро­ ятностью, определенной конечномерными распределениями. Следователь­ но, последняя счетно аддитивна на В0, так что может однозначно быть продолжена на В. Таким образом, семейство конечномерных распределе­ ний любого случайного процесса однозначно определяет распределение вероятностной в выборочном пространстве X для всех множеств 8-поля В, порожденного интервалами, т.е. для всех борелевских множеств в X.

Это первая часть теоремы Колмогорова. Вторая часть отвечает на уже сформулированный вопрос: если дано семейство конечномерных рас­ пределений, то при каких условиях существует случайный процесс, имеющий те же самые конечномерные распределения?

Доказано, что для существования такого процесса необходимо и дос­ таточно, чтобы данное семейство распределений удовлетворяло условиям симметрии и согласованности, приведенным в § 1.1.

В дальнейшем будем рассматривать случайные процессы с парамет­ ром, принимающим значения из некоторого множества Т вещественных чисел. Основное внимание будет сосредоточено на дискретном случае, ко­ гда Т состоит из изолированных точек, обычно целых чисел, на непрерыв­ ном случае, когда Т представляет собой некоторый (конечный или беско­ нечный) интервал. Параметр t при этом будет часто интерпретироваться как время.