fascículo 8

1

Semestre 6

Fascculo

8

Investigacin de

Operaciones

Semestre 6

Investigacin de operaciones


Semestre 6

Tabla de contenido Pgina

Introduccin 1

Conceptos previos 1

Mapa conceptual Fascculo 8 2

Logros 2

Teora de colas (Lneas de espera) 2

Sistemas de lneas de espera 4

Terminologa y estructura 6

Terminologa 6

Estructura 7

Patrones de llegada 8

Patrones de servicio 8

Distribucin exponencial 9

Proceso de Poisson 10

Notacin Kendall-Lee 12

Modelo M/M/1 13

Aplicaciones 14

Actividad de trabajo colaborativo 17

Resumen 17

Bibliografa recomendada 18

Seguimiento al autoaprendizaje 19

Crditos: 3

Tipo de asignatura: Terico Prctica

Semestre 6


Copyright2008 FUNDICIN UNIVERSITARIA SAN MARTN

Facultad de Universidad Abierta y a Distancia,

Educacin a Travs de Escenarios Mltiples

Bogot, D.C.

Prohibida la reproduccin total o parcial sin autorizacin

por escrito del Presidente de la Fundacin.

La redaccin de este fascculo estuvo a cargo de

JUAN CASTRO ORDOEZ

Docente tutor Programa de Ingeniera de Sistemas a Distancia.

Sede Bogot, D.C.

Correccin de estilo

Adriana Valencia Rodrguez

Diseo grfico y diagramacin a cargo de

SANTIAGO BECERRA SENZ

ORLANDO DAZ CRDENAS

Impreso en: GRFICAS SAN MARTN

Calle 61A No. 14-18 - Tels.: 2350298 - 2359825

Bogot, D.C., Marzo de 2012

1

Fascculo No. 8

Semestre 6


Investigacion de

operaciones

Introduccin

El ser humano siempre ha estado preocupado por disminuir el tiempo de

espera de una persona en una fila, es el reto de una empresa en aras de

prestar un mejor servicio o mejorar el plan de produccin en serie. Hoy en

da, todo se puede modelar como un sistema de colas, las cuales deben

ser vistas como clientes que llegan a una estacin de servicio y por medio

de operadores o servidores desean ser atendidos. Los clientes que se so-

meten a largas filas en un banco para ser atendidos, los pacientes quienes

esperan en una sala de emergencias, los aviones que esperan para aterri-

zar, mquinas que paran mientras son reparadas, las piezas que esperan

a ser procesadas, en fin, se podran citar cientos de ejemplos asociados a

una lnea de espera. La modelacin matemtica, propuesta por el esta-

dounidense A. K. Erlang en 1909, permiti analizar la congestin del trfi-

co telefnico. Para un tomador de decisiones gerenciales resulta indispen-

sable su conocimiento manejo de la teora de colas.

Conceptos previos

Para el buen desarrollo de ste fascculo y en general del aprendizaje de la

Investigacin de Operaciones, se debe tener en cuenta lo aprendido sobre

temas como:

Variables discretas y continuas.

Funcin de probabilidades.

Distribucin de probabilidad.

Funcin de densidad de probabilidad.

Funcin exponencial.

Teora de la decisin.

En consecuencia, responda las siguientes preguntas:

1. D tres ejemplos de variables continuas.

2. D tres ejemplo de variables discretas.

2


Investigacin de

operaciones

Fascculo No. 8

Semestre 6

3. Qu es una funcin de probabilidades?

4. Qu es una funcin de densidad de probabilidades?

5. Defina: a) Distribucin de probabilidad; b) Funcin exponencial.

Mapa conceptual Fascculo 8

Al finalizar el estudio de este fascculo, el estudiante:

Identifica y usa la terminologa de una lnea de espera.

Aplica frmulas para la solucin a un modelo de colas.

Teora de colas (Lneas de espera)

Hacer fila para lograr un servicio se ha vuelto tan comn y desgastante que

