Introduction to the Simplex Algorithm

The graphical method of solving linear programming problems is only suitable for problems with two variables, because the constraints, written in terms of the two variables, can be plotted on a set of axes on a piece of paper. If there are more than two variables, the constraints cannot be so plotted.

In this case, the simplex algorithm must be used. This is an algebraic method of finding the maximum (or minimum) of a linear function of variables subject to linear constraints on those variables.

Before the simplex algorithm can be used, the problem must be written in the right form.

The constraints must be written in one of the formsor(for three variablesCorresponding inequalities apply for problems with more than three variables).

Write the objective function in a form which is to be maximised.

Add slack variables to convert the inequalities representing the constraints into equations.

Write the inequalities and objective function in the form of a table called the initial tableau.

The system is then solved by a system of row operations to give optimal values, if possible, of the variables – those values of the variable which maximise (or minimise) the objective function.

Example: Maximisesubject to the constraints

Introducing slack variablesandinto the first two inequalities gives

The objective function is written as

The initial tableau is then

Value

0

1

2

3

1


9

0

3

4

2

0

1

12

1

-1

-4

-2

0

0

0

Add comment

Security code
Refresh