Ejemplos método gráfico (programación lineal)

El método gráfico es la manera más sencilla de resolver un pequeño problema de programación lineal. Por pequeño nos referimos a un problema que se pueda representar en dos dimensiones, es decir que, cuando mucho, tenga dos variables, cada una asociada a un eje del plano cartesiano.

Es posible representar un problema con tres variables, pero estos ejemplos pierden su valor ilustrativo al volverse engorrosos.

En el primer ejemplo vamos a detallar paso por paso, después omitiremos algunos pasos por practicidad.

Ejemplo 1:

Consideremos el siguiente modelo de programación lineal:

$Max\hspace{0.5cm}Z=2x_1+3x_2$

sujeto a:

$8x_1+4x_2\leq32$

$x_1+x_2\leq5$

$x_1, x_2\geq0$

Solución:

La región en la que las variables de decisión del problema cumplen la condición de no negatividad, $x_1, x_2\geq0$ , es el primer cuadrante.

Lo siguiente es graficar la primera restricción (R1), $8x_1+4x_2\leq32$ .

El procedimiento para graficar una desigualdad es el siguiente:

La desigualdad se escribe como una igualdad $8x_1+4x_2=32$ y se representa la recta en el primer cuadrante del plano cartesiano.
Evaluamos un punto cualquiera que no se encuentre sobre la recta. Si el punto cumple la desigualdad sombreamos el área o región del mismo lado en el que se encuentra el punto. Si el punto no cumple con la desigualdad sombreamos la región del otro lado de la recta.

Repetimos el procedimiento con la segunda restricción (R2):

El área sombreada se conoce como región de soluciones factibles. Cualquier punto en esta región satisface las restricciones del problema. Sin embargo, la solución óptima, es decir, aquella que maximiza el valor de la función objetivo se encontrará en un vértice.

Así, tenemos que valuar los vértices O(0,0), A(0,5), B(3,2) y C(4,0) en la función objetivo, aquel con el mayor valor corresponde al máximo.

O(0,0):

$Max\hspace{0.5cm}Z=2x_1+3x_2=2(0)+3(0)=0$

A(0,5):

$Max\hspace{0.5cm}Z=2x_1+3x_2=2(0)+3(5)=15$

B(3,2):

$Max\hspace{0.5cm}Z=2x_1+3x_2=2(3)+3(2)=12$

C(4,0):

$Max\hspace{0.5cm}Z=2x_1+3x_2=2(4)+3(0)=8$

La solución de nuestro problema es la siguiente:

$Z^*=15$

$x_1^*=0$

$x_2^*=5$

Es decir, dados los valores de las variables de decisión se tiene un valor máximo para la función objetivo.

Ejemplo 2:

Consideremos el siguiente modelo de programación lineal:

$Max\hspace{0.5cm}Z=x_1+x_2$

sujeto a:

$8x_1+6x_2\leq48$

$x_1+x_2\leq7$

$x_1, x_2\geq0$

Solución:

Sabemos que todo problema de programación lineal debe cumplir la condición de no negatividad, de tal modo que, la representación de las restricciones la realizaremos en el primer cuadrante.

A continuación vamos a graficar la primer restricción, para ello debemos cambiar el signo de la desigualdad por una igualdad $8x_1+6x_2=48$ , y trazar la recta asociada a dicha ecuación.

El área sombreada corresponde al conjunto de puntos que cumplen la desigualdad.

Repetimos el procedimiento con la segunda restricción $x_1+x_2=7$ :

Así, hemos determinado la región de soluciones factibles. Ya que no hay más restricciones solo tenemos que valuar la función objetivo en los vértices.

O(0,0):

$Z=x_1+x_2=0+0=0$

A(0,7):

$Z=x_1+x_2=0+7=7$

B(3,4):

$Z=x_1+x_2=3+4=7$

C(6,0)

$Z=x_1+x_2=6+0=6$

Ahora debemos elegir el punto con el que obtenemos el valor máximo, este punto resulta ser A(0,7) o B(3,4), en ambos casos se obtiene un valor máximo de 7 para la función objetivo.

En este ejemplo se tienen soluciones óptimas alternas, lo que significa que cualquier otro punto sobre el segmento de recta AB es solución óptima del problema.

Por ejemplo, los puntos D(1,6) y E(2,5) valuados en la función objetivo dan un valor de 7 que corresponde al máximo encontrado anteriormente.