Ir al contenido

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

Sección titulada «§1. Desigualdades lineales en dos variables»

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

Lema 1. Para dos puntos PP y QQ y todo t∈Rt\in\mathbb{R}, con (1−t)P+tQ(1-t)P+tQ el punto que resulta de combinar sus coordenadas,

f((1−t)P+tQ)=(1−t)f(P)+tf(Q)f\big((1-t)P+tQ\big)=(1-t)f(P)+tf(Q)

Demostración. Si P=(x1,y1)P=(x_1,y_1) y Q=(x2,y2)Q=(x_2,y_2), entonces f((1−t)P+tQ)=a((1−t)x1+tx2)+b((1−t)y1+ty2)−cf\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+tcc=(1-t)c+tc, esto es (1−t)(ax1+by1−c)+t(ax2+by2−c)(1-t)(ax_1+by_1-c)+t(ax_2+by_2-c). ■\blacksquare

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

Proposición 2. Sean PP y QQ dos puntos.

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

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

La proposición justifica el método de graficación habitual. Dos puntos con ff 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≤cax+by\le c se traza la recta, se evalúa ff en un punto que no esté sobre ella, por ejemplo el origen si c≠0c\neq0, y se sombrea el lado al que ese punto pertenece si f≤0f\le0 allí, o el otro si no. La recta se traza continua si la desigualdad es ≤\le o ≥\ge, y punteada si es estricta.


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

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 PP y QQ 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≤x2}\{(x,y):y\le x^2\} contiene a (−1,1)(-1,1) y a (1,1)(1,1), pero no al punto medio (0,1)(0,1) de su segmento, porque 1≤01\le0 es falsa: no es convexo. Los sistemas de desigualdades no lineales, como x2+y2≤25x^2+y^2\le25 e y≥x2−5y\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.


Se considera de aquí en adelante un sistema de mm desigualdades lineales, todas escritas en la forma aix+biy≤cia_ix+b_iy\le c_i con (ai,bi)≠(0,0)(a_i,b_i)\neq(0,0); una desigualdad ≥\ge se pasa a esa forma multiplicando por −1-1 (§1.7). Su conjunto solución RR se llama región factible, y sus puntos, puntos factibles. Se dice que la desigualdad ii está activa en X∈RX\in R si allí vale la igualdad, es decir, si XX está sobre su recta frontera.

Definición. Un vértice de RR es un punto de RR 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 mm desigualdades hay a lo sumo (m2)\binom{m}{2} candidatos, de modo que RR tiene un número finito de vértices.

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


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

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

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

Demostración. Se escribe P(X)=p⋅XP(X)=\mathbf{p}\cdot X con p=(α,β)\mathbf{p}=(\alpha,\beta), y las desigualdades como ai⋅X≤ci\mathbf{a}_i\cdot X\le c_i con ai=(ai,bi)\mathbf{a}_i=(a_i,b_i). Se demuestra que, para todo X∈RX\in R, existe un vértice VV con P(V)≥P(X)P(V)\ge P(X).

Primero, un hecho sobre movimientos rectilíneos. Sea X∈RX\in R y d≠0\mathbf{d}\neq\mathbf{0} una dirección. El conjunto de los t≥0t\ge0 con X+td∈RX+t\mathbf{d}\in R está definido por las desigualdades ai⋅X+tai⋅d≤ci\mathbf{a}_i\cdot X+t \mathbf{a}_i\cdot\mathbf{d}\le c_i, cada una una semirrecta cerrada en tt; su intersección es un intervalo cerrado que contiene a t=0t=0, y es acotado porque RR lo es. Luego es [0,t∗][0,t^*]. En el punto X+t∗dX+t^*\mathbf{d} hay una desigualdad activa con ai⋅d>0\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∗t^*.

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

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

Ejemplo: un problema de producción. Un taller fabrica mesas y sillas. Cada mesa requiere 22 unidades de material y cada silla 11, y hay 100100 disponibles; se dispone de 8080 horas de trabajo, una por unidad de cualquiera; y no se pueden fabricar más de 4040 mesas. La ganancia es de 4040 por mesa y 3030 por silla. Si xx es la cantidad de mesas e yy la de sillas, se trata de maximizar P=40x+30yP=40x+30y sujeto a 2x+y≤1002x+y\le100, x+y≤80x+y\le80, x≤40x\le40, x≥0x\ge0, y≥0y\ge0. Resolviendo los sistemas de pares de rectas fronteras y descartando los candidatos que violan alguna desigualdad, como (0,100)(0,100), (80,0)(80,0), (50,0)(50,0) o (40,40)(40,40), los vértices son (0,0)(0,0), (40,0)(40,0), (40,20)(40,20), (20,60)(20,60) y (0,80)(0,80). La región es acotada, y los valores de PP en ellos son 00, 16001600, 22002200, 26002600 y 24002400. El máximo es 26002600, en (20,60)(20,60): conviene fabricar 2020 mesas y 6060 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=260040x+30y=2600 es la última de la familia de rectas paralelas 40x+30y=k40x+30y=k que toca la región al desplazarla hacia arriba: la toca en el vértice (20,60)(20,60).

La Figura 8.5 da la interpretación geométrica. Las rectas P=kP=k son paralelas, y kk crece al desplazarse hacia arriba y a la derecha. El máximo es el mayor kk 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+yP=2x+y, cuya recta de nivel es paralela a la arista de (40,20)(40,20) a (20,60)(20,60), el máximo 100100 se alcanza en ambos extremos, y en todos los puntos del segmento que los une.


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.