Xreferat.com » Рефераты по экономико-математическому моделированию » Моделирование систем массового обслуживания

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

p1 λ 10

Для состояния S1→ p11012) = p0 λ 01 +p2 λ21

Для состояния S2→ p2 λ21 = p1 λ 12

p0 +p1 +p2 =1

dp 4(t) /dt= λ34 p3(t) - λ43 p4(t) ,

p1(t)+ p2(t)+ p3(t)+ p4(t)=1 .


К этим уравнениям надо добавить еще начальные условия. Например, если при t = 0 система S находится в состоянии S1, то начальные условия можно записать так:


p1(0)=1, p2(0)= p3(0)= p4(0)=0 .


Переходы между состояниями СМО происходит под воздействием поступления заявок и их обслуживания. Вероятность перехода в случае, если поток событий простейший, определяется вероятностью появления события в течение времени Δ t, т.е. величиной элемента вероятности перехода λij Δ t, где λij — интенсивность потока событий, переводящих систему из состояния i в состояние i (по соответствующей стрелке на графе состояний).

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


pi(t), p2(t),…., pn(t) .


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


lim pi(t) = pi (i=1,2,…,n) ; t→∞


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

Вычислить предельные вероятности состояния рi можно, если в системе положить все производные равными 0, поскольку в уравнениях Колмогорова при t-> ∞ зависимость от времени пропадает. Тогда система дифференциальных уравнений превращается в систему Обычных линейных алгебраических уравнений, которая совместно с нормировочным условием позволяет вычислить все предельные вероятности состояний.


    1. Процессы «рождения – гибели»

Среди однородных марковских процессов существует класс случайных процессов, имеющих широкое применение при построении математических моделей в областях демографии, биологии, медицины (эпидемиологии), экономики, коммерческой деятельности. Это так называемые процессы «рождения - гибели», марковские процессы со стохастическими графами состояний следующего вида:


S1

S2

λ0 λ1 λ2 λ3 λn-1

S0

S3

kjlSn

μ0 μ1 μ3 μ4 μn-1

Рис. 2.1 Размеченный граф процесса «рождения - гибели»


Этот граф воспроизводит известную биологическую интерпретацию: величина λk отображает интенсивность рождения нового представителя некоторой популяции, например, кроликов, причем текущий объем популяции равен k; величина μ является интенсивностью гибели (продажи) одного представителя этой популяции, если текущий объем популяции равен k. В частности, популяция может быть неограниченной (число n состояний марковского процесса является бесконечным, но счетным), интенсивность λ может быть равна нулю (популяция без возможности возрождения), например, при прекращении воспроизводства кроликов.

Для Марковского процесса «рождения - гибели», описанного стохастическим графом, приведенным на рис. 2.1, найдем финальное распределение. Пользуясь правилами составления уравнений для конечнего числа n предельных вероятностей состояния системы S1, S2, S3,… Sk,…, Sn, составим соответствующие уравнения для каждого состояния:

для состояния S00p00p1;

для состояния S1-(λ10)p1= λ0p01p2, которое с учетом предыдущего уравнения для состояния S0 можно преобразовать к виду λ1р1= μ1p2.

Аналогично можно составить уравнения для остальных состояний системы S2, S3,…, Sk,…, Sn. В результате получим следующую систему уравнений:



Решая эту систему уравнений, можно получить выражения, определяющие финальные состояния системы массового обслуживания:



Следует заметить, что в формулы определения финальных вероятностей состояний р1, р2, р3,…, рn, входят слагаемые, являющиеся составной частью суммы выражения, определяющей р0. В числителях этих слагаемых находятся произведения всех интенсивностей, стоящих у стрелок графа состояний, ведущих слева на право до рассматриваемого состояния Sk, а знаменатели представляют собой произведения всех интенсивностей, стоящих у стрелок, ведущих справа на лево до рассматриваемого состояния Sk, т.е. μ0, μ1, μ2, μ3,… μk. В связи с этим запишем эти модели в более компактном виде:


к=1,n


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

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

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

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

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

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

Например, особенностями показателей СМО с отказами являются: время ожидания заявок в очереди Точ=0, поскольку по своей природе в таких системах существование очереди невозможно, то Lоч=0 и, следовательно, вероятность ее образования Роч=0. По числу заявок k определятся режим работы системы, ее состояние: при k=0 – простой каналов, при 1<k<n – обслуживание заявок, при k>n – обслуживание и отказ. Показателями таких СМО являются вероятность отказа в обслуживании Ротк, вероятность обслуживания Робс, среднее время простоя канала tпр, среднее число занятых nз и свободных каналов nсв, среднее обслуживания tобс, абсолютная пропускная способность А.

Для СМО с неограниченным ожиданием характерно, что вероятность обслуживания заявки Робс=1, поскольку длина очереди и время ожидания начала обслуживания не ограничены, т.е. формально Lоч→∞ и Точ→∞. В системах возможны следующие режимы работы: при k=0 наблюдается простой каналов обслуживания, при 1<k≤n – обслуживание и при k>n – обслуживание и очередь. Показателями таких эффективности таких СМО являются среднее число заявок в очереди Lоч, среднее число заявок в системе k, среднее время пребывания заявки в системе Тсмо, абсолютная пропускная способность А.

В СМО с ожиданием с ограничением на длину очереди, если число заявок в системе k=0, то наблюдается простой каналов, при 1<k≤n- обслуживание, при n<k<n+m – обслуживание и очередь и при k>n+m- обслуживание, очередь и отказ в ожидании обслуживания. Показателями эффективности таких СМО являются вероятность отказа в обслуживании Ротк- вероятность обслуживания Робс, среднее число заявок в очереди Lоч, среднее число заявок в системе Lсмо среднее время пребывания заявки в системе Тсмо, абсолютная пропускная способность А.

Таким образом, перечень характеристик систем массового обслуживания можно представить следующим образом: среднее время обслуживания – tобс; среднее время ожидания в очереди – Точ; среднее пребывания В СМО – Тсмо; средняя длина очереди - Lоч; среднее число заявок в СМО- Lсмо; количество каналов обслуживания – n; интенсивность входного потока заявок – λ; интенсивность обслуживания – μ; интенсивность нагрузки – ρ; коэффициент нагрузки – α; относительная пропускная способность – Q; абсалютная пропускная способность – А; доля времени простоя в СМО – Р0; доля обслуженных заявок – Робс; доля потерянных заявок – Ротк, среднее число занятых каналов – nз; среднее число свободных каналов - nсв; коэффициент загрузки каналов – Кз; среднее время простоя каналов - tпр.

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

Это часто связано с решением вопросов согласованной рабоиы цепочки или совокупностей СМО.

Например, в коммерческой деятельности необходимо учитывать еще и экономические показатели СМО: общие затраты – С; издержки обращения – Сио, издержки потребления – Сип, затраты на обслуживание одной заявки – С1, убытки, связанные с уходом заявки, - Су1, затраты на эксплуатацию канала – Ск, затраты простоя канала – Спр, капитальные вложения – Скап, приведенные годовые затраты – Спр, текущие затраты – Стек, доход СМО в единицу времени – Д1

В процессе постановки задач необходимо раскрыть взаимосвязи показателей СМО, которые по своей базовой принадлежности можно разделить на две группы: первая связана с издержками обращения Сио, которые определяются числом занятых обслуживанием каналов, затратами на содержание СМО, интенсивностью обслуживания, степенью загрузки каналов, эффективностью их использования, пропускной способностью СМО и др.; вторая группа показателей определяется издержками собственно заявок Сип, поступающих на обслуживание, которые образуют входящий поток, ощущают эффективность обслуживания и связаны с такими показателями, как длина очереди, время ожидания обслуживания, вероятность отказа в обслуживании, время пребывания заявки в СМО и др.

Эти группы показателей противоречивы в том смысле, что улучшение показателей одной группы, например, сокращение длины очереди или времени ожидания в очереди путем увлечения числа каналов обслуживания (официантов, поваров, грузчиков, кассиров), связано с ухудшением показателей группы, поскольку это может привести к увеличению времени простоев каналов обслуживания, затрат на их содержание и т.д. В связи с этим формализации задач обслуживания вполне естественно стремление построить СМО таким образом, чтобы установить разумный компромисс между показателями собственно заявок и полнотой использования возможностей системы. С этой целью необходимо выбрать обобщенный, интегральный показатель эффективности СМО, включающий одновременно претензии и возможности обеих групп. В качестве такого показателя может быть выбран критерий экономической эффективности, включающий как издержки обращения Сио, так и издержки заявок Сип, которые будут иметь оптимальное значение при минимуме общих затрат С. На этом осонвании целевую функцию задачи можно записать так:


