Постановка задач массового обслуживания

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

 

Σp_i(t)=1

ⁱ⁼¹

 

Например, для СМО, имеющей размеченный  граф из трех состояний S_o, S₁, S₂, система уравнений Колмогорова, составленная на основе изложенного правила, имеет следующий вид:

 

Для состояния S_o→ p₀ λ ₀₁ = p₁ λ ₁₀

Для состояния S₁→ p₁ (λ₁₀ +λ₁₂) = p₀ λ ₀₁ +p₂ λ₂₁

Для состояния S₂→ p₂ λ₂₁ = p₁ λ ₁₂

p₀ +p₁ +p₂ =1

dp ₄(t) /dt= λ₃₄ p₃(t) – λ₄₃ p₄(t) ,

p₁(t)+ p₂(t)+ p₃(t)+ p₄(t)=1 .

 

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

 

p₁(0)=1, p₂(0)= p₃(0)= p₄(0)=0 .

 

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

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

 

p_i(t), p₂(t),…., p_n(t) .

 

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

 

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

 

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

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

 

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

 

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

Для Марковского  процесса «рождения – гибели», описанного стохастическим графом, найдем финальное распределение. Пользуясь правилами составления уравнений для конечного числа n предельных вероятностей состояния системы S₁, S₂, S₃,… S_k,…, S_n, составим соответствующие уравнения для каждого состояния:

для состояния S₀– λ₀p₀=μ₀p₁;

для состояния S₁– (λ₁+μ₀)p₁= λ₀p₀+μ₁p₂, которое с учетом предыдущего уравнения для состояния S₀ можно преобразовать к виду λ₁р₁= μ₁p₂.

Аналогично  можно составить уравнения для  остальных состояний системы S₂, S₃,…, S_k,…, S_n. В результате получим следующую систему уравнений:

 

 

 

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

 

 

 

Следует заметить, что в формулы определения  финальных вероятностей состояний р₁, р₂, р₃,…, р_n, входят слагаемые, являющиеся составной частью суммы выражения, определяющей р₀. В числителях этих слагаемых находятся произведения всех интенсивностей, стоящих у стрелок графа состояний, ведущих слева на право до рассматриваемого состояния S_k, а знаменатели представляют собой произведения всех интенсивностей, стоящих у стрелок, ведущих справа на лево до рассматриваемого состояния S_k, т.е. μ₀, μ₁, μ₂, μ₃,… μ_k. В связи с этим запишем эти модели в более компактном виде:

 

  к=1,n

 

 

 

 

 

 

 

 

 

 

 

3. СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ С ОГРАНИЧЕННОЙ ОЧЕРЕДЬЮ

 3.1. Общая постановка задачи

На шоссе  проверяет скорость пост ГИБДД. На посту  в течении дня работает 5 инспекторов. Рабочий день инспектора равен 10 часам. Режим работы – раз в трое суток. Затраты на одного инспектора равны 35000 рублей в месяц (зарплата, налоги, специальное обмундирование и др.). Инспектор оформляет протокол примерно за 12 минут. В течение часа скоростной режим нарушают в среднем 35 водителей. Инспекторы останавливают машину, если ожидают оформления не более четырех машин. Средний размер штрафа равен 250 рублям. [7]

1. Определить параметры работы системы. Найти процент оштрафованных нарушителей. Каково среднее время, которое тратит водитель в ожидании оформления протокола? Сколько, в среднем, машин ожидает оформления? Какова средняя сумма от штрафов за месяц? Каковы месячные затраты на пост ДПС? Определить «прибыль» поста за месяц. (Ознакомительная задача).
2. Определить оптимальное (с точки зрения прибыли) число инспекторов на посту при сохранении остальных условий задачи.

3.2. Пример использования СМО с ограниченной очередью

 

Данную  задачу можно отнести к задачам  СМО с ограниченной очередью. Максимальная длина очереди равна m=5. Интенсивность потока требований (в качестве которого выступает поток нарушителей) равна водителей в час. Исходно имеется пять каналов обслуживания (пять инспекторов находятся на посту единовременно): n=5. Среднее время обслуживания одним каналом (среднее время, которое тратит инспектор на один автомобиль) равно , тогда

