Марковские процессы

Тема 6 Системы массового обслуживания.

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

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

Количество каналов-это число обслуживающих единиц в системе.

Поток заявок- это число клиентов, которые обращаются к системе с целью возможности обслуживаться.

СМО делятся на СМО с отказами, СМО с ограниченной очередью и СМО с неограниченной очередью.

СМО с отказами работают по принципу: если канал обслуживания занят- то заявка покидает систему (отказано в обслуживании).

По количеству каналов СМО делятся на одноканальные и многоканальные.

Обозначения

Все параметры систем и показатели работы систем представлены в таблице:

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

Если канал обслуживания занят- то заявка покидает систему (отказано в обслуживании)

t -среднее время обслуживания одного клиента

интенсивность потока обслуживания
-интенсивность потока заявок

абсолютная пропускная способность системы

относительная пропускная способность системы

Одноканальные СМО с очередью

вероятность существования очереди

Если р>1, то очередь растет до бесконечности

Если 0<р<1, то существует вероятность, что вас обслужат.

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

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

Если р=3, k=1

<0 Очередь неограниченна

Многоканальные СМО с очередью

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

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

К- общее число каналов

- среднее число занятых каналов

Задача 1 СМО с отказами одноканальная

T=2 мин/чел.

интенсивность потока обслуживания

абсолютная пропускная способность системы

относительная пропускная способность системы 0.25*100%=25%Количество обслуженных клиентов

Вывод: Система работает неэффективно при одном канале

Задача 2 СМО с отказами одноканальная

Дано:

абсолютная пропускная способность системы

относительная пропускная способность системы

Задача 3 СМО с отказами многоканальная

T=2 мин/чел.

N=5 каналов обслуживания

интенсивность потока обслуживания для одного канала

Q=1-р=1-0,093=0,907относительная пропускная способность системы

0,907*100%=90,7% Количество обслуженных клиентов абсолютная пропускная способность системы

Вывод: Система работает удовлетворительно при пяти каналах

Задача 4 Многоканальные СМО с очередью

Если р=0.8 k=3

Задача 4 Многоканальные СМО с очередью

Если р=0.8 k=3

Процесс работы СМО представляет собой случайный процесс. Случайным (вероятностным, стохастическим) процессом понимается процесс изменения закономерностями.

Процесс называется процессом дискретными состояниями, если его возможные состояния S₁, S₂, S₃,…можно заранее перечислить, а переход из одного состояния в другое переходит мгновенно (скачками).

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

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

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

Вероятности перехода из одного состояния в другое указывают направленными отрезками или дугами.

Вероятность состояния перехода можно записать в виде матрицы:

Правило записи матрица: сумма всех чисел каждой строчки = 1.

Пусть дана матрица перехода системы в новые состояния за один шаг. Найти матрицу перехода в новое состояние за 2 шага.

а₁₁ = 0,3·0,3 + 0,7·0,2 = 0,09 + 0,14 = 0,23

а₁₂ = 0,3·0,7 + 0,7·0,8 = 0,21 + 0,56 = 0,77

а₂₁ =

а₂₂ =

Найти матрицу перехода в новое состояние за 3 шага.

b₁₁ = 0,23·0,3 + 0,77·0,2 = 0,069 + 0,154 = 0,223

b₁₂ = 0,23·0,7 + 0,77·0,8 = 0,161 + 0,616 = 0,777

b₂₁ =0,22·0,7 + 0,78·0,2 = 0,066 + 0,156 = 0,222

b₂₂ =0,22·0,7 + 0,78·0,8 = 0,154 + 0,624 = 0,778

Процесс гибели и размножения

Граф состояния процесса гибели и размножения имеет вид:

  p₀₁ p₁₂ p₂₃ p_n-1,n   p₁₀ p₂₁ p₃₂ p_n,n-1

  S₁  

S₀  

  S₁  

S_n S₁  

S_n S₁  

  S₁  

S_n-1  

…

S₂

Особенности процесса гибели и размножения:

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

  λ₀₁ λ₁₂     λ₁₀ λ₂₁

  S₁  

S₀  

  S₁  

S₁  

S₂

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

Предельные вероятности перехода из одного состояния в другое

  5 4     7 8

  S₁  

S₀  

  S₁  

S₁  

S₂

λ₀₁ = 5; λ₁₂ = 4; λ₂₁ = 8; λ₁₀ = 7.

  S₁  

р₀ -? р₁ -? р₂ -?

S₀  

  S₁  

S₀  

  S₁  

