4.4 Вероятностные модели и имитационное моделирование

Методы Монте-Карло, СМО и подготовка к ЕГЭ по информатике

1 Введение в вероятностные модели

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

Ключевые понятия

Случайная величина — величина, значение которой зависит от случайного события
Распределение вероятностей
Математическое ожидание
Дисперсия и СКО

Области применения

Финансовые рынки
Телекоммуникационные сети
Транспортные потоки
Очереди обслуживания
Надежность систем

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

Метод Монте-Карло — это численный метод решения математических задач при помощи моделирования случайных величин. Название происходит от района Монте-Карло в Монако, известного своими казино (игрой в рулетку).

Пример: Вычисление числа π методом Монте-Карло

Алгоритм:

Генерируем случайные точки (x, y) в квадрате [-1, 1]×[-1, 1]
Подсчитываем точки, попавшие в круг радиусом 1
Площадь круга: S_кр = π·r² = π
Площадь квадрата: S_кв = 4
Отношение точек: π ≈ 4·(N_круг/N_всего)

Результаты моделирования

N точек	Оценка π	Погрешность
100	3.08	1.9%
1 000	3.148	0.2%
10 000	3.1412	0.01%
100 000	3.14156	0.001%

Псевдокод алгоритма:

N = 10000  // количество испытаний
count = 0   // счетчик точек в круге

для i от 1 до N:
    x = случайное_число(-1, 1)
    y = случайное_число(-1, 1)
    если x² + y² ≤ 1:
        count = count + 1

pi_estimate = 4 * count / N
вывести pi_estimate

Преимущества метода

Простота реализации
Универсальность
Возможность решения сложных задач
Естественный учет случайности

Недостатки

Медленная сходимость (1/√N)
Требует много вычислений
Зависит от качества ГСЧ

3 Имитационное моделирование

Имитационное моделирование — это метод, позволяющий исследовать сложные системы путем создания их компьютерной модели и проведения экспериментов с этой моделью.

Пример: Моделирование работы магазина

Параметры системы:

Время между приходами покупателей: случайное, от 1 до 5 минут
Время обслуживания: случайное, от 2 до 6 минут
Количество касс: 2
Время работы: 8 часов (480 минут)

Метрики для анализа:

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

Результаты одного эксперимента:

Параметр	Значение
Время работы	480 мин
Обслужено покупателей	142
Средняя очередь	3.2 чел
Среднее время ожидания	4.8 мин
Загрузка кассира 1	78%
Загрузка кассира 2	82%

Вывод: При 2 кассах образуются очереди. Нужно проанализировать целесообразность добавления третьей кассы.

Алгоритм дискретного события:

инициализация:
    время = 0
    очередь = []
    кассиры = [свободен, свободен]
    статистика = {}

пока время < время_работы:
    // Генерация нового покупателя
    если время >= время_следующего_покупателя:
        добавить покупателя в очередь
        время_следующего_покупателя += случайное_время(1,5)
    
    // Обслуживание покупателей
    для каждого кассира:
        если кассир свободен и очередь не пуста:
            взять покупателя из очереди
            кассир = занят на случайное_время(2,6)
            обновить статистику
    
    время += 1

вывести статистику

4 Системы массового обслуживания (СМО)

СМО — это система, которая обслуживает потоки заявок (требований). Состоит из обслуживающих приборов (каналов) и очереди заявок.

Классификация СМО (нотация Кендалла)

Распределение
входного потока

Распределение
времени обслуживания

Количество
каналов

Дисциплина
обслуживания

Примеры обозначений:

M/M/1 — Пуассоновский поток, экспоненциальное обслуживание, 1 канал
M/G/3 — Пуассоновский поток, произвольное обслуживание, 3 канала
G/D/2/FIFO — Общий поток, детерминированное обслуживание, 2 канала, очередь FIFO
M/M/n/0 — Система с отказами (нет очереди)

Одноканальная СМО с ожиданием (M/M/1)

Основные формулы:

Интенсивность входного потока: λ (заявок/час)
Интенсивность обслуживания: μ (заявок/час)
Загрузка системы: ρ = λ/μ
Среднее число заявок в системе: L = ρ/(1-ρ)
Среднее время в системе: W = 1/(μ-λ)

Пример: λ = 5 заявок/час, μ = 6 заявок/час
ρ = 5/6 ≈ 0.83, L = 0.83/(1-0.83) ≈ 5 заявок

Многоканальная СМО (M/M/n)

Параметры:

n — количество каналов
Вероятность простоя системы: P₀
Вероятность отказа (для СМО с отказами): P_отк
Средняя длина очереди: L_q

Пример: Колл-центр с 3 операторами
λ = 20 звонков/час, μ = 8 звонков/час на оператора
ρ = 20/(3×8) ≈ 0.83

5 Примеры решения задач ЕГЭ

Задача 1: Метод Монте-Карло для площади фигуры

Условие: Требуется оценить площадь фигуры, ограниченной кривыми y = x² и y = 4 на интервале [0, 2]. Используйте метод Монте-Карло с 10000 испытаний.

Решение:

Площадь прямоугольника: S_пр = 2×4 = 8
Генерируем случайные точки (x, y) где x∈[0,2], y∈[0,4]
Точка попадает в фигуру, если y ≤ x²
Площадь ≈ 8 × (N_внутри / N_всего)

Результат

≈ 2.67

Точное значение: 8/3 ≈ 2.6667

Задача 2: Анализ СМО

Условие: В банкомат приходит в среднем 30 клиентов в час. Обслуживание одного клиента занимает в среднем 1.5 минуты. Определите среднюю длину очереди и среднее время ожидания.

Решение:

λ = 30 клиентов/час
μ = 60/1.5 = 40 клиентов/час
ρ = λ/μ = 30/40 = 0.75
L = ρ/(1-ρ) = 0.75/0.25 = 3 клиента
W = L/λ = 3/30 = 0.1 часа = 6 минут

Ответ

Средняя очередь: 3 человека

Среднее время ожидания: 6 минут

Загрузка банкомата: 75%

Практические задания для ЕГЭ

Задание 1: Метод Монте-Карло

Оцените интеграл ∫₀¹ x³ dx методом Монте-Карло с 1000 испытаний. Сравните с точным значением.

Подсказка: Точное значение интеграла равно 1/4 = 0.25

Задание 2: СМО с отказами

На телефонную линию приходит в среднем 0.5 вызовов в минуту. Разговор длится в среднем 4 минуты. Какова вероятность того, что пришедший вызов получит отказ, если линия одна?

Формула: P_отк = ρ/(1+ρ) где ρ = λ/μ

Задание 3: Имитационное моделирование

Смоделируйте работу автозаправочной станции с 3 колонками. Автомобили приходят каждые 3±2 минуты. Заправка занимает 5±3 минуты. Оцените среднюю длину очереди за 12 часов работы.

Шпаргалка для ЕГЭ

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

Погрешность ≈ 1/√N
Для оценки интеграла: ∫f(x)dx ≈ (b-a)·(1/N)·∑f(x_i)

СМО M/M/1

ρ = λ/μ
L = ρ/(1-ρ)
W = 1/(μ-λ)
Условие стационарности: ρ < 1

СМО с отказами

Формула Эрланга:
P_отк = (ρⁿ/n!)/∑(ρ^k/k!)
для k=0..n

Распределения

M — экспоненциальное
G — общее (любое)
D — детерминированное
E_k — Эрланга k-го порядка

Ключевые моменты для ЕГЭ

При решении задач ЕГЭ по вероятностным моделям важно:

Определить тип модели

Выделить параметры

Выбрать метод решения

Проверить адекватность

Совет: На ЕГЭ сначала решите задачу аналитически, если возможно. Метод Монте-Карло используйте как проверку или когда аналитическое решение сложно.

4.4 Вероятностные модели. Методы Монте-Карло. Имитационное моделирование. Системы массового обслуживания