1.- TEORIA DE INVENTARIOS
2.- LINEAS DE ESPERA
3.- SIMULACION
4.- CADENAS DE MARKOV
5.- PROGRAMACION DINAMICA
6.- TEORIA DE JUEGOS
domingo, 31 de julio de 2011
TEORIA DE JUEGOS
INTRODUCCIÓN.
En el presente trabajo se abordaran los antecedentes de la teoría de juegos a si como su descripción de estos mismo, el modo en el que se plantea, se desarrolla y se lleva a cabo.
Existen diversos tipos de teoria de juegos, los cuales de la misma manera de comentan en el presente documento. Este mismo fue realizado con el objetivo de acrecentar el conocimiento no solo economico, si no un conocimiento global, esto por que la teoria de juegos no solo es aplicable a la economia si no tiene muchos campos que van desde la biología hasta la filosofia, la cual se presenta de diversas maneras.
La teoria de juegos tiene una estrecha relacion con la teoria de decisiones la cual en el desarrollo del presente se obordara de la misma manera.
ANTECEDENTES DE LOS JUEGOS.
Los psicólogos destacan la importancia del juego en la infancia como medio de formar la personalidad y de aprender de forma experimental a relacionarse en sociedad, a resolver problemas y situaciones conflictivas. Todos los juegos, de niños y de adultos, juegos de mesa o juegos deportivos, son modelos de situaciones conflictivas y cooperativas en las que podemos reconocer situaciones y pautas que se repiten con frecuencia en el mundo real.
Un juego es una situación competitiva entre N personas o grupos, denominados jugadores, que se realiza bajo un conjunto de reglas previamente establecidas, con consecuencia conocidas. Las reglas definen las actividades elementales, o movimientos, del juego. Pueden permitirse diferentes movimientos para los distintos jugadores, pero cada jugador conoce los distintos movimientos de que disponen los otros jugadores.
Pero la Teoría de Juegos tiene una relación muy lejana con la estadística. Su objetivo no es el análisis del azar o de los elementos aleatorios sino de los comportamientos estratégicos de los jugadores.
PROGRAMACION DINAMICA
˜La programación dinámica se utiliza tanto en problemas lineales como no lineales.
˜La programación dinámica es útil para resolver un problema donde se deben tomar una serie de decisiones interrelacionadas.
˜A diferencia de la P.L, la programación dinámica no tiene formulación matemática estándar. Se trata de un enfoque de tipo general para la solución de problemas, y las ecuaciones se derivan de las condiciones individuales de los mismos.
El problema de la diligencia:
Un caza fortunas desea ir de Missouri a California en una diligencia, y quiere viajar de la forma más segura posible. Tiene los puntos de salida y destino conocidos, pero tiene múltiples opciones para viajar a través del territorio.
Se entera de la posibilidad de adquirir seguro de vida como pasajero de la diligencia.
¿Cual es la ruta que minimiza el costo total de la póliza de seguro?
1. Enumeración exhaustiva: Enumerar todas las rutas posibles, calcular su costo y elegir la de menor valor. En total son 18
2. Elegir la ruta más barata en cada etapa. Esta solución no conduce al óptimo global. Un pequeño sacrificio en una etapa puede permitir mayores ahorros más adelante.
Algunas alternativas de solución.
3. Programación dinámica.
Estrategia de solución: Un problema complejo es desagregado en problemas simples que se resuelven etapa por etapa. En el caso de la diligencia un problema simple sería pensar qué pasaría si al viajero sólo le faltara una jornada de viaje.
Por P.D la solución sería entonces ir desde el estado actual (cualquiera que sea) y llegar a su destino final (estado J) al costo cij Se hace lo mismo para cada jornada (etapa), ensanchando el problema. Así encontramos
la solución óptima del lugar al que debe
dirigirse teniendo en cuenta la información
de la iteración anterior.
Veamos la formulación:
Sea Xn ( n = 1,2,3,4 ) las variables que representan el destino inmediato en la etapa
n.
Luego la ruta seleccionada será:
Formulación.
A X1 X2 X3 X4
Donde X4 = J
sigue
19-10
Sea fn (S, Xn) el costo total de la mejor política global para las etapas restantes, dado que el agente se encuentra en el estado S, listo para iniciar la etapa n y se dirige a Xn
como destino inmediato.
Dados S y n , sea Xn
* el valor de Xn (no
necesariamente único), que minimiza fn (S , Xn) , y sea fn
*(S) el valor mínimo
correspondiente de fn (S, Xn) entonces: sigue sigue fn(S, Xn) =
Costo
inmediato
(etapa n)
Mínimo costo
futuro (etapa
n+1 en adelante)
+
= cs , xn + fn+1 * (Xn) Costos por ir de la ciudad i al destino j Costo óptimo acumulado fn *(S) = Min Xn fn (S, Xn) = fn (S, Xn *)
Como el destino final (estado J) se alcanza al terminar la etapa 4, entonces f5
*(J) = 0
El objetivo es hallar f1 *(A) y su ruta correspondiente. Cuando el cazafortunas tiene sólo una etapa por recorrer (n=4) , su ruta de ahí en adelante, estará determinada por el estado actual (H o I) y su destino
final X4 = J
La ruta será: S J donde S= H o I
Etapa n=4
Procedimiento de solución hacia atrás
3
19-13
f4 (H) = cH , J = 3
f4 (I) = c I , J = 4
= c S , J
S
H
I
f4 *(S) 3 4 X4 * J J
El cazafortunas tiene 2 etapas por recorrer (n=3). Suponga que sale de E. Etapa n=3 E H I C E, H =1 C E, I =4 + f4 *(H) = f3(E)= cE ,H + f4 *(H) = 4 + f4 *(I) = f3(E)= cE ,I + f4 *(I) = 8 Luego f4 *(S) = c S , J + f5 *(J)
Luego f3
*(E) = 4 y X3
* = H En general para la etapa 3 se tiene:
S
E
F
f3 (S, X3)= cS ,X3+ f4
*( X3)
4
9
f3
*(S)
8
7
X3
G
X3
*
6 7
H I
4
7
6
H
I
H
19-15
Etapa n=2
En la segunda etapa, el cazafortunas tiene 3 jornadas por recorrer (n=2). Suponga que sale de C + f3 *(E) = f2(C)= cC ,E + f3 *(E) = 7 + f3 *(F) = f2(C)= cC ,F + f3 *(F) = 9 + f3 *(G) = f2(C)= cC ,G + f3 *(G) = 10 C E F G c C , E =3
c C, F =2 c C , G =4 19-16
Luego f2
*(C) = 7 y X2 * = E
En general para la etapa 2 se tiene:
S
B
C
f2 (S, X2)= cS ,X2 + f3
*( X2)
11
7
f2 *(S) 11 9 X2 D X2 * 8 8 E F 11 7 8 E o F E E o F 12 10 11 G
Etapa n=1
En la primera etapa, el cazafortunas tiene todas las
jornadas por recorrer (n=1). Necesariamente debe
salir de A
+ f2
*(B) = f1(A)= cA ,B + f2
*(B) = 13
+ f2
*(C) = f1(A)= cA ,C + f2
*(C) = 11
+ f2
*(D) = f1(A)= cA ,D + f2
*(D) = 11
A
B
C
D
c A , B=2
c A, C =4
c A , D =3
Luego f1
*(A) = 11 y X1
* = C o D
Veamos :
S
A
f1 (S, X1)= cS ,X1 + f2 *( X1) 13
f1
*(S) 11 X1 X1 *
B C
11 11 C o D
D
Veamos la solución del problema gráficamente:
Podemos apreciar que partiendo de A existen 3 rutas óptimas:
Características de la P.D
1. El problema se puede dividir por etapas, que requieren una política de decisión en cada una de ellas.
2. Cada etapa tiene un cierto número de estados asociados a su inicio. (Estados son las diferentes condiciones posibles en las que se puede encontrar el sistema en cada etapa del problema).
3. El efecto de la política de decisión en cada etapa, es transformar el estado actual en un estado asociado con el INICIO de la siguiente etapa.
4. El procedimiento pretende hallar la política óptima para el problema completo. Esto quiere decir, la política a emplear desde cualquier posible estado del problema.
5. Dado el estado actual, la política óptima desde este estado es independiente de las políticas adoptadas en las etapas anteriores. (la solución depende únicamente del estado actual y no de cómo se llegó allí) PRINCIPIO
DE OPTIMALIDAD EN LA P.D,
(Richard Bellman, 1957)
6. El procedimiento de la solución termina cuando se obtiene la política óptima de la última etapa (por lo general la solución en esta etapa es trivial)
7. Siempre se dispone de una relación recursiva (esto es lo que permite trabajar las decisiones interrelacionadas).
La relación recursiva será:
fn
* (Sn)= Max Xn í fn (Sn, Xn) ý
o también fn
* (Sn)= Min Xn í fn (Sn, Xn) ý
Sn : Estado actual para la etapa n. Xn : variable de decisión
para la etapa n
N: número de etapas.
n: etiqueta para la etapa
actual (1,2,...,N)
8.Cuando se tiene una relación recursiva como la de la función, el procedimiento de solución “hacia atrás” inicia en la última etapa y se mueve hacia la primera, etapa por etapa
S
fn
*(Sn, Xn)= cS ,Xn+ fn+1
*( Xn) fn
Xn *(S) Xn
*
Xn
* : Valor óptimo de Xndado Sn 5
Algoritmo de P.D hacia atrás Para cada probable valor de la variable de estado al inicio de la etapa, determinar el mejor estado final.
Algoritmo de P.D hacia adelante Para cada probable valor de la variable de estado al final de la etapa, determinar el mejor estado inicial.
CADENAS DE MARKOV
Una cadena de Markov es una serie de eventos, en la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior. En efecto, las cadenas de este tipo tienen memoria. " Recuerdan" el último evento y esto condiciona las posibilidades de los eventos futuros. Esta dependencia del evento anterior distingue a las cadenas de Markov de las series de eventos independientes, como tirar una moneda al aire o un dado.
En la figura 4.1.1 se muestra el proceso para formular una cadena de Markov. El generador de Markov produce uno de n eventos posibles, Ej , donde j = 1, 2, . . . , n, a intervalos discretos de tiempo (que no tiene que ser iguales ). Las probabilidades de ocurrencia para cada uno de estos eventos depende del estado del generador. Este estado se describe por el último evento generado. En la figura 4.1.1, el último evento generado fue Ej , de manera que el generador se encuentra en el estado Mj .
La probabilidad de que Ek sea el siguiente evento generado es una probabilidad condicional : P ( Ek / Mj ). Esto se llama probabilidad de transición del estado Mj al estado Ek. Para describir completamente una cadena de Markov es necesario saber el estado actual y todas las probabilidades de transición.
Probabilidades de transición.
Una forma de describir una cadena de Markov es con un diagrama de estados, como el que se muestra en la figura 4.1.2. En ésta se ilustra un sistema de Markov con cuatro estados posibles : M1, M2 , M3 y M4 . La probabilidad condicional o de transición de moverse de un estado a otro se indica en el diagrama
Otro método para exhibir las probabilidades de transición es usar una matriz de transición. . La matriz de transición para el ejemplo del diagrama de estados se muestra en la tabla 4.1.1 .
Otro método para exhibir las probabilidades de transición es usar una matriz de transición. .
Para n = 0, 1, 2, ....
El superíndice n no se escribe cuando n = 1.
CADENAS DE MARKOV
INTRODUCCIÓN
El análisis de Markov tuvo su origen en los estudios de A.A.Markov(1906-1907) sobre la secuencia de los experimentos conectados en cadena y los intentos de descubrir matemáticamente los fenómenos físicos conocidos como movimiento browiano. La teoría general de los procesos de Markov se desarrollo en las décadas de 1930 y 1940 por A.N.Kolmagoron, W.Feller, W.Doeblin, P.Levy, J.L.Doob y otros.
El análisis de Markov es una forma de analizar el movimiento actual de alguna variable, a fin de pronosticar un movimiento futuro de la misma.
ANÁLISIS DE MARKOV
Afin de ilustrar el proceso de Markov presentamos un problema en el que los estados de resultados de actividades son marcas, y las probabilidades de transición expresan la probabilidad de que los consumidores vayan de una marca a otra. Supongamos que la muestra inicial de consumidores se compone de 1 000 participantes distribuidos entre cuatro marcas(A, B, C, D). Una suposición adicional es que la muestra representa a todo el grupo.
En la siguiente tabla la mayor parte de los clientes que compraron inicialmente la marca A, siguieron con ella en el segundo periodo. No obstante la marca A ganó 50 clientes y perdió 45 con otras marcas.
Marca | Periodo 1 Numero de Clientes | Ganancias | Perdidas | Periodo 2 Numero de Clientes |
A | 220 | 50 | 45 | 225 |
B | 300 | 60 | 70 | 290 |
C | 230 | 25 | 25 | 230 |
D | 250 | 40 | 35 | 255 |
1 000 | 175 | 175 | 1 000 |
Esta tabla no muestra la historia completa, sino que necesita un análisis detallado con respecto a la proporción de ganancias y perdidas netas entre las cuatro marcas. Es necesario calcular las probabilidades de transición para las cuatro marcas. Las probabilidades de transición se definen como la probabilidad de que determinada marca, conserve sus clientes. Para determinar lo anterior dividimos se divide el numero de clientes retenidos entre en numero de clientes en el periodo inicial, por ejemplo para la marca A (220- 45=175) se divide 175/220 lo que nos da 0.796, al igual para las otras marcas, obteniendo 0.767(B),0.891(C),0.860(D).
Para aquellos clientes que cambiaron de marcas , es necesario mostrar las perdidas y ganancias entre las marcas a fin de completar las matriz de probabilidades de transición. De acuerdo con los datos desarrollados, el paso siguiente consiste en convertir el cambio de marcas de los clientes de modo que todas las perdidas y ganancias tomen forma de probabilidades de transición, obteniendo la matriz de probabilidad de transición.
La siguiente tabla nos muestra la matriz de transición final.
A | B | C | D | |
A | 175/220=0.796 | 40/300=0.133 | 0/230=0 | 10/250=0.040 |
B | 20/220=0.091 | 230/300=0.767 | 25/230=0.109 | 15/250=0.060 |
C | 10/220=0.046 | 5/300=0.017 | 205/230=0.891 | 10/250=0.040 |
D | 15/220=0.067 | 25/300=0.083 | 0/230=0 | 215/250=0.860 |
La lectura de esta información sería la siguiente:
La marca A retiene 0.796 de sus clientes, mientras que gana 0.133 de los clientes de B, 0.40 de los clientes de D y 0 de los clientes de C.
La administración de mercadotecnia puede tener un gran ventaja de toda esta información que nos pueda arrojar el desarrollo de técnicas como estas, ayudando a la promoción de algunos productos que los necesiten para tener una mejor aceptación entre los consumidores.
Toma de decisiones Incertidumbre
Si se presenta cierta regularidad en los
fenómenos se puede minimizar la
incertidumbre mediante el desarrollo
de modelos probabilísticos.
Definiciones básicas
• Espacio muestral : El conjunto de resultados de un
experimento.
• Evento: Cualquier subconjunto del espacio
muestral.
•Variable aleatoria: Es una función que asigna
valores reales a los resultados de un experimento.
Proceso estocástico
Proceso que evolucionan en el tiempo
de una manera probabilística
Es una colección indexada de variables
aleatorias Xt en donde el índice t, toma
valores de un conjunto T dado
Sigue:
En puntos específicos del tiempo t el sistema se encuentra en
una de un número finito de categorías o estados mutuamente
excluyentes y exhaustivos, etiquetados 0,1,...,M
• Si T es contable o finito, el proceso se denomina
discreto.
• Si T es un subconjunto de los reales, el proceso se
denomina continuo.
Ejemplo
Una tienda de cámaras tiene en almacén un modelo
especial de cámara que puede ordenar cada semana.
Sean D1, D2,..., Dn , las demandas durante la primera,
segunda y n-ésima semana respectivamente.
Se supone que las Di son variables aleatorias que
tienen una distribución de probabilidad conocida.
•X0 : Número de cámaras que se tiene al iniciar el
proceso. Suponga que X0 = 0
•X1 : Número de cámaras que se tiene al final de la
semana 1.
•X2 : Número de cámaras que se tiene al final de la
semana 2
•Xn : Número de cámaras que se tiene al final de la
semana n.
Cadenas de Markov
Las cadenas de Markov tienen la propiedad
particular de que las probabilidades que describen la
forma en que el proceso evolucionará en el futuro,
dependen sólo del estado actual en que se encuentra el
proceso, y por lo tanto, son independientes de los
eventos ocurridos en el pasado.
Futuro
Presente
Pasado
•Si Xt = i , se dice que el proceso estocástico está en el
estado i en el tiempo t.
•Llamemos Pij la probabilidad de estar en el estado j
en el momento t+1, conocidos los estados anteriores
Proceso Markoviano
Pij = P {Xt+1 = j / X0 = k0, X1 = k1,..., Xt-1 = kt-1 ,Xt = i}
Pij = P {Xt+1 = j / Xt = i}
Pij = P {Xt+1 = j / Xt = i} Probabilidades
condicionales para
cada i y j
Pij = P {Xt+1 = j / Xt = i}= P {X1 = j / X0 = i}
para toda t=0,1..
Se llaman probabilidades de transición .
Si para cada i,j
Matriz de transición
P (acción suba mañana / subió hoy) = 0.7
P (acción baje mañana / subió hoy) = 0.3
P (acción suba mañana / bajó hoy) = 0.5
P (acción baje mañana / bajó hoy) = 0.5
Consideremos ahora el mismo mercado de
acciones, sólo que el que una acción suba o no
mañana, depende de si subió o no hoy y ayer.
Estado 0 La acción subió ayer y hoy
Estado 1 La acción bajó ayer y subió hoy
Estado 2 La acción subió ayer y bajó hoy
Estado 3 La acción bajó ayer y hoy
Por último consideremos el ejemplo del jugador.
Suponga que un jugador tiene $1
Su probabilidad de ganar es p, y allí gana $1
Su probabilidad de perder es 1- p, y allí pierde $1
El juego termina cuando el jugador acumula $3 o
bien cuando quiebra.
Este modelo es una cadena de Markov y sus
estados son:
Estado 0 El jugador está quebrado
Estado 1 El jugador tiene $1
Estado 2 El jugador tiene $ 2
Estado 3 El jugador tiene $ 3
Suscribirse a:
Entradas (Atom)