A vertex of the feasible region can be defined by the corresponding values of the decision variables. These values can be determined algebraically. Consider a set of LP constraints of the form
This is equivalent to a set of simultaneous equations
where the variables e
There
are m equations and m + n unknowns (the decision variables and slacks)
in this problem. A solution can be obtained by setting n variables to
zero and finding the values of the remaining m variables. In a
particular solution the variables which are set to zero are called
non-basic variables and the variables for which values are calculated
are called The vertices of the feasible region are given by
Note
that setting a slack variable to zero is the same as stating that its
constraint is one of the boundaries intersecting at the vertex. Such a
constraint is described as A solution which has been found by the above method is called a This
algebraic explanation can be extended to any general LP model. A
solution produced by an LP code always includes a number of decision
variables which are set equal to their upper or lower bounds, and
constraints which are binding. These are called the Note
that the basic variables and rows are the only ones which can have
values away from their limits. (This does not necessarily that the
basic variables cannot have values equal to their limits). The set of
basic variables and rows is called the
Because an optimal solution always occurs at a vertex or To
move from one vertex (basic feasible solution) to another, the Simplex
Algorithm chooses a non-basic variable which would improve the
objective function if its value were moved away from the limit. To
allow this variable to enter the basis one of the previous basic
variables is removed (made non-basic). The process of choosing the
values to be changed is called When no more improvements to the objective function are possible, the solution is optimal. |

LP Training > 4. Interpretation of Results >