The bakery problem solution: the feasible region

The previous step showed how to construct a mathematical formulation of the bakery optimisation problem. In this step you will learn how to use this formulation to find the best solution to the bakery optimisation problem.

A solution to the problem is feasible if it satisfies all of the constraints which are part of the formulation. There will be potentially an infinite number of feasible solutions but we would like to find an optimal solution, that is, a solution which minimises/maximises the objective function.

Using graphs to find the optimal solution

Each of the constraints that have been extracted from the problem can be drawn on a graph. Consider the first constraint defined in the formation:

(0.2x+0.5y≤50.)

This can be rearranged into the equation form of a line. A line on a graph can be written as (y=mx+c) where (m) is the gradient of the line (how steep the line is) and (c) is the value which the line crosses the (y) -axis. When (0.2x+0.5y≤50) is rearranged to make (y) the subject of the equation you get (y ≤ 100-0.4x) The gradient of this line is (-0.4) and it crosses the (y) -axis at (100). A negative gradient indicates that the line slopes from the top left to the bottom right when drawn out. 

When the constraint is drawn as a graph the result is the line in the following illustration. The constraint is an inequality meaning that it uses the (≤,≥) (<) or (>) symbols. In this case it is the (≤) less than or equal to symbol. 

Any point on the graph below or on the line marked as (0.2x + 0.5y ≤ 50)will satisfy the constraint. For example, the point (x=50), and (y=50) is within the region of the graph below or on the line. If these values are substituted into the constraint equation it is satisfied.

Substituting (x=50) and (y=50) into (0.2x+0.5y≤500), results in:

(0.2times 50 + 0.5 times 50 leq 50)

(10 + 25 leq 50)

(35 leq 50), 35 is less than or equal to 50 so the constraint is satisfied when (x=50) and (y=50).

Any point above the line, in the shaded region will not satisfy the inequality. For example, (x=200), and (y=100) is within the shaded region. If these values are substituted into the constraint equation it is clear that the inequality is not satisfied.

Substituting (x = 200) and (y =100) into (0.2x + 0.5y leq 50) results in:

(0.2times 200 + 0.5 times 100 leq 50)

(40 + 50 leq 50)

(90 leq 50) 90 is not less than or equal to 50 so the constraint is not satisfied when (x=200) and (y=100).

View the full size version of the first constraint

The second constraint is:

(0.2x + 0.2y leq 30)

This can be rearranged to make (y) the subject of the equation to get (y leq 150-x) The gradient of this line is (-1), and it crosses the (y) -axis at (150). Any point on the graph below or on the line marked as (0.2x + 0.2y leq 30) will satisfy the constraint. For example, the point (x=50), and (y=100) is within the region of the graph below or on the line. If these values are substituted into the constraint equation it shows that it is satisfied.

Substituting (x = 50) and (y =100) into (0.2x + 0.2y leq 30) results in:

(0.2times 50 + 0.2 times 100 leq 30)

(10 + 20 leq 30)

(30 leq 30), 30 is less than or equal to 30 so the constraint is satisfied when (x=50) and (y=100). Notice that the point and (x=50) and (y=100) is on the line on the graph below. When a point is on the line then the left hand side and the right hand side of the inequality will be equal. At this point the solution is optimised with respect to that constraint.

View the full size version of the second constraint

Any point above the line, in the shaded region will not satisfy the inequality. For example, (x=150), and (y=100) is within the shaded region. If these values are substituted into the constraint equation it shows that the inequality is not satisfied.

Substituting (x = 150) and (y =100) into (0.2x + 0.2y leq 30) results in:

(0.2times 150 + 0.2 times 100 leq 30)

(30 + 20 leq 30)

(50 leq 30), 50 is not less than or equal to 30 so the constraint is not satisfied when (x=150) and (y=100).

The third constraint (0.6x + 0.3y leq 100) can be rearranged to make (y) the subject of the equation to get (y leq 333.33 – 2x). The gradient of this line is (-2), and it crosses the (y) -axis at (333.33). Any point on the graph below or on the line marked as (0.6x + 0.3y leq 100) will satisfy the constraint. For example, the point (x=50), and (y=200) is within the region of the graph below or on the line. If these values are substituted into the constraint equation it shows that it is satisfied.

Substituting (x = 50) and (y =200) into (0.6x + 0.3y leq 100) results in:

(0.6times 50 + 0.3 times 200 leq 100)

(30 + 60 leq 100)

(90 leq 100), 90 is less than or equal to 100 so the constraint is satisfied when (x=50) and (y=200). Notice that the point and (x=50) and (y=200)is relatively close to the line and there is relatively little difference between 90 and 100. The closer the point is to the line the less difference there will be between the constraint and the calculated value.

View the full size version of the third constraint

Any point above the line, in the shaded region will not satisfy the inequality. For example, (x=200), and (y=200) is within the shaded region. If these values are substituted into the constraint equation it shows that the inequality is not satisfied.

Substituting (x = 200) and (y =200) into (0.6x + 0.3y leq 100) results in:

(0.6times 200+ 0.3 times 200 leq 100)

(180 + 60 leq 100)

(240 leq 100), 240 is not less than or equal to 100 so the constraint is not satisfied when (x=200) and (y=200).

The fourth constraint stated that a negative amount cannot be made of Bread B, that is (y geq 0).

View the full size version of the fourth constraint

The fifth constraint stated that a negative amount cannot be made of Bread A, that is (x geq 0).

View the full size version of the fifth constraint

When the constraints and their graphical representation are considered, it can be observed that if a point is to satisfy all of the conditions, that it must be in the unshaded region when all of the constraints are represented on the same set of axis. The graphical representation below contains each of the constraints drawn on the same set of axis. There is a region in the graphical representation which is not shaded. This region is called the feasible region. Any point within this region will satisfy all of the constraints. Any point outside of this region will violate at least one of the constraints and therefore is not a solution to the problem.

View the full size version of all the constraints

The next important question that will be considered in the next step is how do we find the point within this feasible region that maximises the objective function?

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

The feasible region – image full text description