36217

Уравнения Колмогорова. Моделирование многоканальной СМО с ограничением на длину очереди

Доклад

Математика и математический анализ

Моделирование многоканальной СМО с ограничением на длину очереди Марковские процессы уравнения Колмогорова Случайный процесс t называется Марковским если его будущее не зависит от прошлого а определяется настоящим т. Примерами Марковских процессов являются при определенных предположениях процессы функционирования СМО.1 СМО может иметь установившийся стационарный режим. Для построения модели стационарного режима СМО положим все производные в системе 11 равными нулю.

Русский

2013-09-21

75.5 KB

53 чел.

Уравнения Колмогорова. Моделирование многоканальной СМО с ограничением на длину очереди

Марковские процессы, уравнения Колмогорова

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

Введем обозначения.

Пусть S1, S2, ..., Sn, … – возможные состояния марковского процесса с дискретным множеством состояний.

Pi(t) = P{(t) = Si}  вероятность нахождения процесса в момент t в состоянии Si

Pij(t, t + ) = P{ (t + ) = Sj / (t) = Si} – вероятность перехода из Si в Sj за время [t, t + ]. Если эти числа не зависят от t, то процесс называется однородным (стационарным). Поток случайных событий, соответствующих смене состояний процесса будем считать ординарным.

при i j – интенсивность перехода из Si в Sj в момент t.

Графом состояний Марковского процесса называется ориентированный граф G = (V, E), вершинами которого являются состояния процесса, а дуги соответствуют разрешенным переходам из  Si в Sj в случае ij 0, снабженных весами, равными значениям интенсивностей переходов ij. Пример графа Марковского процесса – на рис. 3.3.

Обозначим Г + (Si) и Г (Si) – множества вершин, смежных с Si и таких, что

Иными словами, Г + (Si) – это множество начальных вершин дуг, входящих в Si, а Г (Si) – множество конечных вершин дуг, выходящих из Si.

Теорема 3.2. При сделанных предположениях функции Pi(t), i = 1, ..., n удовлетворяют системе линейных дифференциальных уравнений А. Н. Колмогорова:

для всех i = 1,..., n   (3.11)

и начальным условиям Pi(0) =Piнач .

Отметим одно свойство системы (11). В уравнениях (11) член Pi(t)i k(t) входит со знаком “” в уравнение, соответствующее производной , как вес ребра, иcходящего из Si,  и со знаком “+” – в уравнение, соответствующее производной , как вес ребра, входящего в Sj. Для наглядности запишем это уравнение:

.

Это означает, что, сложив все уравнения (11) получим, что сумма их правых частей (а, следовательно, и левых) равна 0.

Для нестационарного режима это означает, что в любой момент времени выполняется равенство Pj(t) = Pj(0) = const, и если в начальный момент сумма вероятностей равна 1, то это будет выполняться при всех t.

Как было сказано в п. 3.1, СМО может иметь установившийся (стационарный) режим. Необходимым условием его существования является постоянство интенсивностей ij()  = ij. Для построения модели стационарного режима СМО положим все производные в системе (11) равными нулю. В результате получим систему алгебраических уравнений

.                                   (3.15)

В силу свойства уравнений (11), данная алгебраическая система вырождена, т.к. сумма правых частей равна нулю. Чтобы получить невырожденную систему необходимо любое из уравнений (15) заменить условием нормировки:       Pj = 1. Полученные уравнения и будут моделью стационарного режима СМО.

Многоканальная система с ограничением на длину очереди

В систему, содержащую n обслуживающих каналов, поступает простейший поток заявок интенсивности . Если заявка поступает в момент, когда канал обслуживания свободен, а накопитель пуст, то СМО приступает к обслуживанию заявки. Если заявка поступает в момент обслуживания, то заявка становится в очередь и помещается в ячейку накопителя. Если все ячейки заняты, заявка покидает систему не обслуженной. Как только закончится обслуживание заявки, система приступает к обслуживанию заявки из накопителя, ячейка при этом освобождается. Если после окончания обслуживания накопитель пуст, то СМО переходит в состояние ожидания. Поток обслуженных заявок также является простейшим с интенсивностью .

На основании свойства аддитивности простейшего потока, интенсивность обслуживания заявок k каналами равна k. Иными словами, если в данный момент загружено k каналов, то интенсивность освобождения одного занятого канала равна k. Процесс, описывающий изменение состояний СМО, является Марковским с графом, приведенным на рис. 3.4.

Пример 3.2. Пусть m = 1; n = 1, т.е. система имеет 1 обслуживающий канал и накопитель с 1 ячейкой. Граф состояний имеет вид, как на рис. 3.5.

Система дифференциальных уравнений Колмогорова для данной системы имеет вид

                                         (3.16)

 

Для построения модели стационарного режима СМО положим все производные в системе (16) равными нулю. В результате получим систему алгебраических уравнений

.                                           (3.17)

Данная система вырождена, т.к. сумма правых частей равна нулю. Чтобы получить невырожденную систему необходимо любое из уравнений (17), например второе заменить условием нормировки: Pj = 1. Получим следующую систему

