lunes, 1 de agosto de 2011

Temario

1.teoria de inventario
2.lineas de espera
3.cadenas de markov
4.programacion dinamica
5.teoria de colas
6.teoria de juegos

Programacion Dinamica


La programación dinámica.

Concepto

Frecuentemente para resolver un problema complejo se tiende a dividir este en subproblemas, más pequeños, resolver estos últimos (recurriendo posiblemente a nuevas subdivisiones) y combinar las soluciones obtenidas para calcular la solución del problema inicial. Puede ocurrir que la división natural del problema conduzca a un gran número de subejemplares idénticos. Si se resuelve cada uno de ellos sin tener en cuenta las posibles repeticiones, resulta un algoritmo ineficiente; en cambio si se resuelve cada ejemplar distinto una sola vez y se conserva el resultado, el algoritmo obtenido es mucho mejor.
Esta es la idea de la programación dinámica: no calcular dos veces lo mismo y utilizar normalmente una tabla de resultados que se va rellenando a medida que se resuelven los subejemplares.
La programación dinámica es un método ascendente. Se resuelven primero los subejemplares más pequeños y por tanto más simples. Combinando las soluciones se obtienen las soluciones de ejemplares sucesivamente más grandes hasta llegar al ejemplar original.
Ejemplo:
    Consideremos el cálculo de números combinatorios. El algoritmo sería:
    funcion C(n, k)
        si  k=0 o k=n entonces devolver 1
        si no devolver C(n-1, k-1) + C(n-1, k)
    Ocurre que muchos valores C(i, j), con i<n y j<k se calculan y recalculan varias veces.
Un fenómeno similar ocurre con el algoritmo de Fibonacci.
La programación dinámica se emplea a menudo para resolver problemas de optimización que satisfacen el principio de optimalidad: en una secuencia óptima de decisiones toda subsecuencia ha de ser también óptima.
Ejemplo: Si el camino más corto de Madrid a Barcelona pasa por Zaragoza, la parte del camino de Madrid a Zaragoza ha de ser necesariamente el camino mínimo entre estas dos ciudades.
Podemos aplicar esta técnica  en:
  •     Camino mínimo en un grafo orientado
  •     Arboles de búsqueda óptimos


·         La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones que se plantearán en el futuro.
·         Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no sigue una forma estándar. Así, para cada problema será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.
·         El procedimiento general de resolución de estas situaciones se divide en el análisis recursivo de cada una de las etapas del problema, en orden inverso, es decir comenzando por la última y pasando en cada iteración a la etapa antecesora. El análisis de la primera etapa finaliza con la obtención del óptimo del problema.

 MODELOS DE PROGRAMACIÓN DINÁMICA
Existen tres modelos diferentes manejados por WINQSB.
* Problema de la diligencia (Stagecoach Problem)
* Problema de la mochila (Snapsack Problem)
* programación de producción e inventarios (Production and Inventory Scheduling)






