Industria De Fibras

Método Simplex



Referencia: Publicación del Método por George Dantzig en 1947. Primera implementación computacional del Método Simplex el año 1952 en un problema de 71 variables y 48 ecuaciones, tarda 18 horas. En 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.
Consideremos un modelo de Programación Lineal en suforma estandar, que denotaremos en lo que sigue por:
Min c1x1 + c2x2 + ... + cnxn
sa a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
... ... ...
am1x1 + am2x2 + ... + amnxn = bm
xi >= 0, i = 1, 2, ..., n y m = 0
No existe pérdida de generalidad enasumir que un modelo de PL viene dado en su forma estándar.

EJEMPLO

P) Max 9u + 2v + 5z
sa 4u + 3v + 6z = 8
2u – 4v + z = 5
u,v >= 0
z e IR
Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo amaximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) = 0, i=1,2,3,4,5,6.
Ejemplo



Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex:

Max 40*X1 + 60*X2
s.a. 2*X1 + 1*X2 = 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de lasiguiente forma:

X1 X2 X3 X4 X5
2 1 1 0 0 70
1 1 0 1 0 40
1
..... 3
0 0 1 90
-40 -60 0 0 0 0

En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable queentra a la base aquella con el costo reducido "más negativo". En este caso, X2.

Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a latercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cuociente lo llamaremos "Pivote" (marcado con azul) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración.

X1 X2 X3 X4 X5
5/3 0 1
0 -1/3
40
2/3 0 0
1 -1/3 10
1/3 10 0 1/3 30
-20 0 0 0 20 1.800

El valor de la función objetivo luego de una iteración ha pasado de 0 a 1.800. Se recomienda al lector hacer una representación gráfica del problema y notar como las soluciones factibles del método corresponden a vértices del dominio de puntos factibles.

La actual tabla no corresponde a la solución óptima del problema P) debido a que existe unavariable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método:

X1 X2 X3 X4 X5
0 0 1 -5/21/2 15
1 0
0 3/2 -1/2 15
0 1
0 -1/2 1/2 25
0 0
0 30 10 2.100

Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). Notése que la existencia de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con "infinitas...