El nombre programación dinámica probablemente evolucionó debido a su uso con aplicaciones donde intervenía la toma de decisiones relacionadas con el tiempo (como los problemas de inventarios). Sin embargo, con la PD también se resuelven adecuadamente otras situaciones donde el tiempo no es un factor importante. Por este motivo, un nombre más adecuado puede ser programación de etapas múltiples, ya que el procedimiento determina comúnmente la solución en etapas.
La teoría unificadora fundamental de la programación dinámica es el principio de optimidad. Este nos dice básicamente cómo se puede resolver un problema adecuadamente descompuesto en etapas (en vez de una sola etapa) utilizando cálculos recursivos.
Los sutiles conceptos que se utilizan en PD junto con las notaciones matemáticas poco conocidas son una fuente de confusión, en especial para un principiante. No obstante, nuestra experiencia demuestra que la resolución frecuente de formulaciones y soluciones de PD permitirá a un principiante, con algo de esfuerzo, entender estos conceptos avanzados. Cuando sucede esto, la programación dinámica se vuelve sorprendentemente sencilla y clara.
10.1 ELEMENTOS DEL MODELO DE PD, EJEMPLO DEL PRESUPUESTO DE CAPITAL
Una corporación recibe propuestas de sus tres plantas respecto a la posible expansión de las instalaciones. La corporación tiene un presupuesto de $5 millones para asignarlo a las tres plantas. A cada planta se le solicita someta sus propuestas, indicando el costo total (c) y el ingreso total (R) para cada propuesta. En la tabla 10-1 se resumen los costos e ingresos (en millones de unidades monetarias). Las propuestas de costo cero se presentan para dar cabida a la posibilidad de no asignar fondos a plantas individuales. La meta de la corporación es la de maximizar el ingreso total resultante de la asignación de los $5 millones a las tres plantas.
Una manera directa, y quizá ingenua, de resolver el problema es a través de una enumeración exhaustiva. El problema tiene 3.x 4x2 = 24 posibles soluciones y algunas de ellas son infactibles porque requieren más capital que el disponible-($5 millones). La idea de la enumeración exhaustiva es la de calcular el costo total de cada una de las 24 combinaciones. Si éste no excede el capital disponible, se obtiene su ingreso total. La solución óptima es la combinación factible que produce el más alto ingreso total. Por ejemplo, las propuestas 2, 3 y 1 de las plantas 1, 2 y 3 cuestan $4 millones (<5) y producen un ingreso total de $14 millones. Por otra parte, la combinación que comprende las propuestas 3, 4 y 2 es infactible porque cuesta $7 millones. Examinaremos las desventajas de la enumeración exhaustiva.
1. Cada combinación define una política de decisión para todo el problema y por lo tanto, quizá no sea factible en términos de cálculo la enumeración de todas las combinaciones posibles para problemas de tamaños mediano y grande.
2. Las combinaciones infactibles no se pueden detectar con anticipación, lo cual nos conduce a que haya ineficiencia en términos de cálculo.
3. La información disponible referente a combinaciones investigadas con anterioridad no se utiliza para eliminar combinaciones inferiores futuras.
El algoritmo de PD que presentamos aquí está diseñado para facilitar las dificultadas que hemos notado.
10.1.1 MODELO DE PD
En la programación dinámica, los cálculos se realizan en etapas dividiendo el problema en sub problemas. Después se considera por separado cada sub problema con el fin de reducir el número de operaciones de cálculo. Sin embargo, como los sub problemas son independientes, debe idearse un procedimiento para enlazar los cálculos de manera que garantice que una solución factible para cada etapa sea asimismo factible para todo el problema.
Una etapa en PD se define como la parte del problema que posee un conjunto de alternativas mutuamente excluyentes, de las cuales se seleccionará la mejor alternativa. En términos del ejemplo del presupuesto de capital, cada planta define una etapa donde la primera, segunda y tercera etapas tienen tres, cuatro y dos alternativas, respectivamente. Estas etapas son interdependientes porque las tres plantas deben competir por un presupuesto limitado. Por ejemplo, elegir la propuesta 1 de la planta 1 dejará $5 millones para las plantas 2 y 3, en tanto que la elección de la propuesta 2 de la planta 1 sólo dejará $4 millones para las plantas 2 y 3.
La idea básica de PD consiste prácticamente en eliminar el efecto de la interdependencia entre etapas, asociando una definición de estado con cada etapa. Un estado se define normalmente como aquel que refleja la condición (o estado, valga la redundancia) de las restricciones que enlazan las etapas. En el ejemplo del presupuesto de capital, definimos los estados para las etapas 1, 2 y 3 como sigue:
X1= monto de capital asignado a la etapa 1
X2= monto de capital asignado a las etapas 1 y 2
X3= monto de capital asignado a las etapas 1, 2 y 3
Ahora demostraremos cómo se utilizan las definiciones de etapas y estados dadas, para descomponer el problema del presupuesto del capital en tres sub problemas independientes, desde el punto de vista del cálculo.
Obsérvese primero que los valores de X1 y X2 no se conocen con exactitud, pero deben estar en alguna parte entre 0 y 5. De hecho, como los costos de las diferentes propuestas son discretos, X1 y X2 sólo pueden tomar los valores 0, 1, 2, 3, 4 o 5. Por otra parte, X3, que es el capital total asignado a todas las etapas, las tres, es igual a 5.
La forma como resolvemos este problema consiste en comenzar con la etapa 1 (planta). Obtenemos decisiones condicionales para esa etapa que responden la pregunta siguiente: dado un valor específico de X1 (=0,1,2,3,4 o 5), ¿cuál sería la mejor alternativa (propuesta) para la etapa 1? Los cálculos para la etapa 1 son directos. Dado el valor de X1, elegimos la mejor propuesta cuyo costo no exceda X1. En la tabla que sigue se resumen las decisiones condicionales de la etapa 1.
No hay comentarios:
Publicar un comentario