Un ejercicio de programación lineal

ENUNCIADO. Sea $\mathcal{R}$ la región del plano definida por: $$\left\{\begin{matrix}x&+&y&\le&5\\ -x&+&y&\le&3\\ \dfrac{1}{2}\,x&-&y&\le&-2 \end{matrix}\right.$$
Se pide:
a) Representar la región $\mathcal{R}$ y calcular las coordenadas de sus vértices
b) Obténganse los valores máximo y mínimo de la función $f(x,y)=2\,x+y$ en la región $\mathcal{R}$, indicando los puntos de $\mathcal{R}$ en los que se alcanzan dichos valores máximo y mínimo.

SOLUCIÓN.

a)
Región factible:

$\mathcal{R}:\left\{\begin{matrix} y+x\le 5 \\ y-x \le 3 \\ \dfrac{1}{2}\,x-y \le -2\end{matrix}\right. \sim \left\{\begin{matrix} y \le -x+5\\ y \le x+3 \\ y \ge \dfrac{1}{2}\,x+2 \end{matrix}\right. \quad \quad (1)$
Las rectas delimitadoras de la región factible son, por tanto, $\left\{\begin{matrix} r:y=-x+5\\ s:y=x+3\\ t:y=\dfrac{1}{2}\,x+2\end{matrix}\right.$ Analizando el sentido de las desigualdades de (1) obtenemos el triángulo de la figura como polígono ( convexo ) que corresponde a la región factible. Vamos ahora a calcular las coordenadas de los vértices $A,B$ y $C$.

$A=s \cap t$ luego $A: \left\{\begin{matrix} y=x+3 \\ y=\dfrac{1}{2}\,x+2\end{matrix}\right.$ que tiene como solución el punto de coordenadas $(1,2)$
$B=r \cap t$ luego $B: \left\{\begin{matrix} y=-x+5 \\ y=\dfrac{1}{2}\,x+2\end{matrix}\right.$ que tiene como solución el punto de coordenadas $(2,3)$
$C=s \cap r$ luego $C: \left\{\begin{matrix} y=x+3 \\ y=-x+5\end{matrix}\right.$ que tiene como solución el punto de coordenadas $(1,4)$

b)
La región factible ( convexa ) es, en este caso, acotada superior e inferiormente, por lo que podemos asegurar que existe máximo y que existe mínimo. Veamos cuáles son y para qué puntos de la región factible se dan.

La función objetivo $f(x,y)=2x+y$ podemos expresarla de la forma $y=-2x+k$, donde la ordenada en el origen $k$ representa los valores $k\equiv f(x,y)$ de cada una de las rectas del haz de rectas paralelas ( familia de rectas de la función objetivo ). Así, los puntos de la región factible que estén sobre la recta ( o las rectas ) que tengan un valor de $k$ máximo ( respectivamente, mínimo ) corresponden a los puntos donde la función alcanza el máximo ( respectivamente, el mínimo ).

Tal como se puede apreciar en la figura, el máximo de la función objetivo $f(x,y)$ se alcanza en el punto $B(2,3)$ y por tanto su valor es igual a $f(2,3)=2\cdot 2+3=7$; y el mínimo de $f(x,y)$ se alcanza en el punto $A(-2,1)$ y su valor es igual a $f(-2,1)=2\cdot (-2)+1=-3$

$\square$