лекции по менеджменту. лекции. Курс лекций по дисциплине Моделирование систем предназначено для студентов, обучающихся по направлениям подготовки бакалавриата 09. 03. 01

• Название: Курс лекций по дисциплине Моделирование систем предназначено для студентов, обучающихся по направлениям подготовки бакалавриата 09. 03. 01
• Анкор: лекции по менеджменту
• Дата: 21.12.2020
• Размер: 1.74 Mb.
• Имя файла: лекции.pdf
• Тип: Курс лекций; #162568
• страница: 4 из 8

Система M/M/1/K
Общее число возможных состояний в такой системе n = K + 2.
На рис. 4.7 показаны состояния СМО с очередью, в которой три места:

39
K = 3, n = 5
. Получить систему уравнений для построения Марковского графа можно используя уравнения Колмогорова А.Н.
0 0
1 1
1 1
1
( )
( )
( );
( )
( ) (
) ( )
( ),
1, ...,
;
( )
( )
( ).
i
i
i
i
K
M
K
dp t
p t
p t
dt
dp t
p
t
p t
p
t i
K
dt
dp
t
p
t
p
t
dt
(4.24)
Рис. 4.7. СМО с ограниченной очередью и пять состояний S
Для примера СМО, показанного на рис. 4.7 уравнения примут вид:
0 0
1 1
0 1
2 2
1 2
3 3
2 3
4 4
3 4
( )
( )
( );
( )
( ) (
) ( )
( );
( )
( ) (
)
( )
( );
( )
( ) (
)
( )
( );
( )
( )
( ).
dp t
p t
p t
dt
dp t
p t
p t
p t
dt
dp t
p t
p t
p t
dt
dp t
p t
p t
p t
dt
dp t
p t
p t
dt
(4.25)
В установившемся режиме работы СМО производные будут равны нулю и система дифференциальных уравнений будет соответ- ствовать уравнениям 4.12.
Уравнения для определения вероятностей примут вид:
0
;
n
n
p
p
(4.26)

40 0
0 1
;
K
n
n
p
(4.27)
1 0
1
;
1;
1 1
;
1;
1
K
p
K
(4.28)
1
(1
)
;
1;
1 1
;
1.
1
n
K
n
p
K
(4.29)
Число заявок в системе вычисляют по формулам:
1 1
[1 (
1)
]
[ ]
;
1;
(1
) (1
)
[ ]
;
1.
2
K
K
K
K
K
M L
K
M L
(4.30)
Что бы вычислить время нахождения заявки в канале обслужи- вания нужно ввести приведенное значение интенсивности поступле- ния заявок.
(1
).
K
p
(4.31)
Время нахождения в системе будет вычислено:
1
[ ]
[ ].
M T
M L
(4.32)
Время нахождения заявки в очереди и длина очереди вычисля- ются по формулам:
1
[
]
[ ]
;
q
M T
M T
(4.33)
1 1
[
]
[ ]
(
);
1
K
q
K
M L
M L
(4.34)
0
[
]
[ ] (1
).
q
M L
M L
p
Система M/M/m/
Такая СМО обладает неограниченной очередью и несколькими процессорами обслуживания:
,
для n 0, 1, 2, ...;
; 0
;
;
n
n
n
n
m
m
n
m

41
Вероятности состояний такой системы вычисляются по формулам:
0 0
1 0
1 1
; 0
;
!
1
;
;
!
n
n
i
n
n
n
m
n m
i m
p
p
n
m
i
n
p
p
p
n
m
m
m m
(4.35)
1 1
0 1
1 1
1
(1
(
)) .
!
!
1
m
n
m
n
p
n
m
m
(4.36)
Длину очереди, время нахождения заявки в очереди, время на- хождения заявки в системе и число заявок в системе определяют по формулам:
1 0
2
[
]
;
!(1
)
m
q
m
M L
p
m
m
(4.37)
1 0
2 1
[
]
[
]
;
!(1
)
m
q
q
m
M T
M L
p
m
m
(4.38)
1 0
2 1
1
[ ]
[
]
;
!(1
)
m
q
m
M T
M T
p
m
m
(4.39)
1 0
2
[ ]
[ ]
!(1
)
m
m
M L
M T
p
m
m
(4.40)
С помощью формулы Эрланга второго рода вычисляют вероят- ность ожидания обслуживания клиентом:
0 0
1
!
1 1
!
1
n
r
n
n m
n m
n m
m
p
p
p
m m
p
m
m
(4.41)
Система M/M/m/K
В такой системе m процессоров обслуживания и K мест в очере- ди. Определить вероятность отсутствия заявок в системе можно по формулам:

