Стационарный режим для непрерывной цепи Маркова

Известно, что все потоки событий - простейшие (стационарные пуассоновские) потоки. Поставим теперь следующий вопрос: что будет происхо­дить с системой S при ? Будут ли функции стре­миться к каким-то пределам? Эти пределы, если они сущест­вуют, называются предельными вероятностями состояний.

Можно доказать следующее общее положение. Если чис­ло состояний системы S конечно и из каждого состояния мож­но перейти (за то или иное число шагов) в каждое другое, то предельные вероятности состояний существуют и не зави­сят от начального состояния системы.

Таким образом, если поставленное условие выполне­но, то при в системе устанавливается некоторый предельный стационарный режим. Он состоит в том, что сис­тема случайным образом меняет свои состояния, но вероят­ность каждого из них уже не зависит от времени: каждое из состояний осуществляется с некоторой постоянной вероят­ностью. Эта вероятность представляет собой не что иное, как среднее относительное время пребывания системы в дан­ном состоянии. Например, если у системы S три возможных состояния: , причем их предельные вероятности равны 0.2, 0.3,0.5, то это означает, что после перехода к установившемуся режиму система S в среднем две десятых времени будет находиться в состоянии , три десятых - в состоянии , половину времени - в состоянии .

Для вычисления предельных вероятностей необходимо в системе уравнений Колмогорова положить все левые части (производные) равными нулю. Действительно, в предельном (установившемся) режиме все вероятности состояний постоян­ны, значит, их производные равны нулю.

Следовательно, система дифференциальных уравнений превращается в систему линейных алгебраических уравне­ний, точнее, в систему однородных уравнений (без сво­бодных членов). Для получения решения требуется одно из уравнений системы заменить на нормировочное уравнение

Для примера, рассмотренного выше:

9.3. Марковский случайный процесс «гибели и размножения»

 

В приведенном выше примере состояния системы образуют цепь, каждое состояние, кроме исходного и последнего, связано прямой и обратной связью с двумя соседними состояниями. Крайние состояния связаны с одним соседним. Такая схема процесса, протекающего в системе, называется схемой «Гибели и размножения», а сам процесс называют процессом «гибели и размножения».

Если в такой системе все потоки, переводящие систему из состояния в состояние Пуассоновские, то процесс называется Марковским случайным процессом «гибели и размножения».

Термин ведет начало от биологических задач, процесс описывает изменение численности популяции. Переход из состояния в состояние происходит в момент гибели или рождения особи.

На практике значительная часть систем может описываться в рамках процесса «гибели и размножения».

 

10. Элементы теории массового обслуживания, применяемые при моделировании систем

10.1. Основные определения и понятия. Структура СМО. Классификация СМО

 

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

Первые задачи теории систем массового обслуживания (ТСМО) были рассмотрены сотрудниками Копенгагенской телефонной компании, датским ученым А.К. Эрлангом (1878г. – 1929г.) в период между 1908 и 1922гг. Эти задачи были вызваны к жизни стремлением упорядочить работу телефонной сети и разработать методы, позволяющие заранее повысить качество обслуживания потребителей в зависимости от числа используемых устройств. Оказалось, что ситуации, возникающие на телефонных станциях, являются типичными не только для телефонной связи. Работа аэродромов, работа морских и речных портов, магазинов, терминальных классов, радиолокационных комплексов, радиолокационных станций и т.д. и т.д. может быть описана в рамках ТСМО.

Приведем примеры систем массового обслуживания.

Пример 1. Телефонная связь времен Эрланга представляла собой телефонную станцию, связанную с большим числом абонентов. Телефонистки станции по мере поступления вызовов соединяли телефонные номера между собой.

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

Пример 2. Система скорой помощи некоего городского района представляет собой пункт, который принимает на выполнение некоторое количество автомашин скорой помощи и несколько врачебных бригад.

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

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

Задача: Обеспечить определенный объем перевозок при минимальных расходах. При этом сохранить простои судов при погрузочно-разгрузочных работах.

Пример 4. Система обработки информации содержит мультиплексный канал и несколько компьютеров. Сигналы от датчиков поступают на мультиплексный канал, где буферизуются и предварительно обрабатываются. Затем поступают в тот компьютер, где очередь минимальна.

Задача: Обеспечить ускорение обработки сигналов при заданной суммарной длине очереди.

На рис. 13 изображена структурная схема типичной системы массового обслуживания – ремонтного предприятия.

Нетрудно привести множество других примеров из самых различных областей деятельности. Характерным для таких задач является:

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

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

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

 

 

 

Рис. 13. Структурная схема типичной системы массового обслуживания – ремонтного предприятия

 

 

Структура СМО. Все СМО имеют вполне определенную структуру, изображенную на рис. 14.

 

 

 

Рис. 14.