Método Símplex

El método símplex es el algoritmo de programación lineal desarrollado por George B. Dantzig en 1947 y la piedra angular de la investigación operativa. Idea central: la región factible de un LP en forma estándar max c^T x s.a. Ax = b, x ≥ 0 es un politopo convexo, y un objetivo lineal alcanza su óptimo en un vértice; cada vértice corresponde a una solución básica factible (BFS) en la que m variables básicas son positivas y las n-m no básicas son cero. El algoritmo procede: (1) encontrar una BFS inicial (método de la M grande o dos fases); (2) calcular costes reducidos c_j - c_B^T B^(-1) A_j; si son ≥ 0 para toda variable no básica, la BFS actual es óptima; (3) seleccionar una variable entrante con coste reducido negativo (regla de Dantzig: la más negativa), determinar la saliente por la regla del cociente mínimo, pivotar y volver al paso (2). Geométricamente, el método camina de un vértice del politopo a un vértice adyacente. Complejidad: Klee y Minty (1972) demostraron mediante el cubo de Klee-Minty que el peor caso puede requerir 2^n iteraciones (exponencial); sin embargo, el análisis promedio y suavizado (Spielman y Teng 2004) prueba que el símplex es polinómico en promedio, lo que explica su sobresaliente velocidad práctica. Variantes: (a) símplex revisado con factorización de matrices dispersas para problemas grandes; (b) símplex dual (Lemke 1954) avanza por factibilidad dual; (c) símplex de red resuelve transporte y asignación sobre árboles en segundos. El cycling — bucle infinito en un vértice degenerado — se evita con la regla de Bland (1977) o pivoteo lexicográfico. En los solucionadores LP modernos el símplex coexiste con los métodos de punto interior y domina en contextos de warm-start, en particular dentro de branch-and-cut para MILP.