Siguiente:Segundo Ejemplo Arriba:Tutorial Anterior:Contenidos

Primer Ejemplo

Veamos un problema simple de inversión de capital. Una corporación tiene $5 millones para invertir en sus tres plantas para una posible expansión. Cada planta ha presentado un número de propuestas sobre como pretende gastar el dinero. Cada propuesta entrega el costo de la expansión (c) y la ganancia esperada (r). La siguiente tabla resume las propuestas:
 

Tabla 1: Posibilidades de Inversión

Cada planta sólo podrá realizar un de sus propuestas. El objetivo es maximizar el retorno de la firma dada su inversión de $5 millones. Se supondrá que si no se gastan los $5 millones completamente, ese dinero se perderá.

Una forma de resolver este problema es intentar todas las posibilidades y elegir la mejor. En ese caso, hay solo  formas de invertir el dinero. Muchas de estas son infactibles (por ejemplo, propuestas 3, 4 y 1 para las tres plantas cuesta $6 millones). Otras propuestas son factibles, pero son muy pobres en retorno (como propuestas 1, 1 y 2, con un retorno de sólo $4 millones.)

Desventajas de una enumeración completa:

1. Para problemas de gran tamaño la enumeración de todas las posibles soluciones puede no ser factible computacionalmente.
2.  Las combinaciones infactibles no pueden ser detectadas  a priori, llevando a una ineficiencia.
3.  Información sobre combinaciones previamente investigadas no se usan para eliminar otras combinaciones menos buenas, o infactibles.

Cabe hacer notar que este problema no puede ser formulado como un problema de programación lineal, porque los retornos no son funciones lineales.

Un método para calcular la solución es:

Dividamos el problema en 3 niveles: cada nivel representa el dinero asignado a una única planta. Asi el nivel 1 representa el dinero asignado a la planta 1. Artificialmente se dará un orden a los niveles, asumiendo que primero se asignará a la planta 1, luego a la planta 2 y finalmente a la planta 3.

Cada  nivel está dividido en estados. Un estado guarda la información requerida para ir desde un nivel al siguiente nivel.
En este caso los estados por nivel 1, 2 y 3 son:

• {0,1,2,3,4,5}: cantidad de dinero gastado en la planta 1, representado como  ,
•  {0,1,2,3,4,5}: cantidad de dinero gastado en las plantas 1 y 2 (  ), y
•  {5}: cantidad de dinero gastado en las plantas 1, 2, y 3 (  ).

Es necesario notar que diferentemente a lo que es programación lineal, las  no representan variables de decisión: ellas son simplemente representaciones de un estado genérico en el nivel.
Un retorno es asociado a cada estado. Se debe notar que para tomar una decisión en el estado 3, es sólo necesario conocer cuanto fue gastado en las plantas 1 y 2, no cómo esto fue gastado. También note que se desea que  sea 5
Determinando los retornos asociados a cada estado, lo más fácil es en el nivel 1, los estados  . Tabla 2 entrega el retorno asociado con  .

Tabla 2: Cálculos en el nivel 1

Ahora se pueden calcular para el nivel 2. En este caso, deseamos encontrar la mejor solución tanto para la planta 1 como para la planta 2. Si se desea calcular el mejor retorno para un  dado,simplemente se analizarán todas las propuestas de la planta 2, asignando la cantidad requerida a la planta 2 y usar la tabla anterior para ver cómo la planta 1 gastará el excedente.

Por ejemplo, supongamos que deseamos determinar la mejor asignación para el estado  . En el nivel 2 se puede hacer una de las siguientes propuestas:
 

1. Propuesta 1 da un retorno de 0, deja 4 para el nivel 1, el cual retorna 6. Total: 6.
2. Propuesta 2 da un retorno de 8, deja 2 para el nivel 1, el cual retorna  6. Total: 14.
3. Propuesta 3 da un retorno de 9, deja 1 para el nivel 1, el cual retorna 5. Total: 14.
4. Propuesta 4 da un retorno de 12, deja 0 para el nivel 1, el cual retorna  0. Total: 12.

Lo mejor que se puede hacer con 4 unidades es la propuesta 1 para la planta 2 y la propuesta 2 para la planta 1, con un retorno de 14, o la propuesta 2 para la planta 2 y la propuesta 1 para la planta 1, también con un retorno de 14. En cualquier caso, el retorno para este nivel es  es 14. El resto de la tabla 3 se puede interpretar análogamente. .

Tabla 3: Cálculos en el nivel 2 .

Ahora se puede analizar el nivel 3. El único valor en el que estamos interesados es  .
Nuevamente, se analizrá todas las propuestas para este nivel, determinando la cantidad de dinero remanente y usando la tabla 3 para decidir el valor de los niveles previos. Asi se puede realizar lo siguiente en la planta 3:
 

• Propuesta1 da un retorno 0, deja  5. Niveles previos dan 17. Total: 17.
• Propuesta 2 da un retorno 4, deja 4. Niveles previos dan 14. Total: 18.

De esta manera, la solución óptima es implementar la propuesta 2 de la planta 3, propuesta 2 o 3 en la planta 2 y la propuesta 3 o 2 (respectivamente) en la planta 1. Esto da un retorno de 18.

Si se estudia este procedimiento, uno puede observar que los cálculos son efectuados recursivamente. Los cálculos en el nivel 2 están basados en el nivel 1, el nivel 3 sólo en el nivel 2. A su vez, estando en un estado, todas las futuras decisiones son tomadas independientemente de como se llegó a ese estado. Este es el prinicipio de optimalidad en el cual se sustenta la programación dinámica.

Se pueden resumir estos cálculos en las siguientes fórmulas:
 

Sea  el retorno para la propuesta  en el estado  j,y por  el costo correspondiente. Sea  el retorno del stado  en el nivel  j. Luego se harán los siguientes cálculos:

y

 
 

Los cálculos fueron llevados a cabo por un procedimiento forward. Sin embargo, también se calcularon "cosas" desde el último nivel hacia el primero.
Se define:
 

• = cantidad asignada a los niveles 1, 2, y 3,
•   = cantidad asignada a los niveles  2 y 3, y
•   = cantidad asignada al nivel 3.

Esto define una recursividad backward. Gráficamente esto se ilustra en la Figura 1.

Figura 1: Forward vs. Backward Recursividad

Las fórmulas correspondientes son:

• Sea  el retorno óptimo para el nivel 3, dado por  ,
•   es el retorno óptimo para los niveles 2 y 3, dados por  ,y
•   es el retorno óptimo para los estados 1, 2 y 3 dado por  .

Las fórmulas de recursividad son:

y

Si lleva a cabo todos estos cálculos llegará al mismo resultado.
Aunque la recursividad forward parezca más natural, se introdujo una recursividad hacia backward. En este caso particular l orden de los niveles no es relevante. En otros casos puede haber ventajas computacionales en la elección uno versus otro orden. En general, la recursividad backward es más efectiva.

Siguiente:Segundo EjemploArriba: Tutorial Anterior:Contenidos