798f694d81eec0bf52c16d7140c795bd

1.

Филиал ФГБОУ ВО
«Национальный исследовательский университет «МЭИ» в г. Смоленске
Теория принятия решений
Доцент кафедры ВТ
кандидат технических наук, доцент
И.А. Денисова
Смоленск
Смоленск
– 2026
2011

2.

Лекция № 7
ВЕРОЯТНОСТНЫЕ МОДЕЛИ
ТЕОРИИ ПРИНЯТИЯ РЕШЕНИЙ

3.

УЧЕБНЫЕ ВОПРОСЫ
1. Вероятностные задачи ПР
2. Марковские модели задач ПР
3. Системы массового обслуживания

4.

1 вопрос
Вероятностные задачи ПР

5.

Вероятностные задачи принятия решений (задачи с риском) – это
задачи выбора лучшего варианта решения в ситуациях, когда каждая
выбираемая стратегия может привести к разным результатам, а
вероятности тех или иных результатов известны или могут быть оценены.
Оценка вероятности может основываться на объективном знании
(например, на экстраполировании известных тенденций развития
системы) или на субъективных мнениях (субъективные вероятности).
Часто используется сочетание этих подходов.
Задачи с известными вероятностями исходов. Для построения
распределения вероятностей необходимо либо иметь статистические
данные, либо привлекать знания экспертов.
Задачи с неизвестными вероятностями исходов. Известны все
последствия всевозможных решений, но не известны их вероятности, то
есть выбор любой альтернативы может привести к одному из нескольких
исходов.
5

6.

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

7.

Вариант 1 функционирования системы
Рассматривается детерминированная
система, на вход которой через равные промежутки
времени T1 поступают работы. Эти работы
обслуживаются прибором, время выполнения
каждой работы также постоянно и равно T2. Если
T1>T2, т.е. промежуток между поступлением работ
больше времени выполнения работ, то очереди
перед прибором или задержки в выполнении работ
не возникают.
Во втором варианте в системе возникло
качественно новое свойство - это очередь, вызванная
случайным характером поступления заявок.
Следовательно, при конструировании модели
функционирования системы необходимо учитывать
наличие очереди работ, ожидающих освобождения
прибора.
Вариант 2 функционирования системы
Длительность интервала между
работами представляет собой случайную
величину, плотность вероятности которой
распределена по экспоненциальному закону
f(t) = λe-λe. Математическое ожидание этой
случайной величины, так же как и в первом
варианте, равно Т1 т.е. в среднем работы
поступают в систему с той же
интенсивностью λ.
7

8.

Основные вероятностные модели принятия решений:
управляемые Марковские процессы;
сети и системы массового обслуживания;
модели управления запасами;
модели замены оборудования;
вероятностные деревья решения.
Определенную сложность представляет конструирование критерия
оптимальности для вероятностных моделей. Это связано с тем, что в выражение
для характеристики, выбранной в качестве критерия, обычно входят случайные
величины. Тогда применяемая характеристика также является случайной
величиной, а критерий может представляться в виде:
• математического ожидания характеристики;
• комбинации математического ожидания и дисперсии характеристики;
• наиболее вероятного значения характеристики;
• вероятности наступления определенного события.
8

9.

Пример. Оптимизация численности библиотекарей в научно-технических и учебных
библиотеках вузов.
Анализ системы библиотекари-читатели показывает, что можно выделить две
составляющие, влияющие на величину суммарных убытков:
первая составляющая С1 – это убытки, связанные с простоем библиотекарей изза отсутствия читателей. Величина этих убытков определяется как произведение
математического ожидания времени простоя библиотекарей на стоимость одной
единицы времени их работы.
Очевидно, что эта стоимость представляет собой величину заработной платы,
отнесенную к суммарному фонду рабочего времени.
Несложно установить, что при увеличении числа библиотекарей суммарное время
простоя увеличивается и, как следствие, увеличиваются затраты;
вторая составляющая С2 – это потери, вызванные ожиданием в очереди
студентами начала обслуживания. Это время является для студентов бесцельнопотерянным.
Очевидно; что при увеличении количества библиотекарей время ожидания
уменьшается и, следовательно, уменьшаются суммарные потери студентов.
Величина средних суммарных потерь в системе библиотекари-читатели
первоначально при увеличении числа библиотекарей уменьшается, а затем начинает
9
возрастать.

10.