Es una técnica que parte del principio de no calcular dos veces la misma información, por lo tanto se utilizan estructuras de almacenamiento como vectores, tablas, arreglos, archivos, con el fin de almacenarlos resultados parciales, que contribuyan a la solución final.
Este algoritmo evita calcular dos veces la misma información, manteniendo una tabla de resultados conocidos, la cual se va llenando a medida que seresuelven los subcasos. Es una técnica ascendente que normalmente, empieza por los subcasosmás pequeños y más sencillos.Combinando sus soluciones, obtenemoslas respuestas para los subcasos cada vez mayores, hasta que llegamosa la solucióndel caso original.
La programación dinámica se aplica no solo por razones de eficiencia, sino porque permite resolver de manera eficiente problemas que no se pueden resolver por otras metodologías.
El mayor número de aplicaciones se encuentra en problemas que requieren optimización, ya que se pueden hallar múltiples soluciones y así evaluarlas para hallar la óptima.

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.
Aunque tiene algunos puntos en común con la teoría de la decisión, la teoría de juegos estudia decisiones realizadas en entornos donde interaccionan. En otras palabras, estudia la elección de la conducta óptima cuando los costes y los beneficios de cada opción no están fijados de antemano, sino que dependen de las elecciones de otros individuos. Un ejemplo muy conocido de la aplicación de la teoría de juegos a la vida real es el dilema del prisionero, popularizado por el matemático Albert W. Tucker, el cual tiene muchas implicaciones para comprender la naturaleza de la cooperación humana. La teoría psicológica de juegos, que se arraiga en la escuela psicoanalítica del análisis transaccional, es enteramente distinta.
Los analistas de juegos utilizan asiduamente otras áreas de la matemática, en particular las probabilidades, las estadísticas y la programación lineal, en conjunto con la teoría de juegos. Además de su interés académico, la teoría de juegos ha recibido la atención de la cultura popular. La vida del matemático teórico John Forbes Nash, desarrollador del Equilibrio de Nash y que recibió un premio Nobel , fue el tema de la biografía escrita por Sylvia Nasar, Una mente brillante (1998), y de la película del mismo nombre (2001). Varios programas de televisión han explorado situaciones de teoría de juegos, como el concurso de la televisión de Cataluña (TV3) Sis a traïció (seis a traición), el programa de la televisión estadounidense Friend or foe? (¿Amigo o enemigo?) y, hasta cierto punto, el concurso Supervivientes.[1]

 

Representación de juegos

Los juegos estudiados por la teoría de juegos están bien definidos por objetos matemáticos. Un juego consiste en un conjunto de jugadores, un conjunto de movimientos (o estrategias) disponible para esos jugadores y una especificación de recompensas para cada combinación de estrategias. Hay dos formas comunes de representar a los juegos.

 Forma normal de un juego


El jugador 2 elige izquierda
El jugador 2 elige derecha
El jugador 1 elige arriba
4, 3
-1, -1
El jugador 1 elige abajo
0, 0
3, 4
Un juego en forma normal
Artículo principal: Forma normal de un juego
La forma normal (o forma estratégica) de un juego es una matriz de pagos, que muestra los jugadores, las estrategias, y las recompensas (ver el ejemplo a la derecha). Hay dos tipos de jugadores; uno elige la fila y otro la columna. Cada jugador tiene dos estrategias, que están especificadas por el número de filas y el número de columnas. Las recompensas se especifican en el interior. El primer número es la recompensa recibida por el jugador de las filas (el Jugador 1 en nuestro ejemplo); el segundo es la recompensa del jugador de las columnas (el Jugador 2 en nuestro ejemplo). Si el jugador 1 elige arriba y el jugador 2 elige izquierda entonces sus recompensas son 4 y 3, respectivamente.
Cuando un juego se presenta en forma normal, se presupone que todos los jugadores actúan simultáneamente o, al menos, sin saber la elección que toma el otro. Si los jugadores tienen alguna información acerca de las elecciones de otros jugadores el juego se presenta habitualmente en la forma extensiva.
También existe una forma normal reducida. Ésta combina estrategias asociadas con el mismo pago.

 

 

 

 

 

Forma extensiva de un juego

http://bits.wikimedia.org/skins-1.17/common/images/magnify-clip.png
Un juego en forma extensiva.
La representación de juegos en forma extensiva modela juegos con algún orden que se debe considerar. Los juegos se presentan como árboles (como se muestra a la derecha). Cada vértice o nodo representa un punto donde el jugador toma decisiones. El jugador se especifica por un número situado junto al vértice. Las líneas que parten del vértice representan acciones posibles para el jugador. Las recompensas se especifican en las hojas del árbol.
En el juego que se muestra en el ejemplo hay dos jugadores. El jugador 1 mueve primero y elige F o U. El jugador 2 ve el movimiento del jugador 1 y elige A o R. Si el jugador 1 elige U y entonces el jugador 2 elige A, entonces el jugador 1 obtiene 8 y el jugador 2 obtiene 2.
Los juegos en forma extensiva pueden modelar también juegos de movimientos simultáneos. En esos casos se dibuja una línea punteada o un círculo alrededor de dos vértices diferentes para representarlos como parte del mismo conjunto de información (por ejemplo, cuando los jugadores no saben en qué punto se encuentran).
La forma normal da al matemático una notación sencilla para el estudio de los problemas de equilibrio, porque desestima la cuestión de cómo las estrategias son calculadas o, en otras palabras, de cómo el juego es jugado en realidad. La notación conveniente para tratar estas cuestiones, más relevantes para la teoría combinatoria de juegos, es la forma extensiva del juego.

