Programación Lineal

La programación lineal optimiza un objetivo lineal sujeto a restricciones lineales de igualdad y desigualdad, siendo la clase de problemas de optimización más ampliamente aplicada.

Definition

Un programa lineal minimiza o maximiza una función lineal de variables de decisión sujeta a restricciones lineales; su región factible es un poliedro convexo, y un óptimo, si existe, se alcanza en un vértice.

Scope

Este tema cubre la forma estándar de un programa lineal, la geometría de los poliedros factibles y sus vértices, el método simplex, la dualidad de la programación lineal y la holgura complementaria, el análisis de sensibilidad y los métodos de punto interior para problemas a gran escala.

Core questions

• ¿Cómo se formula un problema práctico de recursos como un programa lineal?
• ¿Por qué ocurre un óptimo en un vértice del poliedro factible?
• ¿Qué nos dice el programa lineal dual sobre el primal?
• ¿Qué algoritmos resuelven eficientemente grandes programas lineales?

Key theories

Teorema fundamental de la programación lineal

Si un programa lineal tiene una solución óptima, entonces se alcanza un óptimo en un vértice del poliedro factible, reduciendo la búsqueda a un número finito de puntos candidatos.

Dualidad y holgura complementaria

Cada programa lineal tiene un dual cuyo valor óptimo es igual al del primal, y la holgura complementaria vincula las restricciones activas con las variables duales no nulas, proporcionando certificados de optimalidad e interpretaciones económicas.

Métodos simplex y de punto interior

El método simplex se mueve entre vértices para mejorar el objetivo, mientras que los métodos de punto interior atraviesan el interior y resuelven programas lineales en tiempo polinomial demostrable.

Clinical relevance

La programación lineal es una piedra angular de la investigación operativa, utilizada para la planificación de la producción, el transporte y la logística, la programación, los problemas de dieta y mezcla, y los flujos de red, y sirve como subrutina dentro de la optimización entera y no lineal.

History

Kantorovich introdujo la optimización lineal para la planificación de la producción en 1939, y Dantzig formuló el problema general y el método simplex en 1947. Von Neumann reconoció la dualidad con la teoría de juegos, y el método del elipsoide de Khachiyan y el método de punto interior de Karmarkar establecieron más tarde la solubilidad en tiempo polinomial.

Key figures

• George Dantzig
• Leonid Kantorovich
• John von Neumann
• Narendra Karmarkar

Seminal works

• dantzig1963
• luenberger2008

Frequently asked questions

¿Por qué el óptimo se encuentra en un vértice?

Un objetivo lineal aumenta más rápidamente en una dirección fija, por lo que sobre un poliedro convexo su mejor valor se empuja hacia el límite y, en última instancia, hacia una esquina. A menos que el objetivo sea constante a lo largo de una arista o cara, el óptimo se alcanza en un vértice.

¿Es el método simplex siempre rápido?

En la práctica, el método simplex es muy eficiente, pero los ejemplos de peor caso pueden hacer que tome un número exponencial de pasos. Los métodos de punto interior proporcionan una garantía de tiempo polinomial, y los solucionadores modernos utilizan ambos dependiendo del problema.