La programación lineal es una técnica matemática que permite a las empresas, organizaciones e individuos maximizar o minimizar una función objetivo sujeta a una serie de restricciones. Esta técnica se utiliza en una gran variedad de aplicaciones, como la fabricación, el transporte, la gestión de la cadena de suministro, la economía, la estrategia militar y muchas más. Uno de los conceptos claves en la programación lineal es la solución óptima, que es la combinación de valores para las variables de decisión que maximiza o minimiza la función objetivo.
El conjunto de soluciones factibles básicas
Para entender qué es la solución óptima en programación lineal, es necesario primero comprender el concepto de conjunto de soluciones factibles básicas. Este conjunto está formado por los vértices del recinto definido por las restricciones del problema. Cada vértice del recinto representa una combinación única de valores para las variables del problema. Si el problema tiene n variables, el conjunto de soluciones factibles básicas está formado por n+1 vértices.
Cada vértice del recinto está determinado por las intersecciones de las restricciones del problema. Es decir, cada restricción define un semiplano en el que se encuentran las soluciones factibles. El conjunto de todos los semiplanos formados por las restricciones determina la región de validez o zona de soluciones factibles. El conjunto de los vértices del recinto se llama conjunto de soluciones factibles básicas. En el caso de la programación lineal, la solución óptima se encuentra en uno de los vértices de este conjunto.
La solución óptima en problemas de maximización y minimización
La solución óptima puede ser un mínimo o un máximo, según el objetivo del problema. En un problema de maximización, la solución óptima es el vértice que maximiza la función objetivo. En un problema de minimización, la solución óptima es el vértice que minimiza la función objetivo.
En muchos problemas de programación lineal, el conjunto de soluciones factibles básicas está acotado, lo que significa que tiene un número finito de vértices. En estos casos, la solución óptima es fácil de encontrar porque simplemente se necesita evaluar la función objetivo en todos los vértices y elegir el que maximiza o minimiza la función, según el objetivo del problema.
Formulación canónica de problemas lineales
Para resolver problemas de programación lineal es necesario formular el problema de manera que se pueda aplicar la técnica de optimización. La formulación canónica de un problema lineal es un conjunto de restricciones y una función objetivo lineal, expresada como una combinación lineal de las variables del problema.
Un problema de programación lineal puede tener restricciones de desigualdad del tipo ≤ y del tipo ≥, según si se trata de problemas de maximización o de minimización, respectivamente. La formulación canónica de un problema de programación lineal de maximización es la siguiente:
- Maximizar: Z = c1x1 + c2x2 + … + cnxn
- Sujeto a: a11x1 + a12x2 + … + a1nxn ≤ b1
- a21x1 + a22x2 + … + a2nxn ≤ b2
- …
- am1x1 + am2x2 + … + amnxn ≤ bm
- x1, x2, …, xn ≥ 0
La formulación canónica de un problema de programación lineal de minimización es similar, pero con las restricciones de desigualdad del tipo ≥:
- Minimizar: Z = c1x1 + c2x2 + … + cnxn
- Sujeto a: a11x1 + a12x2 + … + a1nxn ≥ b1
- a21x1 + a22x2 + … + a2nxn ≥ b2
- …
- am1x1 + am2x2 + … + amnxn ≥ bm
- x1, x2, …, xn ≥ 0
Condiciones de Kuhn-Tucker
En algunos casos, los problemas de programación lineal pueden tener restricciones adicionales o requerir una solución no trivial. En estos casos, las condiciones de Kuhn-Tucker pueden ayudar a encontrar la solución óptima. Estas condiciones establecen que la solución óptima debe satisfacer ciertas restricciones adicionales, conocidas como restricciones de complementariedad.
Las restricciones de complementariedad son una forma de garantizar que la solución óptima maximiza o minimiza la función objetivo sujeta a las restricciones del problema. Estas restricciones se escriben en términos de las variables duales, que son una forma de medir el costo o beneficio de cada restricción. Las condiciones de Kuhn-Tucker son un conjunto de ecuaciones y desigualdades que se satisfacen cuando la solución óptima satisface las restricciones de complementariedad.
Dualidad en programación lineal
La dualidad en programación lineal es otro concepto importante que puede ayudar a encontrar la solución óptima. El problema dual es una manera alternativa de ver el problema original. El problema dual es el mismo problema que el original, pero con las restricciones y la función objetivo intercambiadas.
La dualidad en programación lineal es una herramienta útil porque es mucho más sencillo resolver el problema dual cuando el número de variables es más elevado que el de restricciones. Además, el valor óptimo del problema dual es siempre menor o igual que el valor óptimo del problema primal.
Problema específico
Para ilustrar cómo funciona la solución óptima en programación lineal, consideremos el siguiente problema:
- Maximizar: Z = 2×1 + 5×2 + 3×3
- Sujeto a: x1 + x2 ≤ 15
- x1 + 3×2 + x3 ≤ 25
- 3×1 + 2×2 + 2×3 ≤ 40
- x1, x2, x3 ≥ 0
En este caso, el conjunto de soluciones factibles básicas está formado por cuatro vértices: (0,15,0), (10,5,0), (15,0,10) y (0,0,20). Para encontrar la solución óptima, simplemente hay que evaluar la función objetivo en cada uno de los vértices y elegir el que maximiza la función.
La solución óptima en este caso es el vértice (15,0,10), que produce un valor de 70 para la función objetivo. Es importante señalar que la solución óptima siempre se encuentra en un vértice, y que la función objetivo es lineal en el conjunto de soluciones factibles básicas. Esto significa que si la solución óptima se encuentra en un vértice, entonces los puntos intermedios en las aristas que conectan los vértices no son soluciones óptimas.
Problema dual
El problema dual de este problema es el siguiente:
- Minimizar: W = 15y1 + 25y2 + 40y3
- Sujeto a: y1 + y2 + 3y3 ≥ 2
- y1 + 2y3 ≥ 5
- y2 + 2y3 ≥ 3
- y1, y2, y3 ≥ 0
Notemos que el problema dual tiene sólo dos variables, a diferencia de las tres variables del problema primal. Además, el posible punto óptimo del problema dual es el vértice (1,1), que es el punto de intersección de las restricciones y que produce un valor mínimo de 70 para la función objetivo. Esto significa que el punto (15,0,10) es mínimo global del problema dual.
Conclusión
La solución óptima es un concepto clave en la programación lineal. En un problema de programación lineal, la solución óptima es la combinación de valores para las variables de decisión que maximiza o minimiza la función objetivo. La solución óptima suele encontrarse en uno de los vértices del conjunto de soluciones factibles básicas, que está definido por las restricciones del problema. La solución óptima se puede encontrar evaluando la función objetivo en cada uno de los vértices y eligiendo el que maximiza o minimiza la función, según el objetivo del problema.
Existen algunas técnicas y conceptos que pueden ayudar a encontrar la solución óptima en problemas de programación lineal, como la formulación canónica, las condiciones de Kuhn-Tucker, la dualidad y los algoritmos de optimización. Sin embargo, la solución óptima siempre se encuentra en un vértice del conjunto de soluciones factibles básicas. Es importante recordar que los puntos intermedios en las aristas que conectan los vértices no son soluciones óptimas.
La programación lineal es una técnica poderosa que se utiliza en una gran variedad de aplicaciones. Comprender el concepto de solución óptima es esencial para aprovechar al máximo esta técnica. La solución óptima permite a las empresas y organizaciones tomar decisiones informadas y estratégicas que maximizan los beneficios y minimizan los costos.
