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 forms
or
(for three variables
Corresponding 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: Maximise
subject to the constraints
Introducing slack variables
and
into 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 |
