La geometría de la programación lineal

Introducción

Las tareas de programación lineal son aquellas que se pueden modelar como un problema en el que existen varias restricciones lineales y un objetivo que alcanzar: puede ser minimizar o maximizar el valor de algo (una función) que generalmente depende de las variables que existen en esas restricciones.

Dicho de otra manera, son tareas en las que hay un objetivo que cumplir (maximizar o minimizar algo), y existen restricciones sobre cómo conseguirlo.

En este artículo introductorio a la programación lineal haremos un recorrido desde cero, introduciendo conceptos hasta poder responder a preguntas como: ¿qué forma tiene la región factible?

Empezaremos con un problema sencillo para entender cómo funciona la programación lineal.

También veremos por qué la solución óptima siempre cae en un vértice de esa región, y qué ocurre cuando el problema no tiene una única solución.

Problema de ejemplo

Enunciado

En este problema, se tienen dos modelos de ordenador a la venta, cada uno de ellos con un precio de venta y varios tipos de costes para fabricarlos (montaje, placas y memoria):

La empresa que los fabrica y comercializa quiere sacar el mayor beneficio, pero tiene varias restricciones:

• Disponen de 16 h de montaje.
• Tienen 10 placas base en stock.
• Tienen 16 módulos de memoria.

Modelado

Para modelar el problema como una tarea de programación lineal, haremos lo siguiente:

Variables

• $A$ : Nº de ordenadores del modelo A que se fabricarán
• $B$ : Nº de ordenadores del modelo B que se fabricarán

Restricciones

Cada recurso limitado se traduce en una desigualdad:

Juntando todo, la región factible es el conjunto de puntos $(A, B)$ que cumplen:

Función objetivo

Lo que se quiere maximizar es el beneficio (repito, maximizar).

Para ello, queremos encontrar la combinación de ordenadores de los modelos A y B que fabricar que, cumpliendo las restricciones, nos generen el máximo beneficio.

Como cada ordenador A se vende por 1000€ y cada ordenador B por 750€, la función objetivo sería:

La región factible

Para encontrar la solución, vamos a representar todas las posibles combinaciones de ordenadores A y B en un plano, así como las restricciones que limitan el problema.

Para que se entienda mejor, puedes utilizar el gráfico interactivo de debajo para comprender el "proceso de formación" de la región factible. Se controla con los botones de "Siguiente" y "Anterior".

Cada restricción, como se puede apreciar, es representada por una recta en el plano, que lo divide en dos mitades: la que cumple la restricción y la que no.

La región factible es, por tanto, la figura que aparece resaltada.

La solución para este problema se halla en uno de los vértices de esta figura (y más tarde explicaremos por qué).

Siempre es convexa

Existe un teorema que afirma que:

La región factible de un problema definido mediante un número finito de restricciones lineales es un conjunto convexo. Más concretamente, es un poliedro (posiblemente no acotado).

Convexo significa que todos sus ángulos interiores son menores de 180º, es decir, que no tiene "hendiduras". Otra forma equivalente de verlo: el segmento que une dos puntos cualesquiera de la figura no se sale de ella. En cuanto hay una hendidura, deja de cumplirse.

¿Por qué no puede ser cóncavo?

Para explicarlo hay que fijarse en qué construye sus aristas: las restricciones. Y ya hemos determinado que, al ser lineales, la forma de una restricción en el plano es una recta (y en 3D, un plano). Eso completa la idea de poliedro.

Pero, ¿por qué no puede ser cóncavo? Por un motivo sencillo: para que lo fuera, alguna de sus aristas tendría que ser un segmento (una recta con principio y fin), de modo que la frontera pudiera girar hacia dentro. Y una restricción lineal no es un segmento: es una recta infinita, no tiene dónde detenerse.

Se ve mejor prolongando cada arista hasta su recta completa.

Prueba a interactuar con ambas figuras y comprueba por ti mismo por qué es imposible que sea cóncavo.

En la figura convexa, la recta de cualquier arista deja toda la figura a un lado: podría ser una restricción. En la cóncava, las aristas de la hendidura, al prolongarlas, cortan la figura, y ninguna recta infinita puede a la vez cortar la región y ser su borde.

En más dimensiones

Retomando la solución anterior, es importante resaltar que el gráfico anterior ha sido posible crearlo porque hay dos únicas variables (y por tanto, dos dimensiones).

¿Qué pasaría entonces si aparecen más variables?

Si introdujésemos un tercer modelo C, modelar el problema sería tan sencillo como añadir la nueva variable C a las restricciones, pero su interpretación cambia totalmente, ya que en ese caso, el problema solamente sería representable en un espacio tridimensional (3D).

Añadamos C a las restricciones actuales (inventando coeficientes por simplificar):

• $2A + B + 2C \leq 16$, $A + B + C \leq 10$,
• $A + 2B + 3C \leq 16$

ahora cada una de ellas pasa de ser una recta a ser un plano, y la región factible deja de ser un polígono para ser un poliedro.

Gíralo: todas sus caras son planas y no tiene "hendiduras": sigue siendo convexo.

