Programación Matemática• Problemas de optimización con restricciones:

– Maximizar o minimizar la función objetivo– Sujeto a las limitaciones que definen la región de factibilidad del espacio de solución

• Métodos de solución: – La programación lineal (LP): Función objetivo y las restricciones son lineales – Programación no lineal (PNL): Función objetivo y / o algunas restricciones no son

lineales – La programación entera (PE): Espacio factible consiste en variables enteras – Programación entera mixta (MIP): Espacio factible se compone de un número entero

y algunas variables reales – La programación de metas (GP): Trata de encontrar al menos una solución en la

región de factibilidad– Programación dinámica (DP): Buscar política óptima en la toma de decisiones

secuenciales problema

• Programación matemática tradicional ignora la incertidumbre

Ejemplo de Programación Lineal

tipo ganancia horas madera Cant. Min.

Silla 50 10.5 5 5

Banco 100 15 15 7

Mesa 75 17 10 5

Una empresa fabrica 3 tipos de muebles:

Objetivo: Encontrar la combinación de fabricación que de la ganancia más alta

Restricciones: - Horas de trabajo disponibles = 400 - Maderas disponible = 300 - Debe hacer por lo menos la cantidad mínima de cada tema

Formulación del LP

• Maximizar 50 c + 100 b + 75 t ganancia• c = sillas; b = bancos; t = mesas• s.a. – 10.5 c + 100 b + 17 t ≤ 400 trabajo– 5 c + 15 b + 10 t ≤ 300 madera– c ≥ 5 sillas– b ≥ 7 bancos– t ≥ 5 mesas

• Programe el problema en excel y suba el archivo a la tarea llamada ejercicio3

Solución del problema• Método Simplex - desarrollado por Dantzig en 1940,

- Método estándar- Exponencial con el número de variables de - Garantiza solución óptima - Búsquedas puntos extremos en la región de factibilidad

• Algoritmo de Karmarkar - 1980's - Tiempo polinómico - Muy rápido en los problemas grandes - Habilidad limitada para hacer análisis de sensibilidad

• Algoritmos especiales explotan caso de estructuras especiales- Método de transporte - Simplex de la red