Programación lineal

ENUNCIADO. Considérese la región del plano $S$ definida por $$S=\{(x,y)\in \mathbb{R}^2: x+6y\ge 6;5x-2y\ge -2;x+3y\le 20;2x-y\le 12\}$$
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)=4x-3y$ alcanza sus valores máximo y mínimo en $S$, indicando el valor de $f(x,y)$ en dichos puntos

SOLUCIÓN. Es conveniente expresar las ecuaciones de $S$ de la forma $$S:\left\{\begin{matrix}y&\ge&-\dfrac{1}{6}\,x&+&1 \\ y&\le &\dfrac{5}{2}x&+&1 \\ y&\le&-\dfrac{1}{3}\,x&+&\dfrac{20}{3} \\ y&\ge&2\,x&-&12 \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&\ge&-\dfrac{1}{6}\,x&+&1 \\ r_2:y&\le &\dfrac{5}{2}x&+&1 \\ r_3:y&\le&-\dfrac{1}{3}\,x&+&\dfrac{20}{3} \\ r_4:y&\ge&2\,x&-&12 \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,1)$ y $Q_1(6,0)$; para $r_2$, $P_2(0,1)$ y $Q_2(-2/5,0)$; para $r_3$, $P_3(0,20/3)$ y $Q_3(20,0)$; y, para $r_4$, $P_4(0,-12)$ y $Q_4(6,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_4$, y por tanto éstas deben satisfacer el sistema de ecuaciones $\left\{\begin{matrix}y&=&-\dfrac{1}{6}\,x&+&2 \\ y&=&2x&-&12 \end{matrix}\right.$

$B=r_1 \cap r_2$, debiéndose resolver el sistema de ecuaciones $\left\{\begin{matrix}y&=&-\dfrac{1}{6}\,x&+&2 \\ y&= &\dfrac{5}{2}x&+&1 \end{matrix}\right.$

$C=r_2 \cap r_3$, debiéndose cumplir que $\left\{\begin{matrix}y&= &\dfrac{5}{2}x&+&1 \\ y&=&-\dfrac{1}{3}\,x&+&\dfrac{20}{3}\end{matrix}\right.$

y $D=r_3 \cap r_4$, debiéndose cumplir que $\left\{\begin{matrix}y&=&-\dfrac{1}{3}\,x&+&\dfrac{20}{3}\\ y&=&2\,x&-&12 \end{matrix}\right.$

Nota: 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)=4x-3y$ viene descrita por $k=4x-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{4}{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{4}{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, vemos que $A(6,0)$ corresponde al mínimo de $-\dfrac{k}{3}$ y, por tanto, al máximo de $k$ ( esto es, de $f(x,y)$ ); por otra parte, $C(2,6)$ corresponde al máximo de $-\dfrac{k}{3}$ y por tanto al mínimo de $k$ ( es decir, de $f(x,y)$):

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

Nota: Podemos comprobar que en el punto $B(0,1)$ y $D(8,4)$ se alcanzas valores comprendidos entre el mínimo y el máximo; en efecto, $f(0,1)=-3$ y $f(8,4)=20$, con lo cual $-10 \prec f_{B}(0,1) \prec 24$ y $-10 \prec f_{D}(8,4) \prec 24$

$\square$