Programación dinámica

investigación de operaciones



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á enel 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.







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 deproblemas 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.
En contraste con la programación lineal, no se cuenta con una formulación matemática estándar para el problema de programación dinámica,sino que se trata de un enfoque de tipo general para la solución de problemas, y las ecuaciones específicas que se usan se deben desarrollar para que representen cada situación individual. Entonces, se necesita cierto grado de ingenio y un buen conocimiento de la estructura general de los problemas de programación dinámica para reconocer cuando y como se puede resolver un problema por medio deestos procedimientos. Estas habilidades se pueden desarrollar mejor mediante la exposición de una gran variedad de aplicaciones de programación dinámica y con el análisis detallado de las características comunes a todas estas situaciones.
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 última 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 queganaré. 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 aseguromi 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 hemosresuelto 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...