Маслов А.В., Григорьева А.А. Математическое моделирование в экономике и управлении: Учебное пособие. Гриф УМО

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

функцией времени, то имеем систему с регулярным потоком

поступления требований в систему, в противном случае – со случайным.

Для исследования СМО со случайным потоком необходимо, чтобы

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

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

служить хорошо налаженный монтаж какого-либо сооружения по чётко

разработанному плану.

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

стационарный и нестационарный.

Если параметры потока требований не зависят от расположения

рассматриваемого интервала времени на оси времени, то имеем

стационарный поток требований, в противном случае –

нестационарный. Например, если число автомашин, приходящих на

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

стационарный.

По количеству поступающих требований в один момент времени –

на системы с ординарным и неординарным потоками требований. Если

вероятность поступления двух или более требований в один момент

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

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

Например, поток требований – автосамосвалы, обслуживающие

экскаватор, – можно считать ординарным, т.к. вероятность поступления

двух и более автосамосвалов под погрузку к экскаватору – каналу

обслуживания – очень мала, и ею можно пренебречь.

3. По связи между требованиями – на системы без последействия

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

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

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

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

случае – с последействием. Примером задачи без последействия может

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

обслуживания), на которую приходят покупатели (требования), причём

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

4. По характеру поведения требований в системе – с отказом, с

ограниченным ожиданием и с ожиданием без ограничения.

Если вновь поступившее требование на обслуживание застаёт все

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

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

когда очередь достигла определённых размеров. Если, например, на

станции техобслуживания скопилось много автомашин, то

191

целесообразнее покинуть систему; если при посадке самолета полоса

приземления занята, он покидает аэродром.

Если поступившее требование застает все каналы обслуживания

занятыми и становится в очередь, но находится в ней ограниченное

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

имеем систему с ограниченным ожиданием. Примером такого

''нетерпеливого требования'' может быть автосамосвал с раствором.

Если время ожидания велико, то во избежание затвердения раствора он

может быть разгружен на другой стройке.

Если поступившее требование, застав все каналы обслуживания

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

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

Пример: самолет, который находится на аэродроме до тех пор, пока не

освободится взлётная полоса.

5. По способу обслуживания требования – на системы с

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

первым.

Иногда в этом случае говорят о дисциплине обслуживания.

Если СМО охватывает несколько категорий требований и по

каким-либо соображениям необходимо соблюдать различный подход к

их отбору, то имеем систему с приоритетом. Так, при поступлении

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

необходимы в данный момент.

Если освободившийся канал обслуживает требование, ранее других

поступившее в систему, то имеем СМО с обслуживанием требований по

мере их поступления. Это наиболее распространенный класс систем.

Например, покупатель, подошедший первым к продавцу, обслуживается

первым. Этот способ выбора требований на обслуживание применяется

там, где в силу технических, технологических и организационных

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

Если требования из очереди в канал обслуживания поступают в

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

требований на обслуживание. Пример: выбор слесарем-сантехником

одной из нескольких заявок, поступивших от жильцов на устранение

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

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

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

близко расположенную к нему, если никакие другие факторы не

предопределяют другой выбор.

Последний обслуживается первым. Этот способ выбора требований

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

192

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

в систему. Так, при укладке строительных изделий в штабель удобнее

брать из штабеля (очереди) изделие, поступившее последним.

6. По характеру обслуживания требований – на системы с

детерминированным и случайным временем обслуживания. Если

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

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

постоянно, то имеем систему с детерминированным временем

обслуживания, в противном случае – со случайным.

7. По числу каналов обслуживания – на одноканальные и

многоканальные системы. Так, при монтаже дома может быть

использован один подъёмный кран (один канал обслуживания) или

несколько (много каналов) для обслуживания прибывающих на стройку

изделий.

8. По количеству этапов обслуживания – на однофазные и

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

последовательно и они неоднородны, т.е. выполняют различные

операции обслуживания, то имеем многофазную СМО. Примером

двухфазной СМО может быть, например, обслуживание автомобилей на

станции техобслуживания (мойка, диагностирование).

9. По однородности требований, поступающих на обслуживание, –

на системы с однородными и неоднородными потоками требований.

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

грузоподъёмности, то такие требования называются однородными, если

разной грузоподъёмности – то неоднородными.

10. По ограниченности потока требований – на замкнутые и

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

покинувшие систему, могут в неё возвращаться, то имеем замкнутую

систему, в противном случае – разомкнутую. Примером замкнутой

системы может служить система ЭВМ – пользователь, в которой

пользователь, как правило, прикрепляется к ЭВМ и обслуживается ею в

течение определённого времени.

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

(число каналов обслуживания, продолжительность обслуживания и т.д.)

и дисциплина обслуживания, то это дает основание для построения

математической модели системы.

В задачах анализа СМО в качестве основных показателей

функционирования системы могут быть использованы:

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

;

- вероятность того, что в системе находится n требований –

;

193

- среднее число требований, находящихся в системе (сфере

обслуживания)







1n

nсист

nPN

;

- среднее число требований, находящихся в очереди,









nkоч

PNnN )(

, где

– число каналов обслуживания;

- среднее время ожидания требований в очереди

оч

для разомкнутой системы



очоч

NТ 

где



– интенсивность

поступления потока требований в систему;

для замкнутой системы

)),(/(

очочоч

NmNТ 



где m – число

требований, нуждающихся в обслуживании;

- среднее время ожидания требований в системе

сист

;

- среднее число свободных каналов обслуживания









;)(

nkск

PnNN

- среднее число занятых каналов обслуживания

;





nзк

nPN

- среднее число заявок, находящихся на обслуживании в период









TTT



формула Литтла, где



– средняя интенсивность

поступления требований,



– средняя продолжительность

обслуживания одной заявки).

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

Как видно из приведённой классификации СМО, имеется большое

число разновидностей СМО. Ограничимся наиболее часто

встречающимися СМО:

- детерминированной одноканальной;

- одноканальной разомкнутой с ожиданием с простейшим потоком

поступления требований в систему;

- одноканальной замкнутой (поток требований пуассоновский) с

ожиданием.

(Пуассоново распределение – распределение случайной величины,

при котором она может принимать дискретные значения из счётного

множества 0, 1, 2, … с вероятностью

   





где ,,...1,0



параметр распределения.

Все эти системы могут быть исследованы аналитическими

методами, построенными на основе представления процесса

194

функционирования системы как марковского процесса с непрерывным

временем и дискретными состояниями.

Задача анализа детерминированной системы

Постановка задачи

Пусть исследуется производственный процесс, в котором

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

constt



(т.е. интенсивность потока поступлений требований

constt

 /1



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

времени

constt

об



(т.е. интенсивность обслуживания

constt

об

 /1



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

1// 



nоб

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

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

через какое время очередь исчезнет.

Выявление основных особенностей, взаимосвязей и

количественных закономерностей

Величину

 



/кси 

называют коэффициентом использования

СМО. Очередь будет бесконечно возрастать, если

1



, а если же

1



то очередь будет иметь постоянную длину. Схематически работа

рассматриваемой СМО представлена на рис. 12.2.

Рис. 12.2. Схема работы системы

Пока обслуживается очередь из n требований в течение времени

об

tnt 

, вновь поступит на обслуживание

требований:







об











Аналогично, пока будут обслуживаться

требований в течение

времени

об

tnt 

, дополнительно поступит на обслуживание

требований:

195

Входящий поток

требований

об

t

Пункт

обслуживания

Очередь Выходящий поток

требований







nnn

об











Это происходит до тех пор, пока

nк

tt 

, после чего очередь

исчезнет.

Весь процесс функционирования СМО представим в

аналитическом виде.

Построение математической модели

Время, через которое очередь исчезнет, можно представить в таком виде:







iк

ttttT

...

Исследование математической модели

Для определения времени, через которое очередь исчезнет,

необходимо раскрыть математическую модель.

 

   

 

...1.../1

......

















к

кк

кобобкобоб

nnn

nnnttntntnT

В модели использована формула суммы геометрической

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



к интенсивности

обслуживания



, тем через больший промежуток времени исчезнет

очередь (при

1/ 



). Членом

1к



можно для упрощения расчётов

пренебречь, тогда







Задачи анализа разомкнутой системы с ожиданием

(потоки требований пуассоновские)

Постановка задачи

Пусть имеется некоторая СМО, для которой справедливы

следующие гипотезы:

1. Вероятность поступления требований не зависит от принятого

начала отсчёта времени, а зависит только от продолжительности

периода наблюдений (стационарность потока);

2. Не поступают в систему и не покидают её одновременно два или

более требований (поток ординарный).

3. Поступление одного требования не зависит от поступления

другого (отсутствие последействия).

196

Известны также интенсивность



поступления потока требований

(среднее число поступлений требований в единицу времени

t/1

) и

интенсивность



обслуживания требований (среднее число

обслуживаний в единицу времени

об

t/1

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

вероятность простоя канала обслуживания

;

вероятность того, что в системе находится

требований

;

среднее число требований, находящихся в системе,

сист

(в

очереди и на обслуживании);

среднее число требований, находящихся в очереди,

оч

;

среднее время ожидания требования в системе

сист

Выявление основных особенностей, взаимосвязей

и количественных закономерностей

Поток требований, обладающий свойством стационарности и

отсутствием последействия, называется простейшим. В нашей задаче

поток требований простейший. Основным понятием при анализе

процесса СМО является состояние системы. Зная состояние системы,

можно предсказать в вероятностном смысле её поведение.

Простейший поток – это стационарный пуассоновский поток. Если

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

другое, являются пуассоновскими, то для этих систем вероятности

состояний описываются с помощью системы обыкновенных

дифференциальных уравнений.

Существует определённый методический прием, намного

облегчающий вывод дифференциальных уравнений для вероятностей

состояний. Первоначально строится размеченный граф состояний с

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

его более наглядным.

Рис. 12.3. Размеченный граф состояний одноканальной разомкнутой

СМО с ожиданием

Граф состояний, на котором проставлены не только стрелки

переходов, но и интенсивность соответствующих потоков событий,

называют размеченным.

197

1n

1n

Построение математической модели

Если составлен размеченный граф состояний, то для построения

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

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

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

Производная

 

tdP

вероятности пребывания системы в состоянии

n равна алгебраической сумме нескольких членов:

- число членов этой суммы равно числу стрелок на графе состояний

системы, соединяющих состояние n с другими состояниями;

- если стрелка направлена в состояние n, то член берётся со знаком

плюс;

- если стрелка направлена из состояния n, то со знаком минус;

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

состояния, из которого направлена стрелка, на интенсивность потока

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

В соответствии с размеченным графом состояний, используя

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

уравнений вероятностей состояний запишем так:

 

















. )()()(

)(

...

; )()(

)(





tPtPtP

tdP

tPtP

tdP

nnn

Исследование математической модели

Ограничимся исследованием установившегося режима работы

разомкнутой одноканальной системы.

Тогда

,....)1,0( 0

)(

 n

tdP

Вместо системы обыкновенных дифференциальных уравнений

получаем систему алгебраических уравнений:

 

















...

; 0

210





nnn

PPP

Используя полученную систему алгебраических уравнений, легко

выразить вероятности состояний системы в виде некоторой

рекуррентной формулы.

198

(так называемые уравнения

Эрланга)

Из первого уравнения определяется вероятность наличия одного

требования в системе

001

PPP





из второго уравнения – вероятность наличия двух требований в системе

 

1011012

// PPPPPPP





Окончательно получим





Аналогично проводятся преобразования для определения

 

2122123

123

PPPPPPP

PPP





















Окончательно получим





и т.д.

Суммируя формулу суммы членов убывающей геометрической

прогрессии, получаем

 

)1(

...1









n

При

 

















PPn

отсюда имеем:

вероятность простоя канала обслуживания



1

;

вероятность того, что в системе находится

требований

 





среднее число требований, находящихся в системе (или

математическое ожидание):

     

 

...)....

...321/(1......32

111

232

01 1





















 

n n

nсист

nnnPN







Последняя скобка является производной от следующего

выражения:

 

   

1 1/......1......







т.е. равна

 

1/1





Окончательно имеем

   

;

1/1









сист

- среднее число требований, находящихся в очереди:

























систоч

;

- среднее время ожидания требования в системе, которое можно

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

































сист

199

Задача анализа замкнутой системы с ожиданием

(потоки требований пуассоновские)

Постановка задачи

Пусть исследуется некоторая замкнутая СМО с ограниченным

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

возвращаются в систему обслуживания (например, экскаватор или

автосамосвал). Интенсивность поступления одного требования в

систему известна и равна



. Интенсивность обслуживания требований

известна и равна



Число требований, нуждающихся в обслуживании, равно n.

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

вероятность того, что в системе имеется

требований

;

вероятность простоя канала обслуживания

;

среднее число требований, находящихся в очереди

оч

;

среднее число требований, находящихся в системе

сист

;

среднее время ожидания требования в очереди

оч

;

среднее время ожидания требования в системе

сист

Выявление основных особенностей, взаимосвязей

и количественных закономерностей

Состояние системы будем связывать с числом требований,

находящихся в системе. При этом возможны два состояния системы:

- число требований, поступивших в систему,

0n

, т.е. канал

обслуживания простаивает;

- число требований, поступивших в систему

mn 0

Нарисуем размеченный граф состояний однокональной замкнутой

СМО с ожиданием:

2λ

… …

Рис. 12.4. Размеченный граф состояний одноканальной замкнутой

СМО

с ожиданием

Построение математической модели

200

1n

1n

1m

mλ

(m-1)λ

(m-n+1)λ

(m-n)λ

μ μ