Для конструирования вероятностных моделей принятия решений
применяется аппарат случайных процессов.
Процесс называется случайным, если для каждого момента времени его
состояние представляет собой случайную величину.
Основу классификаций случайных процессов составляют три характеристики:
1) пространство состояний;
2) индексирующий параметр;
3) статистические зависимости между случайными значениями процесса.
Пространство состояний – это множество значений случайного процесса.
Различают процессы с дискретными и непрерывными множествами состояний.
Процессы с дискретным множеством состояний характеризуются тем, что множество
возможных значений является конечным или счетным и обычно называется цепью.
Пространство состояний задают натуральным рядом чисел { 0, 1, 2, ..., п, ... }.
В качестве индексирующего параметра обычно используется время. В том
случае, если переходы между состояниями возможны в фиксированные моменты
времени, то такие процессы относятся к процессам с дискретным временем.
Статистические зависимости между случайными значениями процесса
задаются функцией совместного распределения вероятностей.
10

11.

2 вопрос
Марковские модели задач ПР

12.

Случайный процесс называется Марковским, если его дальнейшее
развитие определяется только тем состоянием, в котором он находится в
настоящий момент времени, но не зависит от предыстории попадания
процесса в это состояние (впервые был предложен в 1907 году российским
математиком А.А. Марковым).
Марковский процесс с дискретными состояниями называется цепью
Маркова, т.е. множество случайных величии { хп, п>0 } образует цепь
Маркова, если следующее состояние хn+1 определяется только значением
текущего состояния хn и не зависит от предыдущих значений процесса.
В цепи Маркова с дискретным временем изменения состояний могут
происходить только в моменты, предопределяемые натуральным рядом
чисел 0, 1, 2, ..., n, … .
Цепи Маркова с непрерывным временем характеризуются тем, что
изменение состояний может происходить в любой момент времени.
12

13.

Существует распределение непрерывной случайной величины,
обладающее свойством отсутствия последействия – это показательное
распределение:
,
где λi -1 – среднее время пребывания в i-м состоянии; fi(t) - плотность
распределения вероятностей времени пребывания в i-м состоянии.
Для показательного распределения справедливо следующее
утверждение: распределение времени, оставшегося до перехода в
следующее состояние, при условии, что процесс уже пребывает в текущем
состоянии время t0, тождественно равно безусловному распределению
времени пребывания в текущем состоянии.
13

14.

Дискретные цепи Маркова описываются матрицей переходных
вероятностей R=
, элементы которой rij, представляют собой
вероятность того, что процесс в момент времени tn+1 находится в
состоянии j при условии, что в момент времени tn находился в
состоянии i.
Элементы матрицы rij принимают значения в диапазоне от нуля до
единицы; сумма элементов в каждой строке равна единице.
Цепь Маркова является неоднородной, если вероятности перехода
зависят от n, т.е. rij = rij(n). В противном случае цепь Маркова относится к
однородной.
14

15.

Если цепь Маркова классифицируется как неприводимая,
апериодическая и однородная, то существует стационарное
распределение вероятностей для состояния системы, т.е. с течением
времени система переходит в стационарный режим и можно определить
вероятность пребывания системы в каждом из состояний. Эта
вероятность количественно совпадает с долей времени пребывания
системы в анализируемом состоянии.
Цепь Маркова называется неприводимой, если каждое из ее
состояний может быть достигнуто из любого другого состояния за
конечное число шагов n. В периодической цепи Mapкова существует
период возврата в текущее состояние, и этот период не равен одному
шагу. В апериодической цепи период возврата кратен шагу.
15

16.

Дискретные цепи Маркова описываются матрицей переходных
вероятностей R=
, элементы которой rij, представляют собой
вероятность того, что процесс в момент времени tn+1 находится в
состоянии j при условии, что в момент времени tn находился в
состоянии i.
Элементы матрицы rij принимают значения в диапазоне от нуля до
единицы; сумма элементов в каждой строке равна единице.
Цепь Маркова является неоднородной, если вероятности перехода
зависят от n, т.е. rij = rij(n). В противном случае цепь Маркова относится к
однородной.
16

17.

Вектор стационарного распределения вероятностей π =(π1​,π2​,…,πn​) ключевое понятие в теории цепей Маркова. Он описывает устойчивое
(стационарное) распределение вероятностей состояний системы, которое
устанавливается после достаточно большого числа шагов перехода,
независимо от начального распределения.
17