Tipos de juegos y ejemplos

La teoría clasifica los juegos en muchas categorías que determinan qué métodos particulares se pueden aplicar para resolverlos (y, de hecho, también cómo se define "resolución" en una categoría particular). Las categorías comunes incluyen:



 Juegos simétricos y asimétricos

Artículo principal: Juego simétrico

E
F
E
1, 2
0, 0
F
0, 0
1, 2
Un juego asimétrico
Un juego simétrico es un juego en el que las recompensas por jugar una estrategia en particular dependen sólo de las estrategias que empleen los otros jugadores y no de quién las juegue. Si las identidades de los jugadores pueden cambiarse sin que cambien las recompensas de las estrategias, entonces el juego es simétrico. Muchos de los juegos 2×2 más estudiados son simétricos. Las representaciones estándar del juego de la gallina, el dilema del prisionero y la caza del ciervo son juegos simétricos.[2]
Los juegos asimétricos más estudiados son los juegos donde no hay conjuntos de estrategias idénticas para ambos jugadores. Por ejemplo, el juego del ultimátum y el juego del dictador tienen diferentes estrategias para cada jugador; no obstante, puede haber juegos asimétricos con estrategias idénticas para cada jugador. Por ejemplo, el juego mostrado a la derecha es asimétrico a pesar de tener conjuntos de estrategias idénticos para ambos jugadores.

 Juegos de suma cero y de suma no cero

Artículo principal: Juego de suma cero

A
B
C
1
30, -30
-10, 10
20, -20
2
10, -10
20, -20
-20, 20
Un juego de suma cero
En los juegos de suma cero el beneficio total para todos los jugadores del juego, en cada combinación de estrategias, siempre suma cero (en otras palabras, un jugador se beneficia solamente a expensas de otros). El go, el ajedrez, el póker y el juego del oso son ejemplos de juegos de suma cero, porque se gana exactamente la cantidad que pierde el oponente. Como curiosidad, el fútbol dejó hace unos años de ser de suma cero, pues las victorias reportaban 2 puntos y el empate 1 (considérese que ambos equipos parten inicialmente con 1 punto), mientras que en la actualidad las victorias reportan 3 puntos y el empate 1.
La mayoría de los ejemplos reales en negocios y política, al igual que el dilema del prisionero, son juegos de suma no cero, porque algunos desenlaces tienen resultados netos mayores o menores que cero. Es decir, la ganancia de un jugador no necesariamente se corresponde con la pérdida de otro. Por ejemplo, un contrato de negocios involucra idealmente un desenlace de suma positiva, donde cada oponente termina en una posición mejor que la que tendría si no se hubiera dado la negociación.
Se puede analizar más fácilmente un juego de suma cero, y cualquier juego se puede transformar en un juego de suma cero añadiendo un jugador "ficticio" adicional ("el tablero" o "la banca"), cuyas pérdidas compensen las ganancias netas de los jugadores.
La matriz de pagos de un juego es una forma conveniente de representación. Por ejemplo, un juego de suma cero de dos jugadores con la matriz que se muestra a la derecha.

 Criterios Maximin y Minimax

Los criterios maximin y minimax establecen que cada jugador debe minimizar su pérdida máxima:
  • Criterio Maximin: el jugador A, elige que su pago mínimo posible sea el mayor.
  • Criterio Minimax: el jugador B elige que el pago máximo a A sea el menor posible.

 Equilibrio de Nash.

