Otros algoritmos para programación lineal

La razón por que la programación lineal se usa tan ampliamente es la disponibilidad de un algoritmo excepcionalmente eficiente, el método símplex, que en forma rutinaria resuelve problemas grandes que surgen con frecuencia en la práctica. Sin embargo, el método símplex es sólo una parte del arsenal de algoritmos que se usan con regularidad en la aplicación de la programación lineal. El capítulo 7 describió varias clases especiales de programación lineal para las que existen versiones simplificadas del método símplex (como se pudo observar en el método símplex de transporte en la sección 7.2). En la sección 4.8 se mencionó que los paquetes de computadora adaptan el método símplex a una forma matricial más conveniente. En las secciones 4.7  6.6 se hizo notar la utilidad de ciertas modificaciones o extensiones del método  símplex, en particular para el análisis de sensibilidad. Así, todos estos algoritmos son variantes del método símplex que se presentó en el capítulo 4. En consecuencia, también son excepcionalmente eficientes.

Este capitulo esta dedicado a tres algoritmos de gran importancia, basados en el método símplex. Las tres secciones siguientes presentan la técnica de ramificación y acotamiento (versión simplificada del método símplex para manejar variables que tienen una cota superior), el método dual símplex (modificación muy útil para el análisis de sensibilidad) y programación paramétrica (extensión para el análisis de sensiblidad sistemático).

En la sección 4.9 se introdujo un nuevo desarrollo en programación lineal que causa gran  emoción, un nuevo y poderoso tipo de algoritmo que se mueve por el interior de la región factible. En la sección 9.4 se describirá con detalle este enfoque de punto interior.