DISEÑO DE REDES TELEMÁTICAS
PROCESOS ESTOCASTICOS TALLER No. 4
COLAS M/M/1 y M/M/S
Presentado a:
Carlos Lesmes
Presentado por:
Jorge Andrés Chinome Reyes
Fredy Reinaldo Pineda Pedraza
library(queueing)
library(expm)
## Loading required package: Matrix
##
## Attaching package: 'expm'
## The following object is masked from 'package:Matrix':
##
## expm
1. Las estilistas Linda y Bella pueden atender cada una a un cliente a la vez. Tienen tres asientos para que los clientes puedan esperar cuando están ambas ocupadas. Si estos asientos están ocupados, los clientes adicionales no esperan. Las estilistas operan en forma independiente. Las probabilidades Pn de que haya exactamente n clientes en el sistema, para n = 0, 1, 2,. . ., 5 son \[P_0=0.15, P_1=0.1, P_2=0.25, P_3=0.28, P_4=0.16 \;\; y \;\; P_5=0.06\]
(a) Calcule \[L \;\; y \;\; L_q\]
\[\begin{matrix}n&|&Pn&nPn&(n-1)Pn\\-&-&-&-&-\\0&|&0.15&0(0.15)&(0-1)0.15\\1&|&0.1&1(0.1)&(1-1)0.1\\2&|&0.25&2(0.25)&(2-1)0.25\\3&|&0.28&3(0.28)&(3-1)0.28\\4&|&0.16&4(0.16)&(4-1)0.16\\5&|&0.06&5(0.06)&(5-1)0.06\end{matrix}\] Resultado: \[\begin{matrix}n&|&Pn&nPn&(n-1)Pn\\-&-&-&-&-\\0&|&0.15&0&-0.15\\1&|&0.1&0.1&0\\2&|&0.25&0.5&0.25\\3&|&0.28&0.84&0.56\\4&|&0.16&0.64&0.48\\5&|&0.06&0.3&0.24\end{matrix}\] \[L=\sum_{n=0}^{5}nPn\]
L=0+0.1+0.5+0.84+0.64+0.3
L
## [1] 2.38
\[Lq=\sum_{n=1}^{5}(n-1)Pn\]
Lq=0+0.25+0.56+0.48+0.24
Lq
## [1] 1.53
(b) Halle el número esperado de clientes que están siendo servidos.
NumCli=L-Lq
NumCli
## [1] 0.85
(c) Si llegan 3 clientes en promedio por hora, calcule \[W \;\; y \;\; W_q\]
lambda=3
w=L/lambda
w
## [1] 0.7933333
wq=Lq/lambda
wq
## [1] 0.51
(d) ¿Cuál es el tiempo esperado de un servicio?
Ts=w-wq
Ts
## [1] 0.2833333
2. Demuestre que: \[L=\sum_{n=0}^{s-1}nP_n+L_q+s\left(1-\sum_{n=0}^{s-1}P_n\right)\] Esta ecuación pertenece a un modelo de línea de espera finita, población infinita, tasa de llegadas y servicio constantes
Para s > 1, s < M \[C_n=\frac{\left(\frac{\lambda}{\mu}\right)^{n}}{n!}\;\;\;\;Para\;\;n=1,\;2,\;...,\;s\] \[C_n=\frac{\left(\frac{\lambda}{\mu}\right)^{n}}{(s!\;s)^{n-s}}\;\;\;\;Para\;\;n=s,\;s+1,\;...,\;M\;\;\;\;C_n=0,\;para\;\;n>M\] \[P_n=\frac{\left(\frac{\lambda}{\mu}\right)^{n}P_0}{n!}\;\;\;\;Para\;\;n=1,\;2,\;...,\;s\] \[P_n=\frac{\left(\frac{\lambda}{\mu}\right)^{n}P_0}{s!\;s^{n-s}}\;\;\;\;Para\;\;n-s,\;s+1,\;...,\;M\;\;\;\;P_n=0,\;para\;\;n>M\] \[P_0=\frac{1}{1+\sum_{n=1}^s\frac{\left(\frac{\lambda}{\mu}\right)^n}{n!}+\frac{\left(\frac{\lambda}{\mu}\right)^s}{s!}+\sum_{n=s+1}^M\left(\frac{\lambda}{s\mu}\right)^{n-s}}\] \[L_q=\frac{P_0\left(\frac{\lambda}{\mu}\right)^s\rho}{s!(1-\rho)^2}\left(1-\rho ^{M-s}-(M-s)\rho ^{M-s}(1-\rho)\right)\] \[L=\sum_{n=0}^{s-1}nP_n+L_q+s\left(1-\sum_{n=0}^{s-1}P_n\right)\] \[W=\frac{L}{\lambda}\;\;\;\;W_q=\frac{L_q}{\lambda}\;\;\;\;\lambda _0=(1-P_M)\]
3. Identifique los clientes y los servidores del sistema de colas en cada situación:
(a) La caja de salida de un supermercado.
CAJAS: Servidores, CLIENTES DEL SUPERMERCADO: Clientes del sistema
(b) Un puesto de bomberos.
CAMIONES DE BOMBEROS: Servidores, NÚMERO DE INCENDIOS: Clientes del sistema
(c) Una caseta de peaje.
NÚMERO DE CASETAS DE PEAJE: Servidor, AUTOMÓVILES: Clientes del sistema
(d) Un taller de carros.
PUESTOS DE SERVICIOS: Servidores, AUTOMÓVILES: Clientes del sistema
(e) Un muelle de carga y descarga.
NÚMERO DE BODEGAS: Servidor, NÚMERO DE CAMIONES: Clientes del sistema
(f) Un lavadero de carros.
PUESTOS DE LAVADO: Servidor, AUTOMÓVILES: Clientes del sistema
(g) Un taller que produce máquinas sobre pedido.
LÍNEAS DE PRODUCCIÓN: Servidor, NÚMERO DE PEDIDOS: Clientes del sistema
4. Un banco tiene dos cajeros en servicio. Los clientes llegan a una tasa de 40 por hora. Una cajera requiere en promedio dos minutos para atender a un cliente. Se sabe que los clientes esperan en cola un promedio de un minuto. Determine las medidas de desempeño básicas \[W, W_q, L \;\; y \;\; L_q\]
lambda=40
Mu=30*2
L=lambda/(Mu-lambda)
L
## [1] 2
W=L/lambda
W
## [1] 0.05
Wq=1/60
Wq
## [1] 0.01666667
Lq=lambda*Wq
Lq
## [1] 0.6666667
5. Considere un proceso de nacimiento y muerte con \[\mu_n=2\] para n = 1, 2, 3,. . . \[\lambda_0=3, \lambda_1=2, \lambda_2=1 \;\; y \;\; \lambda_n=0\] para n=3, 4, 5,. . .
(a) Construya el diagrama de tasas.
(b) Calcule \[P_0, P_1, P_2, P_3 \;\; y \;\; P_n\] para n = 4, 5, 6,. . .
\[\mu P_1=\lambda P_0\] \[2P_1=3P_0\;\;\rightarrow\;\;P_1=\frac{3}{2}P_0\] \[\lambda P_0+\mu P_2=\lambda P_1+\mu P_1\] \[3P_0+2P_2=2P_1+2P_1\;\;\rightarrow\;\;2P_2=4P_1-3P_0\;\;\rightarrow\;\;2P_2=4\left(\frac{3}{2}\right)P_0-3P_0\;\;\rightarrow\;\;2P_{2}=3P_0\;\;\rightarrow\;\;P_2=\frac{3}{2}P_0\] \[\lambda P_1+\mu P_3=\lambda P_2+\mu P_2\] \[2P_1+2P_3=P_2+2P_2\;\;\rightarrow\;\;2\left(\frac{3}{2}\right)P_0+2P_3=3\left(\frac{3}{2}\right)P_0\;\;\rightarrow\;\;2P_3=\frac{3}{2}P_0\;\;\rightarrow\;\;P_{3}=\frac{3}{4}P_{0} \] \[\lambda P_2+\mu P_4=\lambda P_3+\mu P_3\] \[P_2+2P_4=2P_3\;\;\rightarrow\;\;2P_4=2\left(\frac{3}{4}\right)P_0-\frac{3}{2}P_0\;\;\rightarrow\;\;2P_4=\frac{3}{2}P_0-\frac{3}{2}P_0\] \[P_4=0\] Ya que se cumple la siguiente ecuación donde: \[P_0+P_1+P_2+P_3+P_n=1\] Entonces: \[P_0+\frac{3}{2}P_0+\frac{3}{2}P_0+\frac{3}{4}P_0+0=1\] \[\left(1+\frac{3}{2}+\frac{3}{2}+\frac{3}{4}+0\right)P_0=1\] \[\frac{19}{4}P_0=1\;\;\rightarrow\;\;(4.75)P_0=1\;\;\rightarrow\;\;P_0=\frac{1}{4.75}=0.2105\] \[P_1=\left(\frac{3}{2}\right)P_0=0.3157\] \[P_2=P_1=0.3157\] \[P_3=\frac{3}{4}P_0=0.1578\] \[P_4=P_5=P_6=0\]
(c) Calcule \[W, W_q, L \;\; y \;\; L_q\]
L=(0*0.2105)+(1*0.3157)+(2*0.3157)+(3*0.1578)+(4*0)
L
## [1] 1.4205
Lq=L-(1-0.2105)
Lq
## [1] 0.631
lambda=1.58
lambda
## [1] 1.58
W=L/lambda
W
## [1] 0.8990506
Wq=Lq/lambda
Wq
## [1] 0.3993671
6. Compruebe que para una cola M/M/1 se tienen las siguientes relaciones:
7. Se tiene un buffer para la transmisión de mensajes que llegan con tiempos entre llegadas exponenciales con media E(X). El tiempo de transmisión de mensajes tiene distribución exponencial con media E(T). El buffer emplea una técnica de autorregulación de tal manera que cuando hay s o más mensajes todo mensaje que llega se rechaza con probabilidad 1-p. Encontrar la probabilidad de que un mensaje sea bloqueado.
\[\lambda P_0=\mu P_1\;\;\rightarrow\;\;P_1=\frac{\lambda}{\mu}P_0=\rho P_0\] \[\lambda P_1=\mu P_2\;\;\rightarrow\;\;P_2=\frac{\lambda}{\mu}P_1=\rho ^2 P_0\] \[\lambda \rho P_S=\mu P_{s+1}\;\;\rightarrow\;\;P_{s+1}=\frac{\lambda \rho}{\mu}P_s=P^{s+1}\rho ^2 P_0 \] \[\lambda \rho P_{s+1}=\mu P_{s+2}\;\;\rightarrow\;\;P_{s+2}=\frac{\lambda \rho}{\mu}P_{s+1}=P^{s+2}\rho ^2 P_0\] \[P_0=\frac{1}{1+\sum_{i=1}^{\infty}\prod_{n=1}^{i}\frac{\lambda _n -1}{\mu _n}}=\frac{1}{\sum_{i=0}^{s-1}P^i+\sum_{i=s}^{\infty}P^{i-s}P^i}=\frac{1}{\frac{1-P^s}{1-P}+P^5\sum_{i=5}^{\infty}(\rho P)^{i-s}}\] \[P_0=\frac{1}{\frac{1-P^s}{1-P}+\frac{P^s}{1-\rho P}}\] \[P_b=\sum_{i=s}^{\infty}(1-\rho)P_i=(1-\rho)P_0\sum_{i=s}^{\infty}\frac{P_n}{P_0}=(1-\rho)P_0\sum_{i=5}^{\infty}\rho ^{i-s}\rho ^i\] \[P_b=(1-\rho)P_0\frac{\rho ^s}{1-\rho}\]
8. Una población finita de usuarios de tamaño N, opera en un múltiplex estadístico en un ciclo continuo de pensar, esperar, servicio. Durante la fase pensar el usuario genera un mensaje. El mensaje hace cola detrás de otros mensajes, si los hay, esperando para ser transmitido. Cuando el mensaje llega a servicio se transmite por un canal de comunicación. Los tiempos de generación del mensaje y servicio tienen distribución exponencial con tasas \[\mu \;\; y \;\; \lambda\] respectivamente. El estado del sistema es el número de usuarios que esperan ser servidos.
(a) Haga el diagrama de tasas.
(b) Escriba las ecuaciones de balance
Estado 0 \[\mu P_1=\lambda NP_0 \;\;\rightarrow\;\;P_1=\frac{\lambda}{\mu}NP_0\] Estado 1 \[\lambda NP_0+\mu P_2=\lambda (N-1)P_1+\mu P_1 \;\;\rightarrow\;\;P_2=\frac{\lambda^2 (N-1)N}{\mu^2}P_0\] Estado 2 \[\lambda (N-1)P_1+\mu P_3=\mu P_2+\lambda (N-2)P_2 \;\;\rightarrow\;\;P_3=\frac{\lambda ^3N(N-2)(N-1)}{\mu}P_0\] Estado 3 \[\lambda (N-2)P_2=\mu P_3 \;\;\rightarrow\;\;P_3=\frac{\lambda ^3}{\mu ^3}N(N-1)(N-2)P_0\] Estado N-1 \[2\lambda P_{N-2}+\mu P_N= \mu P_{N-1}+\lambda P_{N-1} \;\;\rightarrow\;\;P_N=\frac{(\mu+\lambda)P_{N-1}-2\lambda P_{N-2}}{\mu}\] Estado N \[\lambda P_{N-1}=\mu P_N \;\;\rightarrow\;\;P_N=\frac{\lambda}{\mu}P_{N-1}\]
(c) Encuentre expresiones para \[C_n, P_0 \;\; y \;\; P_n\]
\[P_0=1-\rho\] \[P_n=\rho ^n\frac{N!}{(N-n)!}P_0\] \[C_n=\rho ^n\frac{N!}{(N-n)!}\]
9. Diez empleados comparten una oficina con cuatro teléfonos. Los empleados siempre estén haciendo una de dos actividades: trabajando o usando el teléfono. No se permiten otras actividades. Cada empleado opera continuamente como sigue: el empleado está inicialmente trabajando por un período de tiempo exponencial con parámetro \[\lambda\] Luego el empleado intenta usar una de las líneas telefónicas. Si todas las líneas están ocupadas el empleado es bloqueado y retorna a trabajar inmediatamente. Si un teléfono está disponible el empleado lo usa por un tiempo exponencial de parámetro \[\mu\] y retorna a trabajar.
(a) Defina un espacio de estados apropiado para este sistema.
(b) Haga el diagrama de estados para este sistema y muestre las tasas de transición.
(c) Escriba las ecuaciones de balance.
\[\mu P_1=10\lambda P_0\] \[10\lambda P_0+2\mu P_2=9\lambda P_1+\mu P_1\] \[9\lambda P_1+3\mu P_3=8\lambda P_2+2\mu P_2\] \[8\lambda P_2+4\mu P_4=7\lambda P_3+3\mu P_3\] \[7\lambda P_3=4\mu P_4\]
(d) Calcule la probabilidad de bloqueo para el sistema. Es decir, encuentre la proporción de intentos de solicitar servicio que serán bloqueados sobre el número de llegadas, en términos de los parámetros y de las probabilidades de estado.
\[P_B=P_4=\frac{7\lambda}{4\mu}\left[\left(\frac{60\lambda ^3 P_0}{\mu ^4}\right)-\left(\frac{15\lambda ^2 P_0}{\mu ^2}\right)\right]=P_0\left[\left(\frac{105\lambda ^4}{\mu ^4}\right)-\left(\frac{26.25\lambda ^3}{\mu ^3}\right)\right]\]
(e) Halle la tasa de generación promedio de llamadas.
\[\bar{\lambda}=\sum_{n=1}^{4}\lambda _i P_i\] \[\bar{\lambda}=\left(\frac{10\lambda P_0}{\mu}\right)+\left(\frac{45\lambda ^2 P_0}{2\mu ^2}\right)+\left(\frac{60\lambda ^3 P_0}{\mu ^3}\right)-\left(\frac{15\lambda ^2 P_0}{\mu ^2 }\right)+\left(\frac{105\lambda ^4 P_0}{\mu ^4}\right)-\left(\frac{26.25\lambda ^3 P_0}{\mu ^3}\right)\] \[\bar{\lambda}=\sum_{n=1}^4\lambda _i P_i=\left(\frac{10\lambda P_0}{\mu}\right)+\left(\frac{7.5\lambda^2 P_0}{\mu ^2}\right)+\left(\frac{33.75\lambda ^3 P_0}{\mu ^3}\right)+\left(\frac{105\lambda ^4 P_0}{\mu ^4}\right)\]
(f) Resuelva las ecuaciones de balance.
\[P_1=\frac{10\lambda P_0}{\mu}\] \[P_2=\frac{9\lambda P_1+\mu P_1 -10\lambda P_0}{2\mu}=\frac{9\lambda \left(\frac{10\lambda P_0}{\mu}\right)+\mu \left(\frac{10\lambda P_0}{\mu}\right)-10\lambda P_0}{2\mu}=\frac{\left(\frac{90\lambda ^2 P_0}{\mu}\right)}{2\mu}\] \[P_2=\frac{45\lambda ^2 P_0}{2\mu ^2}\] \[P_3=\frac{8\lambda P_2+2\mu P_2 -9\lambda P_1}{3\mu}=P_3=\frac{8\lambda \left(\frac{45\lambda ^2 P_0}{2\mu ^2}\right)+2\mu \left(\frac{45\lambda ^2 P_0}{2\mu ^2}\right)-9\lambda \left(\frac{10\lambda P_0}{\mu}\right)}{3\mu}\] \[P_3=\frac{\left(\frac{360\lambda ^3 P_0}{2\mu ^2}\right)+2\mu \left(\frac{45\lambda ^2 P_0}{2\mu ^2}\right)-\left(\frac{90\lambda ^2 P_0}{\mu}\right)}{3\mu}\] \[P_3=\left(\frac{60\lambda ^3 P_0}{\mu ^3}\right)-\left(\frac{15\lambda ^2 P_0}{\mu ^2}\right)\] \[P_4=\frac{7\lambda P_3}{4\mu}P_{4}=\frac{7\lambda}{4\mu}\left[\left(\frac{60\lambda ^3 P_0}{\mu ^3}\right)-\left(\frac{15\lambda ^2 P_0}{\mu ^2}\right)\right]\] \[P_4=\left(\frac{105\lambda ^4 P_0}{\mu ^4}\right)-\left(\frac{26.25\lambda ^3 P_0}{\mu ^3}\right)\]
(g) Para \[\mu=\frac{1}{3}\] llamadas por minuto. Recalcule.
\[(0)\;\;\rightarrow\;\;\frac{1}{3}P_1=10\lambda P_0\] \[(1)\;\;\rightarrow\;\;10\lambda P_0+\frac{2}{3}P_2=9\lambda P_1+\frac{1}{3}P_1\] \[(2)\;\;\rightarrow\;\;9\lambda P_1+P_3=8\lambda P_2+\frac{2}{3}P_2\] \[(3)\;\;\rightarrow\;\;8\lambda P_2+\frac{4}{3}P_4=7\lambda P_3+P_3\] \[(4)\;\;\rightarrow\;\;7\lambda P_3=\frac{4}{3}P_4\] Se sacan las ecuaciones: \[P_1=\frac{10\lambda P_0}{\frac{1}{3}}=30\lambda P_0\] \[P_2=\frac{9\lambda P_1+\frac{1}{3}P_1-10\lambda P_0}{\frac{2}{3}}=\frac{9\lambda (30\lambda P_0)+\frac{1}{3}(30\lambda P_0)-10\lambda P_0}{\frac{2}{3}}\] \[P_2=\frac{9\lambda (30\lambda P_0)}{\frac{2}{3}}=405\lambda ^2 P_0\] \[P_3=8\lambda P_2+\frac{2}{3}P_2-9\lambda P_1= 8\lambda (405\lambda ^2 P_0)+\frac{2}{3}(405\lambda ^2 P_0)-9\lambda (30\lambda P_0)\] \[P_3=3240\lambda ^3 P_0\] \[P_4=\frac{7\lambda P_3}{\frac{4}{3}}=\frac{7\lambda(3240\lambda ^3 P_0)}{\frac{4}{3}}\] \[P_4=17010\lambda ^4 P_0\]
10. Considere la cola M/M/s en la que los clientes llegan a una tasa promedio de uno cada media hora y cada servidor tarda un promedio 20 minutos por cliente y obtenga los siguientes resultados para s=1 y s=2 servidores. La hora es la unidad de tiempo.
Para la cola M/M/1 se tiene: \[C_n=\left(\frac{\lambda}{\mu}\right)^n=P^n\] \[P_0=1-\rho\] \[P_n=\rho^n(1-\rho)\] \[L=\frac{\rho}{1-\rho}=\frac{\lambda}{\mu-\lambda}\] \[L_q=\frac{\lambda^2}{\mu(\mu-\lambda)}\] \[W=\frac{1}{\mu-\lambda}\] \[W_q=\frac{\lambda}{\mu(\mu-\lambda)}=W-\frac{1}{\lambda}\] \[P(W>t)=e^{\mu(1-\rho)t}\] \[P(W_q>t)=\rho e^{\mu(1-\rho)t}\]
s=1
summary(QueueingModel(NewInput.MMC(lambda = 2, mu = 3, c = 1)))
## The inputs of the model M/M/c are:
## lambda: 2, mu: 3, c: 1, n: 0, method: Exact
##
## The outputs of the model M/M/c are:
##
## The probability (p0, p1, ..., pn) of the n = 0 clients in the system are:
## 0.3333333
## The traffic intensity is: 0.666666666666667
## The server use is: 0.666666666666667
## The mean number of clients in the system is: 2
## The mean number of clients in the queue is: 1.33333333333333
## The mean number of clients in the server is: 0.666666666666667
## The mean time spend in the system is: 1
## The mean time spend in the queue is: 0.666666666666667
## The mean time spend in the server is: 0.333333333333333
## The mean time spend in the queue when there is queue is: 1
## The throughput is: 2
\[\mu=3\] \[\lambda=2\] \[\rho=\frac{2}{3}\] \[P_0=1-\frac{2}{3}=0.333\] \[P_1=\frac{2}{3}\left(1-\frac{2}{3}\right)=0.222\] \[P_n=\frac{\left(\frac{2}{3}\right)^n}{n!}\frac{1}{3}\] \[L_q=\frac{\lambda^2}{\mu(\mu-\lambda)}=\frac{4}{3}=1.333\] \[L=\frac{\lambda}{\mu-\lambda}=2\] \[W_q=\frac{\lambda}{\mu(\mu-\lambda)}=\frac{2}{3}=0.666\] \[W=\frac{1}{\mu-\lambda}=1\] \[P\left(W_q>0\right)=0.666\] \[P\left(W_q>\frac{1}{2}\right)=0.404\] \[P\left(W_q>1\right)=0.245\] \[P\left(W>\frac{1}{2}\right)=0.61\]
s=2
summary(QueueingModel(NewInput.MMC(lambda = 2, mu = 6, c = 2)))
## The inputs of the model M/M/c are:
## lambda: 2, mu: 6, c: 2, n: 0, method: Exact
##
## The outputs of the model M/M/c are:
##
## The probability (p0, p1, ..., pn) of the n = 0 clients in the system are:
## 0.7142857
## The traffic intensity is: 0.333333333333333
## The server use is: 0.166666666666667
## The mean number of clients in the system is: 0.342857142857143
## The mean number of clients in the queue is: 0.00952380952380952
## The mean number of clients in the server is: 0.333333333333333
## The mean time spend in the system is: 0.171428571428571
## The mean time spend in the queue is: 0.00476190476190476
## The mean time spend in the server is: 0.166666666666667
## The mean time spend in the queue when there is queue is: 0.1
## The throughput is: 2
\[\mu=6\] \[\lambda=2\] \[\rho=\frac{1}{3}\] \[P_0=1-\frac{5}{7}=0.714\] \[P_1=\frac{2}{21}=0.095\] \[P_n=\frac{\left(\frac{1}{3}\right)^n}{n!}\frac{5}{7}\] \[L_q=0.009\] \[L=0.342\] \[W_q=0.004\] \[W=0.171\] \[P\left(W_q>0\right)=0.047\] \[P\left(W_q>\frac{1}{2}\right)=0.0003\] \[P\left(W_q>1\right)=2.16E_{-6}\] \[P\left(W>\frac{1}{2}\right)=0.37\]