.                                                     (3.18)

При = получаем P0 = P1 = P2 = 1/3, т.е. третья часть заявок получает отказ, хотя интенсивности поступления заявок и обслуживания равны, и есть возможность ожидания одной заявки в очереди. На основании полученных значений Рj можно, пользуясь материалом п. 3.1 и таблицей 3.1 распределений вероятностей, можно вычислить все характеристики данной СМО.


 

А также другие работы, которые могут Вас заинтересовать

17844. ИНСТРУМЕНТЫ ОРГАНИЗАЦИИ МЕЖБЮДЖЕТНЫХ ВЗАИМООТНОШЕНИЙ 66.5 KB
  Тема 10. ИНСТРУМЕНТЫ ОРГАНИЗАЦИИ МЕЖБЮДЖЕТНЫХ ВЗАИМООТНОШЕНИЙ План 1. Инструменты межбюджетных отношений 2. Межбюджетные отношения в зарубежных странах 3. Проблемы совершенствования межбюджетных отношений в Украине 1. Инструменты межбюджетных отношений М
17845. БЮДЖЕТНЫЕ ТРАНСФЕРТЫ 69.5 KB
  Тема 11. БЮДЖЕТНЫЕ ТРАНСФЕРТЫ План 1. Понятие бюджетных трансфертов и их правовое регулирование 2. Зарубежный опыт использования бюджетных трансфертов 3. Проблемы совершенствования системы трансфертов в Украине 1. Понятие бюджетных трансфертов и их правовое
17846. ЦЕЛИ И ЗАДАЧИ ГОСУДАРСТВЕННОЙ РЕГИОНАЛЬНОЙ ФИНАНСОВОЙ ПОЛИТИКИ 59.5 KB
  Тема 12. ЦЕЛИ И ЗАДАЧИ ГОСУДАРСТВЕННОЙ РЕГИОНАЛЬНОЙ ФИНАНСОВОЙ ПОЛИТИКИ 1. Понятие государственная региональная финансовая политика 2. Цели государственной региональной финансовой политики 3. Задача государственной региональной финансовой политики 4. Регио
17847. КОМПЕТЕНЦИЯ МЕСТНЫХ ОРГАНОВ ВЛАСТИ В ОБЛАСТИ ФИНАНСОВ 86.5 KB
  Тема 13. КОМПЕТЕНЦИЯ МЕСТНЫХ ОРГАНОВ ВЛАСТИ В ОБЛАСТИ ФИНАНСОВ План 1. Составление утверждение и выполнение местного бюджета 2. Бюджетный процесс 3. Образование внебюджетных целевых резервных и валютных фондов 4. Установление местных налогов и сборов Под ко...
17848. МЕСТНЫЕ ФИНАНСОВЫЕ ОРГАНЫ И ИХ ФУНКЦИИ 39 KB
  Тема 14. МЕСТНЫЕ ФИНАНСОВЫЕ ОРГАНЫ И ИХ ФУНКЦИИ План 1. Виды местных финансовых органов 2. Местные финансовые органы в зарубежных странах 1. Виды местных финансовых органов Управление местными финансами осуществляется местными представительными и исполнительн...
17849. ОРГАНИЗАЦИЯ КАССОВОГО ИСПОЛНЕНИЯ МЕСТНЫХ БЮДЖЕТОВ, КОНТРОЛЯ И АУДИТА В МЕСТНЫХ ОРГАНАХ ВЛАСТИ 67 KB
  Тема 15. ОРГАНИЗАЦИЯ КАССОВОГО ИСПОЛНЕНИЯ МЕСТНЫХ БЮДЖЕТОВ КОНТРОЛЯ И АУДИТА В МЕСТНЫХ ОРГАНАХ ВЛАСТИ План 1. Понятие и системы кассового исполнения местных бюджетов 2. Оборотная кассовая наличность 3. Кассовое исполнение местных бюджетов в зарубежных странах ...
17850. Совершенная конкуренция 7.08 MB
  Задача 4 Тема Совершенная конкуренция Исходные данные: Год рождения студента ГР = 1980 Месяц рождения студента МР = 4 День рождения студента ДР = 21 На рынке совершенной конкуренции отраслевой спро
17851. Монополия. Задача 1.98 MB
  Задача 5 Тема: Монополия Исходные данные: Год рождения студента ГР = 1999 Месяц рождения студента МР = 5 День рождения студента ДР = 23 Рыночная функция спроса имеет следующий вид: QD = ГР/3 – 05×МР×P = 666 – 25Р Фу
17852. Потребительский выбор 1.1 MB
  Задача 1 Тема Потребительский выбор Исходные данные: Год рождения студента: ГР = 1985 Месяц рождения студента: МР = 1 День рождения студента: ДР = 3 Функция полезности потребителя: TU = ГР × А × В =1985АВ Доход потребителя: I = ГР = 1985 Цена блага А: PА = 5 × ДР = ...