Resolución Gráfica de Modelos de Programación Lineal
Un modelo de programación lineal en 2 variables resulta ser la forma más sencilla que puede adoptar un modelo de optimización y generalmente son utilizados para introducir los conceptos básicos de la investigación de operaciones y particularmente la programación lineal. Básicamente las propiedas de un modelo lineal en 2 variables son extendibles a problemas lineales con un número mayor de variables y en este sentido la resolución gráfica resulta de gran ayuda para entender estos conceptos.
Ejemplo Resolución Gráfica
Resuelva el siguiente modelo de programación lineal a través de la resolución gráfica.
En primera instancia se asigna un eje a cada una de las variables de decisión, por ejemplo X1 corresponde al eje horizontal y X2 corresponde al eje vertical. Luego se grafican las restricciones. La primera restricción intercepta el eje X1 en 3 (cuando X2=0) y el eje X2 en 6 (cuando X1=0). Dado que la restricción es del tipo "<=" ésta determina el área que esta bajo la recta que une las coordenadas (X1,X2)=(3,0) y (X1,X2)=(0,6). En caso de tener dudas sobre el área que determina cada restricción se recomienda considerar un punto cualquiera fácil de evaluar en la restricción. Por ejemplo la coordenada (X1,X2)=(0,0) al evaluar en la restricción 1 la cumple (2*0+0<=6) y por tanto esta coordenada será parte del dominio de dicha inecuación. De forma similar se gráfica la segunda restricción que corta X1 en (28/7,0) y corta X2 en (0,7/2).
La intersección de los dominios que determinan las restricciones del problema definirán el dominio de soluciones factibles. Este dominio esta en verde en la imagen a continuación.
Una vez que ha identificado el dominio se debe buscar la solución óptima. Una propiedad de los problemas de programación lineal es que cuando admiten solución, ésta se encontrará siempre en un vértice del dominio de soluciones factibles y en caso muy especiales en la frontera de dicho dominio. Por tanto una forma de resolver será enumerando todos los vértices del dominio y evaluando éstos en la función objetivo. En este caso como el problema consiste en maximizar el valor de la función objetivo, el vértice que tenga un valor mayor corresponderá a la solución óptima. En el ejemplo se disponen de 4 vértices de fácil identificación, sin embargo, esta forma de resolución claramente queda limitada a problemas de tamaño menor.
Otra forma de resolución es a través de las curvas de nivel de la función objetivo que corresponden en el ejemplo a rectas paralelas que crecen en la dirección del gradiente de dicha función. Es decir, si desplazamos la función objetivo en la dirección del vector (X1,X2)=(120,80) el valor de la función objetivo crecerá a su mayor tasa.
En consecuencia para encontrar la solución óptima se desplazan las curvas de nivel en la dirección del gradiente hasta que se intercepte por última vez el dominio de puntos factibles. La linea punteada en rojo de la imagen anterior corresponde a dicha curva de nivel y el último punto donde esta curva intercepta el dominio corresponde al vértice con coordenadas (X1,X2)=(20/9,14/9) (Solución Óptima) con Valor Óptimo V(P)=391,1.
EXTENSIONES: Se recomienda revisar en detalle la resolución gráfica de modelos de Programación Lineal y su correspondiente análisis de sensibilidad en Programación Lineal - Resolución Gráfica.