Solving the problem - Linear Programming (LP)
To solve a problem, we need to draw the constraint inequality lines on a graph and shade out the areas which do not satisfy each inequality in order to achieve what we call a ‘feasible region’. This region must satisfy each inequality, and each line must be drawn accurately.
Once the graph has been drawn and axes have been labelled, we must find the coordinates of the vertices of the feasible region. Remember that this includes those on the x and y axes. We can do this by solving the equations simultaneously if the drawn graph is inaccurate.
Now we must find the optimal solution. There are two methods for this.
Set the objective function to equal a constant value which will allow it to be plotted on the graph. Draw this line and move a ruler parallel to the line until you reach the edge of the feasible region. The point it touches last (which is inside the feasible region) will be the optimal solution point.
Work out the value of the objective function at each vertex of the feasible region. Make sure you show each one being worked out. Find which satisfies as the optimal solution (e.g. highest value for maximisation or lowest value for minimisation).
We must remember that if the problem requires integer numbers for the values of x and y, then we must only use integer values. If our vertices are not integers, then we should look at points near them and inside the feasible region.
Finally, write the solution in terms of the question.
Example:
We are going to use a worked solution to show this process. Using the example from the "Formulating a problem" section, we achieved the constraints:
2x + 3y ≤ 30
2x + 4y ≥ 20
x ≥ 5
x ≥ 0
y ≥ 0
… and our objective function was:
Maximise P = 3x + y
Once the graph has been drawn and axes have been labelled, we must find the coordinates of the vertices of the feasible region. Remember that this includes those on the x and y axes. We can do this by solving the equations simultaneously if the drawn graph is inaccurate.
Now we must find the optimal solution. There are two methods for this.
- Objective line method
Set the objective function to equal a constant value which will allow it to be plotted on the graph. Draw this line and move a ruler parallel to the line until you reach the edge of the feasible region. The point it touches last (which is inside the feasible region) will be the optimal solution point.
- Vertex method
Work out the value of the objective function at each vertex of the feasible region. Make sure you show each one being worked out. Find which satisfies as the optimal solution (e.g. highest value for maximisation or lowest value for minimisation).
We must remember that if the problem requires integer numbers for the values of x and y, then we must only use integer values. If our vertices are not integers, then we should look at points near them and inside the feasible region.
Finally, write the solution in terms of the question.
Example:
We are going to use a worked solution to show this process. Using the example from the "Formulating a problem" section, we achieved the constraints:
2x + 3y ≤ 30
2x + 4y ≥ 20
x ≥ 5
x ≥ 0
y ≥ 0
… and our objective function was:
Maximise P = 3x + y
Using the ‘objective line’ method – I’ve drawn the objective function on after equalling it to 6. When using a ruler and moving it parallel to the line, the last point it crosses before leaving the feasible region is (15, 0). This means that this is our optimal solution.
We could also draw out a table and use the ‘vertex method’:
We could also draw out a table and use the ‘vertex method’:
There is no use testing the other coordinates as we can visually see that there is a more optimal solution than those – the examiner will allow this common sense.
Again, we can see that the optimal solution is at the point (15, 0), with the highest value (we are solving a maximisation problem).
Now we must write our solution in terms of the question. The example was asking for maximum profit, in £, which can be recorded to two decimal places. (In this case our profit was an integer, so this is not relevant). In words:
Omkar’s profit can be maximised by producing 15 Economics guides and 0 sets of stationery. This results in a profit of £45.
Again, we can see that the optimal solution is at the point (15, 0), with the highest value (we are solving a maximisation problem).
Now we must write our solution in terms of the question. The example was asking for maximum profit, in £, which can be recorded to two decimal places. (In this case our profit was an integer, so this is not relevant). In words:
Omkar’s profit can be maximised by producing 15 Economics guides and 0 sets of stationery. This results in a profit of £45.
