INVESTIGACION DE OPERACIONES:

EL METODO SIMPLEX
PROFESOR: ING. JUAN C. UBILLUS CALMET
Ing. Juan C. Ubillus C.

EL METODO SIMPLEX

La mayora de los problemas reales en P.L tienen ms de tres variables, donde el mtodo grfico est limitado. El mtodo Simplex es un procedimiento que permite encontrar la solucin ptima en problemas multivariables. Es un algoritmo para examinar los puntos extremos hasta encontrar la solucin ptima. Si bien existen diferentes algoritmos en la actualidad, (entre ellos el de Karmarkar), stos se han basado en los conceptos bsicos del Simplex.

Los Algoritmos del Simplex

Si bien existen diferentes algoritmos en la actualidad, (entre ellos el de Karmarkar), stos se han basado en los conceptos bsicos del Simplex. Entender el algoritmo del Mtodo Simplex, permitir un mayor criterio en la solucin de los problemas aplicativos y del uso del software.

Conversin de restricciones a ecuaciones

El primer paso del Mtodo Simplex requiere convertir las restricciones en igualdades. As para convertir una restriccin del tipo <= ; se suma una variable de holgura s1 7x1+13x2+5x3 <= 500 7x1+13x2+5x3 + s1 = 500 Para convertir una restriccin del tipo = ;se suma una variable artificial A1 2x1 + 1x2 = 100 2x1 + 1x2 + A1 = 100

Variables de holgura y variables artificiales

Para convertir una restriccin del tipo >= ; se suma una variable artificial A1 y se resta una variable de holgura s1 7x1+13x2+5x3 >= 800 7x1+13x2+5x3 + A1 - s1 = 800 La variable de holgura representan recursos no utilizados (tiempos de una mquina, horas hombre); no generan utilidad pero deben sumarse a la f.o. Con coeficiente = 0. La variable artificial tiene asignado un alto costo para asegurar que no sea seleccionada en la solucin final. No tiene un significado fsico, pero permite una solucin inicial. Se le asigna un valor simblico M.

Ejemplo #1 Aplicativo del Mtodo Simplex

Max Z = 7x1 + 5x2 S.t. 2x1 + 1x2 <= 100 4x1 + 3x2 <= 240 Convirtiendo restricciones en igualdades 2x1 + 1x2 + s1 = 100 4x1 + 3x2 + s2 = 240 La nueva funcin objetivo ser: Max Z = 7x1 + 5x2 +s1 +s2

Presentando las ecuaciones, incluyendo las variables holgura: Incluyendo todas las variables en cada ecuacin, se tendr: Max Z = 7x1 + 5x2 +0s1 +0s2 St 2x1 + 1x2 + 1S1+ 0S2 = 100 4x1 + 3x2 + 0S1 + 1S2 = 240

Inicio del Mtodo Simplex Max Z = 7x1 + 5x2 +0s1 +0s2 Se inicia la solucin en el origen 0,0 es decir con valores de x1=0, x2=0 2x1 + 1x2 + 1S1+ 0S2 = 100 4x1 + 3x2 + 0S1 + 1S2 = 240 Por tanto S1 = 100 S2 = 240

Variable Bsicas, una solucin inicial

La solucin inicial as obtenida es una solucin bsica factible y se representa en forma de vector o columna

X1

X2 S1 S2

0 100 240

En esta solucin inicial si y s2 son variables bsicas pues participan de la solucin, en tanto x1 y x2 son variables no bsicas.

Una posible solucin final: ptima Supongamos el siguiente vector solucin. El vector es la base o mezcla solucin, entonces X1, X2 son variables bsicas finales y s1, s2 son variables no bsicas

X1 X2 S1 S2

30 40 0 0

Con la informacin dada se prepara la tabla Simplex inicial:

Cj $0 $0 Mezcla s1 s2

$7 X1 2 4

$5 X2 1 3

$0 s1 1 0

$0 s2 0 1

RHS 100 240

Completando la primera tabla Simplex

Cj $0 $0 Mezcla s1 s2 Z Cj-Z

$7 X1 2 4 $0 $7

$5 X2 1 3 $0 $5

$0 s1 1 0 $0 $0

$0 s2 RHS 0 100 1 240 $0 $0 $0 utilidad

Completando la primera tabla Simplex

