G.1 Conjuntos convexos, puntos extremos e hiperplanos de separación

El polígono de E.1, visto como un conjunto convexo

La región factible del problema de exportación (E.1), definida por x₁+x₂≤500, x₁≤300, x₂≤450, x₁,x₂≥0, es un polígono con cinco vértices: (0,0), (300,0), (300,200), (50,450) y (0,450). La solución óptima (300,200) resultó ser exactamente uno de esos vértices, nunca un punto interior del polígono. Esto no fue casualidad: es una propiedad general de los conjuntos convexos.

Conjuntos convexos y puntos extremos

Un conjunto C es convexo si, para cualesquiera dos puntos u y v que pertenecen a C, todo el segmento que los une también pertenece a C (formalmente, λu + (1−λ)v ∈ C para todo λ entre 0 y 1). La región factible de cualquier problema de programación lineal (definida por restricciones lineales de la forma ≤, ≥ o =) es siempre un conjunto convexo: es la intersección de semiplanos, y la intersección de conjuntos convexos es, a su vez, convexa.

Un punto extremo (o vértice) de un conjunto convexo es un punto que no puede escribirse como una combinación convexa (λu + (1−λ)v, con λ estrictamente entre 0 y 1) de otros dos puntos distintos del conjunto. En el polígono de E.1, los cinco vértices son sus puntos extremos; cualquier otro punto de la región (por ejemplo, el punto medio de un lado, o cualquier punto interior) sí puede escribirse como combinación convexa de otros puntos del polígono.

Hiperplanos de separación: por qué el óptimo cae en un vértice

Un hiperplano en el plano es simplemente una recta; en R³ es un plano; en general, un subespacio de una dimensión menos que el espacio ambiente. Un hiperplano separa dos conjuntos si cada uno queda a un lado distinto. Un hiperplano soportante (o de apoyo) de un conjunto convexo es uno que toca al conjunto en al menos un punto, dejando todo el resto del conjunto de un mismo lado, sin cruzarlo.

En E.1 y E.2, cada valor posible de Z = 2216x₁ + 448x₂ define una recta (una "línea de isoingreso"): todos los puntos (x₁,x₂) donde el ingreso vale exactamente ese número. A medida que Z crece, esa recta se desplaza en la dirección del gradiente, alejándose del origen. La recta correspondiente al valor óptimo Z*=754.400 es, precisamente, un hiperplano soportante de la región factible: toca al polígono en un único punto, el vértice (300,200), y deja todo el resto del polígono de un mismo lado (con Z menor). Es la razón geométrica, no solo algebraica, de por qué la solución óptima de un problema de programación lineal siempre se encuentra en un punto extremo: la última recta de isoingreso que todavía toca la región convexa solo puede tocarla en un vértice (o, en casos especiales, a lo largo de todo un lado).

Preguntas para pensar

• El segmento de reparto presupuestario (arriba) tiene solo dos puntos extremos. El polígono de E.1 tiene cinco. ¿Qué determina cuántos puntos extremos tiene un conjunto convexo definido por restricciones lineales?
• Si dos rectas de isoingreso distintas tocaran la región factible a lo largo de todo un lado del polígono (no solo en un vértice), ¿qué significaría eso sobre la solución óptima del problema?
• Repasa toda la Sección E y G juntas: ¿cómo se conecta la idea de 'vértice de una región factible' (E.1), 'variable básica del símplex' (E.2) y 'punto extremo de un conjunto convexo' (G.1)? ¿Son tres nombres para la misma idea, o hay diferencias importantes?