42 1
1 1
1 0
1 1
1 1 (
)
1 1
(1
) ;
1;
!
!
1 1
1
(1
(
1)) ;
1.
!
!
K m
m
n
m
n
m
n
m
n
m
n
m
m
p
m
K
m
n
m
m
(4.42)
Остальные параметры системы определяют по формулам:
1 0
2
(
)
[
]
1 (
)
(1
) (
1) (
)
;
!(1
)
m
K m
K m
q
m
M L
p
K
m
m
m
m
m
m
(4.43)
(1
);
K
p
1
[
]
[
];
q
M Tq
M L
(4.44)
1
[ ]
[
]
;
q
M T
M T
(4.45)
[ ]
[ ].
M L
M T
(4.46)
Если в систему поступает число клиентов равное число процес- соров K = m для вероятностей можно использовать следующие соот- ношения:
0 1
;
!
n
n
p
p
n
(4.47)
0 0
1
!
m
n
n
p
n
(4.48)
В противном случае вероятности будут равны:
0
! ; 0
!
n
n
i
m
i
n
p
n
m
i
(4.49)
Вероятность полной загруженности системы (заполненная оче- редь, все процессоры обслуживают заявки):
0
! .
!
K
m
i
m
i
m
p
p
i
(4.50)
Контрольные вопросы
1.
Из каких элементов состоит канал обслуживания?
2.
Перечислите и охарактеризуйте правила обслуживания заявок.

43 3.
Какие требования предъявляются к Пуассоновскому потоку событий?
4.
Как используется нотация Кендала для описания канала об- служивания.
5.
Что такое Марковская цепь?
6.
В чем разница между Марковской цепью и процессом?
7.
Как строится переходная матрица Марковского процесса?
8.
Перечислите основные параметры канала обслуживания.
9.
Как строится Марковский граф для канала обслуживания?
10.
Как записываются уравнения Колмогорова А.Н. для канала обслуживания?
ЛЕКЦИЯ №5. СХЕМЫ МОДЕЛИРОВАНИЯ
5.1. Обзор современных схем моделирования
Сети Петри, автоматы, описание работы автомата, автомат Мили,
автомат Мура, конечные детерминированные и недетерминированные авто-
маты, агрегатные модели.
Сети Петри (N-схемы)
В практике моделирования объектов часто приходится решать задачи, связанные с формализованным описанием и анализом при- чинно-следственных связей в сложных системах, где одновременно параллельно протекает несколько процессов [5].
Сеть Петри представляет собой двухдольный направленный граф. Позиции и переходы соединяются между собой направленными дугами. Позиции обозначаются окружностями, переходы показывают- ся в виде прямоугольников (рис. 5.1).
Рис. 5.1. Пример сети Петри
Позиция обладает определенной мощностью и в соответствии с мощностью может содержать несколько знаков (маркеров). Если зна- чение мощности не задано, то оно принимается равной бесконечности