el tiempo que se pierde mientras se hacen acaba con la paciencia hasta

LogrosLogrosLogros

3


Fascculo No. 8

Semestre 6

Investigacion de

operaciones

Una cola se forma cuando el

tiempo que transcurre para

atender un cliente es mucho

mayor que el tiempo en llegar

el siguiente cliente.

de las personas ms tranquilas. La mayora anhela el da en que se les

ponga fin. Es tal la preocupacin por el asunto que muchas empresas no

ahorra esfuerzos por encontrar una salida a tan molesta prctica. Por for-

tuna, hoy en da cualquier fila se puede modelar como un sistema de co-

las.

La modelacin matemtica surgi gracias al estadounidense Agner Krarup

Erlang en 1909, al observar y analizar la congestin del trfico telefnico

que se presentaba en Copenhague. Hoy, la teora de colas, se ha generali-

zado a tal punto que resulta indispensable e imprescindible para cualquier

gerente que tome decisiones.

8.1

En su lugar de trabajo, enumere 5 actividades que se pueden modelar

con un sistema de lneas de espera.

La teora de colas se aplica frente a la demanda de un servicio y supone un

ejercicio matemtico que permita minimizar el tiempo transcurrido entre

atender uno u otro cliente.

Si bien tener demasiados servidores genera un costo muy elevado que las

empresas no estn dispuestas a asumir, no tener la capacidad de servicio

suficiente, puede degenerar en otros costos asociados por la demora en la

cola (prdida de tiempo valioso para el cliente) Entonces, lo ideal tener un

balance entre estos, el costo de servicio y el costo asociado por la espera.

La figura 8.1, es un modelo de decisin de una lnea de espera, basado en

los anteriores costos y cuyo objetivo es minimizarlos.

4


Investigacin de

operaciones

Fascculo No. 8

Semestre 6

Figura 8.1. Modelo de decisin de un sistema de lneas de espera basado en costos.

Fuente: HAMDY A. Taha, INVESTIGACIN DE OPERACIONES, 7a. edicin, Ed. PEARSON, Mxico 2004, pg. 580.

Sistemas de lneas de espera

Un sistema de lneas de espera es un conjunto conformado por clientes,

servidores y un orden tanto de llegada como de atencin de los clientes.

Los clientes y los servidores tambin son un conjunto.

En la figura 8.2, se pueden apreciar diferentes sistemas de lneas de espe-

ra. El normal, en donde hay un solo servidor y los clientes hacen la fila para

ser atendidos, figura 8.2 a); o, tambin se puede encontrar varios servido-

res y una sola fila, figura 8.2 b). De la misma manera, los hay en donde a

cada servidor se le ocasiona una fila, es decir, un sistema en paralelo, figu-

ra 8.2 c). Por ltimo, un cliente puede llegar al sistema de lnea de espera y

pasar por varios servidores para concluir con su servicio. Por lo general, en

cada uno de estos servidores se hace fila y necesariamente el cliente debe

pasar por dos o ms. A este sistema se le llama en serie, figura 8.2 d).

5


Fascculo No. 8

Semestre 6

Investigacion de

operaciones

Figura 8.2.

Sistemas de lneas de espera.

Fuente:

BRONSON Richard, INVESTIGACIN DE OPERACIONES, Ed. Mc Graw Hill, Mxico 1983, pg. 263.

6


Investigacin de

operaciones

Fascculo No. 8

Semestre 6

8.2

D 2 ejemplos de cada uno de los sistemas de lnea de espera de la fi-

gura 8.2.

Un modelo de sistema de lneas de espera, responde a las siguientes pre-

guntas:

1. Cunto tiempo est desocupado el servidor?

2. Cul es la cantidad de clientes esperada en una cola?

3. Cul es el tiempo que puede pasar un cliente en una cola?

4. Cules son las distribuciones de probabilidad de las preguntas 2 y 3?

