Programación lineal: elegir sin saltarse los límites

La pregunta suele pedir «cuánto fabricar para obtener el mayor beneficio» o «qué comprar para gastar lo mínimo». Llama $x$ e $y$ a las dos cantidades que puedes elegir e indica sus unidades. Si son litros, cada coordenada representa litros; si son paquetes completos, representa un número entero de paquetes.

Supón que cada paquete pequeño necesita 2 kg de arroz y cada grande 3 kg. Para $x$ pequeños se gastan $2x$ kg; para $y$ grandes, $3y$ kg. Como ambos usan el mismo almacén, el consumo total es $2x+3y$. Si hay 12 kg, la restricción es $2x+3y\le12$: se permite gastar menos, pero no más.

«Al menos» da una cota inferior, como $x+y\ge3$; «como máximo» da una superior, como $x\le4$. Si $x$ e $y$ cuentan productos, no pueden ser negativas: incluye $x\ge0$ e $y\ge0$. Si el enunciado da directamente un recinto del plano, conserva sus restricciones: las coordenadas pueden ser negativas y no se añaden cotas que no estén impuestas. Una igualdad se usa solo cuando el dato exige una cantidad exacta.

La función objetivo mide lo que quieres mejorar. Si una unidad del primer producto deja 3 € y una del segundo 2 €, el beneficio es $F(x,y)=3x+2y$. Los factores 3 y 2 son euros por unidad; al multiplicar por las cantidades obtienes euros. Esta función compara combinaciones y no es otra limitación de materiales.

La igualdad $x+y=8$ dibuja una recta. Sus puntos gastan exactamente 8 unidades de un recurso. La desigualdad $x+y\le8$ incluye también las combinaciones que gastan menos: ocupa un lado entero de la recta. Ese lado se llama semiplano.

Para dibujar la frontera, calcula dos puntos. Pon $x=0$: $0+y=8$ da $(0,8)$. Pon $y=0$: $x+0=8$ da $(8,0)$. Une esos puntos y prolonga la recta; todavía falta decidir qué lado conservar.

Elige un punto que no esté en la recta. El origen $(0,0)$ suele ser cómodo: $0+0\le8$ es cierto. Por eso conserva el lado que contiene el origen. Si la desigualdad fuera $x+y\ge8$, esa comprobación sería falsa y conservarías el otro lado. Si la frontera pasa por el origen, escoge otro punto.

Los signos $\le$ y $\ge$ incluyen la frontera. Los signos $<$ y $>$ la excluyen. En los problemas habituales de recursos se admite usar exactamente lo disponible, por lo que el borde está incluido.

Una combinación puede respetar un recurso y superar otro. La región factible reúne los puntos que cumplen todas las restricciones a la vez. Se obtiene superponiendo los semiplanos y conservando solo su zona común.

Considera $x\ge0$, $y\ge0$, $x\le4$, $y\le6$ y $x+y\le8$. Las primeras dos condiciones te llevan al primer cuadrante; las dos siguientes forman un rectángulo de anchura 4 y altura 6. La última corta la esquina donde ambas cantidades serían demasiado grandes.

Mira el dibujo del ejemplo: la zona sombreada contiene las combinaciones permitidas. Estar dentro de uno de los semiplanos no basta. Por ejemplo, $(4,6)$ respeta las dos cotas individuales, pero suma 10 y no cumple $x+y\le8$.

Puede quedar una región acotada, una región que continúe sin límite o ninguna región. Si las restricciones se contradicen, no existe ninguna combinación factible y no se puede optimizar un objetivo sobre ella.

Un vértice es una esquina de la región factible. Allí se cruzan dos fronteras activas: dos condiciones que se cumplen como igualdad en ese punto. El dibujo localiza qué rectas se cortan; un sistema de ecuaciones da las coordenadas exactas.

En el ejemplo, la frontera vertical $x=4$ se cruza con $x+y=8$. Sustituye $x=4$ en la segunda igualdad: $4+y=8$. Resta 4 en ambos miembros: $y=4$. El cruce es $(4,4)$.

La frontera $y=6$ se cruza con $x+y=8$: $x+6=8$ y $x=2$. El cruce es $(2,6)$. En este ejemplo se exige no negatividad, así que los ejes $x=0$ e $y=0$ también son fronteras y pueden aportar vértices. En un recinto general, un eje solo es frontera si una restricción lo impone.

No todo cruce de las rectas es una esquina válida. El cruce de $x=4$ con $y=6$ es $(4,6)$, pero no cumple $x+y\le8$. Comprueba cada candidato en todas las restricciones antes de incluirlo en la lista.

La función objetivo asigna un beneficio o coste a cada combinación. En una región poligonal cerrada, no vacía y acotada, una función lineal alcanza máximo y mínimo en al menos un vértice. Por eso puedes resolver el problema comparando esos puntos.

Para $F(x,y)=3x+2y$, el punto $(4,4)$ da $F(4,4)=3\cdot4+2\cdot4=20$. Al sustituir $x$ por 4 e $y$ por 4 se mantienen los factores 3 y 2: son los beneficios por unidad.

Haz una tabla con todos los vértices y sus valores. Para un máximo conserva el mayor; para un mínimo, el menor. Después escribe las cantidades y el valor del objetivo con sus unidades: el beneficio por sí solo no responde cuántas unidades producir.

Si el contexto exige unidades completas y algún vértice tiene coordenadas no enteras, el óptimo continuo no basta. No redondees las coordenadas sin comprobar las restricciones: hay que comparar las combinaciones enteras factibles del problema.

Un máximo puede alcanzarse en una sola esquina o en varios puntos. Si dos vértices de un mismo lado comparten el valor máximo, cualquier punto del segmento entre ellos conserva ese valor: el lado entero es óptimo.

Por ejemplo, si $F=x+y$ y hay una restricción $x+y\le6$, ningún beneficio supera 6. Si el segmento factible va de $(2,4)$ a $(4,2)$ sobre la recta $x+y=6$, todos sus puntos tienen $F=6$. Puedes escribirlos como $(t,6-t)$ con $2\le t\le4$.

Una región que continúa sin límite no implica que todos los objetivos carezcan de óptimo. Debes revisar cómo cambia el objetivo en las direcciones permitidas. Con $x\ge0$, $0\le y\le2$ y $F=x+y$, los puntos $(t,2)$ son factibles para cualquier $t\ge0$ y dan $F=t+2$. Ese beneficio sí aumenta sin límite: no existe máximo finito.

En cambio, minimizar $C=2x+3y$ con $x\ge1$, $y\ge1$, $x+y\ge3$ sí tiene solución. Los vértices $(2,1)$ y $(1,2)$ cuestan 7 y 8. Los rayos permitidos aumentan cantidades con costes positivos, por lo que no reducen 7. La región no está acotada, pero el mínimo es 7.