18.

19.

Для описания цепей Маркова используется стандартная схема, в
которой:
• каждое состояние представляется в виде вершины графа;
•между вершинами указываются дуги, отражающие возможность
перехода системы из i-го состояния в j-е за бесконечно малый
интервал Δt;
•над дугами проставляются величины интенсивностей переходов
λij.
Такой граф называется размеченным, и на основе этого графа
конструируются следующие соотношения:
система дифференциальных уравнений для исследования
переходных режимов, протекающих в анализируемой системе;
система алгебраических уравнений для вычисления компонент
вектора распределения стационарных вероятностей.
19

20.

Пример. Определить параметры (финальные вероятности: р0, р1, р2, р3) состояния
исследуемой системы, состоящей из двух узлов, которые под воздействием потоков
событий (отказов) переходят в нерабочее состояние с интенсивностями λ1 (для первого
узла) и λ2 (для второго узла), а под воздействием другого потока событий
(восстановления) переводятся в рабочее состояние с интенсивностями µ1 (для первого
узла) и µ2 (для второго узла). Потоки событий считаются Марковскими.
Алгоритм:
1. Выделить состояния исследуемой системы (можно построить граф).
2. Рассчитать (если требуется) интенсивности потоков.
3. Решить СЛАУ Колмогорова (добавить нормировочное уравнение)
20

21.

3 вопрос
Системы массового обслуживания

22.

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

23.

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

24.

Источники делятся на: конечные; бесконечные; с ограниченной
емкостью. Конечные источники характеризуются тем, что после
формирования очередной заявки они переходят в состояние ожидания
возвращения обслуженной заявки. В частности, это терминалы
информационной системы, которые после формирования задания для
выполнения сервером переходят в состояние ожидания ответного
сообщения. Бесконечные источники генерируют заявки, не дожидаясь
результатов обслуживания. Например, бесконечным источником является
общежитие, а заявками - студенты, выходящие из общежития и
направляющиеся на обед в столовую. Источники с ограниченной
емкостью р характеризуются тем, что они могут независимо
сформировать р заявок, а следующую (р+1)-ю заявку генерируют только
после обслуживания одной из ранее сформированных заявок.
Источники также классифицируются на: однородные и неоднородные.
Источники являются однородными, если формируемые ими заявки
имеют одинаковые вероятностные характеристики.
Неоднородные источники разбиваются на группы однородных
источников.
24

25.

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

26.

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

27.

Дисциплина обслуживания представляет собой механизм выбора
заявок из общей очереди или раздельных очередей.
Дисциплины обслуживания делятся на бесприоритетные и
приоритетные. В бесприоритетных дисциплинах не учитывается степень
важности заявок.
Наиболее известные бесприоритетные дисциплины обслуживания
заявок:
• в порядке поступления (FIFO);
• в инверсионном порядке (LIFO);
• на основе случайного выбора (RANDOM);
• на основе равномерного разделения приборов (processor sharing - PS),
в соответствии с которой каждая из n находящихся в системе заявок
обслуживается с одинаковой скоростью 1/n;
• на основе циклического алгоритма планирования (round robin - RR).
В приоритетных дисциплинах обслуживания каждой заявке
приписывается число, называемое приоритетом и характеризующее
степень важности заявки.
27

28.

Основные показатели производительности СМО: количество заявок,
находящихся в очереди; время пребывания заявок в очереди; количество
заявок, находящихся в системе, т.е. в очереди и на обслуживании; время
пребывания заявок в системе.
Учитывая, что перечисленные выше величины являются случайными,
они
описываются
вероятностными
характеристиками:
законами
распределения; средними значениями и дисперсиями.
Дополнительные показатели СМО: вероятность отказа в обслуживании
заявок; закон распределения времени простоев приборов и времени до
первого отказа в обслуживании.
28

29.

Поток событий { tk, k>1 } на интервале времени [0, ∞) представляет, собой
неубывающую последовательность случайных моментов t1, t2, t3, …, tk, ..., поступления
заявок в систему:
Поток событий по существу представляет случайный процесс x(t), принимающий
целочисленные значения, равные числу заявок, поступивших за интервал времени [0, t].
Случайный поток называется стационарным, если его вероятностный режим во
времени не изменяется.
Ординарность потока требований означает практическую невозможность
появления двух и более требований в один и тот же момент времени.
Отсутствие последействия состоит в том, что вероятность поступления за
отрезок времени τ определенного числа требований не зависит от того, сколько
требований уже поступило в систему раньше, т.е. не зависит от предыстории
изучаемого явления.
Простейший поток событий – это стационарный, ординарный поток без
последействия.
29