Cj representa la contribucin a la utildad por cada variable Zj representa la contribucin total de una mezcla solucin dada Cj Zj nos indica la utilidad ganada por introducir una unidad de cada producto en la mezcla solucin Por tal razn al maximizar debemos seleccionar la columna con el mayor Cj-Zj que contribuya a la solucin

Determinacin de valores Zj y Cj-Z

Cj $0 $0 Mezcla s1 s2 Z Cj-Z

$7 X1 2 4 $0 $7

$5 X2 1 3 $0 $5
y y y y

$0 s1 1 0 $0 $0

$0 s2 RHS 0 100 1 240 $0 $0 $0 utilidad

Zj(col x1) = 0(2) +0(4) =$0 Zj(col x2) = 0(1) +0(3) =$0 Zj(col s1) = 0(1) +0(0) =$0 Zj(col s2) = 0(0) +0(1) =$0

Cj-Z=7-0 =$7 Cj-Z=5-0 =$5 Cj-Z=$0 Cj-Z=$0

Utilidad total = 0(100)+0(240)=$0

PRIMERA TABLA SIMPLEX , COMPLETA

Cj $0 S1 $0 S2 Zj C j-Zj

$7 $5 2 4 1 3

$0 1 0 $0 $0

$0 0 1 100 240

m ezcla X 1 X 2 S1 S2 R hs

$0 $0 $7 $5

$0 $0 $0 utilidad

Procedimiento para determinar la solucin ptima

1) Qu variable debe ser parte de la mezcla solucin?: La de mayor utilidad Cj-Z, por tanto define la columna pivote 2) Determinamos la fila a reemplazar: la fila pivote = el mayor nmero no negativo resultante de dividir rhs / columna pivote En la interseccin de fila y columna tenemos el pivote Nota: La variable entrante ser entonces x1 y la saliente s1

Cj

$7

$5 $0

$0

me X1 zcla $0 S1 2 $0 S2 4 Zj $0 Cj- $7 Zj
Columna pivote

X2 S1 S2 Rhs 1 3 1 0 0 1 $0 $0 100 240 $0 utili dad

$0 $0 $5 $0

Cj

$7

$5 $0

$0

me X1 zcla $0 S1 2
Rengln pivote

X2 S1 S2 Rhs 1 3 1 0 0 1 $0 $0 100 240 $0 utili dad

$0 S2 4 Zj $0 Cj- $7 Zj
Columna pivote

$0 $0 $5 $0

Cj

$7

$5 $0

$0

Rengln pivote

me X1 zcla $0 S1 2 $0 S2 4 Zj $0 Cj- $7 Zj
Columna pivote

X2 S1 S2 Rhs 1 3 1 0 0 1 $0 $0 100 240 $0 utili dad

$0 $0 $5 $0

Nmero pivote

Cj

$7

$5 $0

$0

Rengln pivote

me X1 zcla $0 S1 2 $0 S2 4 Zj $0 Cj- $7 Zj

X2 S1 S2 Rhs 1 3 1 0 0 1 $0 $0 100 240 $0 utili dad

$0 $0 $5 $0

Variable entrante =X1, Variable saliente = S1

Columna pivote

Nmero pivote

Procedimiento para determinar la solucin ptima

3) Luego, calcular nuevos valores para el rengln pivote: Dividir cada nmero del rengln / nmero pivote: Cj mezcla sol. X1 X2 s1 s2 RHS $7 X1 1 1/2 1/2 0 50 $0 s2 4 3 0 1 240 Como la variable entrante es x1, ingresa con su Cj correspondiente = $/7 en este caso.

Procedimiento para determinar la solucin ptima

4) Calcular nuevos valores para rengln s2

nuevo = viejo -( nmero * nmero en ) valor en valor en debajo rengl.nuevo rengln s2 rengln s2 de pivote del pivote 0 4 4 1 1 3 4 1/2 -2 0 4 1/2 1 1 4 0 40 240 4 50

5) Calcular Zj y Cj-Z Cj 7 0 Zj Cj-Zj mezcla X1 S2 0 0 x1 1 0 3/2 3/2 x2 s1 1/2 1/2 1 -2 7/2 0 -7/2 0 S2 0 1 $350 RHS 50 40

Donde: Zj(col x1) = 7(1) +0(0) =$7 y Cj-Z=$0 Zj(col x2) = 7(1/2) +0(1)=$7/2 y Cj-Z=$3/2 Zj(col s1) = 7(1/2) +0(-2) =$7/2 y Cj-Z=-$7/2 Zj(col s2) = 7(0) +0(1) =$0 y Cj-Z=$0 Utilidad total = 7(50)+0(40)=$350