Los equilibrios de las estrategias dominantes están muy bien cuando aparecen en los juegos, pero desafortunadamente, eso no ocurre con frecuencia. Un par de estrategias es un equilibrio de Nash si la elección del jugador A es óptima, dada elección de B, y la de B es óptima, dada la de A.
El equilibrio de Nash puede interpretarse como un par de expectativas sobre la elección de cada persona tal que, cuando la otra revela su elección, ninguna de las dos quiere cambiar de conducta.

Linea De Espera


Líneas de espera
Línea de espera:
Cuando el servicio no se proporciona en forma inmediata.
Disciplina:
El orden para dar el servicio.
SOP:
Servicio en orden de prioridad.
PLPS:
primero en llegar, primero en entrar.
SOA:
Servicio en orden aleatorio.
ULPS:
Ultimo en llegar , primero en salir.
Servidores secuenciales
Ejemplos: placas,licencia,escuela,al procesar un pronto.
Costo de espera y costo de servicio nomenclatura kendall
En una clinica los pacientes llegan en forma aleatoria , el tiempo de servicio es aleatorio hay 8 doctores para consultar a los pacientes, los cuales son atendidos en el orden en que llegan , únicamente se van atender a 25 personas en total.
  • Patrón de llegadas aleatorio.
  • Patrón de servicio aleatorio.
  • Un sólo servidor.
  • Al cliente se le atiende en el orden que llega.
  • No hay límite en la recepción de clientes.
  • Los Clientes proceden de una población infinita.
  • No hay abandono de la fila.
  • Hay espacio suficiente en el sistema.

El departamento para caballeros de un gran almacén tiene a un sastre para ajustes a la medida . Parece que el numero de clientesd que solicitan ajustes sigue una distribución de poisson con una tasa media de llegadas de 24 por hora, los ajustes se realizaron con un orden de primero que llega, primero en atenderse y los clientes siempre desean esperar ya que las modificaciones son gratis. Aparentemente el tiempo que tarda para realizar el ajuste , se distribuye exponencialmente con una media de 2 minutos.
  1. ¿Cuál es el numero promedio de clientes en la sala de espera?
  2. ¿Cuánto tiempo de permanencia en el sistema deberia de planear un cliente?
  3. ¿Qué % de tiempo poermanece ocioso el sastre?
  4. ¿Cuál es la probabilidad de que un cliente espere los sericios del sastre mas de 10 minutos?
  • Tiempo de servicio y de llegadas del tipo exponencial.
  • Llegadas aleatorias.
  • Múltiples servidoes.
  • PLPS
  • No hay límite de recepción de clientes.
  • Población infinita.
  • Hay epacio suficiente.
  • No hay abandono no rechazo.
Apliquese el modelo de servidores multiples para encontrar las caracteristicas de operación.
  1. Para dos servidores con una tasa de srvicio igual a 4 unidades por hora y una tasa de llegadas igual a 6 unidades por hora.
  2. Para 3 servidores en que cada servidor promedia 6 minitos por unidad y las llegadas en tran en un promexdio de 1 cada 3 minutos.

Ejemplo de modelo con servidores múltiples
El padre de un iglesia utiliza en la actualidad 2 confesionarios con filas separadas para atender las necesidas de sus feligreses se ha observado que las llegads son aleatorias a un ritmo de 30 personas por hora y el tiempo de servicio tiende a ser aleatorio tambien.Puesto que la cantidad de pecados por persona puede diferir en gran medidada.se ha determinado que el tiempo promedio que que se permanece en el confesionario es de 3 minutos.Se ha observado que las llegadas se distribuyen en forma equitativa entre las dos lineas.El padre esta considerando cambiar el sistema en que se utilice una sola fila que alimente ambos confesionarios. El padre deseas saber que sistema actual o el propueto coducira al tiempo promedio mas breve en el sistema.

Distribución Poisson y distribución exponencial negativa

Distribucion Poisson

Es una distribución probabilística que describe el numero de ocurrencias aleatorias en un periodo determinado
Pk
probabilidad k de llegadas por unidad d tiempo
K
num de llagadas por unidad de tiempo
A
num de llegadas por unidad de tiempo