Modelos de programación lineal

Supongamos que elegimos x kilos de un producto A e y kilos de un producto B. Si cada kilo aporta tres y dos euros de beneficio, respectivamente, el objetivo es Z=3x+2y. Maximizar significa buscar el mayor Z entre las decisiones permitidas; minimizar buscaría el menor.

x e y son variables de decisión. Los números tres y dos son datos del modelo, con unidades euros por kilo. Lineal significa contribuciones proporcionales y aditivas: duplicar x duplica su contribución y no hay un término xy ni una potencia x². Un término constante del objetivo cambia el valor final, pero no qué decisiones ganan.

En el ejemplo admitimos a lo sumo cuatro kilos de cada producto y seis kilos entre ambos: x≤4, y≤4, x+y≤6.

Todas las condiciones forman parte del problema.

Cada restricción debe comparar las mismas unidades. Si A necesita dos horas por kilo y B una, una capacidad de ocho horas se escribe 2x+y≤8. Un aporte mínimo se traduce en ≥; un balance exacto, en igualdad. Por ahora las variables son reales y pueden representar cantidades divisibles.

Para elegir el lado probamos un punto que no esté en ella: (0,0) da 0≤6, por tanto ese lado es el permitido.

Factible significa que cumple todas las restricciones simultáneamente. La zona resultante es su intersección, no su unión. Es convexa: mezclar dos decisiones factibles, manteniendo proporciones entre cero y uno, conserva cada desigualdad lineal. Puede quedar una zona, un segmento, un punto o ningún punto.

Calculamos cruces de fronteras, incluidos los ejes de no negatividad.

Los vértices del polígono son (0,0), (4,0), (4,2), (2,4) y (0,4).

No aceptamos todos los cruces automáticamente. Una intersección puede estar fuera de otra restricción. Al listar esquinas, comprobamos todas las condiciones y evitamos duplicados; el dibujo ayuda a localizar, pero las coordenadas se calculan con ecuaciones.

Si es cero, la decisión está en esa frontera: llamamos activa a esa restricción. Si es positiva, queda capacidad sin utilizar.

Una restricción redundante ya se deduce de las demás y no recorta nada adicional. Podemos conservarla en el modelo, pero no crea una nueva esquina. Activa en un punto y redundante en todo el conjunto son ideas distintas.

Para un número q fijo, 3x+2y=q es una recta de nivel. Todos sus puntos tienen objetivo q. Cambiar q desplaza esa recta en paralelo. Maximizar la mueve hacia niveles mayores mientras todavía toque la región factible.

El vector de coeficientes (3,2) señala una dirección de aumento: un desplazamiento de ese tipo aumenta el objetivo. Pero no garantiza que podamos avanzar en ella sin salir de la zona. Si ambos coeficientes fueran cero, el objetivo sería constante y cualquier punto factible empataría.

Un objetivo lineal alcanza máximo y mínimo en un polígono factible no vacío, cerrado y acotado. Al menos un vértice alcanza cada extremo. La razón es que cualquier punto del polígono es una mezcla de sus vértices, y el objetivo de la mezcla es la misma mezcla de sus valores: no supera al mayor ni baja del menor.

Calculamos el objetivo en todos los vértices y comparamos. Puede haber una sola esquina óptima o una arista completa de empate. Si dos extremos de una arista comparten el mejor valor, cualquier mezcla entre ambos conserva ese valor.

Si las restricciones se contradicen, no hay región factible ni óptimo. Si la región es no acotada, el objetivo puede seguir teniendo un mínimo o un máximo: depende de cómo cambie al avanzar por sus direcciones permitidas.

Con desigualdades estrictas puede existir una cota a la que nos acercamos sin alcanzarla. El método elemental de evaluar vértices necesita estas comprobaciones; no basta buscar el punto que parece más alto en una ventana finita.

Una prueba de optimalidad tiene dos partes: ninguna decisión puede superar cierta cota y alguna decisión factible la alcanza. La gráfica orienta, pero esta combinación demuestra el resultado sin depender de su precisión.

El método gráfico desarrolla aquí dos variables reales. En más dimensiones se usan otros algoritmos, como símplex o punto interior. Si las decisiones deben ser enteras, añadimos esa condición: redondear una solución continua puede incumplir restricciones o perder el mejor resultado entero.