Un ejercicio de programación lineal

ENUNCIADO. Sea $S$ la región del plano definida por $S:\left\{\begin{matrix}x+y\ge 2 \\ 2x-y \le 4\\ 2y-x\le 4 \\ x\ge 0\\ y\ge 0\end{matrix}\right.$
a) Represéntese la región $S$ y calcúlense las coordenadas de sus vértices
b) Obténganse los valores máximo y mínimo de la función $f(x,y)=-5x+3y$ en $S$, indicando los puntos de dicha región en los cuales se alcanzan los valores máximo y mínimo

SOLUCIÓN. Es conveniente expresar las ecuaciones de $S$ de la forma $$S:\left\{\begin{matrix}y&\ge&-x&+&2 \\ y&\ge&2x&-&4 \\ y&\le&-\dfrac{1}{2}\,x&+&2 \\ x&\ge&0 \\ y&\ge&0 \end{matrix}\right.$$
con lo cual es fácil escribir las ecuaciones de la rectas que contienen los lados de la región factible
$$\left\{\begin{matrix}r_1:&y&=&-x&+&2 \\ r_2:&y&=&2x&-&4 \\ r_3:&y&=&-\dfrac{1}{2}\,x&+&2 \\ r_4:&x&=&0 \\ r_5:&y&=&0 \end{matrix}\right.$$

Procedemos ahora a representar la región factible. Las dos últimas restricciones nos limitan al primer cuadrante. Para representar las tres primeras rectas ( que contienen los lados de la región convexa ), encontremos una pareja de puntos para cada una de ellas: para $r_1$, tenemos $P_1(0,2)$ y $Q_1(2,0)$; para $r_2$, $P_2(0,-4)$ y $Q_2(2,0)$; y, para $r_3$, $P_3(0,2)$ y $Q_3(-4,0)$. Representando dichas rectas e interpretando correctamente el sentido de las desigualdades del sistema de restricciones, obtenemos la siguiente región factible:

En la figura aparecen las coordenadas de los vértices, que hemos calculado teniendo en cuenta que $A=r_1 \cap r_2$, y por tanto éstas deben satisfacer el sistema de ecuaciones $\left\{\begin{matrix}y&=&-x&+&2 \\ y&=&2x&-&4 \end{matrix}\right.$; $B=r_1 \cap r_3$, debiéndose resolver el sistema de ecuaciones $\left\{\begin{matrix}y&=&-x&+&2 \\ y&=&\dfrac{1}{2}\,x&+&2 \end{matrix}\right.$ y $C=r_2 \cap r_3$, debiéndose cumplir que $\left\{\begin{matrix}y&=&2\,x&-&4 \\ y&=&\dfrac{1}{2}\,x&+&2 \end{matrix}\right.$. Es muy fácil resolver estos sistemas, por lo que se omite el cálculo.

b)
La familia de rectas asociada a la función obtetivo ( haz de rectas paralelas ) $f(x,y)=-5x+3y$ viene descrita por $k=-5x+3y$, donde hemos asignado a $f$ el parámetro $k$, esto es cada una de las rectas del haz tiene por ecuación explícita $y=\dfrac{5}{3}x+\dfrac{k}{3}$, con un valor concreto de $k$ para cada una.

En la figura hemos representado una de ellas en color rojo, cuya ecuación es $y=\dfrac{5}{3}x$ ( dando a $k$ el valor cero ). Desplazando dicha recta paralelamente a sí misma de forma que barra todos los puntos de la región factible, es evidente que $A(2,0)$ corresponde al mínimo de $f(x,y)$ y que $B(0,2)$ corresponde al máximo, pues $f$ alcanza el mínimo cuando la recta desplazada pasa por el punto $A$ y $f$ alcanza el máximo al pasar por el punto $B$, pues al acanzar $\dfrac{k}{3}$ el mínimo ( respectivamente, el mínimo ) $f(x,y)$ alcanza también el máximo ( respectivamente, el máximo):

Así, sustituyendo las coordenadas de sendos puntos en $f(x,y)=-5x+3y$, encontramos que el mínimo de $f$ ( que se alcanza en $A(2,0)$ ) es igual a $f(2,0)=-5\cdot 2 +3\cdot 0=-10$; y, el máximo de $f$ ( que se alcanza en $B(0,2)$ ) es igual a $f(0,2)=-5 \cdot 0 + 3\cdot 2=6$

Nota: Podemos comprobar que en el punto $C(4,4)$ se alcanza un valor comprendido entre el mínimo y el máximo; en efecto, $-10 \prec f(4,4)=-5\cdot 4 + 3\cdot 4=-8 \prec 6$

$\square$