sci.op-research

On Apr 10, 2:47 pm, "saneman" wrote:
> In each iteration the simplex algorithm visit one of the possible corner
> points. But what is the intuition behind this behaviour and why does it not
> investigate a point somewhere in the middle of a line (assuming the number
> of variables n 2 <= n <= 3)?
>
> All corner points can be found by setting (m-n) variables = 0 and then
> solving the remaining system.

These will not be "corner" points unless they are also >= 0; that is,
an infeasible (not all >= 0) BASIC solution is not in the feasible
region and does not correspond to a corner point, although it IS
obtained by setting (m-n) variables to zero and solving for the other
m variables.

> But I still don't see why this is necessary a
> corner point.

What is the definition of a corner point (extreme point)? Well, x is a
corner point if it is feasible, but is *not* a nontrivial convex
combination of two distinct feasible points; that is, there do _not_
exist two different feasible points x1, x2 and a number r strictly
between 0 and 1 such that x = r*x1 + (1-r)*x2. Whether or not this
fits with your intuition about the meaning of "corner" is another
matter; the fact is that this is the _definition_. Now you can show
algebraically that all basic feasible solutions are corner points in
the sense of the definition, and all feasible points that are not
basic are NOT corner points. There is a 1:1 correspondence between
corner points and basic feasible solutions.

As to why the simplex method looks only at corner points (or more
generally, only at basic solutions), well, that is because it is set
up to do exactly that. There is a theorem that saying that if an LP
problem has a finite optimal solution (that is, a feasible solution
whose objective is a max or min over all feasible values) then it has
a basic feasible solution that is optimal. Also, if all basic
solutions are infeasible, the whole problem is infeasible. Therefore,
there is no need to look outside the set of basic solutions. One way
to prove this theorem is through the simplex method itself, showing
that it terminates in finitely many iterations if anti-cycling
strategies are employed. However, there are also other ways to prove
it that do not use the simplex method itself.

Certainly, an LP having a non-unique optimal solution will have an
infinite set of optima that lie on a line segment between two optimal
basic feasible solutions, or possibly in the convex hull of several
optimal basic feasible solutions. If your simplex "output" contains
sufficient auxiliary information, you can generate these other
solutions manually.

R.G. Vickson