A-level Mathematics/OCR/D1/Linear Programming

Linear programming is a method for finding the best solution to a problem (optimisation) using straight-line graphs and inequalities.

Example of a linear programming problem

A factory makes two types of chair, Type A and Type B. The factory makes a profit of £10 on Type A and £10 on Type B. Type A requires 20 man-hours and Type B requires 30 man-hours. Each chair of Type A needs 3m² of wood; each of Type B needs 5m². Given that 400 man-hours and 50m² of wood are available each week, how many chairs of each type should be made each week to maximise the factory's profit?

The graph method

One way to solve this is to set up a graph with a and b on the axes, then plotting a line to represent each of the constraints as an inequality. This should result in a feasible region which is the area where all the constraints are met. The best solution to the problem will be at one of the vertices of this region.

The Simplex method

First we need to represent the problem by linear equations. We will call the number of Type A chairs manufactured a, and the number of Type B chairs manufactured b. We can then see that:

${\begin{aligned}20a+30b\leq 400\Rightarrow &2a+3b\leq 40\\&3a+5b\leq 50\\&a\geq 0\\&b\geq 0\end{aligned}}$

These are called the constraints of the linear programming problem. The function to be maximised (called the objective function) is:

$P=10a+10b\,$

P represents the profit with given values of a and b. To use the Simplex method we have to convert the constraints and objective function into the following format:

${\begin{aligned}P-10a-10b=0\\2a+3b+s=40\\3a+5b+t=50\end{aligned}}$

The variables s and t are called slack variables. They allow us to represent the amount of leeway we have before we hit the maximum of that constraint. It also mean we no longer have to use an inequality. We set up an initial 'tableau' with all the coefficients of the variables for each equation, and the final row is the right-hand side of each equation, as follows:

${\begin{matrix}P&a&b&s&t&=\\1&-10&-10&0&0&0\\0&2&3&1&0&40\\0&3&5&0&1&50\end{matrix}}$

Once you have set up the tableau, you follow the Simplex algorithm:

1. Considering any column that has a negative number on the top row, do the value in the last column divided by the positive value in the same row that is in the column you are considering. In our current example, we see that the a column and the b column have a negative value on the top row. We decide, arbitrarily, to consider column a, so we would do:

${\frac {40}{2}}=20$

${\frac {50}{3}}=16{\frac {2}{3}}$

We now select the value 3 from column a, because it gave us the least value when we divided 50 by it. 3 is now called the pivot.

2. Divide the entire row that the pivot belongs to by the pivot.

3. Now we need to reduce the value of a in the other two rows to 0. We must do this by adding or subtracting a constant multiple of the row with the pivot.

4. If any negative numbers persist in the top row, we have to repeat the algorithm.

See also

• Operations Research/The Simplex Method