PROCEDIMIENTO_SIMPLEX_REVISADO

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

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 lacolumna 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 lavariable 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 00 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...