Моделирование систем: в 2-х частях. Часть II

Министерство образования и науки Российской Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Н. Ю. Салмина

МОДЕЛИРОВАНИЕ СИСТЕМ

Часть II

Учебное пособие

Томск
«Эль Контент»
2013

УДК
519.866.5(075.8)
ББК
22.18я73
С 164

Рецензенты:

Тарасенко В. Ф., докт. техн. наук, профессор кафедры теоретической
кибернетики Томского государственного университета;

Грибанова Е. Б., канд. техн. наук, доцент кафедры автоматизированных систем
управления ТУСУРа.

Салмина Н. Ю.
С 164
Моделирование систем : учебное пособие. В 2-х частях / Н. Ю. Салмина. — Томск : Эль Контент, 2013. — Ч. II. — 114 с.

ISBN 978-5-4332-0147-7

В настоящем учебном пособии изложены основные вопросы моделирования систем: классификация моделей, этапы моделирования. Рассматриваются задачи статистического моделирования, основные моменты планирования эксперимента и анализа результатов, а также некоторые вопросы
теории массового обслуживания и теории игр. В качестве программного
средства моделирования систем рассмотрен язык имитационного моделирования GPSS: синтаксис, особенности применения. Теоретический материал иллюстрируется многочисленными примерами.

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

УДК
519.866.5(075.8)
ББК
22.18я73

ISBN 978-5-4332-0147-7
©
Салмина Н. Ю., 2013

©
Оформление.
ООО «Эль Контент», 2013

ОГЛАВЛЕНИЕ

Введение
4

4
Некоторые вопросы теории массового обслуживания
6

4.1
Общие сведения о моделях массового обслуживания . . . . . . . . . .
6

4.2
Модели потоков событий . . . . . . . . . . . . . . . . . . . . . . . . . . .
9

4.3
Обзор методов решения задач массового обслуживания . . . . . . . .
12

4.4
Процесс обслуживания как марковский случайный процесс . . . . . .
14

4.5
Расчет основных характеристик для различных типов СМО
. . . . .
15

4.5.1
Одноканальная СМО с ожиданием . . . . . . . . . . . . . . . . .
15

4.5.2
Схема гибели и размножения . . . . . . . . . . . . . . . . . . . .
20

4.5.3
Формула Литтла . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21

4.5.4
Одноканальная СМО с отказами . . . . . . . . . . . . . . . . . .
22

4.5.5
Одноканальная СМО с ограниченной очередью . . . . . . . . .
24

4.5.6
Многоканальные СМО с ожиданием . . . . . . . . . . . . . . . .
25

4.5.7
Многоканальные СМО с отказами . . . . . . . . . . . . . . . . .
27

4.5.8
Многоканальные СМО со взаимопомощью
. . . . . . . . . . .
29

4.5.9
Замкнутые СМО . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31

4.5.10 СМО с ограниченным временем ожидания . . . . . . . . . . . .
34

4.5.11 Сети СМО . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35

4.6
Исследование немарковских СМО . . . . . . . . . . . . . . . . . . . . . .
39

5
Теория игр
41

5.1
Определение и классификация игр . . . . . . . . . . . . . . . . . . . . .
41

5.2
Формы представления игр
. . . . . . . . . . . . . . . . . . . . . . . . . .
43

5.3
Антагонистические игры . . . . . . . . . . . . . . . . . . . . . . . . . . .
48

5.3.1
Конечные игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48

5.3.2
Бесконечные антагонистические игры . . . . . . . . . . . . . . .
69

5.4
Игры многих лиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81

5.4.1
Общие понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81

5.4.2
Конечные бескоалиционные игры . . . . . . . . . . . . . . . . .
82

5.4.3
Кооперативные игры без побочных платежей . . . . . . . . . .
87

5.4.4
Классические кооперативные игры . . . . . . . . . . . . . . . . .
90

Заключение
107

Литература
108

Глоссарий
109

ВВЕДЕНИЕ

Соглашения, принятые в книге

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает определение или новое понятие.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает теорему. Данный блок состоит из Названия теоремы (Слова Теорема и Номера теоремы) и Текста теоремы.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает лемму. Данный блок состоит из Названия леммы (Слова Лемма и Номера леммы) и Текста леммы.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает аксиому. Данный блок состоит из Названия аксиомы (Слова Аксиома и Номера аксиомы) и Текста аксиомы.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Соглашения, принятые в книге
5

. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .

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

. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Контрольные вопросы по главе
. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Глава 4

НЕКОТОРЫЕ ВОПРОСЫ ТЕОРИИ
МАССОВОГО ОБСЛУЖИВАНИЯ

4.1 Общие сведения о моделях массового
обслуживания

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

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

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

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

4.1 Общие сведения о моделях массового обслуживания
7

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

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

Для оценки качества работы вероятностной модели вводят количественные
показатели эффективности ее работы. Для СМО — это полная средняя стоимость
в единицу времени:
Γ = C1 ⋅ ν + C2 ⋅ ρ,

где ν — среднее число заявок в очереди; ρ — среднее число свободных обслуживающих приборов; C1 — стоимость ожидания одной заявки в единицу времени; C2 —
стоимость простоя одного обслуживающего прибора в единицу времени.

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

Рис. 4.1 – Простейшая структурная схема СМО

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

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

Глава 4. Некоторые вопросы теории массового обслуживания

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

Существует большое количество различных СМО. Перечислим основные классы СМО по разным основаниям [1]:

а) марковские и немарковские: в марковских СМО динамика описывается
с помощью марковских процессов. Аналитическому исследованию поддаются только частные типы немарковских СМО — полумарковские, линейчатые и др.;

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

в) с отказами и без отказов (в зависимости от того, разрешается входной
заявке ждать в очереди или нет; если разрешается — ограничена очередь по
длине или времени, либо нет);

г) многофазные и однофазные: при последовательном процессе обслуживания
заявки несколькими приборами;

д) открытые и замкнутые: обслуженная заявка либо покидает СМО, либо снова поступает на обслуживание;

е) одиночные и сети СМО: сложные комбинации всех рассмотренных выше
СМО.

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

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

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

4.2 Модели потоков событий
9

рых случаях (абсолютный приоритет) срочная заявка может прервать уже начатое
обслуживание. Снятая заявка поступает в одну из очередей или теряется.

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

4.2 Модели потоков событий

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Потоком событий называется последовательность событий,
следующих
одно
за
другим
в
случайные
моменты
времени
t1, t2,..., tk,.... В качестве событий могут выступать заявки, поступающие на вход СМО, поступление заявок на канал обслуживания и появление обслуженных заявок на выходе СМО.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

τi = ti − ti−1 = T = const.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Рекуррентным потоком является поток, для которого все
функции распределения интервалов между заявками совпадают:
Fi(τ) = F(τ).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

Для характеристики потоков очень часто вводят в рассмотрение вероятность
появления числа событий в заданном интервале времени τ : Pn(τ), где n — число
событий, появляющихся на интервале τ.

Глава 4. Некоторые вопросы теории массового обслуживания

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Поток без последствия характеризуется тем, что для двух непересекающихся интервалов времени ∆t1, ∆t2 > 0, t2 ⩾ t1 + ∆t1 вероятность появления числа событий Pn2(∆t2) на втором интервале
не зависит от числа появления событий n1 на первом интервале.
Здесь отсутствует вероятностная зависимость последующего
течения процесса от предыдущего.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Например, поток покупателей, входящих в магазин, является потоком без последствия, а поток деталей, сходящих с конвейера, является потоком с последствием (детали выходят не чаще, чем через интервал Toбcл).

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ординарным потоком называется поток, для которого вероятность попадания на данный малый отрезок времени ∆t двух
и более требований пренебрежительно мала по сравнению с вероятностью попадания одного требования (порядок малости
○(∆t) ∶ P>1(∆t) = ○(∆t)).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Интенсивностью потока называется предел:

lim
∆t→0
P>0(t0, ∆t)

∆t
= λ(t),

где P>0(t0, ∆t) — вероятность того, что на интервале (t0, t0 + ∆t)
появятся заявки.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Для стационарного потока его интенсивность не зависит от времени и равна
среднему числу событий в единицу времени: λ(t) = λ.