Industrial

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 quela 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 lavariable 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 W B-1

Lado derecho CBXB XB

Tablas en el proceso
W

CB X B

B

−1

x B1 xB2 M x Bm

xk z k − ck y 1k y2k

M y mk

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

5 x1 + 2 x 2 ≤ 10 x1 , x 2 ≥ 0
Así:
x1 3 A= 5 x2 5 2 x3 1 0 x4 0 1 

C = [5

3

0

0

]

15 b=  10

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

10

x3 x4

−5 3

5

←Sale x 4

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 0

1 −3 5 15

10 9 2

x3 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 0 1 −3 515 10 9 2 x3 x1 −2 19 5 25 ← Sale x 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:

5 19 5 19 − 2 19

16 19 − 3 19 5 19

235 19 45 19 20 19

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

0 1 [ ] 16 19 , ] 0 = [5 19 16 19  ] − 0 1 0  Como todos los valores sonmayores 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 3 A = 4  1 

x2 13 1

x3

x4

x5 0 0 1

x6 1 0 0

x7 0 1  0 
C = [3 2 0 0 0 M M]

-1 0 0 -1 0 0

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

Analizando para todas las variables no-básicas:

x1 C B B −1 a j − c j = z j − c j = WA − C = [M C B B −1 a j − c j = z j − c j = WA − C = [7 M M 4M 3 ] 0 4  1  −M

x2 1 3 1

x3

x4

C B B −1 a j − c j = z j − c j = WA − C = [7 M − 3 4M − 2 − M
Entra ensolución x1 por tener el valor más positivo. Tabla 1

[ − M ]− 3 2 0 0]
− M]

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

]

M 1

M 0 0 0

0 0

1 0

0 1

9M 3 6 3

x6 x7 x5

y1 7M − 3 3

← Sale x 6

4 1

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...