Programacion dinamica

INTRODUCCIÓN

En este documento se hablará del concepto de la programación dinámica que es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas.

Donde 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, y a las decisiones que se plantearán en el futuro.

También se recalcará sobre el procedimiento general de resolución de estas situaciones, donde se divide en el análisis recursivo de cada una de las etapas del problema, en orden inverso, es decir comenzando por la última y pasando en cada iteración a la etapa antecesora. El análisis de la primera etapa finaliza con la obtención del óptimo del problema y las demás se verán explicadas en las siguientes páginas.

RESULTADOS DE LA INVESTIGACIÓN

CARACTERÍSTICAS DE LOS PROBLEMAS DE PROGRAMACIÓN DINÁMICA

La programación dinámica es una técnica que se utiliza para resolver diversos problemas de optimización. Esta técnica llega a la solución trabajando hacia atrás partiendo del final del problema hacia el principio, por lo que un problema enorme e inimaginable se convierte en una serie de problemas más pequeños y manejables.

La idea de trabajar hacia atrás se introduce mediante la resolución de acertijos conocidos, luego se muestra cómo la programación dinámica es útil para solucionar redes, inventarios y problemas de asignación de recursos.

A continuación se mostrara como trabajar hacia atrás para hacer de un problema aparentemente difícil uno casi trivial.

Ejemplo: (acertijo de las cerillas)

Supongamos que hay 30 cerillas sobre una mesa. Yo empiezo eligiendo 1,2 ò 3 cerillas. Luego mi contrincante debe tomar 1, 2 ò 3. Así continuamos hasta que alguno de los jugadores toma la ultima cerilla. Este jugador pierde. ¿Cómo puedo yo (el primer jugador) estar seguro de ganar el juego?

Solución:

Si puedo tener la certeza que le tocará el turno a mi oponente cuando quede una cerilla, claro que ganaré. Al regresar un paso hacia atrás, si yo puedo tener la seguridad de que le tocara su turno a mi contrario cuando queden 5 cerillas, yo puedo estar seguro de que cuando le toque el siguiente turno solo le quedara una cerilla. Por ejemplo, suponga que el turno de mi contrincante es cuando quedan 5 cerillas. Si mi contrario toma 2 cerillas, yo elegiré 2 y le dejare una cerilla, con lo que aseguro mi victoria. De manera similar, si soy capaz de obligar a mi contrincante a jugar cuando quedan 5, 9, 13, 17, 21, 25, ò 29 cerillas, tengo la victoria asegurada. Por lo tanto, no puedo perder si tomo 30- 29 = 1 la primera vez que me toque jugar. Luego simplemente me aseguro que mi contrario siempre se quede con 29, 25, 21, 17, 13, 9, ò 5 cerillas cuando le toque jugar.

Obsérvese que hemos resuelto este acertijo al ir hacia atrás desde el final hacia el principio del problema.

Otro ejemplo: (tazas de leche)

Tengo una taza de 9 onzas y otra de 4 onzas. Mi madre me pidió traer a casa exactamente 6 onzas de leche. ¿Cómo puedo cumplir lo pedido?

Solución:

Al empezar cerca del final del problema, me doy cuenta sagazmente de que el problema se puede resolver si soy capaz de poner de alguna manera una onza de leche en la tasa de 4 onzas. Luego lleno la tasa de 9 onzas y vierto 3 onzas de la leche de la tasa de 9 onzas en la taza parcialmente llena de 4 onzas. En este momento me quedo con 6 onzas de leche.

La solución del problema se podría describir como en la tabla anterior (la situación inicial se escribe al último, y la final se escribe primero).

UN PROBLEMA DE REDES

Muchas aplicaciones de programación dinámica se reducen a determinar el camino más corto (ò más largo) que une dos puntos en una red dada.

Mediante el ejemplo siguiente se ilustra como la programación dinámica (trabajando hacia atrás) se puede utilizar con el objeto de encontrar la trayectoria más corta en una red.

(El viaje de Joe)

Joe Cougar vive en Nueva York, pero proyecta viajar en su automóvil hasta los Ángeles en busca de fama y fortuna. Los fondos de Joe son limitados, así que decide pasar cada noche de su viaje en la casa de un amigo. Joe tiene amigos en Columbus, Nashville, Louisville, Kansas City, Dallas, San Antonio y Denver. Joe sabe que después de manejar un día puede llegar a Columbus, Nashville o Louisville. Después de manejar dos días puede llegar a Kansas City, Omaha o Dalla. Después de tres días de viaje puede llegar a San Antonio o Denver. Luego de cuatro días de manejar puede llegar finalmente a Los Ángeles. Para minimizar la cantidad de millas recorridas, ¿Dónde debe Joe pasar cada noche del viaje? Las millas reales por carretera entre las ciudades se dan en la fig. Sig.

Solución:

Joe necesita saber cuál es el camino más corto entre Nueva York y Los Ángeles. La determinaremos yendo hacia atrás. Clasificamos todas las ciudades en las que Joe puede estar al principio de n-esimo día de su viaje como ciudades de la etapa n. por ejemplo, puesto que Joe solo puede estar en San Antonio o Denver al inicio del cuarto día (el día 1empieza cuando Joe sale de Nueva York), entonces clasificamos San Antonio y Denver como ciudades de la etapa 4. La razón de clasificar las ciudades de acuerdo con etapas será evidentemente más adelante.

La idea de trabajar hacia atrás implica que debemos empezar por resolver un problema fácil que con el tiempo nos ayudara a resolver un problema complejo. Por lo tanto, empezamos por determinar la trayectoria más corta a Los Ángeles desde cada ciudad de donde hay solo un día de viaje en automóvil (ciudades de la etapa 4). Luego usamos esta información para encontrar el camino más corto hasta Los Ángeles desde cada ciudad de donde solo quedan 2 días de manejo (ciudades de la etapa 3). Con esta información ya somos capaces de hallar el camino más corto a Los Ángeles desde cada ciudad que esté a 3 días de viaje (ciudades de la etapa 2). Encontramos, por último, la trayectoria más corta a Los Ángeles desde cada ciudad (hay solo

...