Основные вопросы моделирования

Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 19.1. Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S₁, S₂, ..., S_n-1) связано прямой и обратной стрелкой с каждым из соседних состояний -- правым и левым, а крайние состояния (S₀, S_n) -- только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

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

Пользуясь графом рис. 19.1, составим и решим алгебраические уравнения для финальных вероятностей состояний (их существование вытекает из того, что из каждого состояния можно перейти в каждое другое, и число состояний конечно). Для первого состояния S₀ имеем:

(8.1)

Для второго состояния S₁:

В силу (8.1) последнее равенство приводится к виду

далее, совершенно аналогично



и вообще

где k принимает все значения от 0 до n. Итак, финальные вероятности р₀, p₁,..., р_n удовлетворяют уравнениям

(8.2)

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

p₀ + р₁+ р₂+…+ р_n=1 (8.3)

Решим эту систему уравнений. Из первого уравнения (8.2) выразим р₁ через р₀.

(8.4)

Из второго, с учетом (8.4), получим:

(8.5)

из третьего, с учетом (8.5),

(8.6)

и вообще, для любого k (от 1 до N):

(8.7)

Обратим внимание на формулу (8.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния S_k), а в знаменателе -- произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до S_k).

Таким образом, все вероятности состояний p₁, р₂, …, p_n выражены через одну из них (p₀). Подставим эти выражения в нормировочное условие (8.3). Получим, вынося за скобку p₀:

отсюда получим выражение для р₀.

(8. 8)

(скобку мы возвели в степень -1, чтобы не писать двухэтажных дробей). Все остальные вероятности выражены через р₀ (см. формулы (8.4) -- (8.7)). Заметим, что коэффициенты при p₀ в каждой из них представляют собой не что иное, как последовательные члены ряда, стоящего после единицы в формуле (8.8). Значит, вычисляя р₀, мы уже нашли все эти коэффициенты.

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

Задачи теории массового обслуживания. Классификация систем массового обслуживания и их основные характеристики

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

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

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

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

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

Классификация СМО и их основные характеристики

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

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

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

Кроме этих признаков, СМО делятся на два класса: «открытые» и «замкнутые». В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО -- зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже неисправно и ждет наладки. Это -- пример замкнутой СMO.

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

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

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

Условимся все потоки событий, переводящие СМО из состояния в состояние, считать пуассоновскими.

Одноканальная система массового обслуживания с отказами

Простейшая задача. Пусть СМО состоит только из одного канала (n=1) и на нее поступает пуассоновский поток заявок с интенсивностью , зависящей в общем случае от времени =(t) (9.1). Заявка, заставшая канал занятым, получает отказ и покидает систему. Обслуживание заявки продолжается в течение случайного времени Т_об, распределенного по показательному закону с параметром f(t)= e^-t (t0) (9.2).

Из этого следует, что «поток обслуживаний» - простейший, с интенсивностью . Требуется найти: абсолютную (А) и относительную (q) пропускные способности.

Рассмотрим единственный канал обслуживания как физическую систему S, которая может находиться в одном из двух состояний: S₀ - свободен, S₁ - занят. Обозначим вероятности состояний p₀(t) и p₁(t). Очевидно:

t p₀(t)+p₁(t)=1 (9.3).



Рис.

Граф состояний системы

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

(9.4)

В соответствии с (9.3) одно уравнение в (9.4) лишнее. Отбросим второе уравнение, а первое перепишем с учетом (9.3):

или (9.5).

Это уравнение естественно решать при начальных условиях p₀(0)=1; p₁(0)=0. Уравнение (9.5) легко может быть решено не только для простейшего потока заявок (=const), но и для случая =(t). Приведем решение (9.5) только для случая =const: .

Рис.

Для нашего случая вероятность p₀ есть не что иное, как q.

Действительно, p₀ есть вероятность того, что в момент t канал свободен, иначе вероятность того, что заявка, пришедшая в момент t, будет обслужена. А значит, для данного момента времени t среднее число обслуженных заявок к числу поступивших также равно p₀: q= p₀.

В пределе, при t, когда процесс обслуживания уже установится, предельное значение q будет равно .

Легко найти и А, зная q. Они связаны очевидным соотношением:. В пределе, при t, А тоже установится и будет равна .

