Investigación De Operaciones

1. QUE SON LAS CADENAS DE MARKOV

A un tipo especial de proceso estocástico discreto en el que la probabilidad de que ocurra un evento depende solamente del evento inmediatamente anterior. Esta característica de falta de memoria recibe el nombre de propiedad de Markov.

El término cadena de Márkov se usa para dar a entender que un proceso de Márkov tiene un espacio de estados discreto (infinito o numerable). Usualmente una cadena de Márkov sería definida para un conjunto discreto de tiempos (es decir, una cadena de Márkov de tiempo discreto), aunque algunos autores usan la misma terminología donde "tiempo" puede tomar valores continuos.

2. PROCESO Y MODELO ESTOCASTICO

Un proceso estocástico es aquel cuyo comportamiento es no determinista, en la medida que el subsiguiente estado del sistema está determinado tanto por las acciones predecibles del proceso como por elementos aleatorios. No obstante, de acuerdo a M. Kac y E. Nelson, cualquier desarrollo temporal (sea determinista o esencialmente probabilístico) que pueda ser analizable en términos de probabilidad merece ser denominado como un proceso estocástico.

3. CLASIFICACION DE LOS ESTADOS EN UNA CADENA DE MARKOV

Dados dos estados i y j, la trayectoria de i a j es la sucesión de transiciones que comienza en i y termina en j, de forma que cada transición de la secuencia tenga probabilidad positiva.

Un estado j es alcanzable desde un estado i si hay una trayectoria de i a j, por lo tanto si dos estados i y j se comunican si i es alcanzable desde j y j es alcanzable desde i.

Un conjunto de estados S en una cadena de Markov es cerrado (constituyen una clase de la cadena) sin ningún estado fuera de S es alcanzable desde un estado en S.

Un estado i es absorbente si Pij =1

Un estado i es transitorio si hay un estado j alcanzable desde i, pero el estado i no es alcanzable desde j.

Un estado i es absorbente recurrente si no es transitorio.

Un estado i es periódico con periodo k>1 si k es el menor número tal que todas las trayectorias que parten del estado i y regresan al estado i tienen una longitud múltiplo de k.

Si un estado recurrente no es periódico es aperiódico.

Si todos los estados de una cadena son recurrentes, aperiódicos y se comunican entre sí, la cadena es ergódica.

Probabilidades en estado estacionario:

Si P es la matriz de transición de una cadena ergódica de S estados entonces existe un vector p=[p1 p2 ...p3 ] tal que

Se le llama distribución de estado estable o de equilibrio para la cadena de Markov.

- p se puede determinar a partir de la ecuación: pj = Σ Pkj

-En forma K=1 matricial p =pp

- Este sistema tiene un número infinito de soluciones porque el rango de P siempre resulta ser menor o igual que s-1; También se debe verificar que,

p1 +π2 +... + ps = 1

INTERPRETACIÓN INTUITIVA DE LAS PROBABILIDADES DE ESTADO

ESTABLE.

La probabilidad de que una transición determinada deje el estado j es igual a la probabilidad de que una transición determinada entre al estado j.

La probabilidad de que una transición determinada deje el estado j = p j (1 − p j j)

La probabilidad de que una transición determinada entre al estado

En el estado estable el flujo de probabilidad hacia cada estado debe ser igual al flujo de probabilidad que sale de cada estado o sea son las probabilidades de equilibrio.

ANÁLISIS DE ESTADO TRANSITORIO: El comportamiento de una cadena de Markov antes de alcanzar el estado estable se llama comportamiento transitorio. Para su estudio se utiliza las fórmulas dadas anteriormente para Pi j(n).

EJEMPLO. El ascensor de un edificio con bajo y dos pisos realiza viajes de uno a otro piso. El piso en el que finaliza el viaje n-ésimo del ascensor sigue una cadena de Markov. Se sabe que la mitad de los viajes que parten del bajo se dirigen a cada uno de los otros dos pisos, mientras que si un viaje comienza en el primer piso, sólo el 25% de las veces finaliza en el segundo. Por último, si un trayecto comienza en el segundo piso, siempre finaliza en el bajo. Se pide:

a) Calcular la matriz de probabilidades de transición de la cadena

b) Dibujar el grafo asociado

c) ¿Cuál es la probabilidad de que, a largo plazo, el ascensor se encuentre en cada uno de los tres pisos.

SOLUCIÓN:

a) Los estados de la cadena los denotaremos por {0, 1, 2} haciendo corresponder el 0 al bajo y 1 y 2 al primer y segundo piso respectivamente.

Las probabilidades de transición son:

p00 = P (Rn=0 / Rn-1=0), esto es la probabilidad de que el ascensor se encuentre en la planta baja si en la etapa anterior estaba en la planta baja. Obviamente es 0, porque se supone que de etapa a etapa el ascensor se mueve.

p01 = P(Rn=1 / Rn-1=0), esto es la probabilidad de que el ascensor se encuentre en la planta primera si en la etapa anterior estaba en la planta baja. Obviamente es ½. Basta leer el enunciado. Y así sucesivamente vamos obteniendo las distintas probabilidades de transición cuya matriz es:

c)

4. TEORIA DE JUEGOS

Es un área de la matemática aplicada que utiliza modelos para estudiar interacciones en estructuras formalizadas de incentivos (los llamados «juegos») y llevar a cabo procesos de decisión. Sus investigadores estudian las estrategias óptimas así como el comportamiento previsto y observado de individuos en juegos. 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.

HISTORIA:

5. DILEMA DEL PRISIONERO

El dilema del prisionero es un problema fundamental de la teoría de juegos que muestra que dos personas pueden no cooperar incluso si en ello va el interés de ambas.

Fue desarrollado originariamente por Merrill M. Flood y Melvin Dresher mientras trabajaban en RAND en 1950. Albert W. Tucker formalizó el juego con la frase sobre las recompensas penitenciarias y le dio el nombre del "dilema del prisionero" (Poundstone, 1995).

Es un ejemplo de problema de suma no nula. Las técnicas de análisis de la teoría de juegos estándar, por ejemplo determinar el equilibrio de Nash, pueden llevar a cada jugador a escoger traicionar al otro, pero ambos jugadores obtendrían un resultado mejor si colaborasen.

En el dilema del prisionero iterado, la cooperación puede obtenerse como un resultado de equilibrio. Aquí se juega repetidamente, por lo que, cuando se repite el juego, se ofrece a cada jugador

...