Programacion Deterministica
Páginas: 9 (2084 palabras)
Publicado: 18 de julio de 2011
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 etapas sucesivas. 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.Características de un Problema de Programación Dinámica 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 número de estados asociados a ella.
La decisión óptima de cada etapa depende solo del estado actual y no de lasdecisiones anteriores.
La decisión tomada en una etapa determina cual será el estado de la etapa siguiente.
2.3.-PROGRAMACIÓN DINÁMICA DETERMINISTA
Los problemas determinísticos de programación dinámica son aquellos en los cuales el estado asociado en la etapa siguiente está totalmente determinado por el estado y la política de decisión de la etapa actual. La siguiente figuradescribe el funcionamiento de la programación dinámica determinística.
Esta sección considera con mayor amplitud el enfoque de programación dinámica para los problemas determinísticos, en los que el estado en la etapa siguiente queda completamente determinado por el estado y la política en la etapa actual.
Una manera de catalogar los problemas de programación dinámica determinística es por laforma de la función objetivo. Por ejemplo, el objetivo podría ser minimizar la suma de contribuciones de las etapas individuales, o bien minimizar un producto de tales términos y así sucesivamente. En un problema de programación dinámica, las temporadas deben ser las etapas.
La programación dinámica determinística se puede describir en forma de diagrama de la siguiente forma:
En laprogramación dinámica podemos maximizar una función objetivo cuyos términos se suman o se multiplican y las contribuciones a la función objetivo pueden o no ser lineales.
2.4.-PROGRAMACION DINAMICA PROBABILISTICA
Cuando se desarrolla de esta forma para incluir todos los estados y decisiones posibles en todas las etapas, a veces recibe elnombre de árbol de decisión. Si el árbol de decisión no es demasiado grande, proporciona una manera útil de resumir las diversas posibilidades que pueden ocurrir.
La PDP Se caracteriza porque el valor asociado a los arcos es un valor probable, y por lo tanto el valor de las rutas posibles desde el estado inicial hasta el estado final tiene un valor asociado a la probabilidad de ocurrencia deella. Estando en un estado s cualquiera en cualquiera de las etapas del problema, los arcos que de ese estado s salen tienen una probabilidad de ocurrencia, que puede ser igual para todos o tener valores diferentes.
En este tipo de problemas de la PDP se distinguen: -estados, -etapas, -estado inicial, -estado final -valor al horizonte, -función objetivo, -política óptima, -arcos, -valorasociado a los arcos (estos son probables y no determinísticos), -óptimo, -solución óptima, -ruta óptima.
Presentemos otros conceptos asociados a estos problemas de PDP mediante un ejemplo y su solución asociada.
EJEMPLO. PROGRAMACION DINAMICA PROBABILISTICA (PDP)
El Enunciado:
Una empresa ha recibido el encargo de construir un artículo, que, por las características exigidas por elcliente deberá pasar controles de calidad altos. Esto hace que la empresa estime que la probabilidad de que un artículo producido salga bueno es 2/3 (66,6667%) y de 1/3 (33,3333%) que salga malo sin posibilidad de recuperarlo o arreglarlo. El plazo que tiene la empresa para obtener al menos un artículo bueno es de 3 días, y la producción del artículo implica ocupar el día en hacer andar la línea de...
La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. 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.Características de un Problema de Programación Dinámica 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 número de estados asociados a ella.
La decisión óptima de cada etapa depende solo del estado actual y no de lasdecisiones anteriores.
La decisión tomada en una etapa determina cual será el estado de la etapa siguiente.
2.3.-PROGRAMACIÓN DINÁMICA DETERMINISTA
Los problemas determinísticos de programación dinámica son aquellos en los cuales el estado asociado en la etapa siguiente está totalmente determinado por el estado y la política de decisión de la etapa actual. La siguiente figuradescribe el funcionamiento de la programación dinámica determinística.
Esta sección considera con mayor amplitud el enfoque de programación dinámica para los problemas determinísticos, en los que el estado en la etapa siguiente queda completamente determinado por el estado y la política en la etapa actual.
Una manera de catalogar los problemas de programación dinámica determinística es por laforma de la función objetivo. Por ejemplo, el objetivo podría ser minimizar la suma de contribuciones de las etapas individuales, o bien minimizar un producto de tales términos y así sucesivamente. En un problema de programación dinámica, las temporadas deben ser las etapas.
La programación dinámica determinística se puede describir en forma de diagrama de la siguiente forma:
En laprogramación dinámica podemos maximizar una función objetivo cuyos términos se suman o se multiplican y las contribuciones a la función objetivo pueden o no ser lineales.
2.4.-PROGRAMACION DINAMICA PROBABILISTICA
Cuando se desarrolla de esta forma para incluir todos los estados y decisiones posibles en todas las etapas, a veces recibe elnombre de árbol de decisión. Si el árbol de decisión no es demasiado grande, proporciona una manera útil de resumir las diversas posibilidades que pueden ocurrir.
La PDP Se caracteriza porque el valor asociado a los arcos es un valor probable, y por lo tanto el valor de las rutas posibles desde el estado inicial hasta el estado final tiene un valor asociado a la probabilidad de ocurrencia deella. Estando en un estado s cualquiera en cualquiera de las etapas del problema, los arcos que de ese estado s salen tienen una probabilidad de ocurrencia, que puede ser igual para todos o tener valores diferentes.
En este tipo de problemas de la PDP se distinguen: -estados, -etapas, -estado inicial, -estado final -valor al horizonte, -función objetivo, -política óptima, -arcos, -valorasociado a los arcos (estos son probables y no determinísticos), -óptimo, -solución óptima, -ruta óptima.
Presentemos otros conceptos asociados a estos problemas de PDP mediante un ejemplo y su solución asociada.
EJEMPLO. PROGRAMACION DINAMICA PROBABILISTICA (PDP)
El Enunciado:
Una empresa ha recibido el encargo de construir un artículo, que, por las características exigidas por elcliente deberá pasar controles de calidad altos. Esto hace que la empresa estime que la probabilidad de que un artículo producido salga bueno es 2/3 (66,6667%) y de 1/3 (33,3333%) que salga malo sin posibilidad de recuperarlo o arreglarlo. El plazo que tiene la empresa para obtener al menos un artículo bueno es de 3 días, y la producción del artículo implica ocupar el día en hacer andar la línea de...
Leer documento completo
Regístrate para leer el documento completo.