S₁  

  S₁  

S₁  

р₀, р_1, р_2, р₃ -?

р² -? р³ -?

р² -?

•

•

  0,9 0,3 0,1   0,7      

Сумма входящих значений =1.

1)

2) λ10 = 1 λ23 = 5 λ03 = 2 λ21 = 4 λ32 = 3 λ12 = 2         р1 = 2р0

-3·2р0 + 4р2 = 0 - 6р0 + 4р2 = 0 2р2 = 6р0 р2 = 1,5р0 3р3 - 9·1,5р0 + 2·2р0= 0 3р3 - 13,5р0 + 4р0= 0 3р3 = 9,5р0 р0 + р1 + р2 + р3 = 1 р0 + 2р0 + 1,5р0 + = 1 = 1

3)

а₁₁ = 0,7·0,7 + 0,3·0,2 = 0,49 + 0,06 = 0,55

а₁₂ = 0,7·0,3 + 0,3·0,8 = 0,21 + 0,24 = 0,45

а₂₁ = 0,2·0,7 + 0,8·0,2 = 0,30

а₂₂ = 0,2·0,3 + 0,8·0,8 = 0,06 + 0,64 = 0,70

b₁₁ = 0,55·0,7 + 0,45·0,2 = 0,475

b₁₂ = 0,55·0,3 + 0,45·0,8 = 0,165 + 0,36 = 0,525

b₂₁ =0,30·0,7 + 0,7·0,2 = 0,35

b₂₂ =0,30·0,3 + 0,7·0,8 = 0,65

4)

а₁₁ = 0,3·0,3 + 0,2·0 + 0,5·0 = 0,09

а₁₂ = 0,3·0,2 + 0,2·0,1 + 0,5·0 = 0,08

а₁₃ = 0,3·0,3 + 0,2·0 + 0,5·0 = 0,09

а₂₁ = 0,3·0,3 + 0,2·0 + 0,5·0 = 0,09

а₂₂ = 0,3·0,3 + 0,2·0 + 0,5·0 = 0,09

а₂₃ = 0,3·0,3 + 0,2·0 + 0,5·0 = 0,09

а₃₁ = 0,3·0,3 + 0,2·0 + 0,5·0 = 0,09

а₃₂ = 0,3·0,3 + 0,2·0 + 0,5·0 = 0,09

а₃₃ = 0,3·0,3 + 0,2·0 + 0,5·0 = 0,09

S₀  

S₁  

  0,9 0,3 0,1   0,7      

5) Если система остается в том же самом состоянии, то переход осуществляется сам в себя и изображается в виде петли.

Сумма входящих значений = 1.

р₀₀ = 0,3

р₀₁ = 0,9

р₁₁ = 0,1

р₁₀ = 0,7

№ 2.12

№ 2.13.

2р1 – р2 + 0,8р1 = 0 р2 = 2,8р1 р4 = 0,5р1 р1 + 2,8р1 + 0,4р1 + 0,5р1 = 1 4,7р1 = 1

р1 = 2р4 р1 - 5р3 + р1 = 0 2р1 = 5р3

Задания для самостоятельного решения по теме №6

Тема 7. Динамическое программирование (ДП)

Постановка задачи динамического программирования (ДП)

Пусть экономическая система S может находиться в конечном числе состоянии S_k, k=1,2,…n и является управляемой и переходит из одного состояния в другое..

• Принцип оптимальности Беллмана.

Каково бы ни было состояние системы S перед очередным шагом, следует выбирать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

Пусть в результате операции, которую можно разбить на m шагов, некоторая физическая система перешла из состояния в состояние .

Эффективность операции на каждом шаге характеризуется показателем (выигрышем). Эффективность всей операции складывается из показателей эффективности на отдельных шагах:

Требуется на каждом шаге i выбрать такое решение ( - шаговое управление; X – управление всей операцией), чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

Задания для самостоятельного решения по теме №7

Решить задачу распределения инвестиций методом динамического программирования:

А) матричным методом

Б) табличным методом

n=3, m=5

xi	g1(xj)	g2(xj)	g3(xj)
	2,2		2,8
		3,2	5,4
	4,1	4,8	6,4
	5,2	6,2	6,6
	5,9	6,4	6,9

n=3, m=5

xi	g1(xj)	g2(xj)	g3(xj)
	2,4	2,1	2,9
	3,1	3,5	5,7
	4,2	4,9	6,6
	5,4	6,4	6,9
	6,1	6,7	7,2

Дата добавления: 2017-02-01