SEGUNDA TABLA SIMPLEX , COMPLETA, OBTENIDA SIGUIENDO EL PROCEDIMIENTO ANTERIOR

Cj

$7

$5 $0

$0

me X1 zcla $7 x1 1 $0 S2 0 Zj $0 Cj- $0 Zj

X2 S1 S2 Rhs 1/2 1/2 0 1 -2 1 3/2 7/2 $0 3/2 -7/2 0 50 40 $350 utilidad

TERCERA TABLA SIMPLEX , COMPLETA

Cj

$7

$5 $0

$0

me X1 zcla $7 X1 1 $5 X2 0 Zj $7 Cj- $0 Zj

X2 S1 S2 Rhs 0 1 3/2 -1/2 30 -2 1 40

$5 1/2 3/2 410 $0 -1/2 -3/2 utili dad

Como todos los Cj-Zj son ceros o no negativos, Se alcanz la solucin ptima, con x1=30; x2=40; Z=410

Resumen del Mtodo Simplex para maximizacin

Elegir la variable con Cj-Zj positiva ms grande que entre en la mezcla solucin Determinar el rengln a reemplazar, dividiendo rhs/columna pivote, valor ms bajo no negativo Calcular los nuevos valores para el rengln pivote Calcular los nuevos renglones para los otros renglones Calcular los valores Cj y Cj-Zj, regresando al primer paso si resulta algn valor mayor que cero.

Resumen del Mtodo Simplex para minimizacin

Elegir la variable con Cj-Zj negativa ms grande que entre en la mezcla solucin Determinar el rengln a reemplazar, dividiendo rhs/columna pivote, el valor ms bajo no negativo Calcular los nuevos valores para el rengln pivote Calcular los nuevos valores para los otros renglones Calcular los valores Cj y Cj-Zj, regresar al primer paso si resulta algn valor menor que cero.

Ejemplo #2 Aplicativo del Mtodo Simplex

Max Z = 20x1 +10x2 S.t. x1 + 2x2 <= 120 x1 + x2 <= 90 x1 <= 70 x2<=50 x1,x2>=0

Procediendo con el Ejemplo 2

(caso de maximizacin):

Levantamos desigualdades x1 + 2x2 + s1 x1 + x2 + s2 x1 + s3 x2 + s4 = 120 = 90 = 70 = 50

Completando la primera tabla Simplex

$20 mezcla sol. x1 $0 s1 1 $0 s2 1 s3 1 s4 0 Zj $0 Cj-Z $20

Cj

$10 x2 2 1 0 1 $0 $10

$0 s1 1 0 0 0 $0 $0

$0 s2 0 1 0 0 $0 $0

$0 s3 0 0 1 0 $0 $0

$0 s4 RHS 0 120 0 90 0 70 1 50 $0 $0 $0 utilidad

Completando la segunda tabla Simplex

Cj $0 $0 $20 $0 $20 mezcla sol. x1 s1 0 s2 0 x1 1 s4 0 Zj $20 Cj-Z $0 $10 x2 2 1 0 1 $0 $10 $0 s1 1 0 0 0 $0 $0 $0 s2 0 1 0 0 $0 $0 $0 s3 -1 -1 1 0 20 -20 $0 s4 RHS 0 50 0 20 0 70 1 50 0 1400 0 utilidad

Completando la tercera tabla Simplex

MATRIZ SIMPLEX (tercera) $20 $10 mezcla sol. x1 x2 s1 0 0 x2 0 1 x1 1 0 s4 0 0 Zj $20 $10 Cj-Z $0 $0

Cj $0 $10 $20 $0

$0 s1 1 0 0 0 $0 $0

$0 s2 -2 1 0 -1 $10 -$10

$0 s3 1 -1 1 1 10 -$10

$0 s4 0 0 0 1 0 0

RHS 10 20 70 30 1600 utilidad

X1=70; x2=20; z=1600

Ejemplo #3 (Caso de minimizacin):

Min Z = 6x1 + 5x2 S.t. x1 + x2 = 2000 x1 >= 300 x2 <= 600 x1,x2>=0

Agregando variables artificiales y de holgura:

Min Z = 6x1 + 5x2 S.t. x1 + x2 = 2000 x1 >= 300 X2 <= 600 x1,x2>=0

x1 + x2 +A1 =2000 x1 + A2 s1 = 300 x2 + s2 = 600