5. Cuntos servidores se deben tener para que haya un servicio eficiente?

Uun sistema de lneas de espera se puede ver como un proceso de naci-

miento-muerte as:

Nacimiento: cuando un cliente entra al sistema.

Muerte: Cuando un cliente sale del sistema.

Terminologa y estructura

Terminologa

Aunque ya se han nombrado anteriormente, los elementos principales de

una lnea de espera son el cliente y los servidores. Los clientes siempre

provienen de una fuente (figura 8.2), que puede ser finita o infinita. Puede

suceder que al llegar al servidor o instalacin, sea atendido o esperar en

una fila o cola. Es de anotar, cuando una instalacin termina la atencin de

un servicio, el siguiente cliente quien se encuentra en la fila pasa al servi-

dor para ser atendido. Sino hay clientes este servidor queda inactivo u

ocioso, hasta la llegada de un cliente. Segn lo anterior, en el anlisis de

colas son primordiales, los patrones de llegada (tiempo entre llegadas) y

los patrones de servicio (tiempo de servicio) los cuales se analizarn,

ms adelante.

7


Fascculo No. 8

Semestre 6

Investigacion de

operaciones

Los componentes caracters-

ticos de un sistema de colas

son: los clientes, los servido-

res, tiempo de llegadas de

los clientes, tiempo de servi-

cio de los servidores, la ca-

pacidad del sistema, la dis-

ciplina de la cola y la canti-

dad de servidores.

Ahora, se definirn otros trminos requeridos en el anlisis de las lneas de

espera.

Tamao de la Cola: es el nmero mximo admisible de clientes quienes

pueden estar en el sistema. Es la capacidad del sistema y, puede ser

tanto en el servicio como en la lnea de espera. La capacidad puede ser

infinita o finita.

Disciplina de la cola: tiene que ver en la forma en que los clientes son

atendidos en la fila. La ms comn es que el primer cliente quien entra a la

fila sea el primero en ser atendido, esto es, servicio segn el orden de lle-

gada, disciplina FIFO. Tambin las hay LIFO, ltimo cliente en entrar sea el

primero en ser atendido. Las SIRO, si el servicio es en orden aleatorio. De

otro modo, las puede haber de acuerdo a ciertas prioridades (GD).

8.3

D dos ejemplos de cada una de las disciplinas de colas mencionadas

anteriormente.

Nmero de servidores: tanto el nmero como su distribucin (mecanis-

mo de servicio), es importante en un sistema de lneas de espera, ver figu-

ra 8.2.

Estructura

Diferentes estructuras de un sistema de lneas de espera han sido mostra-

das en la figura 8.2. La figura 8.3, representa otras caractersticas de la es-

tructura, que han sido descritas anteriormente en la terminologa.

8


Investigacin de

operaciones

Fascculo No. 8

Semestre 6

Figura 8.3. Estructura de un sistema de lneas de espera.


Patrones de llegada

Tambin enominados tiempo entre llegadas y denotada por , cuando el

patrn de llegada es consecutivo a la instalacin que ofrece el servicio.

Este patrn puede ser determinstico (conocerse exactamente) o proba-

bilstico; es decir, una variable aleatoria con distribucin conocida. Es im-

portante decir, que los clientes pueden llegar de uno en uno o por grupos.

Los patrones de llegada pueden depender incluso del estado de la cola

(nmero de clientes en cola) o no. En este caso, pueden haber rechazo

(se decide no tomar la cola por su tamao) o un abandono (el cliente des-

pus de estar en la fila, se retira, por el tiempo de espera).

Patrones de servicio

Nombrados de manera general como tiempo de servicio y denotada por

, es el tiempo que dura un servidor en atender un cliente. Igual que el an-

terior patrn, este patrn puede ser determinstico (conocerse exactamen-

te) o probabilstico; es decir, una variable aleatoria con distribucin cono-

cida. los patrones de servicio pueden depender del estado de la cola

