Investigacion de operaciones II

viernes, 3 de junio de 2011

Introduccion Teoria de decisiones

Es un estudio formal sobre la toma de decisiones. Los estudios de casos reales, que se sirven de la inspección y los experimentos, se denominan teoría descriptiva de decisión; los estudios de la toma de decisiones racionales, que utilizan la lógica y la estadística, se llaman teoría preceptiva de decisión. Estos estudios se hacen mas complicados cuando hay mas de un individuo, cuando los resultados de diversas opciones no se conocen con exactitud y cuando las probabilidades de los distintos resultados son desconocidas.

La toma de decisión es también un proceso durante el cual la persona debe escoger entre dos o más alternativas.

Teoria de juegos

Juegos bipersonales de suma cero

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.

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.

Estrategia mixta, Valor esperado

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.
El valor esperado del juego con matriz de pagos P que resulta por las estrategias mixtas R y C es dado por

e = RPC

El valor esperado del juego es el pago promedio por turno si cada jugador usa su estrategia mixta especificado por R y C después de un gran número de turnos.

Criterio minimax, Principios fundamentales de la teoría de juegos

Criterio Minimax
Un jugador quien usa el criterio minimax escoge una estrategia que, entre todas las estrategias posibles, minimiza el daño de la mejor contra-estrategia del otro jugador. Es decir, una estrategia óptima según el criterio minimax es una que minimiza el daño máximo que puede hacer el contrincante.
Encontrar la estrategia se llama solucionar el juego. Para juegos general, se puede usar el método simplex Sin embargo, se puede frecuentemente simplificar un juego y a veces solucionarlo por "reducir por predominio" y/o comprobar si es "estrictamente determinado".
Principios fundamentales de la teoría de juegos Cuando analizamos cualquier juego, hacemos los siguientes supuestos acerca de los dos jugadores:

Cada jugador hace la acción mejor posible.
Cada jugador sabe que su contrincante está también haciendo la acción mejor posible.

Reducir por predominio
Una acción domina a otra si todos sus pagos son por lo menos tan provechoso al jugador que los pagos correspondientes de la otra. En términos de la matriz de pagos, podemos decirlo como sigue:

Renglón r en la matriz de pagos domina a renglón s si cada pago en renglón r ≥ el pago correspondiente en renglón s.
Columna r en la matriz de pagos domina a columna s si cada pago en columna r ≤ el pago correspondiente en columna s.

Observe que si dos renglones o columnas son iguales, cada uno domina al otro. Un renglón o columna domina estrictamente a un otro si el uno domina al otro y son desiguales.
Siguiendo el primero principios de la teoría de juegos, la acción que corresponde a un renglón o columna estrictamente dominado nunca será jugado, y ambos jugadores son conscientes de esto por el segundo principio. Entonces cada jugador quien sigue los principios de la teoría de juegos eliminará repetidamente renglones y columnas dominadas como podría ser el caso. (En el caso que son iguales dos renglones o columnas, no hay razón para elegir uno sobre el otro, entonces cualquiera de los dos puede ser eliminado.) Este proceso se llama reducción por predominio.

Punto de silla, juego estrictamente determinado
Un punto de silla es un pago que es simultáneamente un mínimo de su renglón y un máximo de su columna. Para encontrar puntos de silla, Encierre en círculo los mínimos de todos los renglones y meta en caja los máximas de todas las columnas. Los puntos de silla son aquellas entradas que son simultáneamente en círculo y en caja.
Un juego es estrictamente determinado si tiene por lo menos uno punto de silla. Las siguientes declaraciones se aplican a los juegos estrictamente determinado:

Todos los puntos de silla en un juego tienen los mismos valores de pago.
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 valor 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.

Teoría de Juegos (conceptos)

Juegos Se denomina juego a la situación interactiva especificada por el conjunto de participantes, los posibles cursos de acción que puede seguir cada participante, y el conjunto de utilidades.

Estrategias Cuando un jugador tiene en cuenta las reacciones de otros jugadores para realizar su elección, se dice que el jugador tiene una estrategia. Una estrategia es un plan de acciones completo que se lleva a cabo cuando se juega el juego. Se explicita 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 del juego El resultado de un juego es una cierta asignación de utilidades finales. Se denomina resultado de equilibrio si ningún jugador puede mejorar su utilidad 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 utilidad cambiando de estrategia. Alternativamente, un perfil de estrategias conforma un equilibrio si las estrategias conforman la mejor respuesta a las otras.

Introduccion a la Teoria de Juegos

La teoría 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.

Desarrollada en sus comienzos como una herramienta para entender el comportamiento de la economía, la teoría de juegos se usa actualmente en muchos campos, como en la biología, sociología, psicología y filosofía. Experimentó un crecimiento sustancial y se formalizó por primera vez a partir de los trabajos de John von Neumann y Oskar Morgenstern, antes y durante la Guerra Fría, debido sobre todo a su aplicación a la estrategia militar —en particular a causa del concepto de destrucción mutua garantizada. Desde los setenta, la teoría de juegos se ha aplicado a la conducta animal, incluyendo el desarrollo de las especies por la selección natural. A raíz de juegos como el dilema del prisionero, en los que el egoísmo generalizado perjudica a los jugadores, la teoría de juegos ha atraído también la atención de los investigadores en informática, usándose en inteligencia artificial y cibernética.

Ejercicios resuletos Cadenas de Markov

1. Cadenas absorventes

En un juego participan dos jugadores, A y B. En cada turno, se lanza una moneda al aire. Si sale cara, A le da 1 dolar a B. Si sale cruz, B le da 1 dolar a A. Al principio, A tiene 3 dolares y B tiene 2 dolares. El juego continúa hasta que alguno de los dos se arruine. Calcular:

La probabilidad de que A termine arruinándose.

La probabilidad de que B termine arruinándose.

El número medio de tiradas que tarda en acabar el juego.

Tendremos una CM con un estado por cada posible estado de cuentas de A: S={1, 2, 3, 4, 5, 0}. Descomponemos Q:

Probabilidad de que A termine arruinándose.

La ruina de A está representada por el estado 0, que es el 2º estado absorbente. Como empezamos en el 3^er estado transitorio (A empieza con 3 dolares), debemos consultar la 3ª fila, 2ª columna de (I–Q’)^–1R, que nos da una probabilidad de 0,4 de que A empiece con 3 dolares y termine en la ruina.

Probabilidad de que B termine arruinándose

Como es el suceso contrario del apartado a), su probabilidad será 1–0,4=0,6. También podríamos haber consultado la 3ª fila, 1ª columna de (I–Q’)^–1R.

2.

Cada familia norteamericana se puede clasificar como habitante de una zona urbana, rural ó suburbana, durante un año determinado el 15% de las familias urbanas se cambian a la zona suburbana y el 5 % a la zona rural. El 6% de la familias suburbanas pasan a la zona urbana y el 4% a la rural, el 4% de las familias rurales pasan a la zona urbana y el 6% a la suburbana .

A. Matriz de transición

Debemos definir los estados

Eo = Zona urbana

E1 = Zona Rural

E2 = Zona Suburbana

	Eo	E1	E2
Eo	0.8	0.05	0.15
E1	0.04	0.90	0.06
E2	0.06	0.04	0.90

B. Si una familia vive actualmente en lazona urbana ¿ Cual es la probabilidad que después de dos años viva en la zona urbana?

Solución:

Buscamos T²

	Eo	E1	E2
Eo	0.651	0.091	0.258
E1	0.0716	0.8144	0.114
E2	0.1036	0.075	0.8214

El valor que buscamos se encuentra en azul y este nos indica que la probabilidad que buscamos es del 65.1 %.

Cadenas de Markov Absorventes

Una cadena de Markov con espacio de estados finito se dice absorbente si se cumplen las dos condiciones siguientes:
1. La cadena tiene al menos un estado absorbente.
2. De cualquier estado no absorbente se accede a algún estado absorbente.
Si denotamos como A al conjunto de todos los estados absorbentes y a su complemento como D, tenemos los siguientes resultados:

Su matriz de transición siempre se puede llevar a una de la forma

$P = \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}$

donde la submatriz Q corresponde a los estados del conjunto D, I es la matriz identidad, 0 es la matriz nula y R alguna submatriz.

$P_x(T_A < \mathcal{1} \,) = 1$ , esto es, no importa en donde se encuentre la cadena, eventualmente terminará en un estado absorbente.

Resultados de las cadenas absorventes:

La probabilidad de ser absorbido por un estado absorbente jÎS, suponiendo que empezamos en el estado transitorio iÎS, viene dada por el elemento (i,j) de la matriz (I–Q’)–1 R, que se denomina matriz fundamental de la CM.

CADENAS DE MARKOV

Condiciones generales:

Si P [Sj(k) / Sa(k-1), Sb(k-2), Sc(k-3).....] = P[Sj(k) / Sa(k-1)] para todo k, j,a, b, c,..... Entonces el sistema es un estado discreto de discretas transiciones de procesos de Markov. La implicación de esta condición es que la historia anterior del sistema a su llegada en (a) no tiene efecto en la transición a (j). En otras palabras, el sistema no tiene memoria.

Probabilidades de transición:

Para una cadena de Markov, se definen las probabilidades de transición como:

p_ij= P[Sj(k) / Si(k-1)] 1<= i,j <= m

y las p_ijson independientes de (k). Estas probabilidades pueden ser incluidas en una matriz de transición,

	P11	P12	........................	P1m
	P21	P22	........................	P2m
P=	.	.	.	.
	.	.	.	.
	Pm1	Pm2	........................	Pmm

También note que las transiciones de probabilidad satisfacen

0<=p_ij<=1