Зная q (вероятность того, что пришедшая в момент t заявка будет обслужена) легко найти вероятность отказа: P_отк =1-q. P_отк есть не что иное, как средняя доля необслуженных заявок среди поданных. В пределе, при t .

Многоканальная система массового обслуживания с отказами

Рассмотрим n-канальную СМО с отказами. Будем нумеровать состояния системы по числу занятых каналов (или, что в данном случае то же, по числу заявок, связанных с системой). Состояния будут:

S₀ - все каналы свободны;

S₁ - занят ровно один канал, остальные свободны;

……

S_k - заняты ровно k каналов, остальные свободны;

…….

S_n - заняты все n каналов.

Граф состояний имеет следующий вид. Слева направо систему переводит один и тот же поток - поток заявок с интенсивностью .



Рис.

Очевидно, если обслуживанием занято 2 канала, а не один, поток обслуживаний, переводящий систему по стрелке S₂S₁, будет вдвое интенсивнее (2), если занято k- каналов - в k раз интенсивнее (k). Процесс такого вида представляет собой частный случай процесса гибели и размножения. Составляем уравнения Колмогорова:

(9.6).

Уравнения (9.6) называются уравнениями Эрланга. Естественными начальными условиями являются:

p₀(0)=1; p₁(0)=p₂(0)=…=p_n(0)=0

Интегрировать (6) в аналитическом виде довольно сложно, на практике решают численно с использованием ЭВМ. Такое решение дает нам все вероятности состояний как функции времени: p₀(t), p₁(t), …, p_n(t).

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

 (k=1,2,..n) (9.7).

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

(9.8). Формулы Эрланга.

Теперь можно найти характеристики эффективности СМО: q, А, Р_отк.

Заявка получает отказ, если приходит в момент, когда все n каналов заняты. Вероятность этого равна:

.

Вероятность того, что заявка будет принята к обслуживанию (она же q) дополняет Р_отк до 1: q = 1-p_n. И наконец: А= q=(1- p_n).

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

как математическое ожидание дискретной случайной величины, принимающей значение 0,1, …n с вероятностями p₀, p₁…p_n.

Однако значительно проще выразить через А . А есть не что иное, как среднее число заявок, обслуживаемых в единицу времени; один занятый канал обслуживает в среднем за единицу времени заявок; следовательно, среднее число занятых каналов или .

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

На СМО поступает поток заявок с интенсивностью , интенсивность обслуживания (т.е. в среднем непрерывно занятый канал будет выдавать обслуженных заявок в единицу времени), n=1. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Предположим, что количество мест в очереди ограничено числом m (в дальнейшем, при m можно получить характеристики одноканальной СМО без ограничений по длине очереди). Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания): S₀ - канал свободен; S₁ - канал занят, очереди нет; S₂ - канал занят, одна заявка стоит в очереди; S_k - канал занят, k -1 стоят в очереди; S_m+1 - канал занят, m заявок стоят в очереди. Граф состояний (размеченный) имеет вид:

Рис.

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

или (9.9).

В знаменателе выражения для р₀ стоит геометрическая прогрессия, суммируя её находим

(9.10).

(9.10) справедливо только при (иначе неопределенность вида ). Но сумму геометрической прогрессии со знаменателем найти ещё проще, чем по (9.10); она равна (m+2) и в этом случае p₀=1/(m+2) {то же самое получится, если раскрыть неопределенность по правилу Лапиталя}.

Определим характеристики СМО: Р_отк q, А, среднюю длину очереди , среднее число заявок, связанных с системой .

Очевидно, заявка получает отказ только в том случае, когда канал занят и все m мест в очереди - тоже:

(9.11).

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

Найдем среднее число , находящихся в очереди; определим эту величину как математическое ожидание дискретной случайной величины R - числа заявок , находящихся в очереди:.

.

Выведем формулу для суммы. Эта сумма не что иное, как производная по суммы , а для этого выражения мы можем воспользоваться формулой суммы геометрической прогрессии:

Продифференцируем её по и проведя преобразования, найдем (9.13).

Тогда .

Подставляем p₀ из (10) и получаем (9.14).

