Explaining the bakery problem solution using the graphical method

In the previous video, you saw how we solved the bakery problem. This step explains the process of the graphical method in detail:

The formulation devised earlier for the bakery problem was:

Maximise (T = 1.5x + 3y)

Subject to (begin{cases} begin{align*}  0.2x + 0.5y &leq 50 \ 0.2x + 0.2y &leq 30 \ 0.6x + 0.3y &leq 100\ x &geq 0\ y &geq 0. end{align*} end{cases})

The aim is to maximise the objective function (1.5x + 3y) If any point in the feasible region is selected then the turnover can be calculated by substituting the (x) and (y) value into the objective function. For example, if the point (x=50) and (y=50) is selected, this point is within the feasible region. The turnover for this solution is calculated by substituting the (x) and (y) values into the objective function.

(T = 1.5x + 3y)

(T = 1.5times 50 + 3 times 50)

(T = 75 + 150)

(T = 225)

Can there be better than 255? Consider where all of the points within the feasible region are that have a turnover value of 225. All of these points sit on the line (1.5x + 3y = 225). This line is shown in the diagram below. If you substitute the (x) and (y) values of any point on this line into the objective function it will evaluate to 225.

View the full size version of the feasible region with T = 255

If any point in the feasible region is selected then the turnover can be calculated by substituting the (x) and (y) values into the objective function. For example, select the point (x=60) and (y=60). This point is within the feasible region. The turnover for this solution is calculated by substituting the (x) and (y) value into the objective function.

(T = 1.5x + 3y)

(T = 1.5times 60 + 3 times 60)

(T = 90+ 180)

(T = 270)

When (x =60) and (y=60) the value of the objective function is 270. The line with all of the points where the objective function evaluates to 270 are on the line (1.5x + 3y = 270). This line has the same gradient as (1.5x + 3y = 225) only it is further away from the origin. 

View the full size version of the feasible region with T = 270

Using this observation, a solution which optimises the objective function must be on a line parallel to (1.5x + 3y = 270) only it should be the furthest away from the origin whilst still having points which are within the feasible region. This shows that a point which maximises the objective function will be found at a vertex of the feasible region. In this context a vertex is a point where two lines intersect (cross over).

Solving the bakery problem

By drawing a set of parallel lines, where each line is a line of equal turnover, you will be able to identify which vertex maximises the objective function. 

So, one approach to solving the bakery problem is to draw a set of parallel lines which get progressively further away from the origin, where each line is a line of equal turnover. The vertex furthest away from the origin will provide the best solution to the problem. This method is called the graphical method as it uses graphs to identify the vertices.

Alternatively, it is possible to find the vertices by solving pairs of simultaneous equations and then substituting these points into the objective function to determine which yields the most turnover.

Next step

How have you found the graphical method as a way to solve the bakery problem? You’ll have the chance to discuss this with your fellow learners in the next step.

A full text description of the images used in this step is available below:

Explaining the bakery problem solution using the graphical method – image description