método simplex

Método Simplex

Antes de iniciar con la selección del pivote y con las

iteraciones, debemos estandarizar la función Z. Para esto se

deben tener en cuenta algunos puntos para las restricciones:

• Cuando es ≤ se utilizan variables de holgura (s)

• Cuando es ≥ se utilizan v. de exceso (-s) + v. artificial (A)

• Cuando es = se utiliza la variable artificial (A)

Sebastian García

Estudiante de Ing. Industrial

Método Simplex

caso ≤

Ejemplo:

𝑍𝑚á𝑥 = 4𝑥1 + 3𝑥2𝑠𝑢𝑗𝑒𝑡𝑜 𝑎:

2𝑥1 + 𝑥2 ≤ 60𝑥1 + 𝑥2 ≤ 40𝑥1, 𝑥2 ≥ 0

Estandarización

𝑍𝑚á𝑥 − 4𝑥1 − 3𝑥2 = 0

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎:2𝑥1 + 𝑥2 + 𝑠1 = 60𝑥1 + 𝑥2 + 𝑠2 = 40

Método Simplex

Selección del pivote

Columna

• Cuando es Z máx, se toma el valor más negativo de Z

• Cuando es Z mín, se toma el valor más positivo de Z

Fila

• Se realiza la división entre 𝑏0

𝑥0y se elige el menor valor que

sea >0

Método Simplex

¿Cuándo termino de iterar?

• Cuando la función es Z máx, termino cuando

no quedan valores negativos en la fila de z.

• Cuando la función es Z mín, termino cuando

no quedan valores positivos en la fila z.

Método Simplex

VB Bo X1 X2 S1 S2 Bo/Xo

F1 S1 60 2 1 1 0

F2 S2 40 1 1 0 1

F3 Z 0 -4 -3 0 0

1. Organizar en la tabla

2. Seleccionar el pivote (Caso Z máx)

VB Bo X1 X2 S1 S2 Bo/Xo

F1 S1 60 2 1 1 0 30

F2 S2 40 1 1 0 1 40

F3 Z 0 -4 -3 0 0

El pivote es 2, entra X1 y sale S1(ver en la siguiente diapositiva)

Método Simplex

VB Bo S1 X2 S1 S2 Bo/Xo

F1 X1 60 2 1 1 0

F2 S2 40 1 1 0 1

F3 Z 0 -4 -3 0 0

3. Utilizar el método de Gauss (operaciones entre filas) para convertir el 2 en 1 y después los otros valores en 0


F1 X1 60 2 1 1 0

F2 S2 40 1 1 0 1

F3 Z 0 -4 -3 0 0

F1/2

-F1+F2

4F1+F3

Método Simplex


F1 X1 30 1 1/2 1/2 0

F2 S2 40 1 1 0 1

F3 Z 0 -4 -3 0 0

F1/2

-F1+F2


F1 X1 30 1 1/2 1/2 0

F2 S2 10 0 1/2 -1/2 1

F3 Z 0 -4 -3 0 0

Método Simplex

4F1+F3


F1 X1 30 1 1/2 1/2 0

F2 S2 10 0 1/2 -1/2 1

F3 Z 120 0 -1 2 0


F1 X1 30 1 1/2 1/2 0 60

F2 S2 10 0 1/2 -1/2 1 20

F3 Z 120 0 -1 2 0

4. Seleccionar el siguiente pivote y operar nuevamente entre filas El pivote es 1/2, entra X2 y sale S2(ver en la siguiente diapositiva)

Método Simplex

VB Bo S1 S2 S1 S2 Bo/Xo

F1 X1 30 1 1/2 1/2 0

F2 X2 10 0 1/2 -1/2 1

F3 Z 120 0 -1 2 0


F1 X1 30 1 1/2 1/2 0

F2 X2 10 0 1/2 -1/2 1

F3 Z 120 0 -1 2 0

5. Nuevamente utilizar el método de Gauss para convertir el ½ en 1 y después los otros valores en cero

(-1/2)F2+F1

(2)F2

F2+F3

Método Simplex


F1 X1 20 1 0 1 -1

F2 X2 20 0 1 -1 2