Выведем теперь формулу для . Рассмотрим общее число заявок К, связанных с системой, как сумму двух случайных величин: числа заявок, стоящих в очереди и числа заявок, находящихся под обслуживанием: .

По теореме сложения математических ожиданий:

, где - среднее число заявок в очереди; - среднее число заявок под обслуживанием. Найдем . Т.к. канал у нас один, то случайная величина может принимать только два значения: 0 или 1. Значение 0 она принимает, если канал свободен; вероятность этого равна . Значение 1 она принимает, если канал занят; вероятность этого равна .

Отсюда находим:

.

, где находим из (9.14).

Выведем выражение еще для одной существенной характеристики СМО с ожиданием: среднего времени ожидания заявки в очереди. Обозначим его . Пусть заявка приходит в систему в какой-то момент времени. С вероятностью p₀ канал обслуживания не будет занят и ей не придется стоять в очереди (t_ож=0). С вероятностью p₁ она придет в систему во время обслуживания какой-то заявки, но перед ней не будет очереди, и заявка будет ждать начала своего обслуживания в течение времени 1/ (среднее время обслуживания одной заявки). С вероятностью p₂ в очереди перед ней будет стоять еще одна заявка и время ожидания в среднем будет 2/ и т.д. Вообще, с вероятностью p_k пришедшая заявка застанет в системе k заявок и будет ждать в среднем k/ единиц времени (1km). При k=m+1 (в очереди m заявок, вероятность этого p_m+1) t_ож=0 (заявка не обслуживается).

.

Подставим сюда выражения для p₁,p₂,…p_m из (9.9).

.Преобразуем сумму в скобках, используя (9.13)

Или, выражая p₀ через

.

Сравнивая это выражение с (9.14) , замечаем, что , (9.15)

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

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

Т_сист.=Т_ож +, где Т_ож - время ожидания заявки в очереди, случайная величина, равная времени обслуживания Т_об, если заявка обслуживается и 0, если она не обслуживается (получает отказ). По теореме сложения математических ожиданий: , но в наших обозначениях , а . Отсюда находим: или с учетом (9.15) .

Многоканальная система массового обслуживания с ожиданием.

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

S₀ - все каналы свободны;

S₁ - занят один канал, остальные свободны;

… … …

S_k - заняты k каналов, остальные свободны;

… … …

S_n - заняты все n каналов;

S_n+1 - заняты все n каналов, одна заявка стоит в очереди;

… … …

S_n+r - заняты все n каналов, r заявок в очереди;

… … …

S_n+m - заняты все n каналов, m заявок в очереди.

Размеченный граф состояний имеет вид

Рис.

Написать уравнения Колмогорова. Найти вероятности состояний. В их помощью рассчитать все интересующие величины. Затем опять можно рассмотреть и случай m. Многоканальная система массового обслуживания с ограниченным временем ожидания. Можно рассмотреть СМО с ограниченным временем ожидания (на каждую заявку, стоящую в очереди действует как бы «поток уходов» с интенсивностью (- среднее время пребывания в очереди)).

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

Понятие агрегата в моделировании систем

Пусть T - фиксированное подмножество действительных чисел (множество рассматриваемых моментов времени), X,U,Y,Z - множества любой природы. Элементы указанных множеств назовем: tT - моментом времени; xX; входным сигналом; uU- управляющим сигналом; yY - выходным сигналом; zZ состоянием. Состояния, входные, управляющие и выходные сигналы, рассматриваемые как функции времени, обозначим z(t), x(t), u(t) и y(t).

Под агрегатом будем понимать объект <T,X,U,Y,Z,H,G> (11.1), где H,G - операторы (вообще говоря, случайные). Операторы переходов и выходов H и G реализуют функции z(t) и y(t). Структура этих операторов собственно и выделяет агрегаты среди прочих систем.

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

Операторы переходов агрегата

Операторы переходов. Наряду с состоянием z(t) будем рассматривать также точки z(t+0). Договоримся считать, что для любого t₁>t момент (t+0)(t,t₁].

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

Предположение 2. Из особых состояний агрегат может переходить в новое состояние скачком. Пусть z(t*) - некоторое особое состояние агрегата, а u_s - последний управляющий сигнал u_sU.

Примем следующие обозначения для операторов, являющихся частными видами оператора H и определяющих состояние агрегата в момент t*+0. Если t* - момент поступления входного сигнала x_, то

