Programación Lineal (2D)

La programación lineal optimiza una función objetivo lineal sujeta a restricciones lineales de igualdad y desigualdad. La región factible forma un poliedro convexo. El teorema fundamental establece que la solución óptima debe ocurrir en uno de los vértices, resuelto eficientemente por el método Simplex.

En términos sencillos, estás haciendo malabares con recursos limitados bajo varias reglas a la vez, y cada desigualdad recorta una parte del plano. Donde todas las reglas se solapan está la región factible, y cada punto dentro de ella es un plan válido. Como una función objetivo lineal siempre mejora en una dirección, la mejor solución cae en un vértice donde se cruzan las restricciones. La conclusión: para optimizar nunca pruebas todos los puntos, solo el puñado de vértices.

En 1945 el economista George Stigler estudió la dieta más barata que cubría todas las necesidades nutricionales, un problema lineal con 77 alimentos. Sin un algoritmo, hizo una estimación astuta y obtuvo unos $39.93 al año (precios de 1939). Cuando el método símplex de Dantzig lo resolvió con exactitud en 1947, el mínimo real fue $39.69: la estimación a mano de Stigler solo se desvió unos 24 centavos al año. Así, la economía árida se volvió uno de los casos fundacionales de la programación lineal.