30.

Для простейшего потока вероятность поступления в
промежуток времени длительностью τ ровно k требований
определяется формулой Пуассона
где
(постоянное число) – интенсивность потока.
30

31.

Интенсивность
потока
λ
определяется
как
математическое ожидание числа требований в единицу
времени.
Для простейшего потока среднее число требований,
поступающих за время t, равно λt.
Для задания простейшего потока достаточно задать
только его параметр λ.
31

32.

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

33.

Классификация систем массового обслуживания
Общепринятая классификация СМО она включает четыре компоненты:
Первая компонента – характеристика входящего потока (М – закон
Пуассона; Ek – закон Эрланга k-го порядка; D – детерминированный поток;
G – произвольное распределение; НЕ – гиперэрланговское распределение;
HМ – гиперэкспоненциальное распределение; MAP – однородный
марковский поток.
Вторая компонента – характеристика времени обслуживания, в
качестве ее значений применяются такие же буквенные обозначения, как и
при описании входящего потока.
Третья компонента предназначена для задания количества
приборов и принимает целочисленное значение,
Четвертая компонента задает характеристики очереди.
Например, классификационное представление M/G/1/m описывает
разомкнутую одноканальную СМО с очередью ограниченной емкости т,
пуассоновским входящим потоком и произвольным распределением времени
обслуживания.
33

34.

ЗАДАНИЕ НА ПРАКТИЧЕСКОЕ ЗАНЯТИЕ
Задание 1. Цепь Маркова задана матрицей переходных вероятностей
Найти вектор стационарного распределения вероятностей
Задание 2. Определить параметры (финальные вероятности: р0, р1, р2, р3) состояния
исследуемой системы, состоящей из двух узлов, которые под воздействием потоков событий
(отказов) переходят в нерабочее состояние с интенсивностями λ1 (для первого узла) и λ2 (для
второго узла), а под воздействием другого потока событий (восстановления) переводятся в
рабочее состояние с интенсивностями µ1 (для первого узла) и µ2 (для второго узла). Потоки
событий считаются Марковскими.
Время безотказной работы и ремонта для узлов:
– первый узел: t₁₍б.р₎ = 2 ч, t₁₍рем₎ = 0,3 ч ,
– второй узел: t₂₍б.р₎ = 0,2 ч, t₂₍рем₎ = 0,1 ч.
34

35.

ЗАДАНИЕ НА ПРАКТИЧЕСКОЕ ЗАНЯТИЕ
Задание 3. Система массового обслуживания имеет один канал. Входящий поток заявок
на обслуживание – простейший поток с интенсивностью λ . Интенсивность потока
обслуживания равна μ (т. е. в среднем непрерывно занятый канал будет выдавать
обслуженных заявок). Длительность обслуживания – случайная величина, подчиненная
показательному закону распределения. Поток обслуживании является простейшим
пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят,
становится в очередь и ожидает обслуживания. Число мест в очереди для заявок, ожидающих
обслуживания, ограниченно и равно 3 ( т.е. (N - 1) = 3). Если в очереди уже находится три
заявки, то очередной поступившей заявке будет отказано в обслуживании. Поток заявок имеет
интенсивность λ= 0,85 (заявок в час). Время обслуживания в среднем равно 1,05 час.
Определить вероятностные характеристики системы, работающей в стационарном
режиме.
35

36.

ЗАДАНИЕ НА ПРАКТИЧЕСКОЕ ЗАНЯТИЕ
Задание 4. Определить вероятностные характеристики системы из Задания 3 при
условии, что длина очереди не ограничена.
Задание 5. СМО с 3 обслуживающими каналами. Входной и выходной потоки являются
пуассоновскими. Режим функционирования обслуживающего канала не влияет на режим
функционирования других обслуживающих каналов системы, причем длительность
процедуры обслуживания каждым из каналов является случайной величиной, подчиненной
экспоненциальному закону распределения. Поток поступающих заявок имеет интенсивность
λ= 1 заявка в секунду. Средняя продолжительность обслуживания tобсл= 1,8 сек.
Определить вероятностные характеристики системы.