Ingeniería Systems: Método gráfico para resolver un problema de programación lineal de dos variables

Ejemplo 2. Determinar la solución óptima del siguiente problema de programación lineal

Paso 1. Construcción de la región factible

En primer lugar trazamos los ejes coordenados con las variables x1 y x2 . Luego para poder graficar los semiplanos correspondientes a cada una de las restricciones debemos convertir las desigualdades en igualdades, porque la representación gráfica de una ecuación lineal con dos variables es una recta y graficarla es simple. Por tal motivo graficamos las rectas correspondientes a cada una de las restricciones del problema y después seleccionaremos el semiplano correspondiente a cada desigualdad.

La primera restricción del problema es 5x1 + 8x2 <= 50 , y para determinar el semiplano correspondiente, debemos graficar la recta 5x1 + 8x2 = 50 . Como sabemos, para poder graficar una recta es necesario conocer los dos puntos por donde debe pasar ésta, más aún si necesitamos saber en qué puntos corta la recta a los ejes coordenados, sólo debemos asignar el valor de cero a cada una de las variables, del siguiente modo:

De forma similar, si x2 = 0 al sustituir en la ecuación de la recta tenemos 5x1 + 8(0) = 50 , entonces x1 = 10 . Por tanto, tenemos el punto (x1, x2) = (10,0).

Finalmente podemos graficar la recta 5x1 + 8x2 = 50

Dado que la recta divide al plano cartesiano en dos semiplanos, ahora nuestro interés debe centrarse en determinar el semiplano que corresponde a la inecuación, es decir, cuál de los semiplanos creados por la ecuación corresponde a la restricción. Para tal fin, tomamos las siguientes condiciones generales, según el tipo de desigualdad que represente a la restricción:

Siguiendo esta condición, representamos la desigualdad 5x1 + 8x2 <= 50 correspondiente a la primera restricción del problema

De forma similar construimos los semiplanos de las otras dos restricciones

La segunda restricción del problema es 6x1 + 5x2 <= 60 , para determinar el semiplano correspondiente, debemos graficar la recta 6x1 + 5x2 = 60.

Si x1 = 0 , entonces x2 = 12. Por tanto, tenemos el punto (x1, x2)= (0,12).

Si x2 = 0 , entonces x1 = 10. Por tanto, tenemos el punto (x1, x2)= (10,0).

Finalmente podemos graficar la recta 6x1 + 5x2 = 60 y su respectivo semiplano

La tercera restricción del problema es 8x1 - 5x2 <= 40 , para determinar el semiplano correspondiente, debemos graficar la recta 8x1 - 5x2 = 40.

Si x1 = 0 , entonces x2 = -8. Por tanto, tenemos el punto (x1, x2) = (0,-8).

Si x2 = 0 , entonces x1 = 5. Por tanto, tenemos el punto (x1, x2) = (5,0).

Finalmente podemos graficar la recta 8x1 - 5x2 = 40 y su respectivo semiplano

Una vez, graficadas las restricciones del problema, el siguiente paso importante es determinar la región factible, que representa el lugar geométrico donde se encuentra la solución óptima del problema lineal. En forma general la región factible, es determinada por la intersección de los semiplanos dentro del primer cuadrante, dado que las restricciones de no negatividad de las variables x1 ,x 2 >= 0 nos ubica en el primer cuadrante del plano cartesiano. Cabe aclarar que en algunos casos está intersección es vacía.

Siguiendo con el ejemplo, la región factible está limitada por el polígono, cuyos vértices son A, B, C y D como se muestra en la siguiente figura:

Paso 2: Determinación de la solución óptima.

La teoría nos muestra que la solución óptima se encuentra ubicada en uno de los vértices del polígono formado. Por tal motivo, una vez construida la región factible, debemos identificar los vértices del polígono que forma la región factible. Para esto debemos interceptar las rectas correspondientes a la primera y tercera restricción, es decir debemos resolver el siguiente sistema de ecuaciones:

La siguiente tabla muestra las coordenadas de los vértices y su respectivo valor en la función objetivo

Como la función objetivo es de maximización, al comparar los resultados en la función objetivo debemos elegir aquel punto que genere el mayor valor de la función objetivo, para este ejemplo el punto (0,25/ 4) genera el máximo valor. Por tal motivo se dice que el punto óptimo del problema lineal es el punto (0,25/ 4) y el valor máximo de la función objetivo es de 56.25.

Grafica de la función objetivo

A continuación vamos a graficar la función objetivo, con la finalidad de poder explicar la obtención del punto óptimo.

Dado que la función objetivo es Maximizar z = 4x1 + 9x2, podemos ver que dicha función objetivo es lineal, en otras palabras su representación geométrica es una recta, entonces para generar el lado derecho de la ecuación de la recta multiplicamos los coeficientes independientes obteniendo la recta 4x1 + 9x2 = 36

Ahora podemos graficar a la función Objetivo en forma similar a las ecuaciones de las restricciones:

Si x1 = 0 , entonces x2 = 4. Por tanto, tenemos el punto (x1,x2)=(0,4).

Si x2 = 0 , entonces x1 = 9. Por tanto, tenemos el punto (x1,x2)=(9,0).

Finalmente podemos graficar la recta objetivo 4x1 + 9x2 = 36.

Gráfica de la función objetivo en el punto óptimo

Una vez trazada la recta objetivo, debemos determinar la dirección que deberá seguir dicha recta para que la función objetivo aumente su valor. Para esto debemos hacer uso del concepto del gradiente, dado que este vector indica la dirección de crecimiento de una función de varias variables.

El gradiente de la función objetivo es determinado del siguiente modo

Este vector gradiente es perpendicular a la recta 4x1 + 9x2 = 36 y a partir de allí nos desplazaremos paralelamente siguiendo la dirección del vector gradiente, hasta que esta sea tangente a la región factible.

Dado que 4x1 + 9x2 = 36 tenemos como vector gradiente