Модели случайных и хаотических блужданий

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

Есть точка на прямой, имеющая начальную координату x₀, которая движется вправо или влево в зависимости от случайной величины r из интервала [0,1] если r>0,5, то точка делает шаг вправо x₁=х₀+h, в противном случае x₁=x₀-h. Шаг может быть как постоянный, так и переменный. Значение шага в свою очередь может быть случайное число из интервала [0,h_max].

Точка может двигаться по плоскости, может быть n точек - получается модель броуновского движения. Можно ввести различные скорости движения частиц, можно изменять условие, скажем если r_i>0,8, то точка делает шаг вправо x₁=х₀+h, в противном случае x₁=x₀-h. - получим модель поступательного движения частиц вправо - стая комаров, подхваченных ветром. Если первоначально все частицы сконцентрировать в одной точке, а потом пронаблюдать их распространение - то это будет модель взрыва. Если провести вертикальную черту - перегородку, и частицы по разную строну перегородки закрасить разным цветом - получим модель диффузии - смешивания различных газов или жидкостей и т.д.

В модели пьяницы не предусматривается столкновение частиц.

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

 

Генерация случайных чисел. Генераторы случайных чисел. Методика использования. Виды генераторов. Различные алгоритмы генерации случайных чисел. Оценка эффективности работы генераторов.

 

РАЗДЕЛ 4. СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ И МОДЕЛИ ПРОГНОЗИРОВАНИЯ

Теория марковских процессов. Случайный процесс, марковский процесс, поток событий, простейшие потоки. Составление уравнений Колмогорова. Финальные вероятности состояний.

 

 

Модели потоков

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

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

Каждая СМО предназначена для обслуживания (выполнения) некоторого потока заявок (требований), поступающих на вход системы большей частью не регулярно, а в случайные моменты времени. Обслуживание заявок, в общем случае, также длится не постоянное, заранее известное время, а случайное время, которое зависит от многих случайных, порой неизвестных нам, причин. После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времени их обслуживания приводит к неравномерной загруженности СМО: в некоторые промежутки времени на входе СМО могут скапливаться не обслуженные заявки, что приводит к перегрузке СМО, в некоторые же другие интервалы времени при свободных каналах на входе СМО заявок не будет, что приводит к недогрузке СМО, т.е. к простаиванию ее каналов. Заявки, скапливающиеся на входе СМО, либо "становятся" в очередь (т.е. образуют список объектов подлежащих обработке), либо по какой-то причине невозможности дальнейшего пребывания в очереди покидают СМО не обслуженными. Закон, определяющий порядок обслуживания входных заявок, называется дисциплиной очереди. Для примера рассмотрим автозаправочную станцию с одной колонкой. Площадка при станции, на которой машины ожидают заправку, может вместить не более трех машин одновременно, и если она занята, то очередная машина, прибывшая к станции, в очередь не становится, а проезжает на соседнюю станцию. В среднем машины прибывают на станцию каждые две мин. Процесс заправки полной машины продолжается в среднем 2,5 мин. Моделью данной АЗС является одноканальная СМО с ожиданием и ограничением на длину очереди (m=3). Каналом является колонка.

Схема СМО в общем виде изображена на рисунке.

 

 

Входящий Поток обслуженных заявок

поток заявок

....

n

Вход Выход

Поток необслуженных

(покинувших очередь) заявок

 

Таким образом, во всякой СМО можно выделить следующие основные элементы:

1) входящий поток заявок;

2) очередь;

3) каналы обслуживания;

4) выходящий поток обслуженных заявок.

 

Модели потоков

 

Потоком событий (в данном случае заявок) называют последовательность событий, наступающих одно за другим в какие-то заранее неизвестные, случайные моменты времени. Вид и параметры закона распределения входящего потока определяется характером физических процессов, протекающих в моделируемом объекте. Как показывает опыт, для составления системы моделей в основном используются следующие распределения входящего потока: показательное, Эрланга к- ого порядка, Релея, нормальное, равномерное. Случайный характер потока заявок и длительности их обслуживания порождает в СМО случайный процесс.

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

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

Классификация потоков.

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

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

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

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

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

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

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

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

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

1. Показатели эффективности использования СМО:

1.1. Абсолютная пропускная способность СМО - среднее число заявок, которое сможет обслужить СМО в единицу времени.

1.2. Относительная пропускная способность СМО - отношение среднего числа заявок, обслуживаемых СМО в единицу времени, к среднему числу поступивших заявок за это же время.

1.3. Средняя продолжительность периода занятости СМО.

1.4. Коэффициент использования СМО - средняя доля времени, в течение которого СМО занята обслуживанием заявок, и т.п.

2. Показатели качества обслуживания заявок:

2.1. Среднее время ожидания заявки в очереди.

2.2. Среднее время пребывания заявки в СМО.

2.3. Вероятность отказа заявке в обслуживании безожидания.

2.4. Вероятность того, что поступившая заявка немедленно будет принята к обслуживанию.

2.5. Закон распределения времени ожидания заявки в очереди.

2.6. Закон распределения времени пребывания заявки в СМО.

2.7. Среднее число заявок, находящихся в очереди.

2.8. Среднее число заявок, находящихся в СМО, и т.п.

3. Показатели эффективности функционирования пары "СМО — потребитель", где под "потребителем" понимают всю совокупность заявок или некий их источник (например, средний доход, приносимый СМО в единицу времени, который рассчитывается по формуле I=c₁n-c₂r где n -среднее число заявок в очереди, r среднее число свободных обслуживающих приборов с₁ -стоимость ожидания одной заявки в единицу времени, с₂ - стоимость простоя одного прибора в единицу времени) и т.п.

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