44 или единице. Загрузка позиций маркерами, называется маркировкой и представляет собой состояние сети. Каждой дуге графа может быть поставлен в соответствие определенный «вес». Если это значение не указано, то принимается значение равное единице.
Переход считается активным или готовым к активации если во всех входных позициях находится такое число маркеров, которое со- ответствует весу перехода и все выходные позиции обладают доста- точной мощностью – емкостью для того чтобы принять новые марке- ры. В сети Петри маркеры не движутся по графу. Они удаляются и по- являются в определенных позициях.
Маркированная (размеченная) N-схема задается кортежем [5]:
( , , , ,
),
N
B D I O M
(5.1)
В – конечное множество символов – позиций; D – конечное множество символов – переходов; I – входная функция (прямая функция инци- дентности); О – выходная функция (обратная функция инцидентности);
;
B
,
;
D
B
D
{0,1};
I
B D
(5.2)
:
{0,1};
O D B
(5.3)
(
);
(
).
i
j
i
j
b
D d
b
I d
Входная функция I отображает переход d
j
,
в множество входных позиций, а выходная функция О отображает переход d
j
,
в множество выходных позиций.
Рассмотрим фазы работы сети Петри с тремя переходами, дву- мя позициями. Мощность позиции два маркера. Обозначим М – мно- жество маркировок. Работа сети требует смены семи фаз {0…6}. Со- стояние сети показано на рис. 5.2–5.4.
Рис. 5.2. Фаза 0 и фаза 1; M
0
= {0,0}, M
1
=
{1,0}, активный переход d
1
Основными свойствами сети Петри являются: ограниченность – число меток в любой позиции сети не может превысить некоторого значения K; безопасность – частный случай ограниченности, K = 1;

45 сохраняемость – постоянство загрузки ресурсов, величина по- стоянна.
,
i
i
A N где N
i
– число маркеров в i-ой позиции, A
i
– весовой коэффициент; достижимость – возможность перехода сети из одного задан- ного состояния (характеризуемого распределением меток) в другое; живучесть – возможность срабатывания любого перехода при функционировании моделируемого объекта.
Рис. 5.3. Фаза 2 и фаза 3; M
2
= {2,0}, d
1
; M
3
= {1,1}, d
2
Рис. 5.4. Фаза 4 и фаза 5, фаза 6; M
4
= {0,2}, d
2
; M
5
= {0,1}, d
3
; M
6
= {0,0}, d
3
Дискретно-детерминированные модели (F-схемы)
Модели этого типа представляют собой автоматы. Автомат функционирует в моменты автоматного времени t
0
= 0, t
1
= T
0
, t
2
= 2T
0 0
;
0, .
i
t
i T i
Здесь T
0
период дискретизации модели автомата. В каждый мо- мент t
i
T
, автомат может находиться в одном из конечного числа со- стояний z
j
Z.
Принято различать два типа автоматов [5]: автомат Мили; автомат Мура.
Автомат Мили
Автомат может быть задан в виде кортежа:
0
( , ,
, , ,
,
).
A
Q
q F
(5.4)
Q является множеством возможных состояний. Вместо Q часто используется также условное обозначение в виде латинской буквы Z.
Множество является алфавитом ввода, множество является ал- фавитом выхода.

46
Переходная функция имеет вид
:
Q
Q
(5.5)
Функция выхода определяется выражением
:
Q
(5.6)
В конечном итоге выбирается компактная нотация и обе функции сводятся к одной переходной функции состояния
:
Q
Q
(5.7)
Стартовое-начальное состояние:
0
q
Q Вместо q
0
могут быть использованы условные обозначения начального состояния z
0
и s
0
Множество F это множество возможных доступных состояний
F
Q
Схема работы:
(
1)
( ( ), ( ));
( )
( ( ), ( )).
q t
q t
t
t
q t
t
(5.8)
Автоматы представляют в виде направленного графа. На рис. 5.5 показан пример автомата. Дуги помечены дробью
/ ,
i
i
а переход происходит в зависимости от значения из множества алфавита ввода и значения из множества алфавита вывода. Например, условное обо- значение дуги 0/1, означает, что при задании 0 для смены состояний, на выходе появляется сигнал 1.
Рис. 5.5. Автомат Мили; = {0,1}; = {0,1}
Автомат Мура
Автомат Мура получил свое наименование по имени математика
Эдварда Ф. Мура. По сравнению с автоматом Миля вход такого авто- мата исключительно зависит от его состояния. При достижении опре- деленного состояния формируется выходное значение, которое не зависит от перехода в это состояние.
Автомат описывается кортежем
0
( , ,
, , ,
,
).
A
Q
q F
(5.9)

