- •1. Системы массового обслуживания
- •1.1. Основные понятия смо
- •Классификация смо
- •Характеристики смо
- •Связи между основными характеристиками (формулы Литтла)
- •1.2. Потоки заявок
- •1.2.1. Простейший (пуассоновский) поток
- •1.2.2. Потоки Эрланга
- •Аппроксимация произвольного потока заявок потоком Эрланга
- •1.2.3. Верификация потоков заявок
- •Критерий Пирсона
- •Критерий Колмогорова
- •Расчеты для проверки гипотезы по критерию Колмогорова
- •1.3. Марковские процессы
- •1.3.1. Марковские процессы с дискретными состояниями и дискретным временем перехода
- •1.3.2. Марковские процессы с дискретными состояниями и непрерывным временем перехода
- •1.3.3. Процессы гибели и размножения
- •1.4. Пуассоновские смо
- •1.4.1. Одноканальные пуассоновские смо
- •1.4.2. Многоканальные пуассоновские смо
- •1.4.3. Смо с взаимопомощью каналов
- •Смо без очереди
- •С мо с неограниченной очередью
- •Смо с ограниченной очередью
- •1.4.4. Смо самообслуживания
- •1.4.5. Замкнутые смо
- •Одноканальные замкнутые смо
- •Многоканальные замкнутые смо
- •1.4.6. Многофазные смо
- •Многофазные смо без потерь
- •Многофазные смо без очереди
- •1.5. Пуассоновские сети смо
- •1.5.1. Ациклические сети смо
- •1.5.2. Циклические сети смо
- •1.6. Непуассоновские смо
- •1.6.1. Анализ непуассоновских смо методом Эрланга
- •1.6.2. Анализ непуассоновских смо методом вложенных цепей Маркова
- •1.7. Смо с приоритетами
- •1.7.1. Одноканальные смо с приоритетами
- •1.7.2. Многоканальные смо с приоритетами
- •1.8. Оптимизация параметров смо
- •Задача оптимальной интенсивности обслуживания в одноканальной смо с бесконечной очередью
- •Задача оптимальной интенсивности в одноканальной смо без очереди
- •Задачи оптимизации параметров многоканальной смо
- •Задачи оптимизации смо по нескольким параметрам
1.3. Марковские процессы
Математический аппарат марковских процессов используется для анализа систем массового обслуживания. Поэтому прежде чем переходить к анализу СМО, остановимся на марковских процессах. Причем будем рассматривать только те вопросы, которые требуются для анализа СМО.
Пусть в объекте моделирования определены состояния , например, в системе массового обслуживания:
– в СМО нет заявок,
– в СМО одна заявка,
– в СМО две заявки и т.д.
C течением времени СМО переходит из одного состояния в другое.
Рассмотрим марковские процессы с дискретными состояниями (число состояний конечно или счетно). При этом выделим:
а) марковские процессы с дискретным временем перехода (моменты перехода заранее определены);
б) марковские процессы с непрерывным временем перехода (момент перехода не определен, случаен).
Отметим, что марковские процессы обладают свойством безпоследействия.
1.3.1. Марковские процессы с дискретными состояниями и дискретным временем перехода
Пусть система находится в состоянии , где .
Для задания марковского процесса необходимо определить матрицу вероятностей перехода из одного состояния в другое.
Пример матрицы переходов:
Для заданной матрицы граф переходов имеет вид:
Так как на каждом следующем шаге система переходит в другое состояние, то .
Пусть задан вектор вероятностей в первый момент времени:
.
Какова вероятность нахождения системы в состоянии i после первого перехода?
. (1.6)
В векторном виде (1.6): .
На шаге получим уравнение:
. (1.7)
Если (не зависит от шага), то процесс называется однородным.
При устремлении к бесконечности получим вектор предельных вероятностей:
.
Процесс, в котором вектор предельных вероятностей не зависит от вектора начального состояния, называется эргодическим.
Если матрица переходов неприводима (т.е. из каждого состояния можно достигнуть любое другое состояние), то существует вектор предельных вероятностей.
Пример неприводимой матрицы переходов:
1.3.2. Марковские процессы с дискретными состояниями и непрерывным временем перехода
Пусть система может находиться в состояниях ( ).
Время перехода – случайная величина.
– интенсивность перехода из состояния в .
За время вероятность перехода .
Если (не зависит от времени), то это однородный марковский процесс.
Рассмотрим случай с двумя состояниями:
Составим конечно–разностное уравнение для определения .
Для первого состояния:
(1.8)
. (1.9)
Из (1.8) получим:
,
. (1.10)
Из (1.9) получим
. (1.11)
Следует иметь в виду, что в любой момент .
Примем за начальное состояние системы , тогда решением дифференциального уравнения (1.10) будет:
(1.12)
. (1.13)
Графически (1.12) и (1.13) представлены на рис. 1.6.
При стремлении к бесконечности получим предельные вероятности: .
Для определения и приравняем производные из системы уравнений (1.10) и (1.11) к нулю:
Получим:
Рассмотрим случай для четырех состояний (рис. 1.7). Для простоты изображения размеченного графа будем опускать.
Рис.1.7. Размеченный граф
Система уравнений для данного графа приведена ниже.
.
В общем случае, когда число состояний , система уравнений примет вид:
.
Эту систему уравнений по имени автора называют системой уравнений Колмогорова.
Для определения предельных вероятностей получим систему линейных уравнений:
( ),
.