Question

There is a pseudo-code for Simplex algorithm in CLRS:

enter image description here

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,

  1. the slack form is equivalent to the slack form returned by the call of INITIALIZE-SIMPLEX,
  2. foreach $i \in B$, we have $b_i$ >= 0, and
  3. 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:

enter image description here

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
scroll top