17. Одноканальная смо с откащами в обслуживании и ее характеристики. Система с отказами: отсутствует очередь.

λ(t)=const

μ=const

P_k(t)=(λt)^ke^-λt/k! (распределение Пуассона)

k — количество событий за время t

P(T<t)=1-e^-λt (экспоненциальное распределение)

T — интервал времени между заявками

dP₀/dt=-λP₀+μP₁

dP₁/dt=-λP₀-μP₁

P₀(0)=1

P₁(0)=0

P₀+P₁=1

ρ=λ/μ<1

P₀=μ/(λ+μ)+λe^-(λ+μ)t/(λ+μ) — решение уравнения Колмогорова для нестационарного режима

P₁=1-P₀

Для стационарного режима:

P₀=μ/(λ+μ)

P₁=λ/(λ+μ)

q=μ/(μ+λ)

Абсолютная пропускная способность системы:

A=λq=λμ/(λ+μ)

Вероятность отказа (= вероятности занятости только для одноканальной системы):

P_отк=1-q=λ/(λ+μ)

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

Рассмотрим СМО с «n» каналами.

Размеченный граф состояний имеет следующий вид:

S₀ — все «n» каналов свободны

S₁ — один канал занят, остальные — свободны

Задача ставится так: имеется «n» каналов (линии связи), на которые поступает поток заявок с интенсивностью λ. Поток обслуживаний имеет интенсивность μ. Требуется найти показатели эффективности данной СМО.

Составим линейные уравнения для финальных вероятностей состояний системы. Получим:

S₀: 0=-λp₀+μp₁

S₁: 0=λp₀-μp₁-λp₁+2μp₂

…

S_n: 0=λp_n-1-nμp_n

p₁+p₂+…+p_n=1

Размеченный граф соответствует «схеме рождения и гибели» => вероятности всех состояний системы p₁, p₂, …, p_n можно выразить через p₀.

Решим данную систему.

Из первого уравнения получим:

p₁=λp₀/μ; λ/μ=ρ

p₁=ρp₀

Из второго уравнения получаем:

p₂=(λ/μ)²p₀/2=ρ²p₀/2

p₃=ρ³p₀/(1*2*3)

p₄=ρ⁴p₀/(1*2*3*4)

p_n=ρⁿp₀/n!

Подставив в нормировочное условие, получим:

p₀=(1+ρ/1!+ρ²/2!+…+pⁿ/n!)^-1

λ=1/T_з

μ=1/T_обс

ρ=λ/μ

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

Вероятность того, что заняты «k» каналов:

P_k=ρ^kp₀/k!

Вероятность отказа (вероятность того, что заняты все каналы):

P_отк=P_n=ρⁿp₀/n!

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

Q=P_обс=1-P_отк=1-ρⁿp₀/n!

Абсолютная пропускная способность:

A=λQ

Среднее число занятых каналов:

n_з=A/μ=ρp₀(1-ρⁿ/n!)

Коэффициент занятости каналов:

k_з=n_з/n=ρP_обс/n

Среднее время пребывания заявки в системе:

T_СМО=n_з/λ

19. Одноканальная СМО с ограниченной длиной очереди и ее характеристики. Варианты вычислений для ρ=1, ρ<1, ρ>1. Формула Литтла. См. вопр. 21.

P₀=(1-ρ)/(1-ρ^m+2), ρ<1

m — количество мест в очереди

Вероятность того, что заняты «k» каналов и само устройство:

P_k+1=ρ^k+1P₀

Вероятность того, что все места заняты (вероятность отказа):

P_отк=P_m+1=ρ^m+1P₀

Относительная пропускная способность:

Q=1-P_отк=1-ρ^m+1P₀

Абсолютная пропускная способность:

A=λQ=λ(1-ρ^m+1P₀)

Средняя длина очереди:

L_оч=(1-ρ^m(m-mρ+1))ρ²P₀/(1-ρ²)

Среднее время пребывания в очереди:

T_оч=L_оч/A

