Un algoritmo iterativo para resolver problemas de programación lineal moviéndose a lo largo de las aristas del poliedro factible entre soluciones básicas factibles hasta alcanzar un punto extremo óptimo.

Principio

Aprovechar la estructura poliédrica de un programa lineal: los vértices corresponden a soluciones básicas factibles y la optimalidad se alcanza mediante operaciones locales de pivotado que mejoran el objetivo.

Demostración

Resolver un problema de dietas inicializando una solución básica factible, calcular costos reducidos, pivotar hacia vértices adyacentes con costo reducido negativo y detenerse cuando no exista un pivot que mejore.

Aplicación incorrecta

Aplicar el método simplex sin comprobar degeneración o medidas contra ciclos puede provocar bucles infinitos o tablas repetidas cuando varias bases comparten el mismo vértice.

Consecuencia

Cuando se aplica correctamente, el método proporciona una solución óptima en un vértice y ofrece información dual (precios sombra) y certificados de inviabilidad o no acotamiento cuando corresponda.

Inversión

En lugar de recorrer la frontera, los algoritmos de puntos interiores atraviesan el interior factible usando términos barrera; estos métodos cambian pivotes explícitos por progresos sobre la trayectoria central.

Límite

Se aplica solamente a programas lineales (restricciones afines y objetivo lineal); los problemas no lineales, enteros o no convexos requieren modificación u otros algoritmos.

Tensión semántica

Existe tensión entre el 'pivotado combinatorio' (cambios discretos de base) y el 'seguimiento continuo de trayectorias' (métodos interiores) como rutas alternativas hacia el óptimo en optimización convexa.

Síntesis

El método simplex enmarca la programación lineal como una navegación combinatoria de un poliedro convexo: efectuar pivotes algebraicos que corresponden a movimientos geométricos entre vértices hasta que se cumplan las condiciones de optimalidad.