Capítulo 8 - Sistemas de Ecuaciones y Desigualdades¶

8.7 - Sistemas de Desigualdades¶

Cuando las condiciones son desigualdades, las soluciones dejan de ser puntos y se vuelven regiones; y la pregunta deja de ser cuáles son, para ser cuál es la mejor.

Las condiciones que la vida impone rara vez son igualdades exactas. Un taller dispone de a lo sumo cierta cantidad de horas, una dieta debe aportar al menos cierta cantidad de nutrientes, una carga no puede superar un límite. Cada condición es una desigualdad, y un sistema de desigualdades pide los puntos que las cumplen todas a la vez. Su conjunto solución ya no es un punto ni una recta sino una región del plano, y una pregunta nueva aparece: entre todos los puntos de la región, cuál hace mayor o menor una cantidad dada. Esta sección estudia las regiones definidas por desigualdades lineales, demuestra dónde se alcanzan los óptimos, y con ello introduce la programación lineal.

§1. Desigualdades lineales en dos variables¶

Sea $f(x,y)=ax+by-c$ con $(a,b)\neq(0,0)$, y sea $\ell$ la recta $f(x,y)=0$, es decir $ax+by=c$. Las desigualdades $f\le0$, $f\ge0$, $f<0$ y $f>0$ definen los semiplanos cerrados y abiertos determinados por $\ell$. Todo lo que sigue descansa en una propiedad de $f$ que se comprueba a simple vista.

Lema 1. Para dos puntos $P$ y $Q$ y todo $t\in\mathbb{R}$, con $(1-t)P+tQ$ el punto que resulta de combinar sus coordenadas, $$f\big((1-t)P+tQ\big)=(1-t)f(P)+tf(Q)$$

Demostración. Si $P=(x_1,y_1)$ y $Q=(x_2,y_2)$, entonces $f\big((1-t)P+tQ\big)=a\big((1-t)x_1+tx_2\big)+b\big((1-t)y_1+ty_2\big)-c$, y como $c=(1-t)c+tc$, esto es $(1-t)(ax_1+by_1-c)+t(ax_2+by_2-c)$. $\blacksquare$

Los puntos $(1-t)P+tQ$ con $0\le t\le1$ forman el segmento de $P$ a $Q$. Por el Lema 1, a lo largo de un segmento $f$ varía de manera afín, y de ahí se obtienen las dos propiedades de los semiplanos.

Proposición 2. Sean $P$ y $Q$ dos puntos.

Primero, si $f(P)\le0$ y $f(Q)\le0$ entonces $f\le0$ en todo el segmento $PQ$, y si ambos son estrictamente negativos, también lo es $f$ en todo el segmento; lo mismo vale con los signos invertidos. Segundo, si $f(P)<0<f(Q)$, el segmento $PQ$ corta a la recta $\ell$ en exactamente un punto.

Demostración. Para $0\le t\le1$, los coeficientes $1-t$ y $t$ son no negativos, de modo que $(1-t)f(P)+tf(Q)$ es una suma de números no positivos, y por lo tanto $\le0$; si $f(P)<0$ y $f(Q)<0$ es estrictamente negativa, porque $1-t$ y $t$ no son ambos nulos. Para el segundo punto, la ecuación $(1-t)f(P)+tf(Q)=0$ tiene la única solución $t=\dfrac{-f(P)}{f(Q)-f(P)}$, que pertenece a $(0,1)$ porque $-f(P)>0$ y $f(Q)-f(P)>-f(P)$. $\blacksquare$

La proposición justifica el método de graficación habitual. Dos puntos con $f$ del mismo signo están del mismo lado de $\ell$ y su segmento no toca la recta; dos con signos opuestos están a lados opuestos y su segmento la cruza. Por eso, para graficar $ax+by\le c$ se traza la recta, se evalúa $f$ en un punto que no esté sobre ella, por ejemplo el origen si $c\neq0$, y se sombrea el lado al que ese punto pertenece si $f\le0$ allí, o el otro si no. La recta se traza continua si la desigualdad es $\le$ o $\ge$, y punteada si es estricta.

§2. Convexidad¶

Definición. Un conjunto $C$ del plano es convexo si para cada par de puntos $P,Q\in C$ el segmento $PQ$ está contenido en $C$.

La primera parte de la Proposición 2 dice que todo semiplano, abierto o cerrado, es convexo. Y la intersección de conjuntos convexos es convexa: si $P$ y $Q$ pertenecen a todos, el segmento está en cada uno. De ambas se sigue lo esencial.

Corolario. El conjunto solución de un sistema de desigualdades lineales es convexo.

