TEORÍA DE COLAS: SISTEMAS DE COLAS

                                                REGRESAR A LISTADO DE TEMAS IO

Definiciones:

• Cliente: Entidad que entra al sistema con la necesidad de un servicio (proceso); estos se generan de una fuente que puede ser finita o infinita.
• Servidor: Elemento con la capacidad de proveer al cliente con el servicio que necesitan.
• Cola: Grupo de clientes que esperan a ser atendidos, cuando el o los servidores están ocupados, si llega un cliente nuevo al sistema se suma a la cola. Una cola se caracteriza por el número máximo de clientes que puede admitir. Las colas pueden ser finitas o infinitas.

Proceso básico de colas: Los clientes que requieren un servicio se ingresan al sistema. En determinado momento se selecciona un miembro de la cola, para proporcionarle el servicio, mediante alguna regla conocida como disciplina de servicio. Luego, se lleva a cabo el servicio requerido por el cliente, después de lo cual el cliente sale del sistema.

• Tiempo de espera entre llegadas: es el tiempo que separa la llegada entre un cliente y otro.
• Tiempo de atención: Tiempo que demora un servidor en atender a un cliente.

El tiempo para estudiar los sistemas de lineas de espera es continuo

• Estado del sistema: Números de clientes el sistema, incluyendo clientes en los servidores.
• Longitud de cola:  Número de clientes que esperan a ser atendidos en la cola.

Tipos de sistemas de colas:

• Un solo servidor, una  cola con una sola linea. Ejemplo de esto puede ser un Autoservicio (MiniMarket) con una sola caja registradora y una fila de clinetes esperando a pagar.

• Múltiples servidores, una  cola con una sola linea. Ejemplo de esto puede ser la linea de clientes preferenciales de un banco, donde son atendidos por cualquiera de los cajeros sin esperar más.

• Múltiples servidores para colas diferentes, aquí se hace una categorización de clientes, cada servidor debe atender a cierto tipo de cliente; es diferente a tener muchos servidores que atienden a todos los clientes que llegan de diferentes colas, lo cual se considera como un sola cola al no haber distinción entre clientes, ejemplo de esto es como las cajas registradoras en un gran almacén.

Notación kendall:    (a/b/c):(d/e/f)

Existen diferentes situaciones en que se presentan los sistemas de colas y las diferentes configuraciones que pueden presentar, según la prioridad sobre los clientes o las distribuciones de probabilidad de los tiempos de servicios o entre llegadas; Por lo tanto fue creado un sistema de notación estándar para identificar el comportamiento de cada sistema de colas llamado notación Kendall.

Este consta de 6 posiciones donde las más importantes son la 3 primeras y las 3 siguientes se usan en algunos casos.

  1. (a/ Distribución de probabilidad de tiempos entre llegadas.

Algunos tipos de distribución que aplican al tiempo entre llegadas son:
M: (markoviana), los tiempos entre llegadas siguen una distr, exponencial (negativa), que puede llegar a considerarse como distr. de Poisson( en algunos casos) donde se considera un proceso de "llegadas de Poisson" dado que ƛ = clientes/ unidad de tiempo.
G: (general), Aplica a cualquier tipo de distribución arbitraria. (Normal N, uniforme U,  entre otras.
Ek: (Erlang), Un caso especial de la distr. Gamma.
D: (Degenerada), tiempos constantes entre llegadas siempre.

  2. /b/ Distribución de probabilidad de tiempos de servicio (en el servidor). 

Aplican los mismos tipos de distribución que en el caso anterior.

  3. /c) Número de servidores en paralelo

  4. (d/ Disciplina de la cola, es decir la forma de atención y la prioridad que se da sobre los clientes:

FIFO: (First in first out), Un caso especial de la distr. Gamma.
LIFO: (Last in first out ), tiempos constantes entre llegadas siempre.

SIRO: (ramdon order), orden aleatoria de selección de clientes.

DG: (designated priority), La atención de los clientes sigue una prioridad definida con atenrioridad, por ejemplo cuando en un hospital se atiende primero a los pacientes con heridas más graves.

  5. /e/  Capacidad del sistema N finita o K infinita, si no hay una aclaración al respecto se considera infinita siempre.

  6.  /f)  Fuente de entrada de clientes al sistema, también puede ser N finita o K infinita.

Dependiendo de a, b y c podemos ver las características operativas del sistema. 

INTRODUCCIÓN A LA TEORÍA DE COLAS

¿POR QUÉ ESTUDIAR LAS COLAS?

                                                      REGRESAR A LISTADO DE TEMAS IO

La gente espera en un fila para recibir servicios en muchas ocasiones, en el banco, en la cafetería en el paradero del bus, "hacemos cola" hasta que es nuestro turno; de hecho según un articulo de  la revista Muy Interesante <<Acerca de en qué empleamos el tiempo de nuestra vida>> , nos dice que en promedio gastamos 500 días de nuestra vida esperando en una fila. 

Este fenómeno no es exclusivo de las actividades de los seres humanos: en una planta de producción de partes mecánicas, estas esperan a ser preparadas en la horno, los aviones deben pedir permiso a la torre de control y en ocasiones dar vueltas alrededor del aeropuerto antes de aterrizar, los autos esperan en un parqueadero antes de ser lavados en el -CarWash-; en fin los sistemas de colas están presentes también en procesos empresariales, industriales y/o de manufactura, y el estudio de las colas nos puede permitir reducir el impacto negativo de la espera.


NO se puede reducir la espera en la cola en su totalidad (casi en ningún caso), pero podemos reducirla a niveles aceptables sin utilizar recursos exagerados y así hacer más eficiente el sistema. Un estudio de colas determina las medidas de funcionamiento de una situación de colas ( tiempo de espera y longitud de cola etc.) Al determinar esta información se puede jugar con algunas variables controlables del sistema y decidir el nivel apropiado de servicio que estamos dispuestos a prestar.

Referencias:
Tomado del libro: INVESTIGACIÓN DE OPERACIONES UNA INTRODUCCIÓN; Hamdy A. Taha; Sexta edición.
Tomado de clase magistral de Investigación de operaciones 3

JUEGOS QUE NO ESTÁN ESTRICTAMENTE DETERMINADOS

REGRESAR A LISTADO DE TEMAS IO

Existen juegos en los que no convergen los criterios MAXMIN y MINMAX,  es decir que no son iguales y por lo tanto no se puede conocer el valor del juego inmediatamente(no hay punto de silla) y además  no existen estrategias dominantes, por que el juego no favorece a ninguno de los 2 jugadores:

• En este juego de papel, tijera o piedra; no hay punto de silla, ni estrategias dominantes. Los criterios MINMAX y MAXMIN no son iguales.

  

Entonces se tiene estrategias aleatorizadas, por que cada estrategia tiene cierta probabilidad de ser elegida en cada turno y la suma de probabilidades de elegir las estrategias para un jugador debe ser igual a 1. En estos casos, que son los comunes en la realidad, se desea conocer que estrategias son más convenientes de aplicar la mayor parte de la veces, es decir darles mayor probabilidad de ser usadas. Para concer estas estrategias, se debe realizar una reducción de la matriz de pago, para ignorar las estrategias menos convenientes:

Esto se explica más detalladamente en este ejemplo:

Reducción de matriz de pago para estrategias aleatorizadas

Mayor información sobre teoría de juegos

REGRESAR A LISTADO DE TEMAS IO

JUEGO DE SUMA CERO BIPERSONALES

REGRESAR A LISTADO DE TEMAS IO

En un juego bipersonal de suma cero, cada uno de dos jugadores tiene que escoger entre unas acciones dictadas a cada turno, y la pérdida de cada jugador es igual al beneficio del su contrincante, es decir, si se conoce lo que gana uno, se sabe o que perdió el otro y viceversa El tradicional juego infantil, puede ser un juego de suma cero si, ganr y perder tiene el mismo valor, para cada victoria o derrota.

La matriz de pagos de un juego bipersonal de suma cero tiene reglones etiquetados por las acciones del "jugador renglón" y columnas etiquetadas por las acciones del su contrincante, el "jugador columna." La entrada ij de la matriz es el pago que gana el jugador renglón en caso de que el jugador renglón usa acción i y el jugador columna usa acción j, para el caso de papel tijera y piedra, la matriz de pagos es:

El jugador renglón(JR), saca papel y el jugador columna (JC) saca piedra, entonces el JC  debe pagar una 1 al JR.

• Solución óptima a juegos de suma cero.

La solución óptima selecciona una estrategia constante o varias. Un jugador usa una estrategia pura si usa la misma acción a cada turno del juego. El jugador usa una estrategia mixta si a cada turno escoge al azar un acción para que cada acción se está usado una fracción determinada del tiempo. Representamos una estrategia mixta (o pura) del jugador reglón por una matriz con un solo renglón (vector probabilidad):    R = [a   b   c  . . . ] con lo mismo número de entradas que renglones, y en cual cada entrada representa la fracción de tiempo que está usada la correspondiente acción (o la probabilidad de usar aquel acción) y donde a + b + . . . = 1. Una estrategia mixta para el jugador renglón se represente por un vector probabilidad similar, pero en forma de columna C. Para ambos jugadores, estrategias puras son representadas por vectores probabilidad con un solo 1 y el resto de las entradas 0.

Supongamos ahora que tenemos esta matriz de pagos, los positivos(+) son la ganancia de JR  y los negativos(-) son la ganancia el jugador JC; en este caso el JR siempre debería sacar papel(estrategia dominante), por que sin importar lo que haga JC, va a ganar. La solución de este juego se basa en asegurar lo peor para cada jugador al elegir cada estrategia.

Lo peor que puede pasar por ejemplo  JR  si elige la estrategia papel es que gane solo 1, si elige tijera lo peor es que pierda 1 y si elige piedra lo peor es perder 2. Por su parte el  JC; si elige papel lo peor es perder 2; tijera, perder 2 y piedra, perder 1.

Lo siguiente es elegir los criterios "lo mejor de lo peor" o MAXIMIN para JR y lo "peor de lo mejor" o MINIMAX, para JC.  y esos resultados deben ser la elección de estrategias de JC y JR.  En este caso  JR  debe elegir la estrategia papel, como ya lo se hbaia mencionado y JC  debe elegir la estrategia piedra. Este resultado es a favor de JR. 

El valor del juego ValorJ, es el valor donde se cruzan las estrategias de ambos jugadores, en este caso el ValorJ = 1,   ambos jugadores usan la solución de punto de equilibrio o punto de silla.

Un juego es estrictamente determinado si tiene por lo menos uno punto de silla. Las siguientes declaraciones se aplican a los juegos estrictamente determinado:

1. Todos los puntos de silla en un juego tienen los mismos valores de pago.
2. Elegir el renglón y la columna que pasan por cualquier punto de silla de estrategias minimax para ambos jugadores. Es decir, el juego es solucionado por el uso de estas estrategias puras.

El valorJ de un juego estrictamente determinado es el valor del punto de silla. Un juego justo tiene un valor igual a cero, si no, es injusto o parcial.


Se le llama punto de silla por que la función que define a este punto es el paraboloide hiperbólico,  cuya gráfica parace una silla de montar a caballo, donde el púnto de silla es el centro, el punto donde se encuentran todas las lineas:

Podemos encontrar paraboloides hiperbólicos en los trabajos del arquitecto español-mexicano, Félix Candela (1910-1997), el “maestro de las cubiertas de hormigón” llevó al extremo las posiblidades estructurales de estas formas curvilíneas inversas, a través de finas estructuras laminares, con encofrados de madera, armado sencillo y vaciado de concreto.

Referencias:
Tomado del libro: INVESTIGACIÓN DE OPERACIONES UNA INTRODUCCIÓN; Hamdy A. Taha; Sexta edición.
http://www.zweigmedia.com/MundoReal/Summary3b.html

REGRESAR A LISTADO DE TEMAS IO

TEORÍA DE JUEGOS

REGRESAR A LISTADO DE TEMAS IO

Definición

La teoría de juegos es el área de la matemática aplicada que utiliza modelos para estudiar interacciones en estructuras formalizadas de incentivos (los llamados juegos) y tomar decisiones a partir de los resultados. Sus investigadores estudian las estrategias óptimas así como el comportamiento previsto y observado de individuos en juegos, la estadística es una rama de las matemáticas que surgió precisamente de los cálculos para diseñar estrategias vencedoras en juegos de azar. Tipos de interacción aparentemente distintos pueden, en realidad, presentar estructura de incentivo similar y, por lo tanto, se puede representar mil veces conjuntamente un mismo juego. El estudio de los juegos ha inspirado a científicos de todos los tiempos para el desarrollo de teorías y modelos matemáticos. La teoría de juegos es una herramienta que ayuda a analizar problemas de optimización interactiva. Tiene muchas aplicaciones en las ciencias sociales, la mayoría de las situaciones estudiadas por la teoría de juegos implican conflictos de intereses, estrategias y trampas.  Conceptos tales como probabilidad, media ponderada y distribución o desviación estándar, son términos acuñados por la estadística matemática y que tienen aplicación en el análisis de juegos de azar o en las frecuentes situaciones sociales y económicas en las que hay que adoptar decisiones y asumir riesgos ante componentes aleatorios.

Los principales expositores de la teoría de juegos fueron:

Jhon von Neuman(1903-1957): (su nombre en húngaro es Margittai Neumann János Lajos) es un matemático húngaro considerado por muchos como la mente más genial del siglo XX, comparable solo a la de Albert Einstein.

Oskar Morgenstern( 1902-1976): Nacido en Gorlitz, Silesia, estudia en las universidades de Viena, Harvard y New York. Miembro de la Escuela Austriaca y avezado matemático, participa en los famosos  "Coloquios de Viena " organizados por Karl Menger (hijo de Carl Menger) que pusieron en contacto científicos de diversas disciplinas, de cuya sinergia se sabe que surgieron multitud de nuevas ideas e incluso nuevos campos científicos. Emigra a Estados Unidos durante la segunda guerra mundial ejerciendo la docencia en Princeton. Publica en 1944, conjuntamente con John von Neuman, la "Theory of Games and Economic Behavior".

 

Conceptos fundamentales:

• Juegos: Se denomina juego a la situación interactiva especificada por el conjunto de participantes, las posibles estrategias que puede elegir cada participante, y el conjunto de pagos por ganar o por que el adversario pierda.

• Juegos NxM: Una forma de juegos de dos jugadores, en la cual un jugador tiene N acciones posibles(N estrategias) y el otro tiene M acciones posibles(M estrategias). En un juego así, los pares de utilidades o pagos pueden ser representados en una matriz y el juego es fácilmente analizable. Los juegos NxM dan una idea de cómo puede verse la estructura de un juego mas complejo.

• Estrategia: Cuando un jugador tiene en cuenta las reacciones y gestos corporales de los demás jugadores para elegir como proceder, se dice que el jugador tiene una estrategia. Una estrategia es un plan de acciones completo que se lleva a cabo cuando se juega. Se determina antes de que comience el juego, y prescribe cada decisión que los agentes deben tomar durante el transcurso del juego, dada la información disponible para el agente. La estrategia puede incluir movimientos aleatorios.
• Resultados de los juegos: El resultado de un juego es una cierta asignación de pagos finales. Se denomina resultado de equilibrio si ningún jugador puede mejorar su pago unilateralmente dado que los otros jugadores se mantienen en sus estrategias. Un equilibrio estratégico es aquel que se obtiene cuando, dado que cada jugador se mantiene en su estrategia, ningún jugador puede mejorar su pago cambiando de estrategia.
• Matriz de pago: La matriz de pagos de un juego, representa el resultado del juego en una matriz. Si  2 personas, A y B, están jugando un sencillo juego. El juego consiste en lo siguiente: la persona A tiene la posibilidad de elegir “derecha” o “izquierda”, mientras que B puede elegir “arriba” o “abajo”. Los resultados del juego se representan en la matriz de resultados, La matriz de resultados de un juego representa el resultado del juego en una matriz:

• Estrategia dominante: Una estrategia dominante es aquella elección que realiza el jugador independientemente de lo que haga el otro. En el juego representado en la matriz de arriba, la estrategia dominante para A es elegir “izquierda”, mientras que la estrategia dominante para B es elegir “abajo”. Estas estrategias dominantes dan como resultado un juego no equilibrado que favorece a A. Si cada jugador tiene una estrategia dominante se puede predecir el resultado del juego.

Referencias:
http://www.eumed.net/cursecon/economistas/neumann.htm
http://www.eumed.net/cursecon/economistas/morgenstern.htm
http://mashpedia.es/Teor%C3%ADa_de_juegos
http://www.econlink.com.ar/definicion/teoriadejuegos.shtml



REGRESAR A LISTADO DE TEMAS IO

TEORÍA DE DECISIÓN

REGRESAR A LISTADO DE TEMAS IO

El análisis de decisión implica es un proceso racional para escoger la mejor alternativa. el beneficio real que trae un alternativa depende de la calidad de los datos recogidos para tratar de describir el la situación de decisión. Todo proceso de decisión está en algunos de estos 3 tipos de categorías:

1. Toma de decisiones bajo certidumbre,  los datos de forma determinista, se sabe que va a suceder en cada estado.
2. Toma de decisiones bajo riesgo, los datos describen una distribución de probabilidad.
3. Toma de decisiones bajo incertidumbre, en la que no es posible asignar a los datos valoraciones concretas, para darles algún grado de relevancia  en el proceso de decisión.

• Toma de decisiones bajo certidumbre(Datos confiables conocidos).

Este modelos solo se debe aplicar para situaciones donde las alternativas se interrelacionan de con modelos matemáticos lineales bien definidas.

• Toma de decisiones bajo riesgo(probabilidades conocidas).

Bajo condiciones de riesgo, los resultados asociados con cada alternativa normalmente se describen con un distribución de probabilidad, o tienen asignados valores probabilistas cada uno. Por esta razón la toma de decisiones bajo riesgo se basa en el criterio del Valor esperado; se busca comparar las alternativas de decisión para maximizar la utilidad esperada o la minimización del costo. cuando existe un número finito de altenativas se puede utilizar un diagrama arboreo, a fin evaluar las alternativas.

• Toma de decisiones bajo incertidumbre(no se conoce ni la probabilidad ni datos concretos)

Implica un proceso de toma de decisiones , con alternativas cuyos resultados dependen de los estados de la naturaleza(aleatorios). Se posee información muy deficiente para tomar la decisión, no se tienen ningún control sobre el comportamiento e la situación, no se conoce como puede variar o la interacción de la variables del problema entre si, se pueden plantear diferentes alternativas de solución pero no se le puede asignar probabilidad a los resultados que arrojen.

Criterios Para la toma de Decisiones:

1. MaxMin (Pesimista):  Lo mejor de lo peor

2. MinMaX : Lo peor de lo mejor

3. Arrepentimiento (Criterio de Savage): Lo que se dejo de ganar

4.Valor Esperado (VE):  Lo que se espera ganar.

5. VEIPER ( Valor Esperado Información Perfecta)

REGRESAR A LISTADO DE TEMAS IO

CADENAS DE MARKOV ABSORBENTES

REGRESAR A LISTADO DE TEMAS IO

Conceptos iniciales:

• Estado accesible: cuando existe la probabilidad Fji >0 ; de comenzar en un estado j y después de n etapas llegar a un estado i.
• Estado recurrente:  Cuando de comienza en un estado j  y se tiene la certeza de volver en algún momento del tiempo ( n etapas) al estado j, es decir Fjj >0,  probabilidad de salir y llegar después a j es mayor que cero. 
• Estado transciente: Cuando no se tiene certeza de regresar a j si se salio de j en un momento pasado.
• Estado absorbente:  Una vez que se accede a este La probabilidad de quedarse en este estado es de 1 (100%), es decir, no se puiede salir de él.

Los Estados absorbentes  son por definición, Estados recurrentes.

Una CADENAS DE MARKOV ABSORBENTES, es la que tiene un Estado absorbente es su matriz de transición por ejemplo: 

Aquí podemos ver que al llegar al estado 5 no se puede salir del el, por que la probabilidad de volver a el es 1, para todos los periodos, mientras la matriz de transición se mantenga constante. De una cadena de Markov que consta de estados transitorios y absorbentes se dice que es una cadena absorbente de Markov.

Cuando tenemos situaciones en la que se nos presenta un proceso markoviano regido por una cadena absorbente, podemos obtener información muy importante de esta, como tiempo esperado es el que al comenzar en un estado no absorbente se  pasará a un estado absorbente y la probabilidad de que esto ocurra.

Para poder estudiar las cadenas hay que reordenar la matriz de transición de tal manear que las filas correspondientes a los estados absorbentes aparezcan en último lugar. Así ordenada se dirá que la matriz de transición está en la forma canónica. Podemos dividir la matriz en forma canónica en cuatro submatrices. La matriz identidad I que corresponde a la probabilidad de pasar a un estado absorbente desde uno absorbente, del orden correspondiente. La matriz nula 0 de solo ceros. La matriz A, contiene las probabilidades de paso de estados transitorios a estados absorbentes. La matriz N, que contiene las probabilidades de estados transitorios a estados transitorios.

Para hallar el tiempo esperado antes que el proceso sea absorbido, consiste en calcular el número esperado de veces que el proceso puede estar en cada estado no absorbente y sumarlos. Para esto se debe restar una matriz identidad I menos la matriz N y a esta matriz resultante sacarle la inversa, lo que nos da como resultado una matriz Fundamental F.

Teniendo que: I+N+N²+N³+ ….. = (I-N)^-1 = F, representa el número esperado de períodos que el sistema estará en cada estado no absorbente antes de la absorción, la suma de cada fila de F representa el promedio de períodos que transcurren antes de ir a un estado absorbente saliendo del estado en esa fila.

Para hallar la probabilidad de absorción por cualquier estado absorbente dado. Se construye una submatriz A  formada por la probabilidad de pasar de estados no absorbente a estados absorbentes en un paso, N*A representa la probabilidad de ir de un estado no absorbente a un estado absorbente en dos pasos exactamente y así sucesivamente. Por lo tanto:

A+N*A+N²*A+..... =( I+N+N²+N³+ ...)*A-->  (I-N)^-1.A = F*A= P(A), Y esta  matriz representa la probabilidad en que un estado no absorbente pase a un estado absorbente:

Ejemplo:
La Universidad LA SAPIENZA di ROMA a estudiado el comportamiento genera de sus estudiantes a través de datos recogidos en el departamento de admisiones y registro estudiantil y obtuvo los siguientes datos: 

1.  65% de los estudiantes de nuevo ingreso regresan al año siguiente a realizar el segundo año de ciclo básico, 15% de segundo año retornará como estudiante de nuevo ingreso y el resto Desertará del Alma Mater.
2. B) El 71% de los estudiantes de segundo año volverán al año siguiente como estudiantes de tercer año de estudios ya en la profundización profesional, el 22% regresará a repetir segundo año y el resto no regresara. 
3. C) El 83% de los estudiantes de tercer año regresaran al año siguiente como estudiantes de último año, 9% volverá como estudiante de tercer año y el resto no regresara. 
4. D) El 87% de los estudiantes de ultimo año se graduaran, y el 9% volverá como estudiante de ultimo año y el resto no regresara. Se desea conocer:

a) ¿Cuánto tiempo se espera de estudiantes de primer y segundo año para que puedan graduarse?. 

b) ¿Cuál es la probabilidad de estudiantes de primer y segundo año de graduarse?.

C) ¿Cuál es la probabilidad de un estudiante de tercer y último año de retirarse?

Ejercicio resuelto

Referencias:
Tomado del libro: INVESTIGACIÓN DE OPERACIONES UNA INTRODUCCIÓN; Hamdy A. Taha; Sexta edición.

http://www.sistemas.edu.bo/cbalderrama/sis%202210/PRESENTA%2009/9Markov.pdf

REGRESAR A LISTADO DE TEMAS IO