0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for your reply. To state this formally, we need a (proven) guarantee that in case (a), each phase-1 iteration will necessarily select a non-artificial as entering the base, and drop will drop out an artificial one. I failed to find a formal statement or proof in any published work, which intrigues me because my "intuitive" claim is contestable. $\endgroup$ – A.S.H Mar 24 '18 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.