Capitulo 4 Metodo Simplex

4

C A P Í T U L O

Solución de problemas
de programación lineal: método símplex

E

s el momento de comenzar a estudiar el método símplex, un procedimiento general para resolver problemas de programación lineal. Desarrollado por George Dantzig1 en 1947,
se ha comprobado su extraordinaria eficiencia, y se usa en forma rutinaria para resolver problemas grandes en las computadoras de hoy en día.Excepto en el caso de problemas muy pequeños, se ejecuta siempre en una computadora y existe una amplia variedad de paquetes
complejos de software para ello. También se usan extensiones y variaciones del método símplex
para realizar análisis posóptimo (que incluye el análisis de sensibilidad) del modelo.
En este capítulo se describen y ejemplifican las características principales del métodosímplex.
En la primera sección se presenta su naturaleza general junto con su representación geométrica. En las tres secciones subsecuentes se desarrolla el procedimiento para resolver cualquier modelo de programación lineal que se establezca en nuestra forma estándar (maximización, todas las
restricciones funcionales de la forma # y restricciones de no negatividad sobre todas las variables)
y que sólotenga cantidades no negativas en el lado derecho bi de las restricciones funcionales. En
la sección 4.5 se presentan ciertos detalles sobre cómo romper empates, y en la sección 4.6 se describe la adaptación del método símplex a otras formas de modelos. Después se presenta el análisis
posóptimo (sección 4.7) y se describe el manejo de este método en computadora (sección 4.8). En
la sección 4.9 seintroduce una alternativa al método símplex (el enfoque de punto interior) para
resolver problemas de programación lineal grandes.

■ 4.1 ESENCIA DEL MÉTODO SÍMPLEX
El método símplex es un procedimiento algebraico. Sin embargo, sus conceptos fundamentales
son geométricos. La comprensión de estos conceptos geométricos proporciona una fuerte intuición
sobre la forma en que opera el método símplex y lasrazones de su elevada eficiencia. Por lo tanto,
antes de profundizar en los detalles algebraicos, se dedicará esta sección a enfocar el método desde
un punto de vista geométrico.
Para ilustrar los conceptos geométricos generales se usará el ejemplo de la Wyndor Glass Co.
de la sección 3.1. (En las secciones 4.2 y 4.3 se usa el álgebra del método símplex para resolver
este mismo ejemplo.) En lasección 5.1 se profundiza en estos conceptos para resolver problemas
grandes.

1
Ampiamente reconocido como el pionero más importante de la investigación de operaciones, a George Dantzig se le
conoce comúnmente como el padre de la programación lineal debido al desarrollo del método símplex y a una serie de
contribuciones clave subsecuentes. Los autores tuvieron el privilegio de ser sus colegas en elDepartamento de Investigación de Operaciones de la Universidad de Stanford por casi 30 años. El doctor Dantzig permaneció profesionalmente
activo hasta su fallecimiento en 2005 a la edad de 90 años.

82

CAPÍTULO 4

SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL

x2

Maximizar Z 5 3x1 1 5x2,
sujeta a
x1
# 4
2x2 # 12
3x1 1 2x2 # 18
y
x1 $ 0, x2 $ 0

x1 5 0
(0, 9)
3x1 1 2x2 5 18

(0, 6)

(2, 6)

(4,6)

2x2 5 12

x1 5 4

Región
factible
FIGURA 4.1
Restricciones de frontera y
soluciones en los vértices
del problema de la Wyndor
Glass Co.

(4, 3)

x2 5 0

(0, 0)
(4, 0)

(6, 0)

x1

Para refrescar la memoria, el modelo y la gráfica de este ejemplo se repiten en la figura 4.1.
Se marcaron las cinco fronteras de restricción y sus puntos de intersección puesto que son puntos
clave para el análisis.Aquí, cada frontera de restricción es una recta que marca el límite de lo
que permite la restricción correspondiente. Los puntos de intersección son las soluciones en los
vértices del problema. Los cinco puntos que se encuentran en los vértices de la región factible
—(0, 0), (0, 6), (2, 6), (4, 3) y (4, 0)— son las soluciones factibles en los vértices (soluciones FEV).
[Los otros tres —(0, 9),...