Investigación De Operaciones

I
ELEMENTOS PRINCIPALES DE LA PROGRAMACION DINAMICA

La programación dinámica es una técnica matemática principalmente para mejorar la eficiencia de cómputo en ciertos problemas de optimización.Esta técnica se emplea típicamente para resolver problemas de optimización en los cuales el problema principal se encuadra en varios subproblemas analizándolos y resolverlos y así tomar decisionescorrectas a problemas actuales y futuros. La idea básica de la técnica es descomponer el problema en subproblemas (más pequeños) los cuales son computacionalmente más manejables.
Así entonces esta nosdice cuando buscar una solución a un problema mediante el análisis de Subestructura Óptima que aparece si una solución óptima al problema contiene implícitamente soluciones óptimas a subproblemas.
Porotro lado existen los Subproblemas Dependientes cuando el conjunto de sobproblemas debe ser pequeño (polinominal en el tamaño de la entrada), es decir, un algoritmo recursivo para el problema resuelvemuchas veces los mismo sobproblemas. En este caso se dice que los subproblemas se sobreponen, es decir, no son independientes.
Existen 4 elementos que conforman la programación dinámica para laresolución de un problema mediante esta:
1. Principio de Optimalidad de Bellman: una secuencia óptima de decisiones que resuelve un problema debe cumplir la propiedad de que cualquier subsecuencia dedecisiones debe ser también óptima respecto al subproblema que resuelve.
Para que un problema pueda ser resuelto con programación dinámica debe cumplir con estas características:
Naturalezasecuencial de las decisiones: el problema puede ser dividido en etapas.
Cada etapa tiene un número de estados asociados a ella.
De 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.
Esto es: la solución a cualquier instancia no trivial de un problema es una combinación...