Типовые математические схемы

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

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

· непрерывно-детерминированные модели (D -схемы);

· дискретно-детерминированные модели (F -схемы);

· дискретно-стохастические модели (P -схемы);

· непрерывно-стохастические модели (Q -схемы).

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

К дискретно-детерминированным моделям относятся так называемые конечные автоматы. Автомат можно представить как некоторое устройство, на которое подаются входные сигналы и снимаются выходные и которое может иметь некоторые внутренние состояния. У конечного автомата множество входных сигналов и внутренних состояний является конечным множеством. Название F -схема происходит от английских слов finite automata.

К дискретно-стохастическим моделям относятся вероятностные (стохастические) автоматы, или по-английски probabilistic automat. Отсюда название – P -схема. В общем виде вероятностный автомат можно определить как дискретный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и может быть описано стохастически.

Примером типовой схемы непрерывно-стохастического типа может служить схема системы массового обслуживания (СМО), или по-английски queuing system. Отсюда название — Q -схема.

Для реальных объектов Q -схемы образуются композицией многих элементарных приборов обслуживания П _i. Если каналы различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многоканальная Q -схема), а если приборы П _i и их параллельные композиции соединены последовательно, то имеет место многофазное обслуживание (многофазная Q -схема).

Таким образом, для задания Q -схемы необходим оператор сопряжения R, отражающий взаимосвязь элементов структуры. Связи в Q -схеме изображают в виде стрелок (линий потока, отражающих направление движения заявок).

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

Собственными (внутренними) параметрами Q -схемы являются:

· количество фаз L _ф;

· число каналов в каждой фазе L_j ^к;

· число накопителей каждой фазы L_j ^Н;

· емкость i -го накопителя j -ой фазы L_ij ^Н (j = 1,…, L _ф).

В теории массового обслуживания в зависимости от емкости накопителя существуют:

· системы с потерями (L_i ^Н = 0, накопитель отсутствует);

· системы с ожиданием (L_i ^Н → ∞, емкость накопителя бесконечно большая);

· системы с ограниченной емкостью накопителя Н_i (смешанные).

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

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

В зависимости от динамики различают статические и динамические приоритеты.

Статические приоритеты назначаются заранее и не зависят от состояний Q -схемы, т.е. они являются фиксированными в пределах решения конкретной задачи моделирования.

Динамические приоритеты возникают при моделировании.

В зависимости от правила выбора заявок из накопителя Н _i на обслуживание каналом К _i, можно выделить:

· бесприоритетное обслуживание. Оно осуществляется по правилу FIFO (First In – First Out) и LIFO (Last In – First Out) или по случайному правилу. Дисциплины FIFO и LIFO по среднему значению или математическому ожиданию ничем не отличаются, однако, приоритетной считается дисциплина FIFO, которая минимизирует дисперсию времени ожидания (т.е. уменьшается разброс времени относительно среднего значения);

· относительный приоритет. Заявка с более высоким приоритетом, поступившая в накопитель Н _i, ожидает окончания обслуживания предыдущей с более низким приоритетом заявки каналом К _i и только после этого занимает канал;

· абсолютный приоритет. Заявка с более высоким приоритетом, поступившая в накопитель, прерывает обслуживание каналом К _i заявки с более низким приоритетом и сама занимает канал (при этом вытесненная k_i -я заявка может либо покинуть систему, либо перейти в другую ячейку Н _i);

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

Необходимо знать набор правил, по которым заявки покидают Н _i и К _i:

· для Н _i это либо правила переполнения, либо правила ухода, связанные с истечением времени ожидания заявки в Н _i;

· для К _i – правила выбора маршрутов или направлений ухода.

Кроме того, для заявок необходимо задать правила, по которым они остаются в канале К _i, т.е. правила блокировок канала. При этом различают блокировки К _i по выходу и входу. Такие блокировки отражают наличие управляющих связей в Q -схеме, регулирующих поток заявок в зависимости от состояний Q -схемы. Набор возможных алгоритмов проведения заявок в Q -схеме можно представить в виде некоторого оператора А алгоритмов поведения заявок.

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

Процесс функционирования прибора обслуживания П _i можно представить как процесс изменения состояний его элементов во времени Z_i (t). Переход в новое состояние П _i означает изменение количества заявок, которые в нем находятся (в канале К _i и накопителе Н _i). Таким образом, вектор состояний для П _i имеет вид

Z_i = (z_i ^Н; z_i ^К),

где z_i ^Н – состояние накопителя (z_i ^Н = 0 – накопитель пуст, z_i ^Н = 1 – в накопителе одна заявка, z_i ^Н = L_i ^Н – накопитель занят полностью); z_i ^К – состояние канала К _i (z_i ^К= 0 – канал свободен, z_i ^К = 1 – канал занят).

Таким образом, Q -схема, описывающая процесс функционирования СМО любой сложности однозначно задается в виде набора множеств:

Q = < W, U, H, Z, R, A >

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

Для любой системы массового обслуживания характерно наличие трех отличительных свойств:

· объектов, у которых может возникнуть потребность в удовлетворении некоторых заявок;

· агрегатов, предназначенных для удовлетворения заявок на обслуживание;

· специальной организации приема в систему заявок и их обслуживание.