Programación dinamica
Páginas: 8 (1823 palabras)
Publicado: 1 de noviembre de 2009
PROGRAMACIÓN DINÁMICA
La programación dinámica es un método de solución de problemas que permite descomponer un modelo matemático de gran magnitud (que puede ser muy difícil de resolver), en diversos problemas más pequeños que por lo general son de resolución mucho más fáciles. Además, el método de la programación dinámica permite descomponer un problema grande de manera que una vez que sehan resuelto los problemas menores se tiene la solución óptima para el problema mayor. La técnica se ha aplicado en muchos problemas de decisión que son, por naturaleza, de etapas múltiples; con frecuencia, tales etapas se crean por el hecho de que debe tomarse una secuencia de decisiones con el transcurso del tiempo. En la mayor parte de los casos, no es posible considerar a los problemas máspequeños como si fueran completamente independientes de los demás, por lo que el método de programación dinámica resulta muy útil. Comenzando al descubrir la forma en la que se pueda resolver un problema de ruta más corta utilizando un procedimiento de programación dinámica.
La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapassucesivas. 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 (denominadas estados), y a las decisiones que se plantearán en el futuro.
Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no sigue una forma estándar. Así, para cadaproblema será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.
El procedimiento general de resolución de estas situaciones 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 finalizacon la obtención del óptimo del problema.
MODELOS DE PROGRAMACIÓN DINÁMICA
Existen tres modelos diferentes manejados por WINQSB.
* Problema de la diligencia (Stagecoach Problem)
* Problema de la mochila (Snapsack Problem)
* programación de producción e inventarios (Production and Inventory Scheduling)
EL PROBLEMA DE LA DILIGENCIA
Ejemplo 10-1:
Considérese el gráfico que contempla las rutasposibles para ir desde la ciudad 1 hasta la ciudad 10. Cada nodo representa una ciudad y los arcos la infraestructura vial disponible. La tabla recoge el costo asociado al desplazamiento entre cada par de nodos para cada una de las etapas. Supondremos que todos los desplazamientos tienen la misma duración, y que el viaje ha de realizarse en cuatro etapas. Cada una de ellas se corresponde con un únicodesplazamiento entre un par de nodos del grafo, así al finalizar la primera etapa estaremos en una de las ciudades 2, 3 ó 4. La segunda etapa finalizará en la ciudad 5, la número 6 ó la número7. La tercera jornada nos llevará a la ciudad 8 o a la número 9. La cuarta etapa permite finalizar el viaje en la ciudad 10.
10.3 TERMINOLOGÍA Y NOTACIÓN BÁSICA
Períodos o etapas: Sea N= {1, 2,....., n} unconjunto finito de elementos. Mediante el índice , representamos cada uno de ellos. N es el conjunto de períodos o etapas del proceso. En la ilustración anterior N= {1, 2, 3, 4}, las cuatro etapas del viaje, cada una de ellas es un período y se representa mediante un valor del índice n, así cuando n =1 nos estamos refiriendo a la primera etapa del proceso.
Espacio de estados: { } es una familia deconjuntos, uno para cada período n. S se denomina espacio de estados en el período n. Cada uno de sus elementos, que se representa mediante Sn, es un estado, que describe una posible situación del proceso en ese período. En nuestro ejemplo, S1 = {1}, S2= {2, 3, 4}, S3= {5, 6, 7}, S4= {8, 9}.
La función recursiva: Dados unos nodos y unos arcos que conectan estos nodos, el problema de la diligencia...
La programación dinámica es un método de solución de problemas que permite descomponer un modelo matemático de gran magnitud (que puede ser muy difícil de resolver), en diversos problemas más pequeños que por lo general son de resolución mucho más fáciles. Además, el método de la programación dinámica permite descomponer un problema grande de manera que una vez que sehan resuelto los problemas menores se tiene la solución óptima para el problema mayor. La técnica se ha aplicado en muchos problemas de decisión que son, por naturaleza, de etapas múltiples; con frecuencia, tales etapas se crean por el hecho de que debe tomarse una secuencia de decisiones con el transcurso del tiempo. En la mayor parte de los casos, no es posible considerar a los problemas máspequeños como si fueran completamente independientes de los demás, por lo que el método de programación dinámica resulta muy útil. Comenzando al descubrir la forma en la que se pueda resolver un problema de ruta más corta utilizando un procedimiento de programación dinámica.
La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapassucesivas. 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 (denominadas estados), y a las decisiones que se plantearán en el futuro.
Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no sigue una forma estándar. Así, para cadaproblema será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.
El procedimiento general de resolución de estas situaciones 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 finalizacon la obtención del óptimo del problema.
MODELOS DE PROGRAMACIÓN DINÁMICA
Existen tres modelos diferentes manejados por WINQSB.
* Problema de la diligencia (Stagecoach Problem)
* Problema de la mochila (Snapsack Problem)
* programación de producción e inventarios (Production and Inventory Scheduling)
EL PROBLEMA DE LA DILIGENCIA
Ejemplo 10-1:
Considérese el gráfico que contempla las rutasposibles para ir desde la ciudad 1 hasta la ciudad 10. Cada nodo representa una ciudad y los arcos la infraestructura vial disponible. La tabla recoge el costo asociado al desplazamiento entre cada par de nodos para cada una de las etapas. Supondremos que todos los desplazamientos tienen la misma duración, y que el viaje ha de realizarse en cuatro etapas. Cada una de ellas se corresponde con un únicodesplazamiento entre un par de nodos del grafo, así al finalizar la primera etapa estaremos en una de las ciudades 2, 3 ó 4. La segunda etapa finalizará en la ciudad 5, la número 6 ó la número7. La tercera jornada nos llevará a la ciudad 8 o a la número 9. La cuarta etapa permite finalizar el viaje en la ciudad 10.
10.3 TERMINOLOGÍA Y NOTACIÓN BÁSICA
Períodos o etapas: Sea N= {1, 2,....., n} unconjunto finito de elementos. Mediante el índice , representamos cada uno de ellos. N es el conjunto de períodos o etapas del proceso. En la ilustración anterior N= {1, 2, 3, 4}, las cuatro etapas del viaje, cada una de ellas es un período y se representa mediante un valor del índice n, así cuando n =1 nos estamos refiriendo a la primera etapa del proceso.
Espacio de estados: { } es una familia deconjuntos, uno para cada período n. S se denomina espacio de estados en el período n. Cada uno de sus elementos, que se representa mediante Sn, es un estado, que describe una posible situación del proceso en ese período. En nuestro ejemplo, S1 = {1}, S2= {2, 3, 4}, S3= {5, 6, 7}, S4= {8, 9}.
La función recursiva: Dados unos nodos y unos arcos que conectan estos nodos, el problema de la diligencia...
Leer documento completo
Regístrate para leer el documento completo.