20. Одноканальная смо с неограниченной очередью и ее характеристики.

m→∞

P₀=1-ρ

Вероятность отказа:

P_отк=0

Относительная пропускная способность:

Q=1

Абсолютная пропускная способность:

A=λ

λ — поток заявок

Средняя длина очереди:

L_оч=ρ²/(1-ρ)

Среднее время пребывания в СМО:

T_СМО=1/(μ(1-ρ))

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

S_n+m — все каналы заняты и все места в очереди заняты

m — число, ограничивающее количество заявок в очереди

Имея граф состояний, можно составить систему линейных уравнений для финальных вероятностей состояний системы:

S₀: 0=-λp₀+μp₁

…

0=λp_n+m-1-nμp_n+m

p₀+p₁+…+p_n+m=1

Введем обозначения:

λ/μ=ρ

Тогда выражения для финальных вероятностей состояний системы примут следующий вид:

p₁=ρp₀/1!

p₂=ρ²p₀/2!

…

p_n=ρⁿp₀/n!

p_n+1=ρⁿ⁺¹p₀/nn!

p_n+2=ρⁿ⁺²p₀/n²n!

…

p_n+m=ρ^n+mp₀/n^mn!

Поскольку граф соответствует «схеме рождения и гибели», финальные вероятности всех состояний системы можно выразить через вероятность начального состояния P₀.

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

p₀=[1+ρ/1!+ρ²/2!+ρⁿ/n!+ρⁿ⁺¹/nn!+ρⁿ⁺²/n²n!+…+p^n+m/n^mn!]^-1

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

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

1). ρ=λ/μ

2). P_отк=P_n+m=ρ^n+mP₀/n^mn!

3). Q=P_обс=1-P_отк

4). A=λQ

5). Среднее число занятых в обслуживании канала:

n_з=A/μ=ρQ

6). k_з=n_з/n

7). Вероятность образования очереди:

Иногда эту характеристику не рассчитывают, а рассчитывают сразу среднее число заявок, находящихся в очереди:

8). L_оч=(ρⁿ⁺¹/nn!)(P₀(1-(ρ/n)^m(m+1-mρ/n))/(1-ρ/n)²)

Данная формула имеет место, если ρ/n≠1, ρ≠n.

А если ρ/n=1, то длина очереди рассчитывается по следующей формуле:

L_оч’=(ρⁿ⁺¹/nn!)((P₀m(m+1))/2)

9). Среднее время ожидания в очереди (формула Литтла):

T_оч=L_оч/A

T_оч’=L_оч’/A

10). Среднее время пребывания заявки в системе:

T_СМО=T_оч+t_обс

t_обс=1/μ

22. Многоканальная СМО с неограниченной очередью и ее характеристики. Рассмотрим многоканальную СМО с неограниченной длиной очереди.

Размеченный граф состояний данной системы имеет вид:

Вероятности состояний полученных формул для многоканальной СМО с ограниченной длиной очереди при переходе к пределу при m→∞.

Сумма геометрической прогрессии в выражении для P0 расходится: при уровне загрузки ρ/n>1 очередь будет бесконечно возрастать, а при ρ/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО, для которого и определяются финальные вероятности состояний:

P₀=[1+ρ/1!+ρ²/2!+…+ρⁿ/n!+ρⁿ⁺¹/n!(n-ρ)]^-1

Транспортная задача. Транспортная задача является одной их первых потоковых задач, которая была сформулирована и решена в 1914 г. американским ученым Хичкоком.

Данная задача является частным случаем изученной ранее задачи о нахождении потока минимальной стоимости. В этой задаче рассматриваются предложения грузов (товаров) от «m» поставщиков в объемах «a₁, a₂, …, a_m» и спрос «n» покупателей в объемах «b₁, b₂, …, b_n»; затраты на перевозку единицы груза от i-поставщика к j-покупателю составляют C_ij; объемы перевозимых грузов соответственно составляют x_ij, которые необходимо определить.

Математическая модель имеет следующий вид:

x_ij≥0

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