Como nuestro mundo es tridimensional, no podemos hacer un gráfico de regiones factibles de 4 o más dimensiones (o al menos, no sin reducir la dimensionalidad de alguna manera).

Entonces, una pregunta que surge es: ¿Qué forma tiene la región factible en dimensiones superiores?

La respuesta ya la tenemos: la misma. El argumento de las hendiduras no depende de la dimensión. Cada restricción sigue siendo un hiperplano y la región sigue siendo la intersección de sus lados. En cualquier número de dimensiones es un poliedro convexo; lo único que perdemos al subir es la posibilidad de dibujarlo.

Y como sabemos que siempre es convexo, ya podemos responder a la otra pregunta pendiente: por qué la solución óptima está siempre en un vértice.

Dónde está el óptimo

Hasta ahora hemos afirmado que la solución está en un vértice, pero no por qué. La forma más clara de verlo es con las rectas de isobeneficio.

Estas rectas nos indican (aunque indirectamente) hacia dónde crece o decrece la función objetivo. Para entenderlo, primero recordemos nuestra función objetivo:

Esto no es una recta aún, sino una expresión. Para convertirlo en recta, le podemos dar cualquier valor a $f$. Por ejemplo, si le damos el valor 1, nos quedaría: $1 = 1000 A + 750 B$, lo cual ya es una recta.

Generalizando esta idea, podemos darle cualquier valor (llamémosle $k$) a esta función, y así mover la recta.

Matemáticamente, las rectas que salen al cambiar $k$ son todas paralelas (misma dirección). Al aumentar o disminuir $k$, podemos mover la recta a nuestro antojo.

Recordemos que $k$ es un beneficio, entonces, cuanto mayor es $k$, más lejos está su recta en la dirección de más beneficio (la flecha $f \uparrow$ del gráfico).

Si queremos maximizar $k$ y así resolver nuestro problema, lo que queremos es, en realidad, empujar la recta lo más lejos posible sin dejar de tocar la reción factible. El último punto en el que la recta toca esa región factible es la solución.

Tras explorar este gráfico, ya hemos descubierto la solución de una manera muy visual:

Ahora bien, ¿por qué ese último punto es un vértice y no otra cosa? ¿Habrá sido casualidad?

¿Siempre un vértice?

• No puede estar en el interior. Desde cualquier punto interior siempre puedes moverte un poco en la dirección de la flecha y seguir dentro de la región, ganando más beneficio. Si puedes mejorar, no era el óptimo.
• No puede estar en mitad de una arista (salvo un caso especial que vemos abajo): apoyada la recta contra un borde, todavía puedes deslizarte a lo largo de ese borde hacia beneficios mayores, hasta llegar a su esquina.
• Lo único que queda son las esquinas: los vértices del polígono.

Es un resultado general: el máximo de una función lineal sobre un conjunto convexo y acotado se alcanza siempre en un punto extremo (un vértice). Por eso los métodos clásicos de programación lineal, como el símplex, solo necesitan recorrer vértices.

Tipos de solución

Según cómo la recta de isobeneficio acabe tocando (o no) la región factible, aparecen cuatro escenarios.

Solución única

El caso normal, y el que hemos visto: la recta de isobeneficio roza la región en un solo vértice. Hay una combinación de $A$ y $B$ mejor que todas las demás.

Infinitas soluciones

Si la recta de isobeneficio es paralela a una de las restricciones activas, al empujarla su último contacto con la región no es un punto, sino toda una arista. Cualquier combinación sobre esa arista da el mismo beneficio máximo: el problema tiene infinitas soluciones óptimas (aunque, como el máximo también se alcanza en los dos extremos de la arista, siempre hay al menos una solución que es un vértice).

Pasa, por ejemplo, si el beneficio fuese proporcional al número total de ordenadores, $f = A + B$: esa recta es paralela a la restricción de placas, $A + B \leq 10$.

Problema no acotado

Si la región factible está abierta en la dirección de más beneficio —no hay ninguna restricción que la cierre por ese lado— siempre existe un $k$ mayor: no hay óptimo finito. En un problema real esto casi siempre significa que falta modelar alguna restricción.

Problema infactible

Si las restricciones se contradicen, no existe ninguna combinación que las cumpla todas a la vez: la región factible es vacía y el problema no tiene solución.

En resumen

Hemos ido de un problema de fabricación de ordenadores a la geometría que hay detrás de cualquier tarea de programación lineal:

• La región factible es la intersección de los semiespacios que define cada restricción. Como cada restricción es un hiperplano (no un segmento), la región nunca tiene hendiduras: es siempre un poliedro convexo, en dos, tres o más dimensiones.
• El óptimo se encuentra empujando la recta (o el plano) de isobeneficio lo más lejos posible dentro de esa región. Al ser el objetivo lineal y la región convexa, el último punto de contacto es siempre un vértice. Por eso el método del símplex (que no hemos cubierto aquí pero es un algoritmo común) solo necesita recorrer esquinas.
• Y según cómo toque esa recta, el problema tiene una solución, infinitas (isobeneficio paralela a una restricción activa), ninguna finita (región abierta hacia el objetivo) o ninguna en absoluto (restricciones incompatibles).