sci.op-research

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. But I still don't see why this is necessary a
> corner point.
>
>
Let's assume that the variables (x) are constrained nonnegative and that
the origin is feasible, and you start there. This is typical though not
always the case, but the intuition developed this way should generalize.
The origin is clearly a corner of the feasible region, since the
hyperplanes x_i = 0 intersect there. We'll also assume for simplicity
that the lower bound on all variables is zero. (If variables have
nonzero lower bounds, we'll include those in the constraints.)

Now note that every variable ties to the distance of x from a bounding
hyperplane. For the slack variables, this is obvious (it's their
definition). For a "natural" variable x_i, think of it as the surplus
in the nonnegativity constraint x_i >= 0. (Technically, the distance of
x from the hyperplane a'x <= b is s/||a||, where s is the slack
variable, so the slack is not precisely the distance, but it's
proportional to the distance.) In a basic feasible solution, the
nonbasic variables (which take value 0) tell you which constraints
intersect at x. If the solution is degenerate (some basic variables
equal 0), you have extra constraints intersecting there. Assuming there
are n natural variables, you need at least n independent constraints
intersecting to get a single point, and that happens at basic feasible
solutions.

A simplex iteration can be broken into three parts. First, you choose a
variable to enter the basis (become nonbasic). Since the nonbasic
variables designate the constraints that intersect at x, this variable
matches a constraint hyperplane that contains the current solution x but
(barring degeneracy) will not contain the next solution x'. Now assume
that x is a corner where n hyperplanes with linearly independent normals
intersect. Any n-1 of those hyperplanes intersect in an edge. So
identifying the variable to become basic amounts to identifying an edge
through x along which we will move.

The second part of a simplex iteration is to identify the variable that
will leave the basis (become nonbasic). This variable is associated
with a constraint whose slack will become zero at the next solution,
meaning that x' will lie on this hyperplane. The row ratio test used to
select the exiting variable amounts to calculating which currently
nonbinding constraint first becomes binding.

The third part is the actual pivot, which gets us from x to x'.

So picture starting from a corner x, and sliding down an edge on which x
sits until you slam into another hyperplane, yielding x'. The new
hyperplane transects (does not contain) the edge, since if it contained
the edge it would not stop us. The intersection of an edge and a
transecting hyperplane is obviously a corner. So if x is a corner, x'
will be a corner.

Given that we started from a corner (the origin), and every pivot goes
from a corner to a corner, simplex will always end up at a corner.

That's just an intuitive argument. A more formal proof would
demonstrate that a basic feasible solution must be an extreme point of
the feasible region.

/Paul