Programación Lineal: Conceptos Fundamentales, Método Simplex y Ejercicio de Optimización de Producción
Conceptos fundamentales de la programación lineal
Variables y restricciones
Para cada variable xj = xj+ + xj-, donde ambas son ≥ 0.
Los valores específicos de los parámetros sensibles no cambian sin que la solución óptima cambie.
Una solución óptima utiliza todos los recursos disponibles limitados.
Una solución factible es aquella en la que todas las restricciones se cumplen.
Para cualquier problema de PL, dos soluciones FEV son adyacentes si comparten n - 1 fronteras de restricción.
Método Simplex
El método Simplex es algebraico, aun así sus conceptos fundamentales son geométricos.
Cualquier problema de programación lineal con soluciones factibles y región factible acotada debe poseer soluciones FEV y al menos una solución óptima.
Supuesto de aditividad: en un modelo de programación lineal, las variables pueden tomar cualquier valor, incluso valores no enteros, que satisfagan las restricciones funcionales y de no negatividad.
Componentes del modelo
- Planta: m recursos
- Producto: n actividades
- Tasa de producción: nivel de actividad
- Capacidad de producción: recursos
- Fabricación de productos: actividades
- Ganancia: Z
El algoritmo Simplex
Simplex es un algoritmo de optimización que sigue una serie fija de pasos, cada uno denominado iteración.
Estructura del resultado:
- Paso inicial: solución básica factible con Z = 0.
- Si se cumple el criterio de optimalidad, se termina el algoritmo y se retorna la solución óptima.
- En caso contrario, se crea otra iteración.
Una restricción activa es aquella en la que se encuentra la solución óptima (exclusive).
Como gerente, el objetivo es que Ganancias - Gastos se maximice para lograr el éxito.
Variables básicas y no básicas
Cada variable se designa como básica o no básica.
Número de variables básicas = número de restricciones funcionales.
Número de variables no básicas = número de variables - número de restricciones funcionales.
El número de variables no básicas es igual a 0 en la solución básica.
Los valores de las variables básicas se obtienen de la solución simultánea del sistema de ecuaciones.
Si las variables básicas satisfacen las restricciones de no negatividad, la solución es una solución básica factible.
Ejercicio 3.4.15: Asignación de producción por zonas
D = delantero; T = trasero; C = central
Función objetivo
Maximizar Z = 320(x1D + x1C + x1T) + 400(x2D + x2C + x2T) + 360(x3D + x3C + x3T) + 290(x4D + x4C + x4T)
Restricciones
- x1D + x2D + x3D + x4D ≤ 12
- x1C + x2C + x3C + x4C ≤ 18
- x1T + x2T + x3T + x4T ≤ 10
- x1D + x1C + x3 ≤ 12
- x1D + x1C + x1T ≤ 12
- x2D + x2C + x2T ≤ 12
- x3D + x3C + x3T ≤ 12
- 500x1D + 700x2D + 300x3D + 400x4D ≤ 7000
- 500x1C + 700x2C + 300x3C + 400x4C ≤ 9000
- 500x1T + 700x2T + 300x3T + 400x4T ≤ 5000
- 500x1D + 700x2D + 300x3D + 400x4D ≤ 7000
- 18(x1D + x2D + x3D + x4D) = 12(x1C + x2C + x3C + x4C)
- 10(x1D + x2D + x3D + x4D) = 12(x1T + x2T + x3T + x4T)
- x1D, x1C, x1T, x2D, x2C, x2T, x3D, x3C, x3T, x4D, x4C, x4T ≥ 0