Ensayo

PROGRAMACIÓN DINÁMICA
Elementos de un modelo de programación dinámica
La programación dinámica es una técnica matemática principalmente para mejorar la eficiencia de cómputo en ciertos problemasde optimización. 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.
El siguiente problema (simplificado) depresupuesto de capital introduce el concepto de programación dinámica. Una compañía tiene N fábricas existentes, y en cada una se está considerando una posible expansión. El capital total asignado paraexpansión es C unidades monetarias. El número de planes alternativos para la fábrica i (i=1, 2, …, N) es Mi, lo cual incluye la posibilidad de ninguna expansión. El costo esperado adicional de laalternativa mi (de la fábrica
i) es c i, mi y el ingreso resultante es Ri, mi. El objetivo del problema de decisión es seleccionar un plan factible mi para cada fábrica i tal que se maximice elingreso total resultante.
Un método directo para resolver este problema es enlistar las diferentes combinaciones de alternativas (existen Πi=1
N Mi de tales combinaciones, donde Π designa la operaciónde producto).
La combinación óptima es la que proporciona el valor mayor de ΣiΣmi Ri, mi, que satisface las restricciones de capital ΣiΣmi c i,mi ≤ C.
Las dificultades de cálculo asociadas alprocedimiento anterior son:
1. Cada combinación comprende una política de decisión para el problema completo, y por
tanto, el procedimiento requiere enumerar todas las combinaciones posibles; o sea,enumerar (M1 x M2 x … x MN) combinaciones. Esto puede ser no factible para N y Mi grandes, siendo i = 1, 2, …, N.
2. La combinación óptima puede estar disponible desde el principio en los cálculos,pero la optimizad no puede verificarse hasta que se consideren todas las combinaciones.
3. Las combinaciones infactibles (aquellas que infringen las restricciones de capital) no se eliminan por...