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

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

Теория массового обслуживания описывает всё, где есть очередь: касса, сервер, станок, колл-центр. Курсовые по ней делятся на аналитические (расчёт по формулам) и имитационные (моделирование потока заявок).

Классификация Кендалла

Обозначение A/B/n/m:

  A — распределение интервалов между заявками
  B — распределение времени обслуживания
  n — число каналов обслуживания
  m — число мест в очереди (∞ если не ограничено)

  M — показательное (марковское) распределение
  D — детерминированное
  G — произвольное

M/M/1     — одноканальная с неограниченной очередью
M/M/n/0   — многоканальная с отказами
M/M/n/m   — с ограниченной очередью

Одноканальная СМО с очередью

  λ — интенсивность потока заявок (заявок в час)
  μ — интенсивность обслуживания (заявок в час одним каналом)
  ρ = λ/μ — коэффициент загрузки

При ρ < 1 система стабильна:

  Вероятность простоя:      P₀ = 1 − ρ
  Среднее число в системе:  L = ρ/(1 − ρ)
  Среднее в очереди:        L_оч = ρ²/(1 − ρ)
  Среднее время в системе:  W = 1/(μ − λ)
  Среднее время ожидания:   W_оч = ρ/(μ − λ)

Пример: касса обслуживает 30 чел/ч, приходит 24 чел/ч

  ρ = 24/30 = 0,8
  L_оч = 0,64/0,2 = 3,2 человека в очереди
  W_оч = 0,8/(30 − 24) = 0,133 ч = 8 минут

Если поток вырастет до 28 чел/ч:
  ρ = 0,933
  L_оч = 0,871/0,067 = 13 человек
  W_оч = 0,933/2 = 0,47 ч = 28 минут

Рост нагрузки на 17 % увеличил очередь вчетверо.

Многоканальная СМО с отказами

Формулы Эрланга для M/M/n/0:

  P₀ = 1 / Σ(ρᵏ/k!),  k = 0…n
  Pₖ = (ρᵏ/k!)·P₀

  Вероятность отказа: P_отк = Pₙ = (ρⁿ/n!)·P₀
  Относительная пропускная способность: Q = 1 − P_отк
  Абсолютная: A = λ·Q
  Среднее число занятых каналов: k̄ = ρ·Q

Пример: 3 линии связи, λ = 4 вызова/мин, обслуживание 0,5 мин

  μ = 1/0,5 = 2 выз/мин,  ρ = 4/2 = 2

  P₀ = 1/(1 + 2 + 2 + 1,333) = 1/6,333 = 0,158
  P₃ = (8/6)·0,158 = 0,211

  Отказ получают 21 % вызовов
  Пропускная способность: A = 4·0,789 = 3,16 выз/мин
  Занято в среднем: 2·0,789 = 1,58 линии

Чтобы снизить отказы до 5 %, потребуется 5 линий.

Метод Монте-Карло

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

import random, statistics

def simulate_queue(lam, mu, hours=1000, seed=42):
    """Одноканальная СМО: дискретно-событийная модель."""
    rnd = random.Random(seed)
    t = 0.0
    free_at = 0.0            # момент освобождения канала
    waits, served = [], 0

    while t < hours:
        t += rnd.expovariate(lam)          # приход следующей заявки
        if t >= hours:
            break
        start = max(t, free_at)            # ждём освобождения
        waits.append(start - t)
        free_at = start + rnd.expovariate(mu)
        served += 1

    return {
        'обслужено': served,
        'среднее ожидание': statistics.mean(waits),
        'макс. ожидание': max(waits),
        'доля ждавших': sum(1 for w in waits if w > 0) / len(waits),
    }

res = simulate_queue(lam=24, mu=30)
print(res)
# среднее ожидание ≈ 0.133 ч — совпадает с аналитическим расчётом

Генерация случайных величин

Метод обратной функции: если R равномерно на [0,1], то

  Показательное:  X = −(1/λ)·ln(R)
  Равномерное на [a,b]: X = a + (b − a)·R
  Дискретное: разбиваем [0,1] на отрезки по вероятностям

Нормальное (преобразование Бокса-Мюллера):
  X = √(−2·ln R₁)·cos(2π·R₂)

Дискретно-событийное моделирование

1. Определить типы событий: приход заявки, начало обслуживания, завершение, отказ.
2. Создать календарь событий — очередь с приоритетом по времени.
3. Извлекать ближайшее событие, продвигать модельное время к его моменту.
4. Обработать событие: изменить состояние системы, запланировать порождённые события.
5. Накапливать статистику: длина очереди, время ожидания, загрузка каналов.
6. Повторять до истечения времени моделирования.
7. Выполнить несколько прогонов с разными зерновыми значениями и усреднить с доверительным интервалом.

Один прогон ничего не доказывает: результат случаен. Правильная методика — 20-30 независимых прогонов, среднее и доверительный интервал. Это же отличает курсовую с моделированием от курсовой с одной запущенной программой.

Что оптимизируют в задачах СМО

Целевая функция для оптимизации числа каналов:

  C = n·C_канала + λ·P_отк·C_потери + L_оч·C_ожидания

Перебирают n = 1, 2, 3… и выбирают минимум C.
Это типовое задание курсовой: не просто посчитать СМО,
а обосновать экономически оптимальную конфигурацию.