- •5. Части графа. Связность графа. Дерево. Лес. Гамильтонов цикл и гамильтонов граф. Взвешенный граф. Рассмотрим граф g(X, u). Рассмотрим подмножество вершин X’cX и подмножество ребер u’cU.
- •1. Разработка математической модели задачи
- •2). Отдельные работы, помимо полного резерва, имеют свободный резерв времени, составляющий часть полного резерва, остающуюся после исключения резерва времени r(xj) конечного события данной работы
- •11. Анализ сетевых моделей. Определение критического пути. Оптимизация сетевых моделей. См. Вопр. 10.
- •14. Случайные процессы. Марковский случайный процесс. Условия возникновения Марковского процесса. Рассмотрим понятие случайного процесса.
- •15. Граф состояний смо. Уравнения Колмогорова. Как правило, смо изображают ввиде размеченного (взвешенного) графа состояний.
- •17. Одноканальная смо с откащами в обслуживании и ее характеристики. Система с отказами: отсутствует очередь.
- •18. Многоканальная смо с отказами в обслуживании и ее характеристики. Примерами многоканальных смо с отказами являются: офисы коммерческих предприятий с несколькими телефонными каналами и т. Д.
- •20. Одноканальная смо с неограниченной очередью и ее характеристики.
15. Граф состояний смо. Уравнения Колмогорова. Как правило, смо изображают ввиде размеченного (взвешенного) графа состояний.
Рассмотрим пример:
Система «S» может находиться в четырех состояниях «S1», «S2», «S3», «S4». Переход системы из состояния в состояние происходит под действием потоков с интенсивностями λij (см. рисунок)
Имея размеченный граф состояний, можно найти все вероятности состояний pi(t) как функции времени. Для этого составляются и решаются уравнения Колмогорова — особого вида дифференциальные уравнения.
dp1(t)/dt=-λ12p1(t)-λ13p1(t)+λ21p2(t)
dp2(t)/dt=-λ21p2(t)-λ24p2(t)+λ12p1(t)+λ32p3(t)
dp3(t)/dt=λ13p1(t)+λ43p4(t)-λ32p3(t)
dp4(t)/dt=λ24p2(t)-λ43p4(t)
Обязательно добавляется еще одно уравнение:
p1(t)+p2(t)+p3(t)+p4(t)=1 (нормировочное условие)
Эта система линейных ДУ решается при начальных условиях: t=0; pi(t)=1; pj(t)=0; i≠j; i=1, …, n; pi(t) — вероятность какого-то состояния; pj(t) — все остальные вероятности.
Решая систему линейных ДУ, можно получить вероятность всех состояний как функций времени: p1(t); p2(t); p3(t); p4(t).
Как меняются вероятности pj(t) со временем? Стремятся ли они к какому-либо пределу?
Оказывается, если СМО проработала достаточное количество времени, наступает в системе предельный стационарный режим. Условно пишут, что он наступает при t→∞. В данном режиме вероятности состояния системы pj(t) стремятся к своим предельным значениям, которые не зависят от времени: pj(t)→pj. Их называют финальными вероятностями. В этом случае в ДУ Колмогорова левые части приравниваются к 0, т. е. dpi(t)/dt=0, и система ДУ Колмогорова превращается в систему линейных уравнений.
0=λ21p2-(λ12+λ13)p1
0=λ12p1+λ32p3-(λ24+λ21)p2
0=λ13p1+λ43p4-λ32p3
0=λ24p2-λ43p4
По физическому смыслу финальная вероятность представляет собой среднюю долю времени нахождения системы в соответствующем состоянии. Напр., p1=20%. Это означает, что в среднем 20% времени СМО будет находиться в состоянии «S1».
Поскольку данная система (2) не содержит свободных членов, она имеет бесчисленное множество решений. Поэтому, чтобы ее решить, необходимо добавить такое условие
p1+p2+p3+p4=1 — нормировочное условие.
Работа СМО характеризуется показателями эффективности (характеристики СМО).
Показатели эффективности рассчитываются только для предельного стационарного режима. Поэтому для определения показателей эффективности, необходимо составлять не ДУ Колмогорова, а систему линейных уравнений для финальных вероятностей.
16. Процессы «рождения-гибели» среди однородных Марковских процессов. Имея размеченный граф состояний, можно легко написать систему линейных уравнений для финальных вероятностей. Для некоторых случаев удается данные уравнения решить заранее в общем виде. В частности, это удается сделать, если граф состояния системы представляет собой так называемую «схему рождения и гибели» (см. рисунок).
Особенностью данного графа является то, что все состояния системы можно «вытянуть» в одну цепочку.
Термин «схема рождения и гибели» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.
Примером модели чистого рождения является процесс оформления свидетельства о рождении детей. В качестве модели чистой гибели может служить случайное изъятие хранящихся на складе запасов (без пополнения).
Пользуясь графом, составим и решим алгебраические уравнения для финальных вероятностей:
S0: 0=-λ01p0+λ10p1 => λ01p0=λ10p1 => p1=λ01p0/λ10
S1: 0=λ01p0-λ10p1-λ12p1+λ21p2 => -(λ10p1-λ01p0)-λ12p1=λ21p2 => λ12p1=λ21p2 => p2=λ12p1/λ21 => (подстановка p1) p2=λ01λ12p0/λ10λ21
… p3=λ01λ12λ23p0/λ10λ21λ32
… pn=λn-1,n … λ12λ01p0/λn,n-1 … λ21λ10
Т. о., все вероятности состояний СМО p0, p1, p2, …, pn можно выразить через одну вероятность — p0.
Подставим выражения для всех вероятностей p1, p2, …, pn в нормировочное условие. Получим:
p0(1+λ01/λ10+λ12λ01/λ21λ10+…+λn-1,n…λ12λ01/λn,n-1…λ21λ10)=1
Отсюда:
p0=(…)-1
Остальные вероятности вычисляются через p0. Полученные формулы используются при решении задач теории МО.