z(t*+0)=V[z(t*),x,u_s] (11.2)

Аналогично, если t* - момент поступления управляющего сигнала u, то

z(t*+0)=V[z(t*),u] (11.3)

При одновременном поступлении x и u

z(t*+0)=V [z(t*),x,u] (11.4)

Наконец, если t* - момент выдачи выходного сигнала y, то

z(t*+0)=W[z(t*),u_s] (11.5)

В интервале между особыми состояниями, значение z(t) определяется при помощи операторов U, вид которых в общем случае зависит от особого состояния, являющегося для данного интервала времени начальным состоянием:

z(t*+0)=[t,z(t*+0),u_s] (11.6)

Здесь t* - момент особого состояния, являющегося исходным для данного интервала времени. Естественно, замечания о том, что H является случайным оператором, без изменений переносится на его частные виды U,V,V,V и W.

Операторы выходов агрегата

Во множестве Z состояний z(t) агрегата выделим класс подмножеств {Z_y}, обладающих следующими свойствами.

Выходной сигнал y выдается в момент t в тех случаях, когда: 1) z(t)Z_y; z(t-0)Z_y и 2) z(t+0)Z_y, но z(t')Z_y. Тогда, оператор G можно представить в виде совокупности 2 операторов: G, вырабатывающего выходной сигнал

y=G[z(t),u_s] (11.7)

и G, проверяющего для каждого t принадлежность z(t) к одному из подмножеств Z_y. Заметим, что в общем случае, оператор G является случайным оператором. Это значит, что данным t,z(t),u ставится в соответствие не одно определенное значение выходного сигнала, а некоторое множество значений y с соответствующим распределением вероятностей, задаваемых оператором G. В некоторых случаях в качестве одной составляющих z(t), например z₁(t), можно рассматривать время, оставшееся до выдачи выходного сигнала. Тогда оператор G проверяет неравенство z₁(t)>0.

Кусочно-линейные агрегаты. Процесс функционирования КЛА

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

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

Понятие о кусочно-линейном агрегате

Для поставленных здесь задач достаточно считать, что на агрегат не поступают управляющие сигналы u, а поступают лишь входные сигналы x (не ограничивает общности, в качестве x можно рассматривать входной сигнал в широком смысле ()). Итак, мы рассматриваем агрегат как объект, который в каждый момент времени t характеризуется внутренним состоянием z(t), имеет вход и выход. На вход агрегат в изолированные моменты времени могут поступать сигналы, с выхода могут сниматься выходные сигналы. Класс кусочно-линейных агрегатов выделяется с помощью конкретизации структуры множеств Z,X,Y а также операторов H и G. Опишем данную конкретизацию.

Рассмотрим некоторое конечное или счетное множество I. Для определенности предположим, что I={0,1,2,…}, хотя в конкретных задачах I может иметь и другой вид. Назовем I-множеством основных состояний, а элементы I - основными состояниями. Каждому основному состоянию I поставим в соответствие некоторое целое неотрицательное число ||||, которое назовем рангом основного состояния. Кроме того, каждому I поставим в соответствие выпуклый многогранник Z⁽⁾ в евклидовом пространстве размерности ||||. Будем считать, что Z=UZ⁽⁾, т.е. пространство состояний Z можно представить состоящим из всевозможных пар вида (), где I, а z⁽⁾ является вектором размерности |||| и принимает значения из многогранника Z⁽⁾. Вектор z⁽⁾ будем называть вектором дополнительных координат. Если ||||=0 для некоторого I, то это означает, что в данном состоянии дополнительные координаты не определяются.

Процесс функционирования КЛА

Опишем сначала динамику КЛА, т.е. процесс изменения внутренних состояний во времени, в предположении отсутствия поступления x. В предыдущей терминологии, определим действия оператора U. Пусть в начальный момент времени t₀ агрегат находится в состоянии z(t₀)=(,z⁽⁾(0)), где z⁽⁾(0)- внутренняя точка многогранника Z⁽⁾. Тогда при t>t₀ точка z⁽⁾(t) перемещается внутри многогранника Z⁽⁾ до тех пор, пока не достигнет его границы. Пусть это произойдет в момент t₁, который назовем «опорным». Тогда при t₀<tt₁, t=t-t₀ «движение» агрегата описывается следующими законами: (t)==const (11.27),

данному значению соответствует вектор ⁽⁾ размерности |||| и z⁽⁾(t)=z⁽⁾(0)+t⁽⁾. (11.28)

Значение опорного момента t₁ определяется траекторией z(t), вернее её некоторыми параметрами и может быть найдено из соотношения t₁=inf{t:z⁽⁾(0)+(t-t₀)⁽⁾Z⁽⁾, t>t₀}, (11.29)

поскольку Z⁽⁾ многогранник, то нахождение t₁ по (11.29) сводится к следующему. Пусть - j-тая грань многогранника Z⁽⁾ (предположим, что Z⁽⁾ содержит m() граней). Эти грани могут быть заданы линейными уравнениями:

j=1,… m() , (11.30)

где z_i⁽⁾ - компоненты вектора z⁽⁾, i=1.. ||||. Легко понять, что (11.29) может быть записано в виде или Обозначим , j=1,…m() (11.32) Пусть =min{_j;_j>0} (11.33) Тогда из (11.31-11.33) следует, что t₁=t₀+ (11.34)

В момент t₁ состояние рассматриваемого кусочно-линейного агрегата изменяется скачкообразно. Значение z(t₁+0) является случайным, задаваемым распределением P₁, которое зависит лишь от состояния z(t₁). В момент t₁ может выдаваться выходной сигнал (см. оператор G). Содержание (и необходимость выдачи) y зависит от состояния z(t₁). Подмножество Z_y, введенное в общем определении агрегата, в данном случае совпадает с . Для нас важно, указать, что множество Y имеет структуру, аналогичную Z, т.е. выходные сигналы y представляются y=(,y⁽⁾), где -элемент некоторого не более чем счетного множества, y⁽⁾ - вектор, принимающий значения из евклидова пространства размером, зависящим от . При t>t₁ движение агрегата вновь происходит в соответствии с формулами (11.27) и (11.28) до очередного «особого» момента t₂, где под t нужно понимать теперь t-t₁ и т.д. Обратимся теперь к случаю поступления входного сигнала. Подчеркнем, что для КЛА множество X структурно аналогично множествам Z и Y, т.е. x=(,x⁽⁾), где -элемент конечного или счетного множества, а x⁽⁾- действительный вектор, размерность которого зависит от . Следующее описание поведения КЛА можно рассматривать как раскрытие действия оператора V'.

Пусть в рассматриваемый момент t состояние агрегата z(t)=(,z⁽⁾) и пусть в этот момент поступает входной сигнал x=(,x⁽⁾). При этом состояние агрегата меняется скачкообразно. Значение z(t+0) является случайным, задаваемым распределением P₂, которое, вообще говоря, зависит от z(t) и x. Будем считать, что в рассматриваемый момент может выдаваться выходной сигнал, содержание и необходимость выдачи которого зависит не только от состояния z(t) (и, быть может, z(t+0)), но и от содержания поступившего входного сигнала x. После рассматриваемого момента времени t движение агрегата происходит в соответствии с формулами (11.27) и (11.28) до следующего момента поступления входного сигнала или выхода вектора состояния на границу допустимых значений.

Динамика КЛА описана полностью. В виде КЛА могут быть формализованы многие реальные процессы: процессы передачи и обмена данными в сетях связи, системы массового обслуживания и материально-технического снабжения, процессы автомобильного движения на дорогах, разнообразные дискретные производственные процессы, вычислительные системы и т.д. При этом всюду основные состояния агрегата указывают на качественно различные состояния моделируемых объектов. Дополнительные же координаты характеризуют происходящие количественные изменения и часто носят сугубо вспомогательный характер, «вбирая» в себя необходимую информацию о предыстории модели. Следует отметить, что представление реальных систем в форме КЛА неоднозначно, поскольку неоднозначно могут быть выбраны состояния агрегатов. Выбор же состояний определяется как целями исследования, так и стремлением уменьшить размерность задачи. При этом всегда приходится идти на компромисс между точностью описания и полнотой получаемой информации с одной стороны и простотой модели - с другой.

Процесс функционирования агрегата. Агрегат функционирует следующим образом. В начальный момент времени t₀ заданы начальное состояние агрегата z₀ и начальное значение управляющего сигнала u₀.

Пусть t₁ и t₂ - моменты поступления первого x₁ и второго x₂ входных сигналов, ₁ - момент поступления первого управляющего сигнала u₁ и, для определенности t₁<₁<t₂. Рассмотрим полуинтервал (t₀,t₁]. Состояния агрегата изменяются с течением времени по закону

z(t)=[t,z₀,u₀] (t₀<tt₁)

до тех пор (оператор G), пока в момент t (пусть t<t₁) состояние z(t) не окажется принадлежащим подмножеству Z_y, хотя состояние z(t-0) не принадлежало подмножеству Z_y. В этом случае в момент t выдается выходной сигнал y⁽¹⁾, вырабатываемый оператором G. Вместе с тем закон изменения состояний (11.6) нарушается и

z(t+0)=W[z(t),u₀].

Прежде чем рассматривать дальнейшие изменения состояний агрегата во времени, необходимо проверить (оператор G), не удовлетворяет ли состояние z(t+0) условиям выдачи выходного сигнала, или, другими словами, не принадлежит ли (в смысле условий 1) и 2), упомянутых выше) состояние z(t+0) некоторому новому подмножеству Z_y). Если состояние z(t+0) удовлетворяет условиям выдачи выходного сигнала (принадлежит подмножеству Z_y), то в момент t выдается второй выходной сигнал y⁽²⁾ (оператор G), а состояние агрегата описывается соотношением

