Investigación Operativa

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 su forma 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 <= n

sa            Ax = b

                x >=  0

P)            Max        9u + 2v + 5z

                sa            4u + 3v + 6z <=  50

                                u + 2v - 3z >=  8

                               2u – 4v + z = 5

                               u,v >=  0

                               z e IR

1. Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia:  x* es también mínimo de  -f(x)
2. Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgura no negativa, con coeficiente nulo en la función objetivo.
3. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.
4. Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.

Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como:

Min         - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6

sa:              4x1 + 3x2 + 6x3 - 6x4 +    x5          = 50

                     x1 + 2x2 - 3x3 + 3x4             - x6  =  8

                   2x1 - 4x2 +  x3   -   x4                     =  5

                   xi >=  0,    i=1,2,3,4,5,6.  

Se recomienda al lector revisar la bibliografía referente a los preliminares del Método Simplex o a través de una búsqueda en Google.

Ejemplo

 

Resolver el siguiente problema de PL utilizando el Método Simplex:

Max     40*X1 + 60*X2

s.a.     2*X1 + 1*X2 <= 70

            1*X1 + 1*X2 <= 40

            1*X1 + 3*X2 <= 90

             X1 >= 0  X2 >= 0

    

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 que entra 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 la tercera 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	1	0	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 una variable 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/2	1/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 soluciones".

La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico. Dejaremos para una posterior presentación, la forma de calcular el intervalo de variación para el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.

METODO SIMPLEX DE 2 FASES

Esta estrategia se utiliza cuando no es inmediata una solución básica factible inicial en las variables originales del modelo.

FASE I

Se considera un problema auxiliar que resulta de agregar tantas variables auxiliares a las restricciones del problema, de modo de obtener una solución básica factible. Resolver por Simplex un problema que considera como función objetivo la suma de las variables auxiliares. Si el valor óptimo es cero, seguir a la Fase II, en caso contrario, no existe solución factible.

FASE II

Resolver por Simplex el problema original a partir de la solución básica factible inicial hallada en la Fase I.

EJEMPLO

P)            Max         2X1 + X2

                sa           10X1 + 10X2 <=  9

                               10X1 + 5X2  >=  1

                               X1, X2 >=  0

Se debe agregar X3 como variable de holgura de la restricción 1, X4 como variable de exceso de la restricción 2 y X5 variable auxiliar para poder comenzar la Fase 1.  

F1)            Min        X5 

                 sa           10X1 + 10X2 + X3              =  9

                                10X1 + 5X2         - X4 + X5 =  1

                                X1, X2, X3, X4, X5 >=  0

La tabla inicial asociada a la Fase I queda en consecuencia definida de la siguiente forma:

X1	X2	X3	X4	X5
10	10	1	0	0	9
10	5	0	-1	1	1
0	0	0	0	1	0

X1	X2	X3	X4	X5
10	10	1	0	0	9
10	5	0	-1	1	1
-10	-5	0	1	0	-1

Se escoge X1 como variable que entra a la base al tener el costo reducido más negativo. Posteriormente, mediante el criterio del mínimo cuociente se selecciona la variable que sale de la base: Min {9/10; 1/10} = 1/10, X5 sale de la base.

X1	X2	X3	X4	X5
0	5	1	1	-1	8
1	1/2	0	-1/10	1/10	1/10
0	0	0	0	1	0

X1	X2	X3	X4
0	5	1	1	8
1	1/2	0	-1/10	1/10
-2	-1	0	0	0

Hacemos cero los costos reducidos de las variables básicas:

X1	X2	X3	X4
0	5	1	1	8
1	1/2	0	-1/10	1/10
0	0	0	-1/5	1/5

X4 entra a la base. Por el criterio del mínimo cuociente, el pivote se encuentra en la fila 1, por tanto X3 sale de la base.

X1	X2	X3	X4
0	5	1	1	8
1	1	1/10	0	9/10
0	1	1/5	0	9/5

 

Donde la solución óptima es: X1=9/10    X2=0    Con valor óptimo V(P) = 9/5