TABLA SIMPLEX , INICIAL

$6 $5 $0 $0 $M $M mezcla sol. x1 x2 s1 s2 A1 A2 RHS $M A1 1 1 0 0 1 0 2000 $M A2 1 0 -1 0 0 1 300 $0 s2 0 1 0 1 0 0 600 Zj $2M $M $-M 0 $M $M $2300M Cj-Z 6-2M 5-M M $0 $0 $0 costo total en minimizacin escoger como columna pivote el valor negativo ms grande

Cj

SEGUNDA TABLA SIMPLEX

$6 $5 mezcla sol. x1 x2 $M A1 0 1 $6 x1 -1 0 $0 s2 0 1 Zj $6 $M Cj-Z $0 $5-M

Cj

$0 s1 1 -1 0 $M-6 $6-M

$0 s2 0 0 1 $0 $0

$M A1 1 0 0 $M $0

$M A2 RHS -1 1700 1 300 0 600 -$M+6 700M+1800 $2M-6 costo total

TERCERA TABLA SIMPLEX

$6 mezcla sol. x1 $M A1 0 $6 x1 1 $5 x2 0 Zj $6 Cj-Z $0

Cj

$5 $0 $0 x2 s1 s2 0 1 -1 0 -1 0 1 0 1 $5 $M-6 -$M+5 $0 $6-M -5+M

$M A1 1 0 0 $M $0

$M A2 RHS -1 1100 1 300 0 600 -$M+6 100M+4800 $2M-6 costo total

CUARTA TABLA SIMPLEX

Cj $0 $6 $5

MATRIZ SIMPLEX (cuarta) $6 $5 $0 mezcla sol. x1 x2 s1 s1 0 0 1 x1 1 0 0 x2 0 1 0 Zj $6 $5 $0 Cj-Z $0 $0 0

$0 s2 -1 -1 1 -1 1

$M A1 1 1 0 $6 $M-6

$M A2 -1 0 0 $0 $M

RHS 1100 1400 600 11400 costo total

x1=1100; x2=1400; Z= 1100(0)+1400(6)+600(5)=11,400

Ejemplo # 4 (Caso de minimizacin):

Min Z = 5x1 + 5x2 S.t. x1 + x2 = 1000 x1 <= 300 x2 >= 150 x1,x2 >=0

Agregando variables artificiales y de holgura:

Restricciones: x1 + x2 = 1000 1 x1 + 1 x2 + 1 A1 =1000 x1 <= 300 1 x1 + 1 s1 = 300 x2 >= 150 1 x2 - 1 s2 + 1 A1 = 150 Funcin Objetivo: Min Z = 6x1 + 5x2 + 0 s1 + 0 s2 + MA 1 + MA2

Convirtiendo restricciones en igualdades:

Min 5x1 + 6x2 + 0S1 + 0S2 + MA1 + MA2 1 x1 + 1 x2 + 0 s1 + 0 s2 + 1 A1 + 0 A2 1 x1 + 0 x2 + 1 s1 + 0 s2 + 0 A1 + 0 A2 0 x1 + 1 x2 + 0 s1 - 1 s2 + 0 A1 + 1 A2

= 1000 = 300 = 150

Nota: como estamos minimizando, M es un nmero muy grande para obligar que su variable quede fuera de la mezcla solucin.

Tabla Simplex inicial:

$5 $6 $0 $0 $M $M mezcla sol. x1 x2 s1 s2 A1 A2 RHS $M A1 1 1 0 0 1 0 1000 $0 s1 1 0 1 0 0 0 300 $M A2 0 1 0 -1 0 1 150 Zj $M $2M $0 -$M $M $M $1150M Cj-Z -$M+5 -2$M+6 $0 $M $0 $0 costo total en minimizacin escoger como columna pivote el valor negativo ms grande Cj

Cj $M $0 $6

Tabla Simplex segunda: $5 $6 $0 $0 $M $M mezcla sol. x1 x2 s1 s2 A1 A2 RHS A1 1 0 0 1 1 -1 850 s1 1 0 1 0 0 0 300 x2 0 1 0 -1 0 1 150 Zj $M $6 $0 $M-6 $M -$M+6 $850M+900 Cj-Z -$M+5 $0 $0 -$M+6 $0 $2M-6 costo total
x1=300, x2=700,s2=550, costo=5700

Completar las tablas tercera y cuarta, para obtener :