авт./мин  авт./час.

1. Найдем параметры работы исходной задачи.

Приведенная интенсивность системы ρ:

r=I/m=35/5=7

Приведенная интенсивность одного канала:

a=r/n=7/5=1,4

Найдем предельные вероятности СМО: p₀ – вероятность того, что система свободна, р_отк – вероятность того, что все каналы заняты.

р₀

Р_отк

Таким образом рассчитали, что 30,4% заявок не будут обслуженными, т.е. нарушителей не будет оштрафовано.

Вероятность того, что заявка будет принята к  обслуживанию (относительная пропускная способность):

Q=1– 0,304228=0,695772=69,6%

Процент оштрафованных  нарушителей равен 69,6 %.

Эффективная пропускная способность:

λ_эфф=350,695772=24,3503

В среднем 24,35 автомобилей будет оштрафовано в час.

Количество занятых  каналов (инспекторов):

Почти все инспекторы (4,8 из 5)заняты.

Найдем среднюю  длину очереди:

D=

В среднем ожидает  оформления 3 машины.

Среднее количество машин в системе:

Время в очереди  и системе:

W₀

60*0,12=7,2

W_c=7,2+12=19,2

Таким образом, среднее  время, которое тратит водитель в  ожидании оформления протокола, равно 7,2 мин.

Найдем среднюю  сумму штрафов за месяц  . Так как авт./час., сумма штрафа в среднем равна 250 руб., в месяце 30 дней по 10 рабочих часов, то:

C_штр=24,35 250 10 30=18262501826 тыс.р.

Так как затраты  на одного инспектора равны f=35000 руб./мес., а инспекторов по трижды по 5 человек, то месячные затраты на пост ДПС равны:

F= 3535000 = 525000 руб.=525 тыс.р.

«Прибыль» поста  складывается из суммы штрафов («дохода») минус затраты на инспекторов («расхода»). Таким образом, месячная «прибыль»  поста равна:

Z=C_штр– F = 1826 – 525 = 1301 тыс.р.

Определим оптимальное число инспекторов с помощью MS Excel.

Составим  таблицу 1. В строках 1– 5 записаны исходные данные задачи. В столбце А с 10– й по 24– ую строку введены количество инспекторов. По формулам, приведенным выше, для каждого количества инспекторов необходимо вычислить таблицу значений переменных a, B, p₀, p_отк, λ_эфф, С_штр, F, Z – значение прибыли поста за месяц.

Построим  график величины Z в зависимости от числа инспекторов (рисунок 2).

 

 

Рисунок 2 –  Зависимость прибыли  от числа инспекторов на посту

Из графика  и по значениям в таблице видно, что максимальная прибыль достигается при значении n=8 и равна 2250000 р. в месяц.

Таким образом, при прочих постоянных параметрах, выгоднее нанять 30 инспекторов (по 10 инспекторов  одновременно). 
                                           ЗАКЛЮЧЕНИЕ

 

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

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

Во второй главе рассматриваются уравнения Колмогорова, описывающие системы массового обслуживания, а также процессы «рождения – гибели».

Конкретный  пример применения системы массового  обслуживания с ограниченной очередью приведен в главе 3. Данная задача является СМО с ограниченной очередью или СМО с ожиданием. В данной задаче проводится ее анализ, т.е. определяются основные параметры функционирования СМО при неизменных, наперед заданных исходных характеристиках. Исходные характеристики – это интенсивность потока требований , максимальная длина очереди m, количество каналов обслуживания n, среднее время обслуживания одним каналом , интенсивность обслуживания требований . В ходе решения первой части задачи мы определили такие основные параметры функционирования СМО: интенсивность нагрузки , предельные вероятности , относительную пропускную способность Q, абсолютную пропускную способность , среднее число заявок, связанных с системой , среднюю длину очереди D, время в очереди W₀, время в системе W_c, среднюю сумму штрафа за месяц С_штр, затраты на один канал f, затраты на пост в месяц F, прибыль поста Z. При решении задачи использовались формулы Эрланга.