PROGRAMACIÓN DINÁMICA

ESPECIALIZACIÓN EN GERENCIA INFORMÁTICA

INTRODUCCIÓN

Existe una serie de problemas matemáticoscuya solución se puede dar mediante el empleode un algoritmo recursivo o mediante laimplementación de una resolución poretapas, planteando una serie de sub problemasa partir del problema principal; en amboscasos, la solución puede ser caótica, agrandarel tamaño del problema o simplemente, elmétodo empleado convertirse en impracticable.Esto puede mejorar sustancialmente mediantela Programación Dinámica, PD.

¿QUÉ ES LA PROGRAMACIÓN DIMÁMICA?

La Programación Dinámica es una técnica

de programación que se emplea típicamente

para resolver problemas de optimización en

los cuales el problema principal se encuadra

en varios subproblemas, solucionando cada

uno de ellos y luego ligando las soluciones

de una forma óptima, donde la solución final

permita resolver y tomar decisiones

correctas a problemas actuales y futuros.

¿A QUÉ PROBLEMAS SE APLICA?

Esta técnica se aplica sobre problemas que asimple vista necesitan un alto costecomputacional (posiblemente exponencial)donde:

– Subproblemas optimales: La soluciónóptima a un problema puede ser definida enfunción de Soluciones óptimas a subproblemasde tamaño menor, generalmente de formarecursiva.

– Solapamiento entre subproblemas: Alplantear la solución recursiva, un mismoproblema se resuelve más de una vez

¿QUÉ SE LOGRA?

La PD utiliza un enfoque ascendente (botton-up) paraobtener la solución, primero calcula las solucionesóptimas a problemas de tamaño pequeño. Utilizandodichas soluciones encuentra soluciones a problemas demayor tamaño.

– La idea de la PD es encontrar la solución a lossubproblemas y almacenarlos en alguna estructura(diccionario) para utilizarlas posteriormente.

– Por tanto, es más eficiente que la fuerza bruta queresuelve el mismo subproblema una y otra vez.

-- Evita calcular lo mismo varias veces. Usualmente se utiliza una matriz que se rellena conforme las soluciones a los Subproblemas que son calculados (espacio vs. tiempo).

ELEMENTOS DE LA PROGRAMACIÓN DINÁMICA

Los siguientes cuatro elementos conforman

la resolución de un problema mediante PD:

1. Principio de Optimalidad de Bellman

2. Definición Recursiva de la solución

optimal

3. Enfoque ascendente

4. Búsqueda solución optima

PRINCIPIO DE OPTIMALIDAD DE BELLMAN

“Una secuencia óptima de decisiones queresuelve un problema debe cumplir lapropiedad de que cualquier subsecuencia dedecisiones debe ser tambien optimarespecto al subproblema que resuelve”.

Esto es, la solución optima a cualquierinstancia no trivial de un problema es unacombinación de soluciones óptimas dealgunas de las sub-instancias.

CARACTERÍSTICAS DE UN PROBLEMA DE PD

Para que un problema pueda ser resuelto con la técnica de

programación dinámica, debe cumplir con ciertas

características:

- Naturaleza secuencial de las decisiones: El problema puede

ser dividido en etapas.

- Cada etapa tiene un numero de estados asociados a ella.

- La decisión óptima de cada etapa depende solo del estado

actual y no de las decisiones anteriores.

- La decisión tomada en una etapa determina cual será el

estado de la etapa siguiente.

En síntesis, la política óptima desde un estado s de la etapa k

a la etapa final esta constituida por una decisión que

transforma s en un estado s’ de la etapa k +1 y por la política

óptima desde el estado s’ hasta la etapa final.

RESOLUCIÓN DE UN PROBLEMA DE PD

Para resolver un problema de programación dinámicadebemos al menos cumplir con:

Identificación de etapas, estados y variable dedecisión:

• Cada etapa debe tener asociado una o mas decisiones (problema de optimización), cuya dependencia de las decisiones anteriores esta dada exclusivamente por las variables de estado.

• Cada estado debe contener toda la información relevante para la toma de decisión asociada al período.

• Las variables de decisión son aquellas sobre las cuales debemos definir su valor de modo de optimizar el beneficio acumulado y modificar el estado de la próxima etapa.

Descripción de ecuaciones derecurrencia: Nos deben indicar como seacumula la función de beneficios a optimizar(función objetivo) y como varían lasfunciones de estado de una etapa a otra.

Resolución: Debemos optimizar cadasubproblema por etapas en función de losresultados de la resolución del subproblemasiguiente. Al final obtendremos una soluciónóptima para el problema.

EL PROBLEMA DE LAS MONEDAS

Mi empresa de colectivos

• El precio de los boletos puede llegar a cambiar encualquier momento

• En todo momento se puede pagar con cualquiermoneda o billete

• Tengo que dar el vuelto usando pocas monedas obilletes

¿Vuelto usando pocas monedas?

o El boleto, actualmente, sale $0,80

o Viene alguien y paga con un billete de $50

o El vuelto es $50 - $0.80 = $49,20

o Si le llego a dar 492 monedas de 10 centavos, no setoma nunca mas mi colectivo

Si se tienen los siguientes tipos de monedas ybilletes:

Monedas de 1, 5, 10, 25 y 50 centavos y de 1peso

Billetes de 2, 5, 10, 20, 50 y 100 pesos

Si el vuelto de $49,20, ¿Cuál es la mejor manera (menos cantidad de billetes y monedas) de dar esa cantidad?

20 + 20 + 5 + 2 + 2 + 10C+ 10C = 49,20

En general, si voy tomando cada vez el billete mas grande que puedo, me da la cantidad mínima

FALTA DAR ELIJO QUEDA

$ 49,20 20 $ 29,20

$ 29,20 20 $ 9,20

$ 9,20 5 $ 4,20

$ 4,20 2 $ 2,20

$ 2,20 2 $ 0,20

$ 0,20 C 10 C $ 10 C

$ 10 C 10 C $ 0

¿CÓMO SE APLICA EL PRINCIPIO DEL ÓPTIMO?

Si requiero dar vuelto de $24,20

En la anterior vuelto teníamos:

$20 + $20 + $5 + $2 + $2 + $2c + $2c =

$49,20

Aplicando:

$20 + $20 + $5 + $2 + $2 + $2c + $2c =

$24,20

CONCLUSIÓN

La programación Dinámica nos permite resolver un problema hallando soluciones sucesivas asub problemas de menor tamaño y ligándolas como solución óptima del problema.

Para desarrollar el proceso de PD se debe

1. Ver si se aplica el Principio de Optimalidad de Bellman:

– Encontrar la estructura de la solución:

• Dividir el problema en subproblemas y determinar si se puede aplicar el principio de optimalidad.

2. Definición recursiva de la solución optimal:

– Definir el valor de la solución óptima en función de valores de soluciones para sub-problemas de

tamaño menor.

3. Calcular el valor de la solución optimal utilizando un enfoque ascendente.

– Determinar el conjunto de subproblemas distintos a resolver (tamaño de la tabla)

– Identificar los subprblemas con solucion trivial

– Obtener los valores con un enfoque ascendente y almacenar los valores que vamos calculado en la

tabla.

– En etapas posteriores se utilizaran los valores previamente calculados

4. Determinar la solución óptima a partir de la información préviamente calculada.

Así, programación dinámia consiste en solucionar el presente suponiendo que en cada etapa futura siempre se tomaran las decisiones correctas.

WEBGRAFÍA

www.edicionsupc.es

www.lcc.uma.es

www.cimat.mx

www.sci2s.ugr.es

www.decsai.ugr.es

www.dc.uba.ar