Notas Programacion Dinamica Investigación De Operaciones

Investigación de Operaciones II

Notas de clase 2012

Contenido

UNIDAD I: PROGRAMACIÓN DINÁMICA 3

1.1. CARACTERÍSTICAS DE LOS PROBLEMAS DE PROGRAMACIÓN DINÁMICA: ETAPAS, ESTADOS, FÓRMULARECURSIVA, PROGRAMACIÓN EN AVANCE Y EN RETROCESO 3

1.2. EJEMPLOS DE MODELOS DE PROGRAMACIÓN DINÁMICA 5

1.3. PROGRAMACIÓN DINÁMICA DETERMINÍSTICA 5

1.4. PROGRAMACIÓN DINÁMICA PROBABILÍSTICA 6

1.5. PROBLEMA DE DIMENSIONALIDAD EN PROGRAMACIÓN DINÁMICA 6

1.6. EJERCICIOS RESUELTOS 8

Ejercicio # 1 8

Ejercicio # 2 9

Ejercicio # 3 11

Ejercicio # 4 14

UNIDAD I: PROGRAMACIÓN DINÁMICA

1.1. CARACTERÍSTICAS DE LOS PROBLEMAS DE PROGRAMACIÓN DINÁMICA: ETAPAS, ESTADOS, FÓRMULARECURSIVA, PROGRAMACIÓN EN AVANCE Y EN RETROCESO

La programación dinámica es una técnica matemática que se utiliza para la solución de problemas matemáticos seleccionados, en los cuales se toma una serie de decisiones en forma secuencial.

Proporciona un procedimiento sistemático para encontrar la combinación de decisiones que maximice la efectividad total, al descomponer el problema en etapas, las que pueden ser completadas por una o más formas (estados), y enlazando cada etapa a través de cálculos recursivos.

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.

La programación dinámica parte de una pequeña porción del problema y llega a la solución óptima para esa pequeña parte del problema, entonces gradualmente se agranda el problema hallando la solución óptima en curso a partir de la anterior. Este proceso se repite hasta obtener la solución óptima del problema original.

El problema de la diligencia es un prototipo literal de los problemas de programación dinámica. Por tanto una manera de reconocer una situación que se puede formular como un problema de programación dinámica es poder identificar una estructura análoga a la del problema de la diligencia.

Características básicas.

1. El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas.

2. Cada etapa tiene cierto número de estados asociados con su inicio. Los estados son las distintas 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 de solución está diseñado para encontrar una política óptima para el problema completo.

5. Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores. Este es el principio de optimalidad para programación dinámica.

6. El procedimiento de solución se inicia al encontrar la política óptima para la última etapa.

7. Se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa n+1. La forma precisa de relaciónrecursiva difiere de un problema a otro de programación dinámica, perousaremos una notación análoga a la siguiente:

N = número de etapas.

n = etiqueta para la etapa actual ( n = 1,2,...,N)

s = estado actual para la etapa n

xn = variable de decisión para la etapa n

xn* = valor óptimo de xn (dado s)

fn (s,xn) = contribución a la función objetivo de las etapas n, n+1,...,N, si el sistema se encuentra en el estado s en la etapa n, la decisión inmediata es xn y en adelante se toman decisiones óptimas. fn*(s) = fn(s,xn*) La relación recursiva siempre tendrá la forma: fn*(s) = mín fn(s,xn) ó fn*(s) = max fn(s,xn)

8. Cuando se usa esta relación recursiva, el procedimiento de solucióncomienza al final y se mueve hacia atrás etapa por etapa, hasta que encuentra la política óptima desde la etapa inicial.

Procedimiento de solución.

1. Se construye una relación recursiva que identifica la política óptima para cada estado en la etapa n, dada la solución óptima para cada estado en la etapa n + l.

2. Se encuentra la decisión óptima en la última etapa de acuerdo a la política de decisión establecida. Comúnmente la solución de esta última etapa es trivial, es decir, sin ningún método establecido, tomando en cuenta solamente la "contribución" de la última etapa.

3. La idea básica detrás de la relación recursiva es trabajar "hacia atrás", preguntándose en cada etapa: ¿qué efecto total tendría en el problema si tomo una decisión particular en esta etapa y actúo óptimamente en todas las etapas siguientes?

Si se resolviera el problema "hacia adelante", es decir, de la primera etapa hacia la sería necesario realizar una enumeración exhaustiva de todas las alternativas, que resolviéndolo "hacia atrás" reducimos el número de alternativas a analizar, simplificando la solución del problema. Cuando se llega a la etapa inicial se encuentra la solución óptima.

1.2. EJEMPLOS DE MODELOS DE PROGRAMACIÓN DINÁMICA

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 ydestino conocidos, pero tiene múltiples opciones para viajar a través delterritorio. Se entera de la posibilidad de adquirir seguro de vida como pasajero de la diligencia. El costo de la póliza estándar (cij ) se muestra en la tabla siguiente.

El problema de las monedas.

Para el problema de las monedas con programación dinámica se necesita crear un algoritmo que permita a una máquina expendedora devolver el cambio mediante el menor número de monedas posible. Mediante la programación dinámica se solucionará el caso en el que el número de monedas de cada tipo es ilimitado. En el problema de las monedas mediante el algoritmo voraz el que el número de monedas es ilimitado.

El problema de la mochila.

Sean n objetos no fraccionables de pesos pi y beneficios bi. El

...