(nmero de clientes en cola) o no. De igual manera, es relevante saber si

un servidor atiende totalmente a un cliente, figuras 8.2 a) a la c), o si el

cliente requiere de una secuencia de servidores, figura 8.2 d).

9


Fascculo No. 8

Semestre 6

Investigacion de

operaciones

Como su nombre lo indica, la teora de colas estudia el compor-

tamiento de los sistemas de colas mediante modelos matemti-

cos para obtener medidas de rendimiento. Esto con el fin de apo-

yar al tomador de decisiones en aras de mejorar la productividad

de la empresa y de satisfacer el cliente, quien por lo general, se

logra con un balance entre el costo de servir y el costo de esperar.

Se puede apreciar claramente que tanto en los patrones de llegada como

de servicio, en la mayor parte de los casos es bsicamente probabilstico;

entonces, se tiene variable aleatoria con distribucin probabilstica conoci-

da. La aleatoriedad en estos patrones se basa en que un evento ocurre sin

estar influido por el tiempo de ocurrencia del evento anterior. Para esto las

ms adecuadas y estudiadas son la distribucin exponencial y la distri-

bucin de Poisson o proceso de Poisson.

Distribucin exponencial

Los tiempos aleatorios de ocurrencia se describen en forma cuantitativa

mediante la distribucin exponencial, figura 8.4 y se define:

Figura 8.4. Distribucin exponencial y su fdp.


Con esperanza, varianza y P(tT):

10


Investigacin de

operaciones

Fascculo No. 8

Semestre 6

La carencia de memoria de la distribucin exponencial, es una propiedad soportada en que un evento ocurre sin

estar influido por el tiempo de

ocurrencia del evento ante-

rior.

En donde:

es la tasa de llegadas (llegadas/hora), y,

1/: tiempo promedio entre llegadas (horas/llegada),

T: tiempo dado.

Carencia de memoria de la distribucin exponencial. Esta propiedad de

la distribucin exponencial se basa en que un evento ocurre sin estar in-

fluido por el tiempo de ocurrencia del evento anterior.

Visto de otra forma, la distribucin exponencial es utilizada para describir el

tiempo entre llegadas en un nacimiento puro y el tiempo entre salidas de

una muerte pura.

Proceso de Poisson

Otra hiptesis de llegada de clientes es que llegan de acuerdo a un proce-

so Poisson, es decir, el nmero de clientes en cualquier momento dado

tiene una distribucin Poisson, figura 8.5. El proceso de llegadas al sistema

es totalmente aleatorio, pero con una tasa promedio conocida.

Figura 8.5. Distribucin de Poisson y su fdp.

Fuente: El autor.

11


Fascculo No. 8

Semestre 6

Investigacion de

operaciones

La funcin de densidad de probabilidad de Poisson es:

Con media y varianza:

Existe una estrecha relacin entre la distribucin exponencial y la de Pois-

son, puesto que una define automticamente la otra.

Teorema1. Los tiempos entre llegadas son exponenciales, con parmetro

, si y slo si, la cantidad de llegadas en un intervalo de duracin t sigue

una distribucin Poisson con parmetro t.

Entonces, este teorema establece:

Con media y varianza:

Siendo Nt: cantidad de llegadas que ocurre en un intervalo tiempo t cual-

quiera.

La distribucin exponencial ha desempeado un papel fundamen-

tal en la modelizacin de las lneas de espera, para representar

los tiempos tanto de arribos como de servicio, debido a la aleato-

riedad de los mismos y a su prdida de memoria. Con la distribu-

cin de Poisson, son un excelente complemento para la solucin

de este tipo de problemas.

1 WINSTON Wayne L., Investigacin de operaciones: Aplicaciones y algoritmos, 4 edicin, Ed. Thomson, Mxi-

co 2005, pg. 1055.

12


Investigacin de

operaciones

Fascculo No. 8

Semestre 6

Notacin Kendall-Lee-Taha

Es una notacin estndar (Kendall, 1951), para especificar las seis (6) ca-

ractersticas de un sistema de lnea de espera. La notacin es: 1/2/3/4/5/6,

donde:

1=Distribucin del patrn de llegadas y puede ser:

D=Determinstico,

M=Distribucin exponencial,

Ek=Distribucin Erlang tipo k (k=1, 2, ),

G=Cualquier otra distribucin.

2=Distribucin del patrn de servicio y pueden ser los mismos de 1.

3=Nmero de servidores en paralelo (1, 2, 3, , ).

4=Disciplina de la cola y puede ser:

FIFO, LIFO, SIRO y GD; descritas preliminarmente.

5=Capacidad del sistema (finita o infinita).

6=Tamao de la fuente (finito o infinito).

En muchos modelos 4/5/6 es DG// respectivamente, por lo tanto, a me-

nudo se omite.

8.4

Escriba tres ejemplos con la notacin completa de Kendall-Lee-Taha,

descrita anteriormente.

De todos los modelos posibles que se pueden hacer segn la notacin de

Kendall-Lee-Taha, se tratar el modelo con tiempo de llegadas y tiempo de

servicio exponenciales con un solo servidor.

13


Fascculo No. 8

Semestre 6

Investigacion de

operaciones

Modelo M/M/1

Una cola tiene las siguientes medidas de desempeo, eficiencia o funcio-

namiento:

L nmero promedio de clientes en el sistema.

Lq Longitud promedio de la cola.

W tiempo promedio que un cliente permanece en el sistema.

Wq tiempo promedio que un cliente espera en la cola.

W(t) probabilidad de que un cliente permanezca ms de t unidades de

tiempo en el sistema.

Wq(t) probabilidad de que un cliente permanezca ms de t unidades de

tiempo en la cola.

Las primeras cuatro medidas se obtienen de:

Y, de la relacin entre L y W, llamada la frmula de Little, y es:

Para el modelo M/M/1, , obteniendo:

14


Investigacin de

operaciones

Fascculo No. 8

Semestre 6

Donde:

; es el factor de utilizacin o intensidad de trnsito.

Si , se tiene:

;en donde,

Pn = probabilidad de estado estable.

8.5

Concrete qu pasa en estos tres casos:

Aplicaciones

A) Un cajero de un almacn atiende a los clientes quienes llegan en forma

aleatoria a una tasa de 4 por hora. Halle a) la media; b) la varianza; c) la

probabilidad de que un cliente sea atendido en menos de 15 minutos; y

d) la probabilidad de que un cliente se demore por lo menos 15 minutos

en caja.

a) , reduciendo a minutos, se tiene:

, entonces:

b)

c) T=15

Hay una probabilidad del 63.2%, que un cliente sea atendido en menos de

15 minutos.

15


Fascculo No. 8

Semestre 6

Investigacion de

operaciones

d)

Existe una probabilidad del 36.8% que un cliente se demore ms de 15

minutos en caja.

B) Para A), que las llegadas son Poisson, determine: a) Calcule la media y

la varianza b) La probabilidad que lleguen 5 clientes en una hora; c) La

probabilidad que lleguen 2 clientes entre las 9:30 y 10:00 de la maana.

a)

b)

Hay una probabilidad del 15.6% que lleguen 5 clientes en una hora.

c)

Existe una probabilidad del 27% que lleguen 2 clientes en una media hora

del da.

C) Un restaurante especializado en bocadillos tiene una ventanilla desde la

cual da servicio a los automovilistas en su vehculo. Llegan en promedio

40 clientes por hora a la ventanilla. Se requiere 1 minuto en promedio

atender a un cliente. Suponga que los tiempos entre llegadas y de ser-

vicio son exponenciales. (Winston, problema 4, pg. 1082)

16


Investigacin de

operaciones

Fascculo No. 8

Semestre 6

a. Cuntos clientes estn en la cola, en promedio?

