Лекции по теории случайных процессов

Подождите немного. Документ загружается.

т.д. Каждая из этих характеристик описывает, с той или другой стороны, степень

приспособленности системы к выполнению потока заявок, иными словами – ее

пропускную способность.

Под «пропускной способностью» в узком смысле слова обычно понимают

среднее число заявок, которое система может обслужить в единицу времени. Наряду с

нею часто рассматривают относительную пропускную

способность – среднее

отношение числа обслуженных заявок к числу поданных. Пропускная способность

(как абсолютная, так и относительная) в общем случае зависит не только от

параметров системы, но и от характера потока заявок. Если бы заявки поступали

регулярно, через точно определенные промежутки времени, и обслуживание каждой

заявки тоже имело строго определенную длительность,

расчет пропускной

способности системы не представлял бы никакой трудности. На практике обычно

моменты поступления заявок случайны; по большей части случайна и длительность

обслуживания заявки. В связи с этим процесс работы системы протекает нерегулярно:

в потоке заявок образуются местные сгущения и разрежения. Сгущения могут

привести либо к отказам в обслуживании, либо к

образованию очередей. Разрежения

могут привести к непроизводительным простоям отдельных каналов или системы в

целом. На эти случайности, связанные с неоднородностью потока заявок,

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

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

представляет собой случайный процесс. Чтобы дать рекомендации по рациональной

организации системы, выяснить

ее пропускную способность и предъявить к ней

требования, необходимо изучить случайный процесс, протекающий в системе, и

описать его математически. Этим и занимается теория массового обслуживания.

Заметим, что за последние годы область применения математических методов

теории массового обслуживания непрерывно расширяется и все больше выходит за

пределы задач, связанных с «обслуживающими организациями» в

буквальном смысле

слова. Многие задачи автоматизации производства оказываются близкими к теории

массового обслуживания: потоки деталей, поступающих для выполнения над ними

различных операций, могут рассматриваться как «потоки заявок», ритмичность

поступления которых нарушается за счет случайных причин. Своеобразные задачи

теории массового обслуживания возникают в связи с проблемой организации

транспорта и системы сообщений.

Близкими к теории массового обслуживания

оказываются и задачи, относящиеся к надежности технических устройств: такие их

характеристики, как среднее время безотказной работы, потребное количество

запасных деталей, среднее время простоя в связи с ремонтом и т.д., определяются

методами, непосредственно заимствованными из теории массового обслуживания.

Проблемы, родственные задачам массового обслуживания, постоянно

возникают в

военном деле. Каналы наведения, линии связи, аэродромы, устройства

для сбора и обработки информации представляют собой своеобразные системы

массового обслуживания со своим режимом работы и пропускной способностью.

Трудно даже перечислить все области практики, в которых находят

применение методы теории массового обслуживания. За последние годы она стала

одной из самых быстро развивающихся

ветвей теории вероятностей.

Далее будут изложены некоторые элементарные сведения по теории массового

обслуживания, знание которых необходимо любому инженеру, занимающемуся

вопросами организации в области промышленности, народного хозяйства, связи, а

также в военном деле.

2. Система массового обслуживания с отказами.

Уравнения Эрланга

Системы массового обслуживания делятся на два основных типа; а)

системы с отказами, б) системы с ожиданием.

В системах с отказами заявка, поступившая в момент, когда все каналы

обслуживания заняты, немедленно получает отказ, покидает систему и в

дальнейшем процессе обслуживания не участвует.

В системах

с ожиданием заявка, заставшая все каналы занятыми, не

покидает систему, а становится в очередь и ожидает, пока не освободится

какой-нибудь канал. В настоящем вопросе рассмотрим систему с отказами как

наиболее простую.

Пусть имеется n-канальная система массового обслуживания с отказами.

Рассмотрим ее как физическую систему Х с конечным множеством состояний

– свободны все каналы,

– занят ровно один канал,

………

– занято ровно k каналов,

………

– заняты все n каналов.

Схема возможных переходов дана на рис. 1.

Рис. 1. Схема возможных переходов

Поставим задачу:

определить вероятности состояний системы p

(t) (k=0, 1, …, n) для

любого момента времени t. Задачу будем решать при следующих допущениях:

1) поток заявок – простейший, с плотностью λ;

2) время обслуживания Т

об

– показательное, с

параметром

