Mostrando entradas con la etiqueta sistema de restricciones. Mostrar todas las entradas
Mostrando entradas con la etiqueta sistema de restricciones. 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$


viernes, 19 de junio de 2015

Una fábrica de piensos produce diariamente, como mucho, seis toneladas de ...

ENUNCIADO
Una fábrica de piensos para animales produce diariamente, como mucho, seis toneladas de pienso de tipo $A$; y, a lo sumo, cuatro toneladas de pienso de tipo $B$. Además, la producción diaria de pienso de tipo $B$ no puede superar el doble de la de tipo $A$; y, por último, el doble de la fabricación de pienso de tipo $A$ sumada con la de tipo $B$ debe ser, como poco, de cuatro toneladas diarias. Teniendo en cuenta que el coste de fabricación de una tonelada de pienso de tipo $A$ es de $1000$ euros, y el de una tonelada de pienso de tipo $B$ es de $2000$ euros, ¿ cuál es la producción diaria para que la fábrica cumpla con sus obligaciones con un coste mínimo ? Calcúlese dicho coste diario mínimo.

[ PAU 2015, Madrid ]

SOLUCIÓN
Denotemos por $a$ la cantidad de pienso de tipo $A$ producida diariamente; y, por $b$, la de tipo $B$. Entonces, el sistema de restricciones es
$$\mathcal{R:}\left\{\begin{matrix}
a & \ge & 0 \\
b & \ge & 0 \\
a & \le & 6 \\
b & \le & 4 \\
b & \le & 2\,a \\
2a &+&b& \ge & 4 \\
\end{matrix}\right.$$

Las dos primeras desigualdades sitúan la región factible en el primer cuadrante. Para determinar su contorno, trazamos las rectas frontera

$$\left\{\begin{matrix}
r_1:\,b & = & 0 \\
r_2:\,a & = & 6 \\
r_3:\,b & = & 4 \\
r_4:\,b & = & 2\,a \\
r_5;\,b &=&-2\,a& + & 4 \\
\end{matrix}\right.$$

y calculando las coordenadas de los vértices,
$$A \in r_3 \cap r_4 \Rightarrow A:\,\left\{\begin{matrix}
b & = & 4 \\
b & = & 2\,a \\
\end{matrix}\right.
\Leftrightarrow A(2,4)$$

$$B \in r_4 \cap r_5 \Rightarrow B:\,\left\{\begin{matrix}
b & = & -2\,a+4 \\
b & = & 2\,a \\
\end{matrix}\right.
\Leftrightarrow B(1,2)$$

$$C \in r_1 \cap r_5 \Rightarrow C:\,\left\{\begin{matrix}
b & = & -2\,a+4 \\
b & = & 0 \\
\end{matrix}\right.
\Leftrightarrow C(2,0)$$

$$D \in r_1 \cap r_2 \Rightarrow D:\,\left\{\begin{matrix}
a & = & 6 \\
b & = & 0 \\
\end{matrix}\right.
\Leftrightarrow D(6,0)$$

$$E \in r_2 \cap r_3 \Rightarrow E:\,\left\{\begin{matrix}
a & = & 6 \\
b & = & 4 \\
\end{matrix}\right.
\Leftrightarrow E(6,4)$$



La función objetivo es $$f(a,b)=1000\,a+2000\,b$$

Escogiendo $f(a,b):=0$, representamos fácilmente una de las rectas de la familia de rectas de la función objetivo: $b=-\dfrac{1}{2}\,a$; y, trazando paralelas a la misma que incidan en la región factible $\mathcal{R}$, visualizamos dicha familia ( en rojo ), para los diversos valores de $f(a,b)$, cantidad a la que, por comodidad, denominaremos $k$: $$\mathcal{F}:\,b=-\dfrac{1}{2}\,a+\dfrac{k}{2000}$$ De entre estas infinitas rectas, encontramos que la recta que da el mínimo valor de $f(a,b)$; y, por tanto, el mínimo valor de la ordenada en el origen $\dfrac{k}{2000}$, que es la que pasa por el punto $A(2,0)$, como se observa en el gráfico. Las rectas paralelas que pasan por los otros vértices de $\mathcal{R}$ dan valores mayores de $f$, tal y como se puede comprobar, también, de forma numérica. De aquí se deduce que para que el coste sea mínimo, la producción diaria de pienso de tipo $A$ ha de ser de $2$ toneladas; y, la de $B$, $0$ toneladas.

En estas condiciones, el coste mínimo es igual a $f(2,0)=1000 \cdot 2 + 2000 \cdot 0 = 2000$ euros diarios.

$\square$



[nota del autor]

viernes, 22 de mayo de 2015

Resolver el siguiente ejerccio de programación lineal

ENUNCIADO. Considerar el siguiente sistema de restricciones
$$\left\{\begin{matrix}
x & \ge & 0\\
y & \ge & 3\\
x+y & \le & 10\\
2y & \ge & 3x\\
\end{matrix}\right.$$
¿ En qué puntos de la región alcanza el máximo y el mínimo la función objetivo $f(x,y)=4x+3y$ ? ¿ Cuáles son los valores de función en dichos puntos ?.

SOLUCIÓN.
El siguiente gráfico ( realizado con Geogebra ) ilustra el resumen de la resolución del problema
La ordenada en el origen, $k$, de cada una de las rectas de la familia de la función objetivo, representa el valor de $\dfrac{1}{3}\cdot F(x_P,y_P)$, para cada punto $P(x_P,y_P)$ de la región factible; evidentemente, el máximo de $k$ se da para el mismo punto que el máximo de $F(x,y)$, y lo propio podemos decir en cuanto al mínimo. Así, examinando el gráfico, puede verse que el máximo de $F(x,y)$ lo da el punto $C(4,6)$, que es igual a $F(4,6)=4\cdot 4 + 3 \cdot 6 = 34$, y el valor mínimo lo da el punto $A(0,3)$, que es igual a $F(0,3)=4\cdot 0+3 \cdot 3=9$.

Nota: la barra deslizadora de la imagen permite, con Geogebra, hacer que las rectas de la función objetivo recorran los puntos de la región factible.
$\square$

[nota del autor]