Ejercicio de programación lineal

ENUNCIADO. En un cierto problema de programación lineal, la función objetivo es $$f(x,y)=-3x+10\,y$$ siendo la región factible, el cuadrilátero convexo del plano cuyos vértices son $A(1,4)$, $B(2,6)$, $C(4,3)$ y $D(3,2)$ . Se pide:
a) Representar la región factible y determinar el sistema de desigualdades ( restricciones ) correspondiente
b) Representar la gráfica de una de las rectas del az de rectas paralelas asociadas a la función objetivo en el mismo diagrama que se ha representado la región factible
c) ¿ Qué punto de la región factible corresponde al máximo de la función ? ¿ Cuál es el valor de dicho máximo ?
d) ¿ Qué punto de la región factible corresponde al mínimo de la función ? ¿ Cuál es el valor de dicho mínimo ?

SOLUCIÓN.
a)

Las recta que pasa por los puntos $A(1,4)$ y $B(2,6)$ tiene por ecuación $y=2\,x+2$, y para los puntos con abscisas comprendidas entre $x_A=1$ y $x_B=2$, las correspondientes ordenadas de los puntos que quedan por debajo del segmento $AB$ han de cumplir $y \le 2x+2$

Las recta que pasa por los puntos $B(2,6)$ y $C(4,3)$ tiene por ecuación $y=-\dfrac{3}{2}\,x+9$, y para los puntos con abscisas comprendidas entre $x_B=2$ y $x_C=4$, las correspondientes ordenadas de los puntos que quedan por debajo del segmento $BC$ han de cumplir $y \le -\dfrac{3}{2}\,x+9$

Las recta que pasa por los puntos $C(4,3)$ y $D(3,2)$ tiene por ecuación $y=x-1$, y para los puntos con abscisas comprendidas entre $x_D=3$ y $x_C=4$, las correspondientes ordenadas de los puntos que quedan por encima del segmento $CD$ han de cumplir $y \ge x-1$

Las recta que pasa por los puntos $A(1,4)$ y $D(3,2)$ tiene por ecuación $y=-x+5$, y para los puntos con abscisas comprendidas entre $x_A=1$ y $x_D=3$, las correspondientes ordenadas de los puntos que quedan por debajo del segmento $AD$ han de cumplir $y \ge -x+5$

Así, el sistema de restricciones viene dado por $$\left\{\begin{matrix}y & \le & 2x&+&2 \\ y& \le &-\dfrac{3}{2}\,x&+&9\\ y &\ge &x&-&1 \\ y & \ge &-x &+& 5\end{matrix}\right.$$

b)
Sea $f(x,y):=c$; entonces, despejando $y$ de $c=-3x+10\,y$, obtenemos $y=\dfrac{3}{10}\,x+\dfrac{c}{10}$. Llamando ( por comodidad ) $k$ a $\dfrac{c}{10}$, podemos escribir la ecuación del az de rectas paralelas de la función objetivo de la forma $y=\dfrac{3}{10}\,x+k$. La recta roja discontinua ( en el gráfico ) es una de las rectas de dicho az. Dando valores arbitrarios a $k$ ( y por lo tanto a $c$, que es el valor de función ) podemos explorar la región factible para visualizar cuáles son los puntos de la misma donde se alcanza el máximo y el mínimo pedidos.

En la construcción, hecha con GeoGebra, se ha preparado una barra deslizadora para cambiar el valor de $k$ y, así, realizar el desplazamiento de dicha recta paralela a sí misma, dando lugar a las otras rectas del az. El segmento de color rojo sobre el eje de ordenadas indica el valor de $k$, que es proporcional al valor de $c$ ( esto es, de $f(x,y)$ ), observándose que el máximo de $f(x,y)$ ( proporcional al máximo de $k$ ) se obtiene en el punto $B(2,6)$; y, el mínimo en el punto $D(3,2)$

c)-d)
Evaluando la función en los cuatro vértices del cuadrilátero convexo que forma la región factible al objeto de determinar el valor del máximo ( que ya sabemos que corresponde a $B$ ) y del mínimo ( que ya sabemos que corresponde a $D$ ), obtenemos:
$$f_{\text{máx}}=f(x_B,y_B)=-3 \cdot 2 + 10 \cdot 6 = 54$$
$$f_{\text{mín}}=f(x_D,y_D)=-3 \cdot 3 + 10 \cdot 2 = 11$$

$\square$