The simplex algorithm is used to find optimal combinations of certain quantities,
subject to constraints on those quantities. Before the algorithm can be used the problem must be suitably expressed, which involves defining the constraint conditions and the objective function which is to be maximised. Each constrain, and the objective function, is a linear combination of the quantities
Suppose a factory produces three types of car A, B and C. The time, money and labour needed to produce each car is shown in the table below.
|
Car |
Time |
Money |
Labour |
|
A |
3 |
3,000 |
6 |
|
B |
5 |
2,500 |
9 |
|
C |
4 |
2,000 |
10 |
|
Total Available |
100 |
90,000 |
150 |
Each car of type A produces £200 profit, each car of type B £350 and each car of type C £150
The total time needed to produce a cars of type A, b cars of type B, c cars of type C is
so
The total money needed to produce a cars of type A, b cars of type B, c cars of type C is
so
The total labour needed to produce a cars of type A, b cars of type B, c cars of type C is
so
Also, of course,
and
The produced on
cars of type A,
cars of type B,
cars of type C is
The simplex algorithm finds values
andthat maximises the profit subject to time, money and labour constraints.