36217

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

Доклад

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

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

Русский

2013-09-21

75.5 KB

57 чел.

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

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

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


 

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

52332. Впровадження інноваційних технологій у формуванні компетентного учня на уроках біології 71 KB
  Умовами їх використання є: створення психологічного клімату на уроці наявність соціальних навичок уміння учнів спілкуватися бажання вчителя спілкуватися з учнями “на рівних “. 1 Я переконалась що застосування інтерактивних технологій є результативнішим в порівнянні з пасивними методами навчання: у моїх учнів краще розвиваються комунікативні вміння і навики; вони навчилися краще працювати в команді прислухатися до думки кожного; діти удосконалили вміння шукати і аналізувати інформацію захищати...
52333. Органические соединения: микро- и макромолекулы. Углеводы: строение, свойства, функции 57 KB
  Цели урока: содействовать формированию у учащихся понятий макро и микромолекулы органические соединения; обеспечить условия для углубления знаний о роли углеводов в живом организме о связи между строением и свойствами углеводов; создать условия для формирования у учащихся общеучебных приемов и способов учебной деятельности: умения составлять схемы и таблицы работать с учебником и дополнительной литературой использовать данные экспериментов работать индивидуально и в группах; умение решать проблемные вопросы. Чтобы ответить на...
52334. Неклітинні форми життя – віруси 3.48 MB
  Мета: вивчити будову, властивості, механізм проникнення вірусів у клітину. Зясувати роль вітчизняних вчених у розвиток вірусології. Розвивати у учнів комунікативну та самоосвітню компетентність. Виховувати повагу до свого здоров’я.
52336. АЛГОРИТМ ФОРМУВАННЯ ВМІНЬ ВИКОРИСТОВУВАТИ ЗНАННЯ ПРИ РОЗВ’ЯЗАННІ ТИПОВИХ ЗАДАЧ З МОЛЕКУЛЯРНОЇ БІОЛОГІЇ 309.5 KB
  ПРИКЛАДИ РОЗВЯЗАННЯ ЗАДАЧ НА МОЛЕКУЛЯРНІ ОСНОВИ СПАДКОВОСТІ Під час розвязання таких задач необхідно памятати що: довжина одного нуклеотида або відстань між двома сусідніми вздовж осі ДНК становить 034 нм; середня молекулярна маса одного нуклеотида 345 умовних одиниць; середня молекулярна маса однієї амінокислоти дорівнює 100 умовних одиниць; молекула білка в середньому складається з 200 амінокислот; кожну амінокислоту в білковій молекулі кодує триплет нуклеотидів іРНК під час трансляції; для визначення довжини гена l...
52337. Запліднення і внутрішньоутробний розвиток людини 621 KB
  Мета: створити умови для: усвідомленого інформаційного запиту про ембріональний розвиток людини; розуміння учнями значущості знань про індивідуальний розвиток людини; формування морального відношення до зачаття і вагітності, відповідальності за життя, яке не народилось;
52338. Основні групи м’язів тіла людини. Фізичні якості м’язів 50 KB
  Обладнання: таблиця Мязи людини роздаткові картки підручник Біологія 9 клас автор А.Вступ До опорнорухової системи людини належить на лише скелет людини але й мязи які мають властивість збуджуватися і скорочуватися і в результаті виконують основну функцію рухову. До речі скелетні мязи складають близько 40 маси тіла людини. Скелетні мязи виконують функцію мязового насоса при чому покращується рух венозної крові до серця.
52340. Суцвіття 550 KB
  Мета уроку: сформувати поняття суцвіттязнайомити учнів з функціями суцвіть розглянути їх будову і різноманітність; розвивати: вміння виділяти головне порівнюватиузагальнювати систематизувативміння розпізнавати суцвіття і тренувати їх у застосуванні набутих знань у нестандартних ситуаціях; виховувати: естетичні смаки учнів відповідальність за стан навколишнього середовища бережливе ставлення до природи. Обладнання: таблиці: Будова квітки Будова суцвіть Прості суцвіття Складні суцвіттякартки з кросвордом схемою та...