Lectura – Conectando puntos: programación lineal para la maximización de beneficios
¿Qué es el teorema fundamental de la programación lineal?
El teorema fundamental de la programación lineal es una joya matemática. Básicamente, establece que, en problemas de programación lineal donde se busca maximizar o minimizar una función lineal (llamada función objetivo) sujeta a ciertas restricciones lineales, siempre habrá al menos una solución óptima que se encuentra en un vértice (esquina) del conjunto factible, que es la región donde se cumplen todas las restricciones.
En otras palabras, si estás tratando de maximizar o minimizar algo bajo ciertas restricciones lineales, la respuesta óptima se encuentra en uno de los puntos donde las restricciones se encuentran.
¿Cómo se relaciona con las inecuaciones?
El teorema fundamental de la programación lineal se relaciona estrechamente con las inecuaciones debido a que las restricciones en un problema de programación lineal generalmente se expresan como inecuaciones lineales.
Cuando trabajas en un problema de programación lineal, las inecuaciones se utilizan para representar las limitaciones en las variables de decisión. Estas inecuaciones definen la región factible, que es el conjunto de todas las soluciones que cumplen con las restricciones del problema.
Ejemplo
Imagina que estás planeando la producción de dos productos, X e Y, y quieres maximizar tus ganancias, dadas por la función Z = 2X + 3Y, también llamada función objetivo. Sin embargo, tienes ciertas restricciones en términos de recursos.
Supongamos que tus recursos son tiempo y materiales. Tienes 20 horas de tiempo y 40 unidades de material disponible por semana. La producción de un producto X requiere 5 horas de tiempo y 5 unidades de material, mientras que la producción de un producto Y requiere 2 horas de tiempo y 8 unidades de material.
Ahora, puedes expresar estas restricciones como inecuaciones lineales:
- Restricción de tiempo: 5X + 2Y leq 20
- Restricción de material: 5X + 8Y leq 40
Aquí, X e Y representan la cantidad de productos X e Y que produces, respectivamente.
La región factible está determinada por las soluciones que cumplen ambas inecuaciones. Graficar estas inecuaciones te dará un área sombreada que representa todas las combinaciones posibles de X e Y que cumplen con las restricciones.
El teorema fundamental de la programación lineal sostendría que la solución óptima (máximas ganancias) se encuentra en uno de los vértices de esta región factible. Cada vértice representa una asignación específica de recursos a la producción de X e Y.
Ahora, vamos a graficar estas restricciones para encontrar la región factible; dibujamos las rectas a: 5X + 2Y = 20 y b: 5X + 8Y = 40, y nos enfocamos en la región del primer cuadrante delimitada por estas, ya que otra restricción es que ambas variables solo pueden ser cantidades positivas. La región donde estas cuatro áreas se superponen es la región factible.
Una vez que identificas la región factible, necesitas encontrar los vértices. Estos puntos de intersección son donde las inecuaciones se cumplen simultáneamente.
A partir de la gráfica, encontramos cuatro vértices en la región factible: A (0,0), B (0, 5), C (8/3, 10/3) y D (4, 0), donde el punto C representa la intersección de las rectas.
Luego, evaluamos la función objetivo Z en cada vértice:
1. Z_A = 2(0) + 3(0) = 0 + 0 = 0
2. Z_B = 2(0) + 3(5) = 0 + 15 = 15
3. Z_C = 2(8/3) + 3(10/3) = 16/3+ 30/3 = 46/3
4. Z_D = 2(4) + 3(0) = 8+ 0 = 8
La solución óptima es aquella que maximiza Z, así que en este caso, sería el punto C (8/3, 10/3) con Z_C = 46/3.
Por lo tanto, para maximizar las ganancias, deberías producir 8/3 unidades del producto X y 10/3 unidades del producto Y.