JAVA

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

MM
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

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 queentra 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 − cj = WA − C = [ 0 1 ]
 − 3 [ 0 = ]−1[ 1
2 1

]

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

y2
0

1

1
0

−3 5
15

9
2

−2
19 5

10
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
[
] 16 19 , ]
0 = [5 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 lasvariables 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

x3

3
]
0 4

1


M

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