S p_ij =1, i = 1,2,3...........,m

.j=1

Debido a que los estados son mutuamente excluyentes y colectivamente exhaustivos.

La matriz P, proporciona una completa descripción del proceso de Markov el cual se usara para responder numerosas preguntas sobre un sistema. Por ejemplo,

1. Cuál es la probabilidad que el sistema este en Si después de k transiciones si el estado en k=0 es conocido?

Se puede responder la pregunta así:

P[Sj(k+1)]=P[S1(k)p_1j+P[S2(k)]p_2j+......+P[Sm(k)]p_mj,

Donde P[Sj(k+1)]=probabilidad que el sistema este en el estado Sj en el tiempo k+1.

En la ecuación anterior, j=1,2,.....,m. O de la siguiente forma:

P(k+1) = P(k)P , k=0,1,2......

Para responder a la pregunta 1 por inducción

	P(1) =	P(0)P
P(2)=	P(1)P=	P(0)P²
.	.	.
.	.	.
	P(k) =	P(0)P^k
		k=0,1,2......

Clasificación de los estados:

1. Límite de las probabilidades de estado:

Si k tiende a infinito, P(k) llega a una constante, entonces el limite de las probabilidades de estado existe y son independientes de la condición inicial.

Si p es un vector 1 x m definido como,

Lim_k_à_infinito P(k)= p

Entonces p puede satisfacer p =pP.

Para el ejemplo, esta ecuación se puede ser resueltacon la restricción

S_i^m p_i =1 para obtener (p₁ p₂)

2. Estado transitorio

S_i es un estado transitorio si se puede dejar el estado pero nunca retornar a él.

3. Estado absorbente

S_ies un estado absorbente si el sistema entra al estado y permanece ahí. Y el límite de la probabilidad de estado es 1. este estado es conocido también como estado trampa.

4. Cadena recurrente

Una cadena recurrente es un conjunto de estados de los que el sistema no puede salir. Un estado transitorio conduce al sistema dentro de este conjunto de estados. El sistema hace saltos dentro de este conjunto indefinidamente. La cadena recurrente es también llamada subcadena de Markov irreducible o de clases recurrentes.

Datos claves de la cadena de markov:

o Cada cadena de Markov debe tener al menos una cadena recurrente

o Una cadena recurrente es un estado absorbente generalizado

o Un proceso de Markov que tiene una cadena recurrente será completamente ergódica desde dondequiera que el inicie finalizara en cadena recurrente

o Si un proceso tiene dos o más cadenas recurrentes, entonces la propiedad ergódica no se mantiene en el tiempo

o Un estado transitorio es un estado que ocupa el sistema antes de convertirse en una cadena recurrente

Comportamiento a largo plazo de una cadena regular

La notación X(n)=(x₁(n),.....,x_k(n))^t representa la probabilidad de que una cadena se encuentre en cada uno de los estados en la etapa n.

X_c=Lim_n_à_infinitoX(n)=LX(0) donde L=Lim_n_à_infinitoTⁿ.

El vector X_c caracteriza el comportamiento a largo plazo de la cadena, ya que nos informa de la probabilidad de que la cadena se encuentre en cada uno de los estados cuando ha transcurrido un número grande de etapas. Al vector X_c se le llama distribución estacionaria de la cadena. El límite no siempre existe debido a la existencia de periodos.

"Se dice que una cadena de Markov con matriz de probabilidades de transición T (esta matriz es la transpuesta de la original) es regular si todos los elementos de matriz Tⁿson estrictamente positivos para algún valor de n."

Es decir, una cadena de Markov es regular si existe un número de etapas n tal que la probabilidad de la transición en n etapas entre cualquier par de estados es estrictamente positiva.

Cadenas ergódicas:

Si existe un n>0 tal que P_ijⁿ >0, i, j=0,1,2....m. la cadena de Markov, con esta propiedad, se llama ergódica. Entonces, P_ijⁿ = S_k=0 (P_ikⁿ * P_kj), luego p_j = S_k=0 (p_k * P_kj) y como S_j=0 P_ijⁿ = 1, entonces S_j=0 p_j=1

Teorema. Para una cadena de Markov ergódica, p_j=Lim_n_à_infinito P_ijⁿ existe y p_j(j pertenece {0,..,m}) es la única solución no negativa de p_j. Entonces:

p_j = S_k=0 (p_k * P_kj) y S_j=0 p_j=1.

Límites ergódicos en la cadena de markov:

La relación fundamental en una cadena de Markov es: Pⁿ =Mⁿ P₀. Y si nuestro interés es el comportamiento asintótico de P_n, es decir Lim_n_à_infinito P_nentonces elproblema es encontrar las condiciones para que este límite exista y en caso de existir, ¿dependerá del estado inicial del sistema?

Bajo condiciones de “regularidad” la distribución asintóticaexiste y bajo estas condiciones la distribución en el límite será independiente de la distribución inicial.