z(t+0+0)=W[z(t+0),u₀]=W{W[z(t),u₀],u₀} (11.8)

и т.д. В силу принятого соглашения в любой интервал времени может быть выдано лишь конечное множество выходных сигналов. Это свойство агрегата является ограничением, накладываемым на структуру подмножеств Z_y и оператор W. Предположим теперь, что z(t+0) не принадлежит никакому из подмножеств Z_y. Поэтому далее состояние агрегата изменяется в соответствии с законом

z(t)=u_t[t,z(t+0),u₀]=u_t{t,W[z(t),u₀],u₀} (11.9)

Пусть теперь в момент t₁ поступает входной сигнал x_1. Проследим поведение агрегата в момент t₁ при различных вариантах возможных событий.

Если при достаточно малых >0 в момент t₁- состояние агрегата не принадлежало подмножеству Z^*_y, а в момент t₁ z(t₁) принадлежит Z^*_y, то условимся, что в момент t₁ выдается выходной сигнал y^*_, а состояние агрегата есть

z(t₁+0)=W[z(t₁),u₀] (11.10)

Вместе с тем действие входного сигнала x₁ приводит к тому, что

z(t₁+0+0)=V[z(t₁+0),x₁,u₀]=V'{W[z(t₁),u₀],x₁,u₁} (11.11)

