Investigación De Operaciones

Características básicas.

1.- El problema se puede dividir en etapas que requieren una política dedecisión en cada una de ellas.2.- Cada etapa tiene cierto número de estados asociados con su inicio. Losestados son las distintas condiciones posibles en las que se puede encontrar elsistema en cada etapa del problema.3.- El efecto de la política de decisión en cada etapa es transformar el estadoactual 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 esindependiente de la política adoptada en etapas anteriores. Este es el principiode 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 laetapa 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)sn = estado actual para la etapa nxn = variable de decisión para la etapa nxn* = valor óptimo de xn (dado sn)fn(sn,xn) = contribución a la función objetivo de las etapas n, n+1,...,N, si elsistema se encuentra en el estado sn en la etapa n, la decisión inmediata es xny en adelante se toman decisiones óptimas. fn*(sn) = fn(sn,xn*) La relaciónrecursiva siempre tendrá la forma: fn*(sn) = mín fn(sn,xn) ó fn*(sn) = maxfn(sn,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 encuentrala política óptima desde la etapa inicial

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

1.2EJEMPLOS DE MODELOS DE PROGRAMACIÓN DINÁMICA

El problema de la diligencia.

Un cazafortunas desea ir de Missouri a California en una diligencia, yquiere 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 pasajerode 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 senecesita crear unalgoritmoque permita a unamáquinaexpendedora devolver el cambio mediante el menor número de monedas posible. Mediante laprogramación dinámicase solucionará el caso en el que el número demonedas de cada tipo es ilimitado. En el problema de las monedas mediante elalgoritmo voraz el que el número de monedas es ilimitado.

6

El problema de la mochila.

Sean n objetos no fraccionables de pesos pi y beneficios bi. El pesomáximo que puede llevar la mochila es C. Queremos llenar la mochila conobjetos, tal que se maximice el beneficio.Los pasos que vamos a seguir son los siguientes:

•

Ver que se cumple el principio de optimalidad de Bellman.

•

Buscar ecuaciones recurrentes para el problema.

•

Construir una tabla de valores a partir de las ecuaciones.

1.3PROGRAMACIÓN DINÁMICA DETERMINÍSTICA

Los problemas determinísticos de programación dinámica son aquellos enlos cuales el estado asociado en la etapa siguiente está totalmentedeterminado por el estado y la política de decisión de la etapa actual. Lasiguiente figura describe

...