Un ejercicio de programación lineal

ENUNCIADO. Considérese la región del plano $S$ definida por $$S=\{(x,y)\in \mathbb{R}^2: 1\le x \le 5\,;\,2 \le y \le 6\,;\,x-y\ge -4\,;\,3x-y\le 10\}$$
a) Represéntese gráficamente la región $S$ y calcúlense las coordenadas de sus vértices
b) Determínense los puntos en los que la función $f(x,y)=-200\,x+600\,y$ alcanza sus valores máximo y mínimo en $S$, indicando el valor de $f(x,y)$ en dichos puntos

SOLUCIÓN.

a)
Las condiciones del enunciado que definen la región factible (región convexa del plano) pueden expresarse de la forma $$\left.\begin{matrix}x\le 5 \\ x\ge 1 \\ y\le 6 \\ y\ge 2 \\ x+4 \ge y \\ 3x -10 \le y \end{matrix}\right\} \sim \left.\begin{matrix}x\le 5 \\ x\ge 1 \\ y\le 6 \\ y\ge 2 \\ y\le x+4 \\ y \ge 3x-10 \end{matrix}\right\}$$ y las rectas que contienen los lados de la misma son $$\left.\begin{matrix}r_1\equiv x=5 \\ r_2\equiv x=1 \\ r_3\equiv y= 6 \\ r_4\equiv y= 2 \\ r_5\equiv y= x+4 \\ r_6\equiv y = 3x-10 \end{matrix}\right\}$$
Atendiendo al sentido de las desigualdades obtenemos,

Procedemos ahora a calcular las coordenadas de los vértices de dicha región:
$$A=r_2\cap r_4 \equiv\left\{\begin{matrix}x=1\\y=2\end{matrix}\right.\; \text{luego} \rightarrow A(1,2)$$
$$B=r_2\cap r_5 \equiv\left\{\begin{matrix}x=1\\y=x+4\end{matrix}\right.\sim \left\{\begin{matrix}x=1\\y=5\end{matrix}\right.\; \text{luego} \rightarrow B(1,5)$$
$$C=r_5\cap r_3 \equiv\left\{\begin{matrix}y=6\\y=x+4\end{matrix}\right.\sim \left\{\begin{matrix}x=2\\y=6\end{matrix}\right.\; \text{luego} \rightarrow C(2,6)$$
$$D=r_1\cap r_3 \equiv\left\{\begin{matrix}x=5\\y=6\end{matrix}\right.\; \text{luego} \rightarrow D(5,6)$$
$$E=r_1\cap r_6 \equiv\left\{\begin{matrix}x=5\\y=3x-10\end{matrix}\right.\sim \left\{\begin{matrix}x=5\\y=5\end{matrix}\right.\; \text{luego} \rightarrow E(5,5)$$
$$F=r_4\cap r_6 \equiv\left\{\begin{matrix}y=2\\y=3x-10\end{matrix}\right.\sim \left\{\begin{matrix}x=4\\y=2\end{matrix}\right.\; \text{luego} \rightarrow F(4,2)$$

b)
Encontramos la familia de rectas asociada a la función objetivo $f(x,y)=-200x+600y$, considerando el valor de $f$ como parámetro: $k=f(x,y)$ y despejando la variable dependiente $y$, llegamos a $y=\dfrac{1}{3}\,x+\dfrac{k}{600}$, para todo $k\in \mathbb{R}$. La pendiente de las rectas de dicho haz ( de rectas paralelas ) es $\dfrac{1}{3}$, que no coincide con la pendiente de ningua de las rectas que contienen los lados de la región convexa, en consecuencia el máximo y el mínimo de $f(x,y)$ se darán para ciertos vértices de la región factible ( no para los lados ). Veamos los valores de dichos máximo y mínimo y en qué vértices para que valores de $x$ e $y$ ( coordenadas de los respectivos vértices ) se alcanzan; para ello, organizaremos los resultados en la siguiente tabla:

----------------------------------------------------------
----------------------------------------------------------
 vértice  |  x  |     y       |    f(x,y)=-200x+600y
----------------------------------------------------------
    A     |  1  |     2       |   -200+1200=1000
----------------------------------------------------------
    B     |  1  |     5       |   -200+3000=2800
----------------------------------------------------------
    C     |  2  |     6       |   -400+3600=3200 (máximo)
----------------------------------------------------------
    D     |  5  |     6       |   -1000+3600=2600
----------------------------------------------------------
    E     |  5  |     5       |   -1000+3000=2000
----------------------------------------------------------
    F     |  4  |     2       |   -800+1200= 400 (mínimo)
----------------------------------------------------------

$\square$