b. Cunto tiempo, en promedio pasa un cliente en el restaurante (desde

el tiempo de llegada hasta que el tiempo de servicio se completa)?

c. En qu fraccin de tiempo hay ms de tres automviles esperando

servicio [esto comprende el automvil (si acaso alguno) en la ventani-

lla]?

Datos:

a. Cuntos clientes estn en la cola en promedio?

b. Cunto tiempo en promedio pasa un cliente en el restaurante (desde el

tiempo de llegada hasta que el tiempo de servicio se completa)?

c. En qu fraccin de tiempo hay ms de tres automviles esperando

servicio [esto comprende el automvil (si acaso alguno) en la ventani-

lla]?

Cuando

17


Fascculo No. 8

Semestre 6

Investigacion de

operaciones

Defina y d un ejemplo de cada uno de los siguientes conceptos:

1. Distribucin Erlang.

2. Cadena de Markov (Proceso markoviano).

3. Modelo de nacimientos puros.

4. Modelo de muertes puras.

5. Modelo M/M/1/GD/c/.

Lo primero que hay que decir es que los sistemas de colas predominan en

todo el universo. El efecto de un modelo matemtico de estos sistemas

debe redundar en la calidad de vida de las personas (clientes) y en la pro-

ductividad de las empresas. Todos los modelos de lneas de espera se

pueden representar mediante la notacin de Kendall-Lee-Taha que es:

1/2/3/4/5/6. El 1, representa la tasa de llegadas de los clientes al sistema

(); el 2, tasa de servicio al cliente por el operador del sistema (); el 3, es

la cantidad de servidores en paralelo; el 4, la disciplina de la cola (FIFO,

LIFO, SIRO o GD); el 5, la capacidad del sistema (finita o infinita); y, el 6,

tamao de la fuente (finito o infinito). Mediante la frmula de Little, se re-

suelve fcilmente un modelo M/M/1. Pero, es gracias a la distribucin ex-

ponencial, que se pueden resolver todos estos modelos.

A la teora de colas o de lneas de espera, se debe la efectividad con que

se han resuelto muchos problemas tanto para los clientes como para las

empresas. Ahora, se deja la invitacin a seguir en esta lnea, mediante la

simulacin de eventos discretos. Terma de gran aplicacin en la industria y

de excelente oportunidad para los ingenieros de sistemas de aprender

nuevos software como el ProModel y su debida programacin.

18


Investigacin de

operaciones

Fascculo No. 8

Semestre 6

BRONSON Richard, INVESTIGACIN DE OPERACIONES, Ed. Mc Graw

Hill, Mxico 1983.

HAMDY A. Taha, INVESTIGACIN DE OPERACIONES, 7a. edicin, Ed.

PEARSON, Mxico 2004. Texto gua.

HILLIER Frederick, LIEBERMAN Gerarld J., Introduccin a la Investigacin

de Operaciones, 3a. edicin, Ed. Mc Graw Hill, Mxico l982.

MOSKOWITZ Herbert, WRIGHT Gordon P., Investigacin de operaciones,

Ed. Prentice Hall, Mxico 1982.

WINSTON Wayne L., Investigacin de operaciones: Aplicaciones y algorit-

mos, 4 edicin, Ed. Thomson, Mxico 2005. Texto gua.

19


Fascculo No. 8

Semestre 6

Investigacion de

operaciones

Seguimiento al autoaprendizajeSeguimiento al autoaprendizajeSeguimiento al autoaprendizaje

Investigacin de operaciones - Fascculo No. 8

Nombre_______________________________________________________

Apellidos ________________________________ Fecha: _________________

Ciudad___________________________________Semestre: _______________

Con el fin de evaluar su proceso de autoaprendizaje, encuentre dos casos de

aplicacin de los siguientes temas:

1. Distribucin exponencial.

2. Distribucin de Poisson.

3. Modelo M/M/1.

fascículo 8

Documents