об

g(t) =μe

-μt

(t >0) (1)

Заметим, что параметр

, в формуле (1) полностью аналогичен

параметру

показательного закона распределения промежутка T между

соседними событиями простейшего потока:

f(t) =λe

(t >0) (2)

Параметр λ имеет смысл «плотности потока заявок». Аналогично,

величину

можно истолковать как «плотность потока освобождений» занятого

канала. Действительно, представим себе канал, непрерывно занятый

(бесперебойно снабжаемый заявками); тогда, очевидно, в этом канале будет

идти простейший поток освобождений с плотностью μ.

Так как оба потока – заявок и освобождений – простейшие, процесс,

протекающий в системе, будет марковским.

k-1

k+1

n - 1

…

Рассмотрим возможные состояния системы и их вероятности

(t), p

(t), …, p

(t). (3)

Очевидно, для любого момента времени

∑

1)( (4)

Составим дифференциальные уравнения для всех вероятностей (3),

начиная с p

(t). Зафиксируем момент времени t и найдем вероятность р

(t + Δt)

того, что в момент t +Δt система будет находиться в состоянии x

(все каналы

свободны). Это может произойти двумя способами (рис. 2):

А – в момент t система находилась в состоянии x

а за время Δt не

перешла из нее в x

(не пришло ни одной заявки);

В – в момент t система находилась в состоянии x

, а за время Δt канал

освободился, и система перешла в состояние x

Рис. 2.

На рис. 2 возможные способы появления состояния х

в момент t +Δt

показаны стрелками, направленными в x

; стрелка, направленная из x

в x

перечеркнута в знак того, что система не должна выйти из состояния x

Возможностью «перескока» системы через состояние (например, из x

в x

через x

) за малый промежуток времени можно пренебречь, как величиной

высшего порядка малости по сравнению с Р(А) и Р(В). (В дальнейшем все

время будем пренебрегать слагаемыми высших порядков малости по

сравнению с Δt. В пределе при Δt → 0 приближенные равенства перейдут в

точные.)

По теореме сложения вероятностей имеем

(t + Δt) ≈ Р(А) + Р(В). (5)

Найдем вероятность события А по теореме умножения. Вероятность того,

что в момент t система была в состоянии х

равна p

(t). Вероятность того, что за

время Δt не придет ни одной заявки, равна е

–λΔt

. С точностью до величин

высшего порядка малости

–λΔt

≈ 1 – λΔt . (6)

Следовательно,

Р(А) ≈ р

(t)⋅(1 – λΔt).

Найдем Р(В). Вероятность того, что в момент t система была в состоянии

равна p

(t). Вероятность того, что за время

t канал освободится, равна (1 –

λΔt); с точностью до малых величин высшего порядка

1 –е

–μΔt

≈ μΔt .

Следовательно,

Р(В) ≈ р

(t)⋅ μΔt.

Отсюда

(t + Δt) ≈ р

(t)⋅(1 – λΔt) +μ р

(t)Δt .

Перенося р

(t) в левую часть, деля на Δt и переходя к пределу при Δt → 0,

получим дифференциальное уравнение для р

(t):

)(μ)(λ

)(

tptp

tdp

(7)

Аналогичные дифференциальные уравнения могут быть состав- -лены и

для других вероятностей состояний.

Возьмем любое k (0 < k < n) и найдем вероятность p

(t + Δt) того, что в

момент (t + Δt) система будет в состоянии x

(рис. 3).

Рис. 3 Рис. 4

Эта вероятность вычисляется как вероятность суммы уже не двух, а трех

событий (по числу стрелок, направленных в состояние x

А – в момент t система была в состоянии x

(занято k каналов), а за время

Δt не перешла из него ни в х

k+1

, ни в х

k–1

, (ни одна заявка не поступила, ни один

канал не освободился);

В – в момент t система была в состоянии х

k–1

(занято k–1 каналов), а за

время Δt перешла в х

(пришла одна заявка);

С – в момент t система была в состоянии х

k+1

(занято k+1 каналов), а за

время Δt один из каналов освободился.

Найдем Р(А). Вычислим сначала вероятность того, что за время Δt не

придет ни одна заявка и не освободится ни один из каналов:

–λΔt

(е

–μΔt

)

≈ e

–(λ+kμ)Δ t

Пренебрегая малыми величинами высших порядков, имеем

–(λ+kμ)Δ t

≈ 1– (λ + kμ)Δt ;

откуда

Р(А) ≈ р

(t)⋅[1 – (λ + kμ)Δt].

Аналогично,

Р(В) ≈ р

k–1

λΔt ;

Р(С) ≈ р

k+1

(t)⋅(k + 1)μΔt

(t + Δt) ≈ р

(t)⋅[1 – (λ + kμ)Δt] + р

k–1

λΔt + р

k+1

(t)⋅(k + 1)μΔt .

Отсюда получаем дифференциальное уравнение для р

(t) (0 < k < n)^

tdp

)(

λ р

k–1

(t) – (λ + kμ) р

(t) + (k + 1) μ р

k+1

(t) .

Составим равнение для последней вероятности р

(t) (рис. 4).

Имеем

(t + Δt) ≈ р

(t)(1 – nμΔt) + р

n–1

(t)λΔt ,

где (1 – nμΔt) – вероятность того, что за время Δt не освободится ни один

канал;

λΔt – вероятность того, что за время Δt придет одна заявка.

Получаем дифференциальное уравнение для р

(t):

tdp

)(

λ р

n–1

(t) – nμ р

(t) .

Таким образом, получена система дифференциальных уравнений для

вероятностей р

(t), р

(t), …, p

(t):

)(μ)(λ

)(

tptp

tdp

………

tdp

)(

λ р

k–1

(t) – (λ + kμ) р

(t) + (k + 1) μ р

k+1

(t) (0 < k < n), (8)

………

tdp

)(

λ р

n–1

(t) – nμ р

(t) .

Уравнения (8) называются уравнениями Эрланга. Интегрирование

системы уравнений (8) при начальных условиях

(0) = 1; р

(0) = … = p

(0) = 0

(в начальный момент все каналы свободны) дает зависимость р

(0) для любого

k. Вероятности р

(t) характеризуют среднюю загрузку системы и ее изменение с

течением времени. В частности, р

(t) есть вероятность того, что заявка,

пришедшая в момент t, застанет все каналы занятыми (получит отказ):

отк

= p

(t) .

Величина q(t) = 1 – p

(t) называется относительной пропускной

способностью системы. Для данного момента t это есть отношение среднего

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

Система линейных дифференциальных уравнений (8) сравнительно легко

может быть проинтегрирована при любом конкретном числе каналов п.

Заметим, что при выводе уравнений (8) мы нигде не пользовались

допущением о

том, что величины λ и μ (плотности потока заявки «потока

освобождений») постоянны. Поэтому уравнения (8) остаются справедливыми и

для зависящих от времени λ (t), μ (t), лишь бы потоки событий, переводящих

систему из состояния в состояние, оставались пуассоновскими (без этого

процесс не будет марковским).

Использованная для подготовки лекций литература:

1. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные

приложения. – Учеб. Пособие для втузов. – 2-е изд., стер. – М.: Высш.шк.,

2000. – 383с.: ил.

2. Вероятность и математическая статистика: Энциклопедия / Гл. ред. Ю.В.

Прохоров; Ред. кол.: В.И.Битюцков, А.А.Боровков: Б.В.Гнеденко и др

. – М.:

Большая российская энциклопедия, 1999. – 910 с.

3. Волков И.К., Зуев С.М., Цветкова Г.М. Случайные процессы: Учеб. Для

вузов/ Под ред.В.С.Зарубина, А.П. Крищенко. –М.: Изд-во МГТУ им.

Н.Э. Баумана, 2000. -448 с. (Сер. Математика в техническом университете;

Вып.XVIII).

4. Гмурман В. Е. Руководство к решению

задач по теории вероятностей и

математической статистике. Учеб. Пособие для студентов вузов. – Изд. 9-е

стер. – М.: Высш. Шк., 2004. – 404с.

5. Гмурман В. Е. Теория вероятностей и математическая статистика: Учебное

пособие для студентов вузов. – Изд. 9-е, стереотип. – М.: Высшая школа,

2004. – 479 с.

6. Кремер Н. Ш. Теория вероятностей и математическая статистика: Учебник

для вузов. – М.: Юнити, 2000. -543 с.

Лекции разработаны

доцентом кафедры ОТЗИ

ктн, доцентом В. Петренко

“ 7 “ сентября 2006 г.