Очевидно, что состояние z(t₁+0+0) должно быть проверено (оператором G) по отношению к условиям выдачи выходного сигнала. Предположим теперь, что в момент t₁ не было оснований для выдачи выходного сигнала y*. Тогда вместо (11.10 и11.11) в силу действия входного сигнала x₁ состояние агрегата имеет вид

z(t₁+0)=V[z(t₁),x₁,u₀], (11.12)

а в дальнейшем, если состояние (11.12) не соответствует выдаче выходного сигнала:

z(t)={t,V[z(t₁),x₁,u₀],u₀} (11.13) t₁<t (t₁,]

Пусть в момент ₁ в агрегат поступает управляющий сигнал u₁. Тогда состояние агрегата имеет вид

z(₁+0)=V[z(₁),u₁], (11.14)

если в момент ₁ не происходит выдача выходного сигнала, или

z(₁+0+0)=V{[W[z(₁),u₀]]u_1,}, (11.15)

если в момент ₁ выдается выходной сигнал.

Необходимо отметить, что управляющий сигнал u в общем случае является параметром, определяющим операторы V,V,W,U,G,G. Поэтому в дальнейшем вместо начального значения управляющего сигнала u₀ в этих операторах должно использоваться значение u₁ до тех пор, пока не поступит следующий управляющий сигнал u_2. Например, в полуинтервале (₁, t₂], если нет оснований для выдачи выходного сигнала

