Método Simplex

Introducción a la programación lineal

La programación lineal se aplica a modelos de optimización en los que las funciones objetivo y
restricción son estrictamente lineales. La técnica se aplica en una amplia variedad de casos, en
los campos de agricultura, industria, transporte, economía, salud, ciencias sociales y de la conducta,
y militar. También produce algoritmos eficientes de cómputo para problemas con miles
de restricciones y variables. En realidad, debido a su tremenda eficiencia de cálculo, la programación
lineal forma la columna vertebral de los algoritmos de solución para otros modelos de
investigación de operaciones, como las programaciones entera, estocástica y no lineal.
Este capítulo comienza con el caso de un modelo de dos variables, y presenta su solución
gráfica. Esta solución gráfica permite tener una perspectiva del desarrollo del método
símplex, técnica algebraica general (véase el capítulo 3). También presenta ideas concretas
para el desarrollo y la interpretación de análisis de sensibilidad en programación lineal. El capítulo
termina con la formulación y la interpretación de la solución de varias aplicaciones realistas.

El método símplex
 
El método gráfico indica que la solución óptima de un programa lineal siempre
está asociada con un punto esquina del espacio de soluciones. Este resultado es la clave del
método símplex algebraico y general para resolver cualquier modelo de programación lineal.
La transición de la solución del punto esquina geométrico hasta el método símplex implica
un procedimiento de cómputo que determina en forma algebraica los puntos esquina. Esto
se logra convirtiendo primero a todas las restricciones de desigualdad en ecuaciones, para
después manipular esas ecuaciones en una forma sistemática.
Una propiedad general del método símplex es que resuelve la programación lineal en
iteraciones. Cada iteración desplaza la solución a un nuevo punto esquina que tiene potencial
de mejorar el valor de la función objetivo. El proceso termina cuando ya no se pueden obtener
mejoras.
El método símplex implica cálculos tediosos y voluminosos, lo que hace que la computadora
sea una herramienta esencial para resolver los problemas de programación lineal. Por
consiguiente, las reglas computacionales del método símplex se adaptan para facilitar el cálculo
automático.