Investigacion De Operaciones

Instituto Tecnológico Superior de Xalapa

Antología

de

Investigación de

Operaciones II

Docente:

ISC René Zahorí Torres Becerra

Temario

1. Programación Dinámica

1.1. Características de los problemas de programación dinámica: etapas, estados, formulación recursiva, programación en avance y en retroceso

1.2. Algunos ejemplos de modelos de P.D.

1.3. Programación Dinámica Determinística

1.4. Programación Dinámica Probabilística

1.5. Problema de dimensionalidad en P.D.

1.6. Uso de programas de cómputo

2. Líneas de Colas

2.1. Introducción y casos de aplicación

2.2. Definiciones, características y suposiciones.

2.3. Terminología y notación

2.4. Proceso de nacimiento o muerte

2.5. Modelos de Poisson

2.5.1. Un servidor

2.5.2. Múltiples Servidores

2.6. Uso de programas de cómputo

3. Teoría de Decisión

3.1. Características generales de la teoría de decisiones

3.2. Criterios de Decisiones Determinísticos y Probabilísticos

3.3. Valores de la información Perfecta

3.4. Árboles de Decisión

3.5. Teoría de Utilidad

3.6. Decisiones secuenciales

3.7. Análisis de Sensibilidad

3.8. Uso de programas de cómputo

4. Cadenas de Markov

4.1. Introducción

4.2. Formulación de las cadenas de Markov

4.3. Procesos estocásticos

4.4. Propiedad Markoviana de primer orden

4.5. Probabilidad de transición estacionarias de un solo proceso

4.6. Probabilidad de transición estacionarias de n pasos

4.7. Estados absorbentes

4.8. Probabilidad de transición estacionarias de estados estables Tiempos de primer paso

4.9. Uso de programas de cómputo

5. Optimización de Redes

5.1. Terminología

5.2. Problema de la ruta más corta. Redes cíclicas y acíclicas

5.3. Problema del árbol de mínima expansión

5.4. Problema de flujo máximo

5.5. Problema de flujo de costo mínimo

5.6. Programación lineal en Teoría de Redes

5.7. Uso de programas de cómputo

Unidad 1

Programación Dinámica

1.1. Características de los problemas de programación dinámica: etapas, estados, formulación recursiva, programación en avance y en retroceso

La programación dinámica es una técnica matemática que a menudo resulta útil a tomar una sucesión de decisiones interrelacionadas. Proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximice la efectividad global.

Contrastando con la programación lineal, no existe un planteamiento matemático estándar "del" problema de programación dinámica. Más bien, la programación dinámica es un tipo general de enfoque para resolver problemas y las ecuaciones particulares usadas deben desarrollarse para que se ajusten a cada situación individual. Por lo tanto, se requiere un cierto grado de ingenio y de visión de la estructura general de los problemas de programación dinámica, a fin de reconocer cuando un problema se puede resolver mediante los procedimientos de esta programación y cómo se haría. Probablemente se puedan desarrollar mejor estas aptitudes por medio de una exposición de una amplia variedad de aplicaciones de la programación dinámica y de un estudio de las características que son comunes a todas estas.

Por fortuna, la programación dinámica suministra una solución con mucho menos esfuerzo que la enumeración exhaustiva. (Los ahorros de cálculo serían enormes para versiones más grandes de un problema.) La programación dinámica parte de una pequeña porción del problema y encuentra la solución óptima para este problema más pequeño.

Entonces gradualmente agranda el problema, hallando la solución óptima en curso a partir de la anterior, hasta que se resuelve por completo el problema original. En seguida se dan los detalles involucrados en la implementación de esta filosofía general.

Considérese que las variables de decisión xn (n = 1,2,3,4) son el destino inmediato en la etapa n. Así, la ruta seleccionada sería 1 - XI - X2 - X3 - X4 en donde X4 = 10. Sea fn(s, Xn) el costo total de la mejor política global para las etapas restantes, dado que el vendedor se encuentra en el estado s listo para iniciar la etapa n y se selecciona a XII como el destino inmediato. Dados s y n, denotemos por x el valor de X*n que minimiza al fn(s, Xn) y sea f*(s) el valor mínimo correspondiente de fn(s, Xn) por tanto, f*n(s) = fn(s, Xn). El objetivo es hallar f1*(1) y la pol1tica correspondiente. La programación dinámica hace esto, hallando sucesivamente f4*(s),f3*(s), f2*(s) , a continuación, f1*(1).

Características de la Programación Dinámica

1.2. Algunos ejemplos de modelos de P.D.

1.3. Programación Dinámica Determinística

Esta sección considera con mayor amplitud el enfoque de programación dinámica para los problemas determinísticos, en los que el estado en la etapa siguiente queda completamente determinado por el estado y la política en la etapa actual.

La programación dinámica determinística se puede describir en forma de diagrama de la siguiente forma:

Una manera de catalogar los problemas de programación dinámica determinística es por la forma de la función objetivo. Por ejemplo, el objetivo podría ser minimizar la suma de contribuciones de las etapas individuales, o bien minimizar un producto de tales términos y así sucesivamente.

En un problema de programación dinámica, las temporadas deben ser las etapas.

1.4. Programación Dinámica Probabilística

La programación dinámica probabilística difiere de la programación dinámica determinística en que el estado de la etapa siguiente no queda completamente determinado por el estado y la decisión de la política en el estado actual. En lugar de ello existe una distribución de probabilidad para lo que será el estado siguiente. Sin embargo, esta distribución de probabilidad todavía esta completamente determinada por el estado y la decisión de la política del estado actual. En la siguiente figura se describe diagramáticamente la estructura básica que resulta para la programación dinámica probabilística, en donde N denota el número de estados posibles en la etapa n+1.

Cuando se desarrolla de esta forma para incluir todos los estados y decisiones posibles en todas las etapas, a veces recibe el nombre de árbol de decisión. Si el árbol de decisión no es demasiado grande, proporciona una manera útil de resumir las diversas posibilidades que pueden ocurrir.

1.5. Problema de dimensionalidad en P.D.

y

Unidad 2

Teoría de Líneas de Espera (Teoría de Colas)

2.1. Introducción y casos de aplicación.

En este capítulo se aplica la teoría de colas. Una Cola es una línea de espera y la teoría de colas es una colección de modelos matemáticos que describen sistemas de líneas de espera particulares o de sistemas de colas. Los modelos sirven para encontrar el comportamiento de estado estable, como la longitud promedio de la línea y el tiempo de espera promedio para un sistema dado.

El problema es determinar qué capacidad o tasa de servicio proporciona el balance correcto. Esto no es sencillo, ya que el cliente no llega a un horario fijo, es decir, no se sabe con exactitud en qué momento llegarán los clientes. También el tiempo de servicio no tiene un horario fijo.

2.2. Definición, Características y Suposiciones.

Una

...