Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

CADENAS DE MARKOV, TEORIA DE COLAS, PROGRAMACION DINAMICA

INVESTIGACIO OPERATIVA II
by

brayan puelles olivares

on 5 September 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of CADENAS DE MARKOV, TEORIA DE COLAS, PROGRAMACION DINAMICA

CADENAS DE MARKOV
PROGRAMACIÓN DINÁMICA
INVESTIGACIÓN OPERATIVA II
Una sucesión de observaciones X1, X2, . . . se denomina proceso estocástico:
•Si los valores de estas observaciones no se pueden predecir exactamente
•Pero se pueden especificar las probabilidades para los distintos valores posibles en cualquier instante de tiempo.
A continuación se presenta una implementación de la programación dinámica. Al estudiarla se debe poner atención especial a los tres elementos básicos de un modelo de programación dinámica:
•Definición de las etapas
•Definición de las alternativas en cada etapa
•Definición de los estados para cada etapa
En general, de los tres elementos, la definición del estado suele ser la más sutil. La aplicación que aquí se presenta muestra que varía la definición de estado, dependiendo del caso que se modele. Sin embargo, al investigar cada aplicación encontrará útil tener en cuenta las siguientes preguntas siguientes:
•¿Qué relaciones vinculan entre si a las etapas?
•¿Qué información se necesita para tomar decisiones factibles en la etapa actual sin volver a examinar las decisiones tomadas en las etapas anteriores?
PROBLEMA DE LA MOCHILA/EQUIPO DE VUELO/CARGA DE CONTENEDOR
TEORIA DE COLAS
El estudio de las líneas de espera trata de cuantificar el fenómeno de esperar formando colas, mediante medidas representativas de eficiencia, como la longitud promedio de la cola, el tiempo promedio de espera y la utilización promedio de instalaciones.
proceso estocástico
cadena de markov
matriz de transición
es un proceso estocástico en el que, si el estado actual Xn y los estados previos X1, . . . , Xn-1 son conocidos entonces la probabilidad del estado futuro Xn+1:
•No depende de los estados anteriores X1, . . . , Xn-1, y
•Solamente depende del estado actual Xn.
Es una matriz cuadrada cuyos elementos son no negativos y tal que la suma de los elementos de cada fila es igual a 1.
Dada una cadena de Markov con k estados posibles s1, . . . , sk y probabilidades de transición estacionarias.
Dada una cadena de Markov con k posibles estados s1, . . . , sk y matriz de transición P
Si notamos P 2 ij = P (Xn+2 = sj |Xn = si)
P 2 ij: Elemento de la i−ésima fila y j−ésima columna de la matriz P 2
P m : Potencia m−ésima de P, con (m = 2, 3, . . .) y
P m ij : Elemento de la fila i y de la columna j de la matriz P m
GENERALIZANDO
•P m es la matriz de probabilidades pm ij de que la cadena pase del estado si al estado sj en m pasos; para cualquier valor de m, (m = 2, 3, . . .).
•P m es la matriz de transición de m pasos de la cadena de Markov
de un solo paso
La matriz de transición P de cualquier cadena de Markov finita con probabilidades de transición estacionarias es una matriz estocástica.
en varios pasos
matriz estocástica
Dada una cadena de Markov con k estados posibles s1, . . . , sk y probabilidades de transición estacionarias.
en un solo paso
VECTOR DE PROBABILIDADES INICIALES
El vector de probabilidades v = (v1, . . . , vk) se llama vector de probabilidades iniciales de la cadena.
El vector de probabilidades iniciales y la matriz de transición determinan la probabilidad para el estado de la cadena en el segundo instante de tiempo, dicha probabilidad viene dada por el vector vP
Supongamos que introducimos un ratón de forma aleatoria en una de las celdas de dicho laberinto, este ratón se traslada aleatoriamente de cada celda a una de las contiguas.
Consideremos el laberinto siguiente:
•Definiendo las variables aleatorias:
Xn celda ocupada en el instante n
•Los posibles estados:
n=1,2,3,4,5 y 6
Consideremos que la probabilidad de introducir el ratón en cada una de las celdas del laberinto para comenzar el experimento es la misma. Una vez dentro del laberinto el ratón se va a cualquier celda contigua o se queda en la celda en la que está con la misma probabilidad.
MODELO DEL JARDINERO
Cada año, al comenzar la estación de para trabajar los jardines (de marzo a setiembre) un jardinero usa una prueba química para determinar el estado del suelo. Dependiendo del resultado, la productividad para la nueva estación cae en uno de estos tres estados: 1) bueno, 2) regular y 3) malo.
A través de los años el jardinero observó que las condiciones meteorológicas prevalecientes durante el invierno (de octubre a febrero) juegan un papel muy importante en la determinación de la condición del suelo, dejándolo igual o empeorándolo, pero nunca mejorándolo
Las probabilidades de transición en P1 indican que la productividad de determinado año no puede ser mejor que la del año anterior. El jardinero puede alterar las propiedades de la transición P1 con otras acciones, en el caso normal se aplica fertilizante para mejorar las condiciones del suelo, y se produce la siguiente matriz de transición:
$ ingresos
Supongamos que el jardinero desea jubilarse de la jardinería dentro de N años(en este caso 3 años). Lo que interesa es determinar las acciones óptimas de cada año (fertilizar o no) que produzca los ingresos esperados máximos al final de N años(es decir 3 años).
Sean k=1y2 las dos acciones disponibles del jardinero. Las matrices de Pk y Rk que representa las probabilidades de transición y la función de recompensa para la alternativa k.
m=cantidad de estados en cada etapa (año)=3 en el problema del jardinero.
Fn(i)=ingreos óptimo esperado en las etapas n,n+1…N, cuando i es el estado del sistema(condiciones del suelo al comenzar el año n.
La solución óptima indica que para los años 1 y 2, el jardinero debe aplicar fertilizante independientemente del estado del sistema (condiciones del suelo, determinadas por medio de las pruebas químicas). En el año 3 se debe aplicar fertilizante solo si el sistema está en el estado 2 ó 3 (condiciones del suelo regulares o malas). Los ingresos totales esperados en los tres años son f1(1)=10.74, si el estado del sistema en el año es bueno, f1(2)=7.92, si es regular, y f1(3)=4.23 si es malo.
Cliente: quien recibe el productoServidor: donde se ofrece el servicio.
Fuente: de donde provienen los clientes
Instalación: donde se recibe el servicio o se espera en cola.
Tiempo de llegada y de servicio: tiempos en que se acercan y son atendidos respectivamente
Tamaño de la cola: cantidad de clientes en espera
Disciplina de la cola: orden en que se seleccionan a los clientes de una cola
Saltar: pasar de una cola a otra en busca de menor tiempo de espera
elementos de un modelo de cola
modelo generalizado de Poisson
colas especializadas de Poisson
El modelo general comprende una combinación de llegadas y salidas, basándose en la hipótesis de Poisson: “Los tiempos entre llegadas y de servicio tienen una distribución exponencial.” Es decir que la llegada de clientes o la terminación de un servicio no están influidos por el tiempo que haya transcurrido desde la ocurrencia del evento anterior, es aleatoria.
Este modelo es aplicable a un estado estable, donde la cola se alcanza después de que el sistema ha estado funcionando durante un tiempo suficientemente largo, como sucede en la mayoría de los casos.
Este caso se da cuando existe c servidores en paralelo, un cliente se selecciona de la cola para iniciar su servicio en el primer servidor disponible.
La frecuencia de llegada al sistema es clientes por unidad de tiempo. Todos los servidores están en paralelo y son idénticos, lo que quiere decir que la tasa de servicio en cualquier servidor es μ clientes por unidad de tiempo.
modelo de medidas de desempeño en estado estacionario
modelo con varios servidores
El modelo clásico de la mochila tiene que ver con el caso de un soldado que debe decidir cuales son los artículos más valiosos que debe llevar en su mochila. Este problema parafrasea un modelo general de asignación de recursos en el que un solo recurso limitado se asigna a varias alternativas (por ejemplo, fondos limitados asignados a proyectos) con objeto de maximizar el ingreso total.
La forma mas sencilla de determinar la ecuación recursiva es un procedimiento con dos pasos:
La ecuación recursiva (en reversa) se desarrolla para el problema general de una mochila de W libras, con n artículos. Sea m, la cantidad de unidades de del artículo i en la mochila, y defínase ri y wi como ingreso y el peso por unidad de artículo i. el problema general se representa con el siguiente programa lineal entero:
Un barco de 4 toneladas se carga de con uno o más de tres artículos. La tabla siguiente muestra el peso unitario, wi, en toneladas, y el ingreso por unidad ri, en miles de dólares, para el artículo i.
PROGRAMACIÓN DINÁMICA PROBABILÍSTICA
Para esta aplicación veremos una variación del juego de la ruleta rusa, donde se hace girar una rueda con marcas de n números consecutivos: 1 a n, en su periferia. La probabilidad de que la rueda se detenga en el número i después de un giro es pi. Un jugador paga x dólares por el privilegio de hacer girar la rueda un máximo de m giros. La recompensa para el jugador es el doble de la cantidad obtenida en el último giro. Suponiendo que el juego se repite (hasta m giros cada vez) una cantidad razonablemente grande de veces, propone una estrategia óptima para el jugador.
Se puede formular el problema como un modelo de programación dinámica con las siguientes definiciones:
La etapa i se representa con el giro i, i=1,2,,..,m.
Las alternativas en cada etapa incluyen girar la rueda una vez mas o terminar el juego.
El estado j del sistema en la etapa i se representa con uno de los números de 1 a n que se haya obtenido en el último giro.
La programación dinámica probabilística se difiere de la determinística en que los estados y los retornos o retribuciones en cada etapa son probabilístico. La programación dinámica probabilística se origina en especial en el tratamiento de modelos estocásticos de inventarios y en los procesos markovianos de decisión.
Suponga que el perímetro de la rueda de la ruleta rusa está marcado con los números 1 a 5. La probabilidad de detenerse en el número i es p1=0.3, p2=0.25, p3=0.2, p4=0.15 y p5=0.1.
El jugador paga $5 para hacer un máximo de 4 giros. Determine la estrategia óptima para cada uno de los cuatro giros, y el ingreso neto esperado correspondiente.
por brayan puelles olivares
Full transcript