Total cost = 0.48 + 0.56 + 38
= 1.42
= £1.42
The cost of one fruity pie will be:
(300/50)*12 = 72
= 72p for apples
(20/100)*56 = 11.2
= 11.2p for pastry
(30/20)*19 = 28.5
= 28.5p for pastry
The total cost of a fruity pie = 0.72 + 0.112 + 0.285
= £1.117
= £1.12 to the nearest whole pence
Objective function:
The selling prices for the pies will be:
£2.69 for sweet pies
£3.39 for fruity pies
The profit will then be:
£1 for every sweet pie sold
£2 for each fruity pie
Summary
In table form:
Algebraically
Let x = sweet pie
Let y = fruity pie
The following constraints can be formed:
Apple constraint
200x + 300y ≤ 1000
simplified to 2x + 3y ≤ 10
Honey constraint
100x + 200y ≤ 250
simplified to 10x +2y ≤ 25
Pastry constraint
40x + 30y ≤ 120
simplified to 4x + 3y ≤ 12
Transportation constraint
y ≤ 3
Profit line (objective function) x + 2y
There are also two trivial constraints:
x ≥ 0
y ≥ 0
The problem can than be summarised as:
Maximise x + 2y
Subject to:
2x + 3y ≤ 10
10x +2y ≤ 25
4x + 3y ≤ 12
y ≤ 3
and by x ≥ 0 and y ≥ 0 which are considered trivial constraints
Graph (see graph 1 at end of investigation)
The optimum solution for this problem must be at the vertices of the feasible region, of which there is six possibilities, five of which could be the most profitable solution (the origin is clearly not the optimum solution as nothing would be made). This point must also be the furthest away from the origin. The objective function ensures that the optimum solution will be at point B, the estimated coordinates of (0.4 , 3). Because this is an integer problem, this solution will not be the real world answer, as you cannot sell 0.4 of a pie to the public. This would then be called the linear programming solution, and not the integer solution.
We can solve via simultaneous equations to find the exact location of each of the points
Vertex A: where y = 3 meets x = 0
So the coordinates will be (0 , 3)
Vertex B: where y = 3 meets 2x + 3y = 10
2x + (3*3) = 10
2x = 10-9
2x = 1
x = ½
therefore coordinates of B are ( ½ , 3 )
Point C: where 2x + 3y = 10 meets 4x + 3y = 12
2x = 10 – 3y
x = (10 – 3y)/2
4*[(10 – 3y)/2] + 3y = 12
20 – 6y + 3y =12
20 – 3y = 12
8 = 3y
8/3 = y
substituted into 2x + 3y = 10
2x + (3*8/3) = 10
2x + 8 = 10
2x = 2
x = 1
coordinates of C are ( 1 , 8/3 )
Point D: where 10x + 2y = 25 meets 4x + 3y = 12
10x + 2y =25
2y = 25 – 10x
y = (25 – 10x)/2
4x + 3(12.5 – 5x) = 12
4x + 37.5 – 15x =12
37.5 –11x = 12
25.5 = 11x
2.3181 = x
51/22 = x
substituted into 10x + 2y = 25
(10*2.3181) + 2y = 25
23.18 + 2y = 25
2y = 1.81
y = 0.90
y = 10/11
coordinates of D are ( 51/22 , 10/11 )
Point E: where 10x + 2y = 25 meets y = 0
10x + (2*0) = 25
10x = 25
x = 2.5
coordinates of E are ( 5/2 , 0 )
Substituting these values into the objective function (x + 2y) which will give the profit:
Profit
Vertex A 0 + (3*2) = 6
B ½ + (3*2) = 6.5
C 1 + (8/3*2) = 6.3
D 51/22 + (10/11*2) = 4.136
E 2.5 + 0 = 2.5
From this we can calculate that the most profitable linear programming solution is at vertex B, coordinates ( ½ , 3 ). This will create half a sweet pie and 3 fruity pies. This gives a profit of $6.50. However, as stated previously, it will not be practical to sell half a pie, so the real world solution requires an integer search to be carried out.
Integer Search
There are 3 points that are closest to the vertex B at:
Vertex p at ( 0 , 3 )
q at ( 0, 2 )
r at ( 1 , 2 )
Substituting these values into x + 2y (the objective function) gives:
at point p a profit of:
0 + (3*2) = 6
at vertex q a profit of:
0 + (2*2) = 4
at point r a profit of:
1 + (2*2) = 5
Therefore the most profitable real world solution is at point P, coordinates ( 0 , 3 ) giving a profit of £6. This requires making no sweet pies and three pies.
Conclusion
From this investigation we can conclude that the optimum integer solution is at ( 0 , 3 ), which creates three fruity pies and no sweet pies for a profit of £6. However the linear programming solution is at ( ½ , 3 ) which would create half a sweet pie and three fruity pies giving a profit of £6.50. This solution is not used because this is an integer problem and half is not an integer.
Slack Variables
We can introduce slack variables to determine exactly how much of each of the key ingredients are wasted when producing three fruity pies.
The constraints would now be:
2x + 3y + S1 ≤ 10
10x + 2y + S2 ≤ 25
4x + 3y + S3 ≤ 12
For the integer solution, coordinates ( 0 , 3 ), the slack would be:
(2*0) + (3*3) + S1 = 10
S1 = 10 – 9
S1 = 1
(10*0) + (2*3) + S2 = 25
S2 = 25 – 6
S2 = 19
(4*0) + (3*3) + S3 = 12
S3 = 12 –9
S3 = 3
Therefore the full coordinates of the integer solution are ( 0 , 3 , 1 , 19 , 3 ). This shows that there is a lot of slack in terms of honey left over and a bit of pastry and apples (19*10 = 190g of honey, 3*10 = 30g of pastry and 1*100 = 100g of apples).
We must also check the slack at the optimum solution:
(2*1/2) + (3*3) + S1 = 10
S1 = 10 – 10
S1 = 0
(10*1/2) + (2*3) + S2 = 25
S2 = 25 – 11
S2 = 14
(4*1/2) + (3*3) + S3 = 12
S3 = 12 – 11
S3 = 1
From this we can see that the full coordinates point B, the optimum solution are ( ½ , 3 , 0 , 14 , 1 ). There is some honey left over and a little pastry (14*10 = 140g of honey and 1*10 = 10g of pastry). We can also see that the apple constraint is a tight constraint and makes effective use of all the available resources to finalise a product.
Refinements
It has been discovered that the total amount of ingredients used is in fact less than what was stated. The total weight of apples took into account the parts of the apple that were thrown away such as the apple cores. The recipe does not state this, instead it states the weight of usable fruit in its description for both constraint will have to be adjusted sweet and fruity pies. It is estimated that twenty per cent of the apple is thrown away. The constraint will have to be adjusted accordingly. In addition, the amount of honey available is different to what was stated, as some of it remains stuck inside the jar, ten per cent was not used. Some pastry is also wasted as it sticks to the inside of the packet where approximately ten per cent is left inside it and is thrown away.
The constraints will have to be reformed as:
2x + 3y ≤ 8
10x +2y ≤ 22.5
4x + 3y ≤ 10.8
Graph (see graph 2 at end of investigation)
From the graph we can now see that the transportation constraint has now become a redundant variable as the other constraints have become tighter. This constraint is no longer effective as there are not enough ingredients to “push through” it and break it.
These constraints will alter the size of the feasible region so it is possible that the optimum solution will change. It will then be necessary to input the coordinates of the optimum solution into the new constraints to check that it is still a viable answer.
Maximising Profit
We already know that the most profitable solution, the linear programming solution, was at ( ½ , 3 ) and this gave a profit of £6.50. The full coordinates of this solution were ( 0 , 3 , 1 , 19 , 3 ).
When enter the x and y values into the new constraints, they should return true, otherwise we will have to search for a new solution.
Apple constraint
(2*1/2) + (3*3) ≤ 8
1 + 9 ≤ 8
10 ≤ 8
This constraint has been broken
Honey constraint
(10*1/2) + (2*3) ≤ 22.5
5 + 6 ≤ 22.5
11 ≤ 22.5
This constraint is still true
Pastry constraint
(4*1/2) + (3*3) ≤ 10.8
2 + 9 ≤ 10.8
11 ≤ 10.8
This constraint is false
The old optimum solution is no longer true. When looking at the graph, we will have to search for another optimum solution. The objective function ensures this to be at the intersection of the apple constraint and the trivial constraint of x ≥ 0.
By solving these equations simultaneously:
x = 0
2x + 3y = 8
(2*0) + 3y = 8
3y = 8
y = 8/3
Therefore the coordinates of the new optimum solution will be ( 0 , 8/3 )
We must then calculate profit using the objective function:
x + 2y
0 + (2*8/3) = £5.33
The original optimum solution was incorrect but it is not known whether the original integer solution was still correct.
Apple constraint
(2*0) + (3*3) ≤ 8
0 + 9 ≤ 8
9 ≤ 8
This constraint has been broken
Honey constraint
(10*0) + (2*3) ≤ 22.5
0 + 6 ≤ 22.5
6 ≤ 22.5
This constraint is still true
Pastry constraint
(4*0) + (3*3) ≤ 10.8
0 + 9 ≤ 10.8
9 ≤ 10.8
This constraint is still true
This solution is no longer true as it would break the apple constraint.
Integer Search
As the original integer solution to the equation is no longer true, we will have to carry out an integer search of the surrounding area. There are two possible integers that could give the most profit, point s at ( 0 , 2 ) and point t at ( 1 , 2 ). We will then calculate the profit using x + 2y:
Point s:
0 + (2*2) = 4
= £4 profit
Point t:
1 + (2*2) = 5
= £5 profit
As a result of integer search the real world solution to this refined problem is now at the coordinates ( 1 , 2 ) which will give a profit of £5.
Slack Variables
We can now calculate the slack variables for both the new optimum solution and the new integer solution.
The constraints would now read as:
2x + 3y + S1 ≤ 8
10x + 2y + S2 ≤ 22.5
4x + 3y + S3 ≤ 10.2
At the optimum solution the slack would be:
(2*0) + (3*8/3) + S1 = 8
0 + 8 + S1 = 8
S1 = 0
(10*0) + (2*8/3) + S2 = 22.5
0 + 16/3 + S2 = 22.5
S2 = 17.16
(4*0) + (3*8/3) + S3 = 01.2
0 + 8 + S3 = 10.2
S3 = 2.2
The full coordinates of the optimum solution are:
( 0 , 2.33 , 0 , 17.16 , 2.20 )
At the integer solution the slack would be:
(2*1) + (3*2) + S1 = 8
1 + 6 + S1 = 8
S1 = 1
(10*1) + (2*2) + S2 = 22.5
10 + 4 + S2 = 22.5
S2 = 6.5
(4*1) + (3*2) + S3 = 10.2
4 + 6 + S3 = 10.2
S3 = 0.2
The full coordinates of the integer solution are:
( 1 , 2 , 1 , 6.5 , 0.2 )
Conclusion
Upon investigation of the original solutions of the investigation, it was found that the apple constraint was tight at the optimum solution with no apples left over, with a little slack on the integer solution. After refinements, the transportation constraint was no longer used, as it had become redundant. In addition it was found that the original solutions were no longer viable as they had burst the apple constraint in both optimum and integer solutions. The new optimum solution was found to be at ( 0 , 2.33 , 0 , 17.16 , 2.20 ) with no slack for apples, a lot of slack for honey and a little slack in terms of pastry. This optimum solution gave a profit of £5.33. However, as stated previously, this cannot be the real world solution as this is an integer problem. After an integer search, the final solution was found to be at ( 1 , 2 , 1 , 6.5 , 0.2 ). This gave some slack in terms of honey, much less than the optimum solution, and very little slack in terms of apples or pastry. This solution gave a profit of £5.00 exactly, by making one sweet pie and two fruity pies.
Extensions
This project could be extended by creating a production line in which the optimum solution would represent the ratio of sweet pies to fruity pies. Currently this project is intended as a one off, to benefit a charity fete. The ratio could be scaled up to create integer values, using the values obtained would create eight fruity pies and zero sweet pies. However the amount of ingredients would also have to be scaled up accordingly. In addition, this would require the additional constraints of time and labour costs.
There are other uses for linear programming, such as organising a production line effectively. For example, if there were a set number of parts available for different type cars, linear programming could help to decide the ratio of cars to be made. Another example would be in the production of two different types of lemonade produced using the same key ingredients, which could provide the best number of each type of drink to be produced.
