PROCEDIMIENTO SIMPLEX REVISADO Este método requiere una menor cantidad de cálculos, ya que realiza cálculos únicamente en los vectores de aquellas variables no-básicas y registra en memoria lo relativo a las variables básicas, B −1 , c B B −1 , x B y c B x B (así como todos los valores iniciales cj, aij y b i). Pasos: ♦ Determinar las variables básicas y formar B. ♦ Obtener B −1 . ♦ Obtener z j − c j = wa j − c j . Donde W = c B B −1 Si z j − c j ≤ 0 para un problema de minimización o z j − c j ≥ 0 para un problema de maximización la solución es óptima y es el fin del proceso. Si esto no se cumple continúe el proceso. ♦ Determinar la variable que entra en solución (sea esta x k ) usando WA-C para toda variable no-básica ( wi a j − c j ). ♦ Se analiza

xBi (para toda i) para determinar que la variable sale de solución, ykj

sea ésta x f . Ahora actualice la columna a k para que ésta aporte la columna de la matriz identidad que aportaba la variable saliente x f . ♦ Regresar al principio del proceso, realizar los cálculos necesarios para sacar de la base a x f y meter a la misma x k (actualice la columna a k para que esta aporte la columna de la matriz identidad que aportaba la variable saliente x f ). Procedimiento: Si Z = c B X B donde X B = B −1 A , entonces Z = c B B −1 A equivale a z j = c B B −1 a j y si W = c B B −1 entonces ahora WA − C = Z − C equivale a wi a j − c j = z j − c j .

Base de la inversa

Lado derecho

W

CBXB

B-1

XB

Tablas en el proceso CB X B

W

B

xk z k − ck y 1k y2k

x B1 xB2

−1

M

M y mk

x Bm

Ejemplo: Max Z = 5 x1 + 3 x 2 Sujeto a: 3 x1 + 5 x 2 ≤ 15

5 x1 + 2 x 2 ≤ 10 x1 , x 2 ≥ 0 Así: x1 3 A= 5

x2

x3

5 2

1 0

x4 0 1 

C = [5

3

0

15 b=  10

0]

Analizando para todas las variables no-básicas: x1 x2

z j − c j = WA − C = [0

3 0] 5

5 − [5 2

3] = [− 5

3]

por lo que entra en solución x1 . Tabla 1

y1 0 0 1 0 0 1

0 15

−5 3

x3 x4

10

← Sale x 4

5

Generando en la columna de la variable entrante la columna necesaria para formar la matriz identidad (la que aportaba la variable saliente x 4 ) se tiene:

0 1

1 −3 5

10 9

x3

0

15

2

x1

Analizando para todas las variables no-básicas: x2

x4

 5 0 z j − c j = WA − C = [ 0 1]   − [3 0] = [ −1 1] 2 1

por lo que entra en solución x 2 . Tabla 2

y2 0

1

10

1 0

−3 5 15

9 2

−2 19 5

x3 x1

← Sale x 3

25

Generando en la columna de la variable entrante la columna necesaria para formar la matriz identidad (la que aportaba la variable saliente x 3 ) se tiene:

5 19 5 19

16 19 − 3 19

235 19 45 19

− 2 19

5 19

20 19

Analizando para todas las variables no-básicas: x3 x4

