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

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

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

· непрерывно-детерминированные модели (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>

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

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

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

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: