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 распределений вероятностей, можно вычислить все характеристики данной СМО.


 

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

66010. Государственные предприятия, государственные корпорации, объединения предприятий, дочерние и зависимые общества 59 KB
  Все они направлены на использование преимуществ крупного капитала но отличаются друг от друга: Конкретными стратегическими целями и текущими задачами которые ставятся объединением ; Структурой участников; Установленными имущественными и правовыми отношениями; Понятие и сущность...
66012. Немецкая и американская модель ипотечного кредитования 18.96 KB
  Период кредитования начинается когда член кассы накапливает половину той суммы что нужна на покупку жилья. Период накопления заменяется периодом внесения вкладов в долговое участие в строительстве а период кредитования периодом покупки в рассрочку или аренды с правом выкупа.
66013. Инвестиционный рейтинг регионов 97.5 KB
  Рейтинг крупнейшего независимого агентства Эксперт РА это взаимосвязанная оценка двух осей инвестиционной привлекательности: риска и потенциала. Им в ходе оценки составляющих инвестиционного климате инвестиционного риска и потенциала используется около двух сотен исходных количественных и качественных характеристик.
66014. Внутренний долг РФ с 2007-2012 года 55.46 KB
  Структура и динамика государственного внутреннего долга по состоянию на 1 мая 2007 года в части государственных ценных бумаг номинированных в валюте Российской Федерации Виды государственных ценных бумаг млрд.
66015. Внешняя задолженность 28.59 KB
  В случае внешнего государственного долга кредиторами правительства выступают: иностранные государства иностранные юридические лица международные финансовые институты МВФ связанный с ним Парижский клуб Лондонский клуб Всемирный банк.
66016. Международный валютный фонд, МВФ 33.27 KB
  На Бреттон-Вудской конференции ООН по валютно-финансовым вопросам 22 июля 1944 года была разработана основа соглашения Хартия МВФ. Наиболее существенный вклад в разработку концепции МВФ внесли Джон Мейнард Кейнс возглавлявший британскую делегацию...
66017. Антикризисная программа Китая 34 KB
  Учитывая что промышленность этой страны в большей части ориентирована на экспорт а мировой и в первую очередь американский спрос с учетом кризиса существенно снизился китайское правительство в своих планах по поддержке экономики сделало ставку...
66018. Бюджетные системы зарубежных стран 31 KB
  Принцип обязательного облечения бюджета в форму акта, принимаемого представительным органом власти, означает требование законодательного оформления бюджета. В большинстве стран бюджет принимается в виде закона