0 1 0] = [5 19 16 19], 16 19] − [0 1  0 Como todos los valores son mayores que cero la solución óptima se ha alcanzado. z j − c j = WA − C = [5 19

Solución óptima:

Z = 325 19 x1 = 20 19 x 2 = 45 19

Ejemplo: Método de la M Min Z = 3 x1 + 2 x 2 Sujeto a: 3 x1 + x 2 ≥ 3

4 x1 + 3 x 2 ≥ 6 x1 + x 2 ≤ 3 x1 , x 2 ≥ 0 3 x1 + x 2 − x 3

+ x6

=3

4 x1 + 3 x 2 − x4 + x7 = 6 x1 + x 2 + x5 =3 x 6 y x 7 son variables artificiales Así:

x1

x2

x3

x4

x5

x6

x7

3 A = 4  1

1 3 1

-1 0 0 -1 0 0

0 0 1

1 0 0

0 1  0

C = [3 2 0 0 0 M

M]

3 b = 6    3

Analizando para todas las variables no-básicas:

C B B −1 a j − c j = z j − c j = WA − C = [M

M

C B B −1 a j − c j = z j − c j = WA − C = [7 M

x1

x2

x3

3 0]4  1

1 3

- 1 0 0 - 1 − [3 2 0 0]  0 0 

4M

1

−M

x4

− M ] − [3 2 0 0]

C B B −1 a j − c j = z j − c j = WA − C = [7 M − 3 4M − 2 − M

− M]

Entra en solución x1 por tener el valor más positivo. Tabla 1

M 1

M 0 0 0

0 0

1 0

9M 3 6 3

0 1

x6

y1 7M − 3 3

x7 x5

4 1

← Sale x 6

Generando en la columna de la variable entrante la columna necesaria para formar la matriz identidad (la que aportaba la variable saliente x 6 ) se tiene:

− 4 3M +1 13

M 0

0 0

2M + 3 1

−43 −1 3

1 0

0 1

2 2

Analizando para todas las variables no básicas:

x2

x3

1 0]  4  1

-1

x4

x6

1 CB B a j − c j = z j − c j = WA − C = [ −4 3 M + 1 M 0 -1 0  − [ 2 0 0 M ]  0 0 0  CB B −1a j − c j = z j − c j = WA − C = [ 5 3 M + 1 −4 3 M − 1 − M −4 3 M ] − [ 2 0 0 M ] −1

0

CB B −1a j − c j = z j − c j = WA − C = [ 5 3 M − 1 4 3 M − 1 − M

−4 3 M + 1]

Entra en solución x 2 por tener el valor más positivo. Tabla 2

y2

− 4 3M +1 13

M 0

0 0

2M + 3 1

x1

5 3M −1 13

−43 −1 3

1 0

0 1

2 2

x7 x5

53 23

Generando en la columna de la variable entrante la columna necesaria para formar la matriz identidad (la que aportaba la variable saliente x 7 ) se tiene:

15 35

35 −1 5

0 0

21 5 35

−4 5 15

35 −25

0 1

65 65

x1 x2 x5

Analizando para todas las variables no-básicas: x3

x4

x6

x7

1 0  -1 0  CB B a j − c j = z j − c j = WA − C = [1 5 3 5 0] 0 -1 0 1  − [ 0 0 M    0 0 0 0  CB B −1a j − c j = z j − c j = WA − C = [ − 1 5 − 3 5 1 5 3 5] − [ 0 0 M M ] −1

CB B −1a j − c j = z j − c j = WA − C = [ − 1 5 − 3 5 1 5 − M

M]

3 5− M ]

Se ha alcanzado la solución óptima por ser todos los valores negativos.

Solución óptima: Z = 21 5

x1 = 1 5 x2 = 6 5 x5 = 6 5

Ejemplo: Método de las 2 Fases Max Z = x1 − 2 x 2 + x 3 − x 4 Sujeto a: x1 + 4 x 2 + x 3 − x 4 ≤ 6

2 x1 + x 2 + 3 x 3 − 3 x 4 ≥ 2 x1 , x 2 , x 3 , x 4 ≥ 0 =6 x1 + 4 x 2 + x 3 − x 4 + x 5 2 x1 + x 2 + 3 x 3 − 3 x 4 − x6 + x7 = 2 x1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ≥ 0 donde x 5 y x 6 son variables de holgura y x 7 es una variable artificial. FASE I Así:

x1

x2

x3

x4

x5

x6

x7

1 A= 2

4 1

1 3

-1 -3

1 0

0 -1

0 1

C = [0 0 0 0 0 0 - 1]

Analizando para todas las variables no-básicas:

 6 b=   2

x1

x2

x3

x4

4 1 -1 1 - 1] 1 3 -3 2 z j − c j = WA − C = [- 2 - 1 - 3 3 0] Por lo que entra en solución x 3 . z j − c j = WA − C = [0

x6 0 − [0 1

0

0

- 1]

0

Tabla 1

0 0

0

1 0

6

0 1

2

y3 -3

1

x5 x7

← Sale x 7

3

Generando en la columna de la variable entrante la columna necesaria para formar la matriz identidad (la que aportaba la variable saliente x 7 ) se tiene:

0

1 3

−2

1

−1 3

16

0

1 3

2

3

3

3

x5 x3

Analizando para todas las variables no-básicas: x1

x2

1 z j − c j = WA − C = [0 0] 2

x3

x4

4

1

0

1

3

1

x5 0 − [0 0 0 0 0] = [0 0 0 0 0] - 1

Como todos los valores son iguales a cero se ha alcanzado el final de la Fase I. FASE II Ahora C = [5 - 2 1 - 1 0 las c j .

0] y se recalcula la tabla con los valores verdaderos de

x1

]

z j − c j = WA − C = [0

1 3

z j − c j = WA − C = [23

1 3

1 2 -1

x2

x4

x6

4 1

-1 -3

0 − [5 - 2 - 1 1

1 3

] − [5

- 2 -1

0] = [−133

0] 7

3

0

1 3

]

Entra x1 en solución por tener el valor más negativo. Tabla 2

y1 0

1 3

2

1

−1 3

16

0

1 3

2

13

3

x5 x3

3

3

3

1 3 2

← Sale x 3

3

Generando en la columna de la variable entrante la columna necesaria para formar la matriz identidad (la que aportaba la variable saliente x 3 ) se tiene:

0

−5

1

−1

0

1

5

2

2

5

2

1

x5 x1

Analizando para todas las variables no-básicas: x 2 x3 x 4 x6

z j − c j = WA − C = [0

−5

z j − c j = WA − C = [−5 2

2

15

]

4 1

2

1 -1 3 -3 -15

2

−5

2

0 − [- 2 1 

] − [5

0]

1 -1

- 2 -1

0] = [ 12

13

2

−13

2

−5

2

]

Entra x 4 en solución por tener el valor más negativo. y4 0 5/2 1 0

−1 1

2

2

5

5 1

- 14

x5 x1

1

2

−3

← Sale x 5

2

Generando en la columna de la variable entrante la columna necesaria para formar la matriz identidad (la que aportaba la variable saliente x5 ) se tiene:

13 − 4

70

2 −1 3 −1

10 16

x4 x1

Analizando para todas las variables no-básicas: x2

x3

x4

x6

4 1 - 1 0  z j − c j = WA − C = [13 − 4]  − [- 2 1 - 1 0] 1 3 - 3 - 1 z j − c j = WA − C = [48 1 - 1 4] − [5 - 2 - 1 0] = [43 3 0 4]

Como todos los valores son mayores que cero la solución óptima se ha alcanzado. Solución óptima: Z * = 70 x * 4 = 10 x *1 = 16