Espacios vectoriales y conjuntos convexos

1. La pregunta

Una fábrica puede repartir sus horas de máquina entre tres productos de infinitas maneras. El conjunto de todos los planes que respetan las restricciones —horas, materia prima, no producir cantidades negativas— es enorme. Y sin embargo, el mejor plan está siempre en una de sus esquinas, que son un puñado.

Ese hecho no es una casualidad: es una propiedad geométrica del conjunto factible, y es lo que hace que el símplex del tema 16 funcione. Este tema lo demuestra, y de paso cierra el bloque 2 con el vocabulario —independencia lineal, base, dimensión— que la econometría y la programación lineal usarán sin volver a explicarlo.

2. Intuición

Combinación lineal. Con dos tipos de café, uno a 8 €/kg y otro a 14 €/kg, cualquier mezcla es una combinación lineal de los dos. Los coeficientes son las proporciones. La pregunta «¿qué mezclas puedo conseguir?» es la pregunta por el subespacio generado.

Independencia lineal. Si añades un tercer café que resulta ser exactamente la mezcla al 50 % de los otros dos, no has ganado nada: cualquier cosa que puedas hacer con los tres la podías hacer con los dos. Ese tercero es linealmente dependiente. Es el mismo fenómeno que en el tema 7 hacía que el rango fuera menor que el número de columnas.

Base y dimensión. Una base es un conjunto de ingredientes sin redundancia con el que puedes fabricar todo lo del espacio. La dimensión es cuántos hacen falta. No es una elección única —hay muchas bases— pero el número siempre es el mismo.

Convexidad. Un conjunto es convexo si, tomando dos puntos cualesquiera de dentro, el segmento que los une está también dentro. Un disco es convexo; una luna creciente no. Lo que hace especiales a los conjuntos convexos es que no tienen entrantes: si vas mejorando en línea recta, no te vas a encontrar con que hay que salir del conjunto para seguir mejorando.

Y de ahí sale la propiedad clave: en un conjunto convexo con esquinas, una función lineal alcanza su máximo en una esquina. Piensa en un solar poligonal en una ladera de pendiente constante: el punto más alto está siempre en un vértice de la valla, nunca en mitad del campo.

3. Formalización

Espacio vectorial ${\mathbb{R}}^n$

${\mathbb{R}}^n$ es el conjunto de las $n$-tuplas de números reales, con la suma componente a componente y el producto por escalares. Sus elementos son vectores, y en economía representan cestas de bienes, planes de producción o carteras.

Un subespacio vectorial es un subconjunto que contiene al vector nulo y es cerrado para la suma y el producto por escalares. Los subespacios de ${\mathbb{R}}^3$ son: el origen, las rectas que pasan por él, los planos que pasan por él, y todo el espacio.

Aviso que importa en programación lineal: el conjunto factible de un problema con restricciones del tipo $x\ge 0$ no es un subespacio, porque no admite multiplicar por escalares negativos. Es un conjunto convexo, que es otra cosa y es lo que se estudia más abajo.

Combinación lineal, dependencia e independencia

Una combinación lineal de ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_k$ es

$$c_1{\mathbf{v}}_1+c_2{\mathbf{v}}_2+\cdots +c_k{\mathbf{v}}_k$$

con $c_1,\dots ,c_k$ números reales.

Los vectores son linealmente independientes si la única forma de que esa combinación dé el vector nulo es con todos los coeficientes nulos:

$$c_1{\mathbf{v}}_1+\cdots +c_k{\mathbf{v}}_k=0⟹c_1=\cdots =c_k=0$$

Si existe alguna combinación no trivial que dé cero, son dependientes, y entonces al menos uno se puede escribir en función de los demás: sobra.

Cómo se comprueba en la práctica. Se ponen los vectores como filas de una matriz y se calcula el rango. Son independientes si el rango es igual a su número. Si son tantos vectores como componentes, basta con mirar si el determinante es distinto de cero.

Base y dimensión

