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 de US$) $20 19 19 21 22 22

6.3 Distribución de vendedores a diversas áreas de mercado

El modelo de asignación es un modelo bastante utilizado para distribuir vendedores a diferentes territorios.

Procedimiento Manual:

• Restar todos los números de la matriz del número más grande en la matriz

• Efectuar una reducción por renglón y por otra por columna, tomando como base el valor más pequeño en cada renglón y columna.

• Cubrir todos los ceros con el menor número de líneas posibles, si el número mínimo fue igual al número de columnas o renglones la asignación es óptima.

• Si no fue optima se encuentra una nueva asignación, sumado el numero mas pequeño que quedó sin cubrir a los que se encuentran en los cruces de las líneas y restándolos de todos los números que quedaron sin cubrir.

El procedimiento de computadora se puede hacer mediante QSA. QSB. LINDO o EXCEL-Solver.

Los siguientes datos muestran las ventas de de cuatro vendedores en cuatro territorios, asignar de manera óptima los vendedores a los territorios.

T1 T2 T3 T4

V1 100000

...