С= (Сиоип) →min


Поскольку издержки обращения включают затраты, связанные с эксплуатацией СМО – Сэкс и простоем каналов обслуживания - Спр, а издержки заявок включают потери, связанные с уходом не обслуженных заявок – Снз, и с пребыванием в очереди – Соч, тогда целевую функцию можно переписать с учетом этих показателей таким образом:


С={(Спрnсвэкзnз)+СочРобсλ(Точ+tобс)+СизРоткλ}→min.

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

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


С={Сэкзnз+Cпр(n-n з)+Cоткотк*λ+Ссист* nз}→min


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


Коб=[(Зпуу)+(Зпвв)+(Зпдд)+(Зпзз)+(Зпо0)+(Зкткт)]*Кмп,


где Зпу – значимость показателя устойчивости ассортимента товаров;

Ку - коэффициент устойчивости ассортимента товаров;

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

Кв – коэффициент внедрения прогрессивных методов продажи товаров;

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

Кд - коэффициент дополнительного обслуживания;

Зпз - значимость показателя завершенности покупки;

Кз - коэффициент завершенности покупки;

Зпо - значимость показателя затрат времени на ожидание в обслуживании;

Ко – показатель затрат времени на ожидание обслуживания;

Зкт – значимость показателя качества труда коллектива;

Ккт – коэффициент качества труда коллектива;

Кмп – показатель культуры обслуживания по мнению покупателей;

Для анализа СМО можно выбирать и другие критерии оценки эффективности работы СМО. Например, в качестве такого критерия для систем с отказами можно выбирать вероятность отказа Ротк, значение которого не превышало бы заранее заданной величины. Например, требование Ротк<0,1 означает, что не менее чем в 90% случаев система должна справляться с обслуживанием потока заявок при заданной интенсивности λ. Можно ограничить среднее время пребывания заявки в очереди или в системе. В качестве показателей, подлежащих определению, могут выступать: либо число каналов n при заданной интенсивности обслуживания μ, либо интенсивность μ при заданном числе каналов.

После построения целевой функции необходимо определить условия решения задачи, найти ограничения, установить исходные значения показателей, выделить неуправляемые показатели, построить или подобрать совокупность моделей взаимосвязи всех показателей для анализируемого типа СМО, чтобы в конечном итоге найти оптимальные значения управляемых показателей, например количество поваров, официантов, кассиров, грузчиков, объемы складских помещений и др

Глава III. Модели систем массового обслуживания


3.1 Одноканальная СМО с отказами в обслуживании


Проведем анализ простой одноканальной СМО с отказами в обслуживании, на которую поступает пуассоновский поток заявок с интенсивностью λ, а обслуживание происходит под действием пуассоновского потока с интенсивностью μ.

Работу одноканальной СМО n=1 можно представить в виде размеченного графа состояний (3.1).

Переходы СМО из одного состояния S0 в другое S1 происходят под действием входного потока заявок с интенсивностью λ, а обратный переход – под действием потока обслуживания с интенсивностью μ.


λ

S0

S1


μ

S0 – канал обслуживания свободен; S1 – канал занят обслуживанием;

Рис. 3.1 Размеченный граф состояний одноканальной СМО


Запишем систему дифференциальных уравнений Колмогорова для вероятностей состояния по изложенным выше правилам:



Откуда получим дифференциальное уравнение для определения вероятности р0(t) состояния S0:


Это уравнение можно решить при начальных условиях в предположении, что система в момент t=0 находилась в состоянии S0, тогда р0(0)=1, р1(0)=0.

В этом случае решение дифференциального уровнения позволяет определить вероятность того, что канал свободен и не занят обслуживанием:



Тогда нетрудно получить выражение для вероятности определения вероятности занятости канала:



Вероятность р0(t) уменьшается с течением времени и в пределе при t→∞ стремится к величине