No todo conjunto definido por desigualdades lo es. El conjunto $\{(x,y):y\le x^2\}$ contiene a $(-1,1)$ y a $(1,1)$, pero no al punto medio $(0,1)$ de su segmento, porque $1\le0$ es falsa: no es convexo. Los sistemas de desigualdades no lineales, como $x^2+y^2\le25$ e $y\ge x^2-5$, que describen los puntos del círculo por encima de la parábola de la Figura 8.1, definen regiones limitadas por arcos de curva, y se grafican de la misma manera: se dibuja cada curva frontera, se decide con un punto de prueba de qué lado está la solución, y se intersecan las regiones.

Recordatorio. Un semiplano $ax+by\le c$ es convexo, y también lo es la solución de cualquier sistema de desigualdades lineales. Se grafica trazando la recta y evaluando un punto de prueba.

§3. Regiones factibles y vértices¶

Se considera de aquí en adelante un sistema de $m$ desigualdades lineales, todas escritas en la forma $a_ix+b_iy\le c_i$ con $(a_i,b_i)\neq(0,0)$; una desigualdad $\ge$ se pasa a esa forma multiplicando por $-1$ (§1.7). Su conjunto solución $R$ se llama región factible, y sus puntos, puntos factibles. Se dice que la desigualdad $i$ está activa en $X\in R$ si allí vale la igualdad, es decir, si $X$ está sobre su recta frontera.

Definición. Un vértice de $R$ es un punto de $R$ en el que están activas dos desigualdades cuyas rectas fronteras no son paralelas.

Un vértice es, entonces, el punto donde se cortan dos rectas fronteras, de modo que se lo halla resolviendo el sistema de sus dos ecuaciones, que por el Teorema 1 del §8.2 tiene solución única cuando las rectas no son paralelas. El procedimiento es sistemático: se resuelve el sistema de cada par de rectas fronteras no paralelas, y de las soluciones se conservan las que cumplen todas las demás desigualdades. Con $m$ desigualdades hay a lo sumo $\binom{m}{2}$ candidatos, de modo que $R$ tiene un número finito de vértices.

Ejemplo. Sea la región $x\ge0$, $y\ge0$, $x+y\le4$, $x-y\le2$. Los pares de rectas fronteras dan los candidatos $(0,0)$; $(2,0)$, de $y=0$ con $x-y=2$; $(4,0)$, de $y=0$ con $x+y=4$, que no cumple $x-y\le2$; $(0,4)$, de $x=0$ con $x+y=4$; $(0,-2)$, de $x=0$ con $x-y=2$, que no cumple $y\ge0$; y $(3,1)$, de $x+y=4$ con $x-y=2$. Los vértices de la región son $(0,0)$, $(2,0)$, $(3,1)$ y $(0,4)$, y la región es el cuadrilátero que ellos determinan.

§4. Programación lineal¶

Definición. Dado un sistema de desigualdades lineales con región factible $R$ y una función objetivo $P(x,y)=\alpha x+\beta y$, un problema de programación lineal consiste en hallar el mayor o el menor valor de $P$ sobre $R$, y los puntos de $R$ donde se alcanza. La región $R$ es acotada si está contenida en algún disco.

El resultado siguiente dice dónde buscar: no en todos los puntos de $R$, que son infinitos, sino en sus vértices, que son finitos.

Teorema (fundamental de la programación lineal). Sea $R$ una región factible no vacía y acotada. Entonces toda función objetivo lineal $P$ alcanza su máximo y su mínimo sobre $R$, y ambos se alcanzan en vértices.

Demostración. Se escribe $P(X)=\mathbf{p}\cdot X$ con $\mathbf{p}=(\alpha,\beta)$, y las desigualdades como $\mathbf{a}_i\cdot X\le c_i$ con $\mathbf{a}_i=(a_i,b_i)$. Se demuestra que, para todo $X\in R$, existe un vértice $V$ con $P(V)\ge P(X)$.

Primero, un hecho sobre movimientos rectilíneos. Sea $X\in R$ y $\mathbf{d}\neq\mathbf{0}$ una dirección. El conjunto de los $t\ge0$ con $X+t\mathbf{d}\in R$ está definido por las desigualdades $\mathbf{a}_i\cdot X+t \mathbf{a}_i\cdot\mathbf{d}\le c_i$, cada una una semirrecta cerrada en $t$; su intersección es un intervalo cerrado que contiene a $t=0$, y es acotado porque $R$ lo es. Luego es $[0,t^*]$. En el punto $X+t^*\mathbf{d}$ hay una desigualdad activa con $\mathbf{a}_i\cdot\mathbf{d}>0$: de lo contrario, las de ese tipo tendrían holgura y se podría avanzar un poco más, contra la maximalidad de $t^*$.