F3 Z 140 0 0 1 2

Al realizar las operaciones observamos que no quedan valores negativos en la fila de Z, por tanto ya no debemos continuar iterando.

La respuesta será:Z máx = 140

X1 = 20X2 = 20

Método Simplex – Gran M

Caso ≥

Para usar el método de la Gran M se debe tener en cuenta:

• Cuando la función es Zmín, la estandarización de la FO no se iguala a

cero, solamente se agregan las variables artificiales con el coeficiente

+M y las de holgura y exceso con coeficiente 0

• Cuando la función es Zmáx, la estandarización de la FO no se iguala a

cero, solamente se agregan las variables artificiales, pero con el

coeficiente –M y las de holgura y exceso con coeficiente 0


Caso ≥

Ejemplo:

𝑍𝑚í𝑛 = 0,05𝑥1 + 0,1𝑥2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎:2𝑥1 + 12𝑥2 ≥ 247𝑥1 + 2𝑥2 ≥ 28

𝑥1, 𝑥2 ≥ 0

Estandarización

𝑍𝑚í𝑛 = 0,05𝑥1 + 0,1𝑥2 +𝑀𝐴1 +𝑀𝐴2 + 0𝑠1 + 0𝑠2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎:

2𝑥1 + 12𝑥2 − 𝑠1 + 𝐴1 = 247𝑥1 + 2𝑥2 − 𝑠2 + 𝐴2 = 28


Caso ≥

1. Organizar en la tablaLa fila y columna de CJ lleva los coeficientes de las variables de la función objetivo. Se debe tener en cuenta que las variables de holgura y de exceso no contribuyen entonces llevan coeficiente 0

CJ0,05 0,1 0 0 +M +M

VB Bo X1 X2 S1 S2 A1 A2

F1 +M A1 24 2 12 -1 0 1 0

F2 +M A2 28 7 2 0 -1 0 1

Z 52M 9M 14M -M -M M M

ZJ-CJ 52M 9M-0,05 14M-0,1 -M -M 0 0


Caso ≥

2. Se elige el ZJ-CJ más positivo porque la función es de minimizar y para la fila se elige el menor coeficiente > 0

CJ0,05 0,1 0 0 +M +M

Bo/XiVB Bo X1 X2 S1 S2 A1 A2

F1 +M A1 24 2 12 -1 0 1 0 2

F2 +M A2 28 7 2 0 -1 0 1 14

ZJ-CJ 52M 9M-0,05 14M-0,1 -M -M 0 0

El pivote es 12, entra X2(ver en la siguiente diapositiva)

Este valor es el resultado de:12*M+2*M – 0,1


Caso ≥

3. Proceder con el método de Gauss hasta que no queden valores positivos de ZJ-CJ

F1/12

-2F1+F2

CJ0,05 0,1 0 0 +M +M


F1 0,1 X2 2 1/6 1 -1/12 0 1/12 0

F2 +M A2 24 20/3 0 1/6 -1 -1 5/6

ZJ-CJ 0,2+24M -0,03+ 6,7M 0 -0,01+0,2M -M 0,01-2M -0,17M

4. Siguiente pivote

CJ0,05 0,1 0 0 +M +M


F1 0,1 X2 2 1/6 1 -1/12 0 1/12 0 12

F2 +M A2 24 20/3 0 1/6 -1 -1 5/6 3,6

ZJ-CJ 0,2+24M -0,03+ 6,7M 0 -0,01+0,2M -M 0,01-2M -0,17M

El pivote es 20/3, entra X1

CJ0,05 0,1 0 0 +M +M


F1 0,1 X2 7/5 0 1 -7/80 1/40 13/120 -1/48

F2 0,05 X1 18/5 1 0 1/40 -3/20 -3/20 1/8

ZJ-CJ 0,32 0 0 -3/400 -1/200 1/300-M 1/240-M

(3/20)F2

(-1/6)F2+F1

5. Como ya no quedan valores positivos en la fila de ZJ-CJ entonces ya terminamos

Respuesta:

Zmín = 0,32X1 = 18/5 = 3,6X2 = 7/5 = 1,4

método simplex

Engineering