z(t)=z(₁+0),u₁] ₁<tt₂ (11.16)

В частном случае, операторы H и G могут оставаться неизменными при поступлении очередного управляющего сигнала. Аналогично, оператор U может быть одним и тем же при любых выходных сигналах (при попадании z(t) в любые подмножества Z_y).

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

Рассмотрим однолинейную СМО следующего вида

В моменты времени t_j, представляющие собой случайный поток однородных событий с заданным законом распределения, в систему поступают заявки, каждая из которых характеризуется параметром _j. Величина _j является случайной величиной с условным законом распределения f(/t) при условии, что t_j=t. Если линия обслуживания занята, заявка попадает в очередь и может находиться там (ждать) не более, чем

_k^(ж)=(_j,_i) (11.17)

Величина _i является случайной величиной с условным законом распределения f(/t) при условии, что _k=t. Величины _k образуют случайный поток однородных событий с заданным законом распределения, не зависимый от t_j. Заявка должна быть принята к обслуживанию не позднее, чем в момент времени t_j+_k^(ж), в противном случае она получит отказ.

Время обслуживания заявки или время занятости линии

_k^(з)=(_j,_i) (11.18)

Представим эту СМО в виде агрегата. Состояние агрегата будем характеризовать вектором z(t)Z со следующими компонентами:

z₁(t) - время, оставшееся до конца обслуживания заявки (для заявки, которая находится на обслуживании);

z₂(t) - значение величины _i;

z₃(t) - количеств заявок в очереди;

z₄(t) - оставшееся время ожидания первой заявки из очереди (время до момента отказа);

z₅(t) - оставшееся время ожидания второй заявки из очереди (время до момента отказа);

z_k(t) - оставшееся время ожидания последней заявки из очереди (время до момента отказа).

Входной сигнал x_j поступает в момент t_j и несет с собой информацию об _j, т.е. x_j=a_j. Управляющий сигнал g_i поступает в момент t_i и несет с собой информацию о величине _i, т.е. g_i=_i.

Рассмотрим подмножества Z_y и соответствующие им выходные сигналы y, операторы W и U.

Подмножество Z_y⁽¹⁾. Пусть в момент времени t₁:

z₁(t₁)=0; z_l(t)>0; l=3,4,…,k.

Это означает, что обслуживание заявки закончилось. Выходной сигнал y₁=(y₁⁽¹⁾,y₁⁽²⁾). Здесь y₁⁽¹⁾ - признак «заявка обслужена», y₁⁽²⁾=y₁⁽²⁾(_j,_i,t₁) - выходной параметр заявки, зависящий от _j и _i. Заметим, что случайный характер оператора G может проявляться в том, что y₁² (_j,_i,t₁) представляет собой случайную функцию _j,_i,t_1. Оператор W, определяющий состояние агрегата в момент t₁+0, задается следующим образом. Из всех z_l(t₁), где l=4,5,..k=z₃(t), выбирается наименьшее и соответствующая заявка, например номер m, mk принимается к обслуживанию со временем обслуживания (занятости канала) ⁽³⁾_m=(_m,_i). Поэтому

(11.19)

Количество заявок в очереди уменьшится на 1: z₃(t₁+0)=z₃(t₁)-1 (11.20), а величина z_m(t₁+0) не определяется. Все остальные z_l(t₁+0) при l=4,5,..(за исключением z_m)

z_l(t₁+0)= z_l(t₁) (11.21)

Оператор U, определяющий состояния агрегата для моментов времени t>t₁ (до последующего особого состояния) имеет вид

z₁(t)=z₁(t₁+0)-(t-t₁)

z₂(t)=z₂(t₁+0)=const

z₃(t)=z₃(t₁+0)=const (11.22)

z₄(t)=z₄(t₁+0)-(t-t₁)

............…………

z_k(t)=z_k(t₁+0)-(t-t₁)

Подмножество . Пусть в момент времени t₂:

z₁(t₂)>0; z₃(t₂)>0, z_m(t₂)=0, 4mk

