4
$\begingroup$

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 ?

$\endgroup$
  • 2
    $\begingroup$ I think $x_e=\infty$ should be understood as „for every arbitrarily large value of $x_e$“. Solutions $\bar x$ for $x_e\geq 0$ form an infinity ray, which certifies unboundedness. $\endgroup$ – Marcus Ritt Jun 21 at 3:17
3
+50
$\begingroup$

Because of line 9, $\Delta_l$ is going to be $\infty$ if and only if all the $\Delta_i$ with $i \in B$ are $\infty$. This can happen only when all the $a_{ie}$ with $i \in B$ are $ \le 0$. Hence, by construction the solution $\bar{x}$ satisfies $\bar{x}_i \ge 0$ for all $i$. Therefore it is both feasible and it has unbounded objective value.

If you are confused by the $\infty$, as Marcus Ritt mentioned in a comment you can replace the $\infty$ in the definition of $\bar{x}$ with a very large value $M$ and consider what happens as $M$ tends to $\infty$.

$\endgroup$
  • $\begingroup$ But if $\Delta_l = \infty$, function returns "unbounded" result, not the the solution $\bar x$ on line 17. I thought, the result set that's being discussed, where $\bar x_i = \infty$ when $i = e$, is the one that is returned on line 17. $\endgroup$ – maksadbek Jun 25 at 16:49
  • $\begingroup$ The return value of line 17 has been already discussed in the first 3 lines of the "Termination" paragraph you cited (the feasible and bounded case). The remaining argument in that paragraph deals only with the return value of line 11 (the unbounded case). The argument says that returning unbounded is correct in that case, because an infinite "ray" of solutions $\bar{x}$ exists. $\endgroup$ – Vincenzo Jun 26 at 9:00

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.