Requerimientos para la formulación de un problema de programación dinámica

UNIDAD 6.-PROGRAMACIÓN DINÁMICA

El método de programación dinámica sirve para resolver problemas combinando las soluciones de subproblemas. Normalmente es usada para resolver problemas de optimización.

6.1 Requerimientos para la formulación de un problema de programación dinámica

Hay dos condiciones que se deben cumplir antes de comenzar a pensar en una solución a un problema de optimización usando programación dinámica.

Sub-estructura óptima: Un problema tiene sub-estructura óptima cuando la solución óptima a un problema se puede componer a partir de soluciones óptimas de sus sub-problemas.

Superposición de Problemas. El cálculo de la solución óptima implica resolver muchas veces un mismo sub-problema. La cantidad de sub-problemas es “pequeña”.

Al construir un algoritmo usando la estrategia de programación dinámica es

necesario:

1. Caracterizar la estructura de una solución optima.

2. Definir recursivamente el valor de una solución óptima.

3. Computar el valor de una solución en forma bottom-up.

4. [Opcional] Construir una solución óptima a partir de la información computada.

6.2 Ajuste de producción y control de inventarios

Un fabricante produce grandes transformadores eléctricos para la industria eléctrica. La empresa tiene pedidos para los siguientes seis meses. Se espera que el costo de fabricación de un transformador se modifique durante los siguientes meses, debido a las variaciones en los costos de los materiales y en el valor de la mano de obra. La empresa puede producir hasta 50 unidades por mes en tiempo normal y hasta 20 unidades adicionales por mes en tiempo extra. Los costos de producción normal y en tiempo extra se muestran en la tabla 6-1.

El costo de mantener en inventario un transformador no vendido es de US $500 por mes. La empresa tiene 15 transformadores en inventario al 1ro de enero y desea tener no menos de 5 en inventario al 30 de junio

Formular un problema de programación lineal para determinar el cronograma de producción óptimo para el fabricante. La capacidad no utilizada en tiempo normal se asume con un costo del 50% , la de tiempo extra se asume com cero y no se acepan entregas con retrazo.

Tabla 6-1

Mes Enero Febrero Marzo Abril Mayo Junio

Pedidos (unidades) 58 36 34 69 72 43

Costo por unidad en tiempo normal

(en miles de US$) $ 18 17 17 18.5 19 19

Costo por unidad en tiempo extra

(en miles

...