Sea ahora $X\in R$. Se elige $\mathbf{d}_1\neq\mathbf{0}$ con $P(\mathbf{d}_1)=\mathbf{p}\cdot\mathbf{d}_1\ge0$, por ejemplo $\mathbf{d}_1=\mathbf{p}$ si $\mathbf{p}\neq\mathbf{0}$, o cualquiera si $\mathbf{p}=\mathbf{0}$. Se avanza hasta $X'=X+t^*\mathbf{d}_1$, que está en $R$, cumple $P(X')\ge P(X)$ y tiene alguna desigualdad activa. Si en $X'$ hay dos desigualdades activas de rectas no paralelas, $X'$ es un vértice. Si no, todas las activas tienen rectas paralelas que pasan por $X'$, es decir, una misma recta $\ell$. Sea $\mathbf{e}\neq\mathbf{0}$ un vector paralelo a $\ell$, con signo elegido de modo que $P(\mathbf{e})\ge0$. Para las desigualdades activas, $\mathbf{a}_i\cdot\mathbf{e}=0$, de modo que siguen activas al avanzar según $\mathbf{e}$; las inactivas tienen holgura, así que se puede avanzar un poco. Por el hecho anterior se avanza hasta $X''=X'+t^*\mathbf{e}$, donde hay una desigualdad activa nueva, con $\mathbf{a}_k\cdot\mathbf{e}>0$, luego con recta no paralela a $\ell$. En $X''$ hay entonces dos desigualdades activas de rectas no paralelas: es un vértice, y $P(X'')\ge P(X')\ge P(X)$.

Como $R$ tiene un número finito de vértices y, por lo anterior, al menos uno, sea $M$ el mayor valor de $P$ entre ellos. Para todo $X\in R$, $P(X)\le M$, y $M$ se alcanza en un vértice: es el máximo de $P$ sobre $R$. Aplicando lo mismo a $-P$ se obtiene el mínimo. $\blacksquare$

Ejemplo: un problema de producción. Un taller fabrica mesas y sillas. Cada mesa requiere $2$ unidades de material y cada silla $1$, y hay $100$ disponibles; se dispone de $80$ horas de trabajo, una por unidad de cualquiera; y no se pueden fabricar más de $40$ mesas. La ganancia es de $40$ por mesa y $30$ por silla. Si $x$ es la cantidad de mesas e $y$ la de sillas, se trata de maximizar $P=40x+30y$ sujeto a $2x+y\le100$, $x+y\le80$, $x\le40$, $x\ge0$, $y\ge0$. Resolviendo los sistemas de pares de rectas fronteras y descartando los candidatos que violan alguna desigualdad, como $(0,100)$, $(80,0)$, $(50,0)$ o $(40,40)$, los vértices son $(0,0)$, $(40,0)$, $(40,20)$, $(20,60)$ y $(0,80)$. La región es acotada, y los valores de $P$ en ellos son $0$, $1600$, $2200$, $2600$ y $2400$. El máximo es $2600$, en $(20,60)$: conviene fabricar $20$ mesas y $60$ sillas.

La región factible del problema de producción, un pentágono de vértices (0,0), (40,0), (40,20), (20,60) y (0,80), con la recta de nivel 40x + 30y = 2600 que toca la región solo en el vértice (20,60) Figura 8.5 — La recta de nivel $40x+30y=2600$ es la última de la familia de rectas paralelas $40x+30y=k$ que toca la región al desplazarla hacia arriba: la toca en el vértice $(20,60)$.

La Figura 8.5 da la interpretación geométrica. Las rectas $P=k$ son paralelas, y $k$ crece al desplazarse hacia arriba y a la derecha. El máximo es el mayor $k$ para el que la recta todavía toca la región, y como la región es un polígono convexo, la última posición toca un vértice, o toda una arista si la recta de nivel es paralela a ella. En este segundo caso hay infinitos puntos óptimos, aunque siempre alcanza con mirar los vértices: con la función $P=2x+y$, cuya recta de nivel es paralela a la arista de $(40,20)$ a $(20,60)$, el máximo $100$ se alcanza en ambos extremos, y en todos los puntos del segmento que los une.

Recordatorio. Un vértice de la región es un punto factible donde se cortan dos rectas fronteras no paralelas. Si la región es acotada y no vacía, una función lineal alcanza su máximo y su mínimo en vértices. Se resuelve calculando los vértices y evaluando la función en cada uno. {{Todo: regiones no acotadas, método símplex y dualidad | Investigación Operativa}}

Este teorema es notable por lo que reduce: un problema con infinitos candidatos, todos los puntos de una región, pasa a tener un número finito, los vértices. La razón es la linealidad. Una función lineal no tiene máximos interiores, porque en cualquier punto que no sea un vértice hay una dirección en la que crece, o al menos no decrece, y por lo tanto el óptimo se refugia en los extremos de la región. Con funciones no lineales esa reducción falla, y el estudio del óptimo exige otros métodos, los del cálculo. Con muchas variables, además, la cantidad de vértices crece de manera explosiva, y la manera de recorrerlos sin enumerarlos todos es el método símplex, que este libro no desarrolla.

Con esto queda completo el recorrido del capítulo, de las ecuaciones a las desigualdades y de los puntos a las regiones. La sección final lo mira en conjunto: de dónde vino cada idea, y qué tienen en común.