Método Simplex Revizado

EL MÉTODO REVISADO

Maz Z = CB XB + CN XN …………….1
s.a.:
B XB + N XN = b …………..…2

XB , XN ≥ 0

al multiplicar por B-1 la ecuación 2, tenemos:

B-1 B XB + B-1 N XN = B-1 b

XB + B-1 N XN = B-1 b …………….3

Ahora, multiplicando la ecuación 3 por CB, tenemos;

CB XB + CB B-1 N XN = CB B-1 b

CB XB + CB B-1 N XN - CB B-1 b = 0 ………4Sumando la ecuación 4 a la ecuación 1, tenemos;

Z - CB XB - CN XN + CB XB + CB B-1 N XN - CB B-1 b = 0

Z - CN XN + CB B-1 N XN = CB B-1 b

Z + (CB B-1 N - CN) XN = CB B-1 b resultado de los pasos por algoritmo de pivoteamiento

Y si las variables no básicas le asignamos valor nulo,
Tenemos;

XN = 0
XB = B-1 b 5
Z = CB B-1 b

PASOS DEL ALGORITMO SIMPLEXREVISADO

Paso 1.- Una solución básica factible está representada por el sistema 5

Paso 2.- Debemos averiguar la conveniencia o no de convertir alguna de las variables no básicas en variable básica. Esto se logra examinando los costos reducidos asociados a las variables no básicas en la función objetivo.

Cj - Zj = Cj - CB B-1aj Costo Reducido, luego debemos elegir aquella vartaible nobásica que tenga asociado un mayor costo reducido:

Ck - Zk = max de Cj - Zj

Cuando Ck - Zk ≤ 0 V k = 1,2,….n == > FIN

Paso 3.- Caso contrario;
.
Calcular ak = B-1 ak ; si los ak ≥ 0 == > Problema ilimitado

Si no es así, entonces el subíndice o columna de la variable que sale de la base está dado por la siguiente expresión:.
br / ark = min {bi/aik ; aik > 0}
1≤i≤n
Luego se debe analizar B-1 reemplazando el coeficiente aB por ak y volver al Paso 1.

Veamos un ejemplo:

Min Z = - 1 X1 -2 X2 + 1X3 - 1X4 - 4X5 + 2X6
s.a.:
X1 + X2 + X3 + X4 + X5 + X6 ≤ 6
2X1 - X2 - 2X3 + X4 ≤ 4X3 + X4 + 2X5 + X6 ≤ 4
XJ ≥ 0 ; j = 1, 6

El modelo estándar y ampliado:

Max H = 1 X1 + 2 X2 - 1X3 + 1X4 + 4X5 - 2X6
s.a.:
X1 + X2 + X3 + X4 + X5 + X6 + h1 = 6
2X1 - X2 - 2X3 + X4 +h2 = 4
X3 + X4 + 2X5 + X6 +h3 = 4

XJ≥ 0, hs ≥ 0

Resolver por método SIMPLEX por cuadro y luego revisado.

X1 X2 X3 X4 X5 X6 h1 h2 h3 b
h1 1 1 1 1 1 1 1 0 0 6
h2 2 -1 -2 1 0 0 0 1 0 4
h3 0 0 1 1 2 1 0 0 1 4
-H 1 2 -1 1 4-2 0 0 0 0

h1 1 1 1/2 1/2 0 1/2 1 0 -1/2 4
h2 2 -1 -2 1 0 0 0 1 0 4
X5 0 0 1/2 1/2 1 1/2 0 0 1/2 2
-H 1 2 -3 -1 0 -4 0 0 -2 -8

X2 1 1 1/2 1/2 0 1/2 1 0 -1/24
h2 3 0 -3/2 3/2 0 1/2 1 1 -1/2 8
X5 0 0 1/2 1/2 1 1/2 0 0 1/2 2
-H -1 0 -4 -2 0 -5 -2 0 -1 -16

Revisado: B-1 __.V. básicas inversa b
1 0 0 1 0 0 h1 1 0 0 6
B = 0 1 0 == > B-1 = 0 1 0 h2 0 1 0 4
0 0 1 0 0 1 h3 0 0 1 4

Analicemos los costos reducidos

Cj - Zj = Cj - CB B-1aj para...