Это означает, что время ожидания одной из заявок в очереди истекло. Поскольку заявка до момента t₂ не была принята к обслуживанию, она получает отказ. Выходной сигнал y₂=(y₂⁽¹⁾,y₂⁽²⁾). Здесь y₂⁽¹⁾ представляет собой признак «заявка получила отказ», y₂⁽²⁾= y₂⁽²⁾( _j,_i,t₂) - выходной параметр заявки. Оператор W в момент t₂+0 описывается соотношениями:

z₁(t₂+0)=z₁(t₂)

z₂(t₂+0)=z₂(t₂

z₃(t₂+0)=z₃(t₂)-1 (11.23)

z_l(t₂+0)=z_l(t₂) l=4,5,..k lm

Величина z_m(t₂+0) не определяется. Оператор U₍₎ для моментов времени t>t₂ определяется равенствами.

z₁(t)=z₁(t₂+0)-(t-t₂)

z₂(t)=z₂(t₂+0)=const

z₃(t)=z₃(t₂+0)=const (11.24)

z_l(t)=z_l(t₂+0)-(t-t₂) ) l=4,5,..k lm

Подмножество . В момент времени t₃: z₁(t₃)=0, z₃(t₃)=0. Это значит, что очередь заявок отсутствует, и обслуживание закончилось в момент t₃. Выходной сигнал y₃=(y₃¹,y₃²). Здесь y₃¹ - признак «система свободна», а y₃²=t₃ показывает момент освобождения системы. Оператор W: z₁(t₃+0)=0; z₃(t₃+0)=0; другие z_l не определяются. Оператор для всех t>t₃ задается соотношениями: z₁(t)=0, z₃(t)=0; z_l(t) при l>3 не определяются (до следующего особого состояния).

Пусть теперь в момент t_j поступает входной сигнал x_j=_j (заявка с параметром _j). Оператор V имеет следующий вид. Если входной сигнал поступил после выходного сигнала y₃ (действовал оператор ) , то это означает, что система была свободной, и заявка сразу поступила на обслуживание с _j³=(_j,_i). Поэтому

z₁(t_j+0)= _j⁽³⁾=(_j,_i) (11.25)

z₃(t_j+0)=0

Величины z_l(t_j+0) для l>3 не определяются. Если входной сигнал поступил после выходных сигналов y₁ и y₂, то заявка попадает в очередь, т.е.

z₁(t_j+0)=z₁(t_j)

z₂(t_j+0)=z₂(t_j)

z₃(t_j+0)=z₃(t_j)+1

z_l(t_j+0)=z_l(t_j); l=4,5,..k

z_k+1(t_j+0)=_j^(ж)= (_j,_i)

В дальнейшем (оператор ) состояния z(t) определяются аналогично (11.22)

Пусть теперь в момент _i поступает управляющий сигнал g_i=_i+1. При этом изменится только значение z₂(t): вместо прежнего значения _i должно быть z₂(t)=_i+1. остальные z_l(t) не зависят от _i+1. Из этого легко усмотреть содержание операторов W и U.

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

Моделирование стохастических процессов методом статистических испытаний

В тех случаях, когда построение аналитической модели явления по той или иной причине трудно осуществимо, применяется другой метод моделирования, известный под названием метода статистических испытаний или, иначе, метода Монте-Карло.

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

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

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

Способы организации единичного жребия

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

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

Предположим, что в ходе моделируемого процесса наступил момент, когда его дальнейшее развитие (а значит и результат) зависит от того, появилось ли на данном этапе событие А или не появилось (например: произошло ли попадание в цель, обнаружен ли некоторый объект, исправна ли некоторая аппаратура и т.д). Тогда нужно «бросанием жребия» решить вопрос: появилось событие А или не появилось? Для этого нужно привести в действие некоторый случайный механизм розыгрыша (бросить игральную кость, несколько монет или выбрать число из таблицы случайных чисел) и условиться о том, какой результат жребия означает появление, а какой - непоявление события А). Ниже мы увидим, что розыгрыш всегда можно организовать так, чтобы событие А имело любую наперед заданную вероятность. Кроме событий, появляющихся случайным образом, на ход и исход операции могут так же влиять разные случайные величины (время, координаты и т.д.). С помощью жребия можно разыграть значения любой случайной величины или совокупность значений нескольких случайных величин. Условимся называть единичным жребием любой элементарный опыт, в котором решается один из вопросов: