Сделай Сам Свою Работу на 5

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





Практическая работа №23

Уравнения описывающие системы массового обслуживания

Ответы на контрольные вопросы

Уравнения Колмогорова

Рассмотрим математическое описание марковского случайного процесса с дискретными состояниями системы So, Sl, S2(см. рис. 6.2.1) и непрерывным временем. Полагаем, что все переходы системы массового обслуживания из состояния Si в состояние Sj происходят под воздействием простейших потоков событий с интенсивностями λij, а обратный переход под воздействием другого потока λij,. Введем обозначение pi как вероятность того, что в момент времени t система находится в состоянии Si. Для любого момента времени t справедливо записать нормировочное условие—сумма вероятностей всех состояний равна 1:

Σpi(t)=p0(t)+ p1(t)+ p2(t)=1

i=0

Проведем анализ системы в момент времени t, задав малое приращение времени Δt, и найдем вероятность р1 (t+ Δt) того, что система в момент времени (t+ Δt) будет находиться в состоянии S1 которое достигается разными вариантами:

а) система в момент t с вероятностью p1(t) находилась в состоянии S1 и за малое приращение времени Δt так и не перешла в другое соседнее состояние — ни в S0, ни b S2. Вывести систему из состояния S1 можно суммарным простейшим потоком c интенсивностью (λ1012), поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S1 за малый промежуток времени Δ t приближенно равна (λ1012)* Δ t. Тогда вероятность невыхода из этого состояния равна [1 -(λ1012)* Δ t].B соответствии с этим вероятность того, что система останется в состоянии Si на основании теоремы умножения вероятностей, равна:



 

p1(t) [1 -(λ1012)* Δ t];

 

б) система находилась в соседнем состоянии So и за малое время Δ t перешла в состояние So Переход системы происходит под воздействием потока λ01 с вероятностью, приближенно равной λ01Δ t

Вероятность того, что система будет находиться в состоянии S1, в этом варианте равна po(t) λ 01 Δ t;

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



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

 

p2(t+Δt)= p1(t) [1 -(λ1012)* Δ t]+ po(t) λ 01 Δ t+ p2(t) λ21Δ t ,

 

которое можно записать иначе:

 

p2(t+Δt)- p1(t)/ Δ t= po(t) λ 01+ p2(t) λ21- p1(t) (λ1012) .

 

Переходя к пределу при Δt -> 0, приближенные равенства перейдут в точные, и тогда получим производную первого порядка

 

dp2/dt= p0 λ 01 +p2 λ21 -p11012) ,

 

что является дифференциальным уравнением.

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

 

dp0 /dt= p1 λ 10 ,

dp1 /dt= p0 λ 01 +p2 λ21 -p11012) ,

dp2 /dt= p1 λ 12 +p2 λ21 .

 

Для составления уравнений Колмогорова существуют общие правила.

Уравнения Колмогорова позволяют вычислить все вероятности состояний СМО Si в функции времени pi(t). В теории случайных процессов показано, что если число состояний системы конечно, а из каждого из них можно перейти в любое другое состояние, то существуют предельные (финальные) вероятности состояний, которые показывают на среднюю относительную величину времени пребывания системы, в этом состоянии. Если предельная вероятность состояния S0 – равна p0 = 0,2, то, следовательно, в среднем 20% времени, или 1/5 рабочего времени, система находится в состоянии So. Например, при отсутствии заявок на обслуживание к = 0, р0 = 0,2,; следовательно, в среднем 2 ч в день система находится в состоянии So и простаивает, если продолжительность рабочего дня составляет 10 ч.



Поскольку предельные вероятности системы постоянны, то заменив в уравнениях Колмогорова соответствующие производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим СМО. Такую систему уравнений составляют по размеченному графу состояний СМО по следующим правилам: слева от знака равенства в уравнении стоит предельная вероятность рi рассматриваемого состояния Si умноженная на суммарную интенсивность всех потоков, выводящих (выходящие стрелки) изданного состояния Si систему, а справа от знака равенства — сумма произведений интенсивности всех потоков, входящих (входящие стрелки) в состояние Si систему, на вероятность тех состояний, из которых эти потоки исходят. Для решения подобной системы необходимо добавить еще одно уравнение, определяющее нормировочное условие, поскольку сумма вероятностей всех состояний СМО равна 1: n

 

Σpi(t)=1

i=1

 

Например, для СМО, имеющей размеченный граф из трех состояний So, S1, S2 рис. 6.2.1, система уравнений Колмогорова, составленная на основе изложенного правила, имеет следующий вид:

 

Для состояния So→ p0 λ 01 = 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-> ∞ зависимость от времени пропадает. Тогда система дифференциальных уравнений превращается в систему Обычных линейных алгебраических уравнений, которая совместно с нормировочным условием позволяет вычислить все предельные вероятности состояний.

 

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

 

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

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

 

 

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

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

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

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

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

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

Например, особенностями показателей СМО с отказами являются: время ожидания заявок в очереди Точ=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 при заданной интенсивности обслуживания μ, либо интенсивность μ при заданном числе каналов.

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


 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.