Mistake in a proof of termination phase of Simplex algorithm in CLRS?
-
05-11-2019 - |
Question
There is a pseudo-code for Simplex algorithm in CLRS:
The proof consists from three-part loop invariant:
Proof We use the following three-part loop invariant:
At the start of each iteration of the while loop of lines 3–12,
- the slack form is equivalent to the slack form returned by the call of INITIALIZE-SIMPLEX,
- foreach $i \in B$, we have $b_i$ >= 0, and
- the basic solution associated with the slack form is feasible.
The initialisation and maintenance phases are clear for me. But, the termination case seems(not sure) wrong to me:
So, my question is:
It is unclear for me that $\bar{x_i} = \infty $ if $i = e$. But, if we look at the pseudo-code, it is obvious that such thing happens only if $x_e \leq 0$. What am I missing ?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange