metodo simplex

UNIVERSIDAD SIMON BOLIVAR
DEPARTAMENTO DE PROCESOS Y SISTEMAS
PS 1111 INVESTIGACION DE OPERACIONES


ALGORITMO SIMPLEX

METODO SIMPLEX DE 2 FASES


FASE II


PASO 1: Llevar el problema a su formastandard de maximización:
Max Z(x)= CX
s.a.: AX=b
X≥0, b≥0. A ε R mxn, X ε R nx1,C ε R 1xn, b ε R mx1

Si el problema es de minimización, se plantea igual, se invierte la condición deoptimalidad (ver paso 6)



PASO 2: Plantear la matriz de trabajo de la siguiente forma:

Z
VB
X1
X2 . . . . . . . . . . . . . . . . . .
Xn-m. . . . .
Xn
b
1
Z
-C1
-C2 . . . . . . . . . . . . . . . . .-Cn-m
-Cn
0
0
.
.
.
.
0

a11




am1
a12. . . . . . .. . . . . . . . . . .




a2m. . . …. . . . . . . . . . . . .
a1,n-m. . . .




am, n-m .. .
a1n




amn
b1
b2



bm







(Se estárepresentando +Z-C1X1-C2X2-.......................-CnXn=0 )



PASO 3: Chequear si existe una matriz identidad de orden mxm.
Si existe: Ir al paso 4 de esta misma fase.
Si no existe: Efectuar Fase I.



PASO4: Las variables asociadas a la matriz identidad constituyen las variables básicas iniciales y la tabla se presenta de la siguiente forma:
Z
VB
X1
X2 . . . . . . . . . . . . .
Xn-m Xn-m+1
Xn
b
1Z
-C1
-C2 . . . . . . . . . . . .
-Cn-m –Cn-m+1
-Cn
0
0
.
.
.
.
0
0
0
X1
X2
X3




Xm
a11






am1
a12. . . . . . .. . . . . . .






a2m. . . …. . . . . . . .
a1,n-m 10
0




am, n-m 0
0






1
b1
b2





bm










PASO 5: Hacer cero los coeficientes de costo de las variables básicas iniciales(mediante operaciones elementales de fila) y de esta manera se obtiene la siguiente tabla denominada tabla canónica:
Z
VB
X1
X2 . . . . . . . . . . . . .
Xn-m Xn-m+1
Xn
b
1
Z
-C1
-C2 . . . . . . . . .. . .
-Cn-m –Cn-m+1
-Cn
0
0
.
.
.
.
0
0
0
X1
X2
X3




Xm
a11






am1
a12. . . . . . .. . . . . . .






a2m. . . …. . . . . . . .
a1,n-m 1
0...