4.3 Algebraic Description of LP Solution

Slack Variables

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

Σj Aij xj ≤ Bi (i = 1, 2, ... m; j = 1, 2, ... n)

This is equivalent to a set of simultaneous equations

Σj Aij xj + ei = Bi

where the variables ei are explicit slack variables.Consider the constraints in section 2.2. These are equivalent to

3 x1 + 5 x2 + e1 = 15 ROW1

2 x1 + x2 + e2 = 4 ROW2

x1 - x2 + e3 = 1 ROW3


Basic and Non-Basic Variables

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 basic variables.

The vertices of the feasible region are given by

Non-basic variables Basic variables

A x1 = x2 = 0 e1 = 15, e2 = 4, e3 = 1

B x2 = e3 = 0 x1 = 1, e1 = 12, e2 = 2

C e2 = e3 = 0 x1 = 5/3, x2 = 2/3, e1 = 20/3

D e1 = e2 = 0 x1 = 5/7, x2 = 18/7, e3 = 20/7

E x1 = e1 = 0 x2 = 3, e1 = 1, e3 = 4

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 binding.

A solution which has been found by the above method is called a basic solution. If it satisfies all the LP constraints (i.e. all basic variables must be non-negative) it is called a basic feasible solution.

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 non-basic variables and non-basic rows. The remaining variables and rows are described as basic. The total number of basic variables and rows in the solution is equal to m, the number of constraints.

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 basis.


The Simplex Method

Because an optimal solution always occurs at a vertex or extreme point of the feasible region, an LP problem can be solved by finding the vertices and comparing their objective function values. However, the number of extreme points can be very large and it would be impractical to examine all of them in the search for the best solution. The Simplex Method is a more efficient technique for finding the optimal solution. It starts from one possible solution and moves through a sequence of adjacent vertices, which are chosen with the aim of improving the objective function value at each step.

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 pivoting.

When no more improvements to the objective function are possible, the solution is optimal.

previous contents next

Comments