47
Здесь Q конечное множество состояний, множество – входной алфавит автомата:
,
0.
Q
Множество – выходной алфавит автомата. Переходная функ- ция автомата описывается выражением
:
;
Q
Q
(5.10) функция выхода имеет вид
:
;
Q
(5.11)
(
1)
( ( ), ( ));
( )
( ( )).
q t
q t
t
t
q t
(5.12)
Пример автомата Мура показан на рис. 5.6. Известны следую- щие значения для множеств автомата:
0 1
2 3
{
,
,
,
},
{ , , },
{ , , }.
Q
q q q q
x y z
a b c
Для иллюстрации работы автомата составим табл. 5.1. Стрелкой показан процесс смены состояния. При переходе из состояния q
0
в со- стояние q
1
требуется подать сигнал y, на выходе будет сигнал b. Ана- логично можно проследить смену остальных состояний.
Рис. 5.6. Автомат Мура
Таблица 5.1
Алгоритм работы автомата
Переход ( )
x
y
z
Выходное значение ( )
q
0
q
3
q
3
q
1
b
q
1
q
3
q
2
q
3
a
q
2
–
q
3
–
a
q
3
q
3
–
q
2
c

48
Детерминированные и недетерминированные конечные ав-
томаты
Рассмотрим автомат Миля с четырьмя состояниями. Множество входных воздействий автомата
1 2
3 4
{ ,
,
,
}, множество выходных сигналов автомата
1 2
2 4
{ ,
,
,
}. Схема смены состояний автома- та показана на рис. 5.7. На рисунке под номером 4 обозначено конеч- ное состояние автомата. В зависимости от того какой сигнал будет получен автоматом из множества автомат переходит однозначно в новое состояние, выдавая сигнал из множества . Смена состояний и выдачи выходных сигналов происходят до тех пор пока автомат не перейдет в конечное состояние. Такое поведение автоматов называ- ется детерминированным, а автоматы называют конечными и детер- минированными.
Рис. 5.7. Детерминированный автомат
На рисунке 5.8 показаны схемы поведения не детерминирован- ных автоматов. В недетерминированных автоматах возникает неоп- ределенность перехода из одного состояния в другое. Автомат может перейти с определенной вероятностью из одного состояния в другое и выдать один и тот же сигнал из множества при появлении на входе сигнала из множества .
а)
б)
Рис. 5.8. Недетерминированный автомат:
а) неоднозначность смены состояний; б) неизвестный входной и выходной сигнал
Другой вариант неопределенности возникает, когда для перехо- да из одного состояния в другое выбирается с определенной вероят-

49 ностью сигнал из множества и на выходе появляется с определен- ной вероятностью сигнал из множества .
Агрегаты (A-схемы)
Такие модели требуют определения следующих множеств [5]:
T
– множество моментов времени;
X
– множество входных сигналов;
Y
– множество выходных сигналов;
Z
– множество состояний.
Процессы перехода агрегата из одного состояния в другое про- исходит за малый промежуток времени, т.е. имеет место скачек со- стояний z. В качестве элемента А-схемы выступает агрегат. Каждый агрегат A
n
, состоит:
1,
A
n
N На рис. 5.9 показана схема модели, со- стоящая из двух агрегатов, на котором окружности – коммутационные точки агрегатов – полюса.
Рис. 5.9. Пример схемы агрегатной модели
Последовательность выходных сигналов, упорядоченную отно- сительно времени выдачи называют выходным сообщением или
Y- сообщением. Информация, которая циркулирует в А-схеме делить- ся на внутреннюю и внешнюю. Внешняя информация поступает от внешних объектов, а внутренняя вырабатывается агрегатами А- схемы. Обмен информации А-схемы с внешней средой происходит через агрегаты, которые называют полюсами.
Различают входные полюсы, на которые поступают X-сообще- ния. Выходные полюсы – это агрегаты, выходная информация кото- рых представляет Y-сообщения.