а вероятность р1(t) в то же время увеличивается от 0, стремясь в пределе при t→∞ к величине



Эти пределы вероятностей могут быть получены непосредственно из уравнений Колмогорова при условии


Функции р0(t) и р1(t) определяют переходный процесс в одноканальной СМО и описывают процесс экспоненциального приближения СМО к своему предельному состоянию с постоянной времени характерной для рассматриваемой системы.

С достаточной для практики точностью можно считать, что переходный процесс в СМО заканчивается в течение времени, равно 3τ.

Вероятность р0(t) определяет относительную пропускную способность СМО, которая определяет долю обслуживаемых заявок по отношению к полному числу поступающих заявок, в единицу времени.

Действительно, р0(t) есть вероятность того, что заявка, пришедшая в момент t, будет принята к обслуживанию. Всего в единицу времени приходит в среднем λ заявок и из них обслуживается λр0 заявок.

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



В пределе при t→∞ практически уже при t>3τ значение относительной пропускной способности будет равно

Абсолютная пропускная способность, определяющая число заявок, обслуживаемых в единицу времени в пределе при t→∞, равна:



Соответственно доля заявок, получивших отказ, составляет в этих же предельных условиях:



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

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


3.2 Многоканальная СМО с отказами в обслуживании


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

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

Туристические фирмы по продаже путевок имеют два, три, четыре и более каналов, как, например, фирма Express-Line.

Рассмотрим многоканальную СМО с отказами в обслуживании на рис. 3.2, на вход которой поступает пуассоновский поток заявок с интенсивностью λ.


λ λ λ λ λ

S0

S1

Sk

Sn


μ 2μ kμ (k+1)μ nμ

Рис. 3.2. Размеченный граф состояний многоканальной СМО с отказами


Поток обслуживания в каждом канале имеет интенсивность μ. По числу заявок СМО определяются ее состояния Sk, представленные в виде размеченного графа:

S0 – все каналы свободны k=0,

S1 – занят только один канал, k=1,

S2 – заняты только два канала, k=2,

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

Sn – заняты все n каналов, k= n.

Состояния многоканальной СМО меняются скачкообразно в случайные моменты времени. Переход из одного состояния, например S0 в S1, происходит под воздействием входного потока заявок с интенсивностью λ, а обратно – под воздействием потока обслуживания заявок с интенсивностью μ. Для перехода системы из состояния Sk в Sk-1 безразлично, какой именно из каналов освободиться, поэтому поток событий, переводящий СМО, имеет интенсивность kμ, следовательно, поток событий, переводящий систему из Sn в Sn-1, имеет интенсивность nμ. Так формулируется классическая задача Эрланга, названная по имени датского инженера – математика- основателя теории массового обслуживания.

Случайный процесс, протекающий в СМО, представляет собой частный случай процесса «рождения- гибели» и описывается системой дифференциальных уравнений Эрланга, которые позволяют получить выражения для предельных вероятностей состояния рассматриваемой системы, называемые формулами Эрланга:

.


Вычислив все вероятности состояний n – канальной СМО с отказами р0 , р1, р2, …,рk,…, рn, можно найти характеристики системы обслуживания.

Вероятность отказа в обслуживании определяется вероятностью того, что поступившая заявка на обслуживание найдет все n каналов занятыми, система будет находиться в состоянии Sn:


k=n.


В системах с отказами события отказа и обслуживания составляют полную группу событий, поэтому


Роткобс=1


На этом основании относительная пропускная способность опредляется по формуле


Q = Pобс= 1-Ротк=1-Рn


Абсолютную пропускную способность СМО можно определить по формуле


А=λ*Робс


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


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



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



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



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



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


Тсмо= nз/λ.


3.3 Модель многофазной системы обслуживания туристов


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

Для увеличения эффективности работы турфирмы необходимо смоделировать в целом поведение потенциального клиента от начала операции до ее завершения. Структура взаимосвязи основных систем массового обслуживания фактически состоит из СМО разного вида (рис. 3.3).


Поиск Выбор Выбор Решение



поиск фирмы тура по туру



Оплата Перелет Исход

Рис. 3.3 Модель многофазной системы обслуживания туристов


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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

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

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: