книги / Прикладная теория систем массового обслуживания
..pdfМинистерство образования и науки Российской Федерации
Федеральное агентство по образованию
Пермский государственный технический университет
А.А. Южаков
ПРИКЛАДНАЯ ТЕОРИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
Рекомендовано УМО по образованию в области телекоммуникаций в качестве учебного пособия для студентов, обучающихся по специальности 200900 - «Сети связи
и системы коммутации»
Пермь 2004
УДК 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.
Легко получить обобщенную форму этого определения в случае, ко гда для полного описания состояния системы при каждом фиксированном
значении параметра t |
необходимо знать несколько величин £i(/), |
Ç;l(f). |
Если рассматривать |
как компоненты случайного вектора !;(t, |
со) = |
= {£i(f, со), ..., £„(/, со)}, то семейство случайных векторов, получающееся при изменении t на множестве Г, будет определять векторный случайный процесс.
Итак, Ç(f) - случайный процесс. При каждом фиксированном t = t\ случайная величина Ç(/i) = (fb со) имеет определенное распределение веро ятностей, функцию распределения которой обозначим Р\х, t\) = F{Ç(/i) < <*}.
Пусть tu - , tn- произвольное конечное множество значений t. Соот ветствующие случайные величины £(/j), ..., Ç(f„) имеют совместную функ цию распределения
F(xb |
.... /„) = P{Ç(fi) <хи £(/„) <лг„}. |
|
Семейство таких совместных распределений для « = 1,2, |
и всех |
возможных значений 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. Теорема Колмогорова
Введем несколько вспомогательных понятий, связанных с функцио нальным х.
Открытым интервалом в х называется множество всех конечных ве щественных функций х(/), которые удовлетворяют конечному числу нера венств вида
ai < x({j) < bj |
(у = 1, 2,..., п), |
( 1.1) |
где п - произвольное целое число; tj - |
точки из Т\ aj и bj - |
конечные или |
бесконечные вещественные числа.
Замкнутым интервалом называется множество всех 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 при этом будет часто интерпретироваться как время.