(first post on math SE)
I am looking for a formal upper-bound on the number of iterations in the first phase, in terms of the number of artificial variables (A.V).
I have some intuition that it might be exactly the number of A.V. but I might be wrong, and my search on the theoretical complexity of the first phase was fruitless so far.
Thanks for your kind help.
Your intuition is right. Remember that at each iteration of the simplex algorithm exactly one variable enters the basis while another one leaves the basis. Therefore if the constraints of problem to be solved are given as $m$ equalities $Ax=b$, then the first phase will take at most $m$ iterations, either a) eliminating all the artificial variables from the optimal basis of the artificial problem, or b) declaring that the original problem is unfeasible. Actually in the case a), the first phase could take less than $m$ iterations. This happens when $rank(A)<m$. Therefore we can conclude that $$Iterations \leq rank(A) \leq \min\{m,n\}=m$$