Mostrando entradas con la etiqueta máximo. Mostrar todas las entradas
Mostrando entradas con la etiqueta máximo. Mostrar todas las entradas

martes, 17 de mayo de 2016

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$