Programacion dinamicaю

PROGRAMACION DINAMICA

La programación dinámica es una técnica matemática útil en la toma de una serie de decisiones interrelacionadas. Proporciona un procedimiento sistémico para determinar la combinación de decisiones que maximiza la efectividad total.

En contraste con la programación lineal, no 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 deben desarrollar para que representen cada situación individual entonces, se necesita un cierto grado de creatividad y un buen conocimiento de la estructura general de los problemas de estos procedimientos y como esto se puede llevar a cabo. Estas habilidades se pueden desarrollar mejor mediante la exposición de una gran variedad de aplicaciones de la programación dinámica y con el análisis detallado de las características comunes a estas situaciones.

[pic 1]

EL PROBLEMA DE LA DILIGENCIA.

Se construyó especialmente para ilustrar las características e introducir la terminología de la programación dinámica. Este paradigma se refiere a un caza fortunas míticas de Missouri que decide ir al Missouri que decide ir la oeste a sumergirse en la fiebre del oro que surgió en california a mediados del siglo XIX. Tiene que hacer el viaje en diligencia a través de territorios sin ley, donde existen serios peligros de ser atacado pro merodeadores. A pesar de que su punto de partida y su destino son fijos, tiene muchas opciones en cuanto a que estados o territorios debe elegir como puntos intermedios, se muestran las rutas posibles, en donde cada estado se representa mediante un círculo con una letra; además, en el diagrama, la dirección del viaje es siempre de izquierda a derecha. Como se puede observar, se requieren cuatro etapas.

Este caza fortunas es un hombre prudente preocupado por su seguridad. Después de reflexionar un poco ideo una manera bastante ingeniosa para determinar la ruta más segura, se ofrecen pólizas de seguros de vida  a los pasajeros. Como es el costo de la póliza de cualquier jornada en la diligencia está basada en una evaluación cuidadosa de la seguridad del recorrido, la ruta más segura debe ser aquella cuya póliza represente el menor costo total.

[pic 2]

PROCEDIMIENTO DE SOLUCIÓN: cuando el caza fortunas tiene solo una etapa por recorrer (n=4), su ruta de ahí en adelante esta perfectamente determinada por su estado actual s (ya sea H o I), asa como su destino final, x4 = j, de manera  que la ruta de esta última hornada en diligencia es s → J. Por tanto, f*4 (s) = f4(s, J)=cs, J, la solución inmediata al problema para n=4 es

[pic 3]

Cuando el caza fortunas tiene dos etapas por recorrer (n=3), el procedimiento de solución requiere unos cuantos cálculos. Por ejemplo, su ponga que se encuentra en el estado F. Entonces, como se describe en el diagrama, debe ir al estado H o al estado I con unos costos inmediatos respectivos de CF, H =6 o CF,I=3. Si elige el estado H, el costo adicional mínimo al llegar ahí se presenta en la tabla anterior como f* 4 (H)=3, como se muestra sobre el nodo H del diagrama. En consecuencia, el costo total de esta decisión es 6+3 = 9. Si en su lugar elige el estado I, el costo total es 3+4= 7, que es menor. Por tan to, la opción óptima es esta última, x*3=I, puesto que proporciona el costo mínimo, f*3(F)=7.

[pic 4]

Son necesarios cálculos similares cuando se parte de los otros dos estados posibles s=E y s=G con dos jornadas por delante. Intente obtener la res puesta con la ayuda tanto de un diagrama como del álgebra [combine los valores de CIJ y f*4(s)], para verificar los siguientes resultados del problema con n=3.

´[pic 5]

Ahora deberá ir al estado E, F o G con costos inmediatos respectivos de CC,E = 3, CC,F = 2 o CC,G =4. Al llegar a este punto, el costo adicional mínimo hasta llegar al des ti no se presenta en la tabla de n=3 como f *3(E)=4, f *3(F)=7 o f * 3(G)=6, respectivamente.

[pic 6]

A continuación se resumen estos cálculos sobre los tres distintos inmediatos posibles:

[pic 7]

‘

[pic 8]

Como mínimo es 11, f*1(A)=11 y x*1 = C o D, como se muestra en la siguiente tabla:

[pic 9]

Ahora es posible identificar una solución óptima a partir de las cuatro tablas. Los resulta dos del problema con n=1 indican que el caza fortunas debe elegir como primer destino inmediato el estado C o el estado D. Por tanto, una ruta óptima es A → C → E → H → J. Si se elige x*1=D, se obtienen otras dos rutas óptimas A → D → E → H → J y A → D → F → I → J. Todas tienen un costo

...