Una base de un subespacio es un conjunto de vectores que (1) es linealmente independiente y (2) genera todo el subespacio. La dimensión es el número de elementos de cualquiera de sus bases.

En ${\mathbb{R}}^n$, la base canónica son los vectores con un 1 en una posición y ceros en el resto. Su dimensión es $n$.

Un resultado que se usa constantemente: en ${\mathbb{R}}^n$, $n$ vectores son base si y solo si son linealmente independientes. No hace falta comprobar que generan: si son $n$ e independientes, generan automáticamente.

Conjuntos convexos

Un conjunto $S\subseteq {\mathbb{R}}^n$ es convexo si para todos $\mathbf{x},\mathbf{y}\in S$ y todo $\lambda \in [0,1]$:

$$\lambda \mathbf{x}+(1-\lambda )\mathbf{y}\in S$$

La expresión $\lambda \mathbf{x}+(1-\lambda )\mathbf{y}$ es una combinación convexa: al variar $\lambda$ de 0 a 1 recorre el segmento que va de $\mathbf{y}$ a $\mathbf{x}$.

Ejemplos que aparecen en el bloque 4:

• Un semiespacio, $\{\mathbf{x}:{\mathbf{a}}^{\top }\mathbf{x}\le b\}$, es convexo. Cada restricción de desigualdad define uno.
• Un hiperplano, $\{\mathbf{x}:{\mathbf{a}}^{\top }\mathbf{x}=b\}$, es convexo.
• La intersección de convexos es convexa. Este es el teorema decisivo: como cada restricción da un convexo, el conjunto factible —que es la intersección de todas— es automáticamente convexo, sin importar cuántas restricciones haya.

La unión, en cambio, no tiene por qué serlo.

Poliedros, vértices y el teorema fundamental

Un poliedro es la intersección de un número finito de semiespacios: exactamente lo que define un conjunto de restricciones lineales. Si además está acotado, se llama politopo.

Un punto extremo o vértice de un conjunto convexo es un punto que no se puede escribir como combinación convexa de otros dos puntos distintos del conjunto. Son las esquinas.

Teorema fundamental de la programación lineal. Si el conjunto factible de un problema lineal es un politopo no vacío, la función objetivo alcanza su óptimo en al menos un vértice. Si lo alcanza en dos, lo alcanza en todos los puntos del segmento que los une.

Por qué es tan importante. Convierte un problema con infinitos candidatos en uno con un número finito de ellos. El símplex no hace otra cosa que recorrer vértices de forma inteligente, y su legitimidad viene entera de este teorema.

Un vértice de un poliedro en ${\mathbb{R}}^n$ se caracteriza algebraicamente: es un punto factible donde hay al menos $n$ restricciones que se cumplen con igualdad y cuyos vectores de coeficientes son linealmente independientes. Esa caracterización es la que permite encontrarlos resolviendo sistemas, que es lo que se hará en el tema 15.

4. Ejemplo económico resuelto

Problema. Un taller fabrica dos productos, $x_1$ y $x_2$. Dispone de 120 horas de máquina y 100 kg de materia prima. Cada unidad de $x_1$ consume 2 horas y 1 kg; cada unidad de $x_2$, 2 horas y 2,5 kg. Describe el conjunto factible, demuestra que es convexo y halla sus vértices.

Paso 1. Escribir las restricciones.

