The bakery problem: formulation

Translating a practical problem such as the bakery problem into the mathematical notation using the technique called linear programming is known as formulating the problem. Formulation is a specific example of mathematical modelling, similar to how we modelled the GigaFibre network expansion problem as a graph.

In this step we will look at the process of formulating the bakery problem.

Identifying variables

The first, and possibly the most important, step in the formulation of a linear program is to identify the variables which are to be used. Sometimes these variables are called decision variables. Variables are quantities that we are able to change when coming up with an optimum solution.

In the bakery problem the variables are the amount of each type of bread. The formulation of the bakery problem will thus have two variables.

Let (x) be the number of kilograms of Bread A which are to be produced, and let (y) be the number of kilograms of Bread B which are to be produced.

Modelling constraints

A constraint in a linear program is a restriction that is placed on the decision variables of a mathematical model, based on the requirements and limitations of the problem being addressed. Constraints can be expressed as equalities or inequalities, and they can be specified in terms of linear equations or linear inequalities.

The objective of the linear program is to find the values of the decision variables that satisfy all the constraints while optimising the objective function. The objective function defines the goal of the linear program – in the case of the bakery, the objective function is the amount of Bread A and Bread B it should make to maximise profit.

In the bakery problem there are 5 constraints; 3 of them are the amount of wholemeal flour, spelt flour and strong white flour (we’ll come back to the other two later in this step).

Let’s take each type of flour in turn:

Constraint 1: wholemeal flour

Any solution to the problem can’t use more than 50 kg of wholemeal flour as that is all the wholemeal flour that is available to the bakery. This constraint limits the values that the decision variables can have. The constraint can be modelling by the following inequality.

(0.2x+0.5y≤50)

This inequality captures the idea that whatever values the variables 
(x) and (y) have, when we add the amount of wholemeal flour used by Bread A and Bread B, it can’t exceed 50 kg.

Constraint 2: spelt flour

Similarly, any solution to the problem can’t use more than 30Kg of spelt flour as that is all the spelt flour that is available to the bakery. This constraint limits the values that the decision variables can have. The constraint can be modelling by the following inequality.

(0.2x+0.2y≤30)

This inequality captures the idea that whatever values the variables 
(x) and (y) have, when we add the amount of spelt flour used by Bread A and Bread B, it can’t exceed 30 kg.

Constraint 3: strong white flour

Now the strong white flour; any solution to the problem can’t use more than 100Kg of strong white flour as that is all the strong white flour that is available to the bakery. This constraint limits the values that the decision variables can have. The constraint can be modelling by the following inequality.

(0.6x+0.3y≤100)

As before, this inequality captures the idea that whatever values the variables (x) and (y) have, when we add the amount of strong white flour used by Bread A and Bread B, it can’t exceed 100kg.

Constraints 4 and 5: weight of flour must be more than or equal to 0kg

There are also two, sneaky, implicit constraints which we need to model. It is assumed in the problem that the number of kilograms of Bread A must be greater than or equal to zero. That is, we can’t make a negative amount of Bread A. And likewise for Bread B, we can’t make a negative amount of Bread B so we assume that the number of kilograms of Bread B must be greater than or equal to zero. These two constraints can be modelled by the following inequalities.

(x≥0)

(y≥0)

Notice that any value oF (x) and (y) which satisfy the 5 inequalities are a potential solution to the bakery problem.

Each of these constraints are linear constraints. We will go into this in more detail a little later, but they are called linear because if we plot them on a graph then they are straight lines.

Defining the objective function

In the bakery problem we are asking to find the best plan for producing bread. We would like to maximise the amount of turnover. We need a way of capturing the turnover by making a certain amount of Bread A and Bread B. This is captured in something called the objective function.

An objective function in linear programming is a mathematical expression that defines the goal of the optimisation problem. It is the function that is to be maximised or minimised subject to the constraints of the problem. The objective function is a linear function of the decision variables in the problem, and it represents the quantity that the linear program is trying to optimise. The objective function is typically represented as a linear combination of the decision variables, with coefficients representing the relative importance of each variable in achieving the objective.

The linear programming problem then becomes the task of finding the values of the decision variables that maximise (or minimise) the objective function subject to the constraints of the problem.

In the bakery problem we would like to maximise the amount of turnover. We can make a mathematical expression that calculates the amount of turnover we would expect to have when we know how much Bread A we are going to make and how much Bread B we are going to make.

The turnover can be calculated as the summation of the product of the amount of Bread A and the cost per kilogram of Bread A and the product of the amount of Bread B and the cost per kilogram of Bread B. This can be expressed in the following expression. Let use say that 
(T) is the turnover. Then,

(T=1.5x+3y .)

Recalled that Bread A sells for £1.50 per 1Kg loaf, and that Bread B sells for £3.00 per 1Kg loaf.

If we put the previous steps together we have a concise mathematical description of the bakery problem. The formulation of the bakery problem can be written thus:

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})

In summary, to formulate a linear program, follow these general steps:

1. Identify the decision variables: These are the variables that you want to optimise. For example, if you want to optimise the production of two products, your decision variables might be the quantities of those two products.
2. Establish the constraints: These are the limitations or restrictions that you must consider when optimising the objective function. Constraints should also be expressed as linear functions of the decision variables. For example, if you have a limited amount of raw materials, you might set a constraint on the total amount of each raw material used.
3. Define the objective function: This is the function that you want to maximise or minimise. It should be a linear function of the decision variables. For example, if you want to maximise profits, your objective function might be the total revenue minus the total cost.

It’s important to note that formulating a linear program requires a good understanding of the problem at hand, including the relevant variables, constraints, and objectives. It may also require some trial and error to find the most effective formulation.

Now let’s move on to figure out the solution!