$$\{\begin{array}{ll}2x_1+2x_2\le 120& \text{(horas)}\\ x_1+2,5x_2\le 100& \text{(materia prima)}\\ x_1\ge 0,x_2\ge 0& \text{(no negatividad)}\end{array}$$

Simplificando la primera entre 2: $x_1+x_2\le 60$.

Paso 2. Demostrar que el conjunto factible es convexo. Cada una de las cuatro restricciones define un semiespacio, y los semiespacios son convexos. El conjunto factible es la intersección de los cuatro, y la intersección de convexos es convexa.

No hace falta dibujar nada ni comprobar puntos: el argumento vale igual con 4 restricciones que con 400, y es la razón de que todo problema lineal tenga región factible convexa.

Paso 3. Encontrar los vértices. Con $n=2$ variables, un vértice es un punto donde dos restricciones se cumplen con igualdad. Hay $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ parejas; se resuelve cada sistema y se descartan los puntos que no sean factibles.

Pareja $x_1=0$, $x_2=0$: punto $(0,0)$. Factible. Vértice A.

Pareja $x_1=0$, $x_1+x_2=60$: punto $(0,60)$. Comprobamos la otra restricción: $0+2,5(60)=150>100$. No factible, se descarta.

Pareja $x_1=0$, $x_1+2,5x_2=100$: punto $(0,40)$. Comprobamos: $0+40=40\le 60✓$. Vértice B.

Pareja $x_2=0$, $x_1+x_2=60$: punto $(60,0)$. Comprobamos: $60+0=60\le 100✓$. Vértice C.

Pareja $x_2=0$, $x_1+2,5x_2=100$: punto $(100,0)$. Comprobamos: $100>60$. No factible, se descarta.

Pareja de las dos restricciones de recursos:

$$\{\begin{array}{l}{x}_1+x_2=60\\ x_1+2,5x_2=100\end{array}$$

Restando la primera de la segunda: $1,5x_2=40⟹x_2=26,67$, y $x_1=60-26,67=33,33$. Los dos son no negativos. Vértice D: $(33,33;26,67)$.

Paso 4. El conjunto factible. Es el cuadrilátero de vértices

$$A(0,0),B(0,40),D(33,33;26,67),C(60,0)$$

Paso 5. Usar el teorema. Si el margen es de 30 € por unidad de $x_1$ y 40 € por unidad de $x_2$, el beneficio $Z=30x_1+40x_2$ es lineal, así que basta evaluarlo en los cuatro vértices:

Vértice	$x_1$	$x_2$	$Z$
A	0	0	0
B	0	40	1600
D	33,33	26,67	1000 + 1066,8 = 2066,8
C	60	0	1800

El óptimo es D, con 2066,80 € de beneficio, y ahí los dos recursos se agotan por completo.

Lo que hay que retener. Se han evaluado cuatro puntos en lugar de explorar infinitos planes, y la garantía de que el óptimo está entre ellos la da el teorema fundamental. Con veinte variables los vértices son muchos más y hay que recorrerlos con método: eso es el símplex.

5. Errores típicos

Confundir subespacio con conjunto convexo. El conjunto factible de un problema lineal casi nunca es un subespacio (no contiene el vector nulo si hay restricciones de mínimos, y no admite escalares negativos por la no negatividad). Sí es convexo. Son propiedades distintas.

Creer que la unión de convexos es convexa. Dos discos separados forman un conjunto no convexo: el segmento que une un punto de cada uno pasa por fuera. Solo la intersección conserva la convexidad.

Dar por vértice cualquier corte de dos restricciones. El punto tiene que ser factible, es decir, cumplir todas las demás restricciones. En el ejemplo, dos de los seis cortes quedaron fuera de la región.

Olvidar las restricciones de no negatividad al contar vértices. $x_1\ge 0$ y $x_2\ge 0$ son restricciones como las demás y generan vértices, incluido el origen.

Confundir independencia lineal con «vectores distintos». Tres vectores pueden ser distintos dos a dos y aun así dependientes, si uno es combinación de los otros dos. La prueba es el rango, no la vista.

Aplicar el teorema fundamental a funciones no lineales. Solo garantiza vértices para objetivos lineales. Con una función objetivo cuadrática el óptimo puede estar en el interior, y ahí hace falta el bloque 3.

6. Ejercicios

Ejercicio 1 · Dependencia lineal

básico

Determina si son linealmente independientes:

$${\mathbf{v}}_1=\left(\begin{array}{c}1\\ 2\\ 3\end{array}\right),{\mathbf{v}}_2=\left(\begin{array}{c}2\\ 1\\ 0\end{array}\right),{\mathbf{v}}_3=\left(\begin{array}{c}4\\ 5\\ 6\end{array}\right)$$

Ver solución

Son tres vectores en ${\mathbb{R}}^3$: basta el determinante de la matriz que forman.

$$\det =\left|\begin{array}{ccc}1& 2& 4\\ 2& 1& 5\\ 3& 0& 6\end{array}\right|$$

Por Sarrus. Diagonales a la derecha: $1\cdot 1\cdot 6+2\cdot 5\cdot 3+4\cdot 2\cdot 0=6+30+0=36$. Diagonales a la izquierda: $4\cdot 1\cdot 3+1\cdot 5\cdot 0+2\cdot 2\cdot 6=12+0+24=36$.

$$\det =36-36=0$$

Determinante nulo: son linealmente dependientes.

La relación concreta es ${\mathbf{v}}_3=2{\mathbf{v}}_1+{\mathbf{v}}_2$: $2(1)+2=4$, $2(2)+1=5$, $2(3)+0=6$. Los tres vectores generan solo un plano, no todo ${\mathbb{R}}^3$.

Ejercicio 2 · ¿Es convexo?

básico

Di si son convexos, justificando:

1. $S_1=\{(x,y):x+2y\le 10,x\ge 0,y\ge 0\}$
2. $S_2=\{(x,y):x^2+y^2=25\}$
3. $S_3=\{(x,y):x^2+y^2\le 25\}$

Ver solución

1. Sí. Es intersección de tres semiespacios, y la intersección de convexos es convexa.

2. No. Es una circunferencia, solo el borde. Tomando $(5,0)$ y $(-5,0)$, ambos del conjunto, su punto medio es $(0,0)$, que cumple $0=0\ne 25$: no pertenece. El segmento se sale.

3. Sí. Es el disco, borde incluido. Cualquier segmento entre dos puntos del disco queda dentro. La diferencia con el caso 2 es la desigualdad frente a la igualdad: la igualdad deja solo la cáscara, que es hueca.

Moraleja. Una restricción de igualdad no lineal rompe la convexidad; una de desigualdad no lineal puede conservarla. Con restricciones lineales, tanto igualdades como desigualdades dan conjuntos convexos.

Ejercicio 3 · Vértices de una región de dieta

medio

Un centro debe servir raciones que aporten al menos 60 g de proteína y al menos 80 g de hidratos. El alimento A aporta 3 g de proteína y 2 g de hidratos por unidad; el B, 1 g y 4 g. Encuentra los vértices de la región factible.

Ver solución

Restricciones, con $x_A$ y $x_B$ las unidades de cada alimento:

$$\{\begin{array}{l}3x_A+x_B\ge 60\\ 2x_A+4x_B\ge 80\\ x_A\ge 0,x_B\ge 0\end{array}$$

Nótese que ahora son $\ge$: la región no está acotada por arriba (siempre se puede servir de más). Aun así tiene vértices.

Corte con $x_A=0$: de la primera, $x_B\ge 60$; de la segunda, $x_B\ge 20$. Manda la más exigente: $(0,60)$. Comprobación: $2(0)+4(60)=240\ge 80✓$. Vértice P.

Corte con $x_B=0$: de la primera, $x_A\ge 20$; de la segunda, $x_A\ge 40$. Manda $(40,0)$. Comprobación: $3(40)+0=120\ge 60✓$. Vértice R.

Corte de las dos restricciones nutricionales:

$$\{\begin{array}{l}3x_A+x_B=60\\ 2x_A+4x_B=80\end{array}$$

De la primera, $x_B=60-3x_A$. Sustituyendo en la segunda:

$$2x_A+4(60-3x_A)=80⟹2x_A+240-12x_A=80⟹-10x_A=-160$$$$x_A=16,x_B=60-48=12$$

Los dos no negativos. Vértice Q: $(16,12)$.

Cortes descartados: $(0,20)$ del segundo con el eje incumple la primera ($0+20<60$); $(20,0)$ incumple la segunda ($40<80$).

Vértices: $P(0,60)$, $Q(16,12)$, $R(40,0)$.

Si el alimento A cuesta 2 € y el B 3 €, el coste $Z=2x_A+3x_B$ vale 180, 68 y 80 respectivamente. El mínimo está en Q, con 68 €. Al ser una región no acotada, para un problema de maximización no habría solución finita; para uno de minimización sí, y está en un vértice, como garantiza el teorema.

Ejercicio 4 · Demostrar que la intersección conserva la convexidad

avanzado

Demuestra que si $S_1$ y $S_2$ son convexos, entonces $S_1\cap S_2$ es convexo. Explica por qué ese resultado, y no otro, es el que garantiza que toda región factible lineal sea convexa.

Ver solución

Demostración. Sean $\mathbf{x},\mathbf{y}\in S_1\cap S_2$ y $\lambda \in [0,1]$. Hay que probar que $\lambda \mathbf{x}+(1-\lambda )\mathbf{y}$ pertenece a la intersección, es decir, a los dos conjuntos.

Como $\mathbf{x},\mathbf{y}\in S_1$ y $S_1$ es convexo, por definición

$$\lambda \mathbf{x}+(1-\lambda )\mathbf{y}\in S_1$$

Como $\mathbf{x},\mathbf{y}\in S_2$ y $S_2$ es convexo, igualmente

$$\lambda \mathbf{x}+(1-\lambda )\mathbf{y}\in S_2$$

Al pertenecer a los dos, pertenece a la intersección. Y como $\mathbf{x}$, $\mathbf{y}$ y $\lambda$ eran arbitrarios, $S_1\cap S_2$ es convexo. $■$

El argumento se extiende sin cambios a cualquier número de conjuntos, incluso infinitos: el punto pertenece a cada uno por separado, luego a todos.

Por qué es el resultado clave. Un problema de programación lineal con $m$ restricciones tiene una región factible

$$S=\bigcap _{i=1}^m\{\mathbf{x}:{\mathbf{a}}_i^{\top }\mathbf{x}\le b_i\}$$

Cada conjunto de la intersección es un semiespacio, que es convexo (se comprueba directamente: si ${\mathbf{a}}^{\top }\mathbf{x}\le b$ y ${\mathbf{a}}^{\top }\mathbf{y}\le b$, entonces ${\mathbf{a}}^{\top }(\lambda \mathbf{x}+(1-\lambda )\mathbf{y})=\lambda {\mathbf{a}}^{\top }\mathbf{x}+(1-\lambda ){\mathbf{a}}^{\top }\mathbf{y}\le \lambda b+(1-\lambda )b=b$).

Por el teorema, $S$ es convexo sea cual sea el número de restricciones y sin comprobar nada más. Esto es lo que permite afirmar, antes de resolver, que el óptimo está en un vértice, y por tanto que el símplex del tema 16 es un método correcto y no una heurística.

Si el resultado fuera falso —si añadir restricciones pudiera crear entrantes— habría que comprobar la convexidad problema a problema, y el símplex podría quedarse atrapado en un óptimo local. La programación lineal, tal como se conoce, no existiría.

7. Qué desbloquea

Necesitas antes:

• Sistemas de ecuaciones lineales y método de Gauss — tema 8

Te abre la puerta a:

• Optimización con restricciones: Lagrange y Kuhn-Tucker — tema 14
• Investigación operativa: formulación de problemas lineales y resolución gráfica — tema 15

8. Recursos externos

• OCW UPV/EHU — Investigación Operativa. Programación Lineal, Tema 0. Es el recurso más ajustado a este tema: álgebra lineal y conjuntos convexos presentados exactamente como preparación del símplex, con la caracterización algebraica de los vértices.
• OCW UC3M — Matemáticas para la Economía I. Espacios vectoriales, independencia lineal, bases y dimensión, con ejercicios de determinación de rango.
• Sydsæter & Hammond, Matemáticas para el análisis económico. Capítulo de conjuntos convexos y programación lineal, con el teorema fundamental enunciado y justificado.
• Gnuplot. Para ver la región factible del ejemplo, dibujar las rectas frontera ayuda a localizar los vértices antes de calcularlos: plot [0:70] 60-x, (100-x)/2.5.