Optimisation problems with linear programming
A workshop makes two models of backpack with the same two workers and the same workshop hours. How many backpacks of each model should it make to earn as much as possible? This question —sharing out limited resources between two activities to maximise a profit or minimise a cost— is a linear programming problem. You already know how to set up constraints, draw the feasible region and find its vertices; in this section you put all of that together with the objective function, the quantity you want to maximise or minimise, to solve the whole problem from start to finish.
The pieces of a linear programming problem
The school canteen bakery prepares sponge cakes ($x$) and muffins ($y$) for the cultural week, with the data summarised in the figure. There are $40$ eggs and $25$…
The school canteen bakery prepares sponge cakes ($x$) and muffins ($y$) for the cultural week, with the data summarised in the figure.
There are $40$ eggs and $25$ baking moulds available: each sponge cake uses $2$ eggs and each muffin, $1$, and each item requires one mould. The profit is $1\ \text{€}$ per sponge cake and $0,75\ \text{€}$ per muffin (work with the objective function in euro cents, $F(x, y) = 100x + 75y$).
-
a) Formulate the system of constraints.
-
b) Find the vertices of the feasible region.
-
c) Determine how many items of each type maximise the profit and calculate this profit.
The complete method: from the data table to the solution
A textile workshop manufactures city backpacks ($x$) and mountain backpacks ($y$). The table summarises the minutes that each model needs in each department and the…
A textile workshop manufactures city backpacks ($x$) and mountain backpacks ($y$). The table summarises the minutes that each model needs in each department and the available daily minutes:
| Department | City | Mountain | Available |
|---|---|---|---|
| Cutting | $2$ | $3$ | $240$ |
| Sewing | $3$ | $2$ | $210$ |
The profit is $12\ \text{€}$ per city backpack and $15\ \text{€}$ per mountain backpack.
-
a) Formulate the system of constraints.
-
b) Find the vertices of the feasible region.
-
c) Determine the daily production that maximises profit and its value.
A dance school is opening two new levels: beginner ($x$ groups) and advanced ($y$ groups). It only has $8$ weekly time slots available, and each beginner group has $14$…
A dance school is opening two new levels: beginner ($x$ groups) and advanced ($y$ groups). It only has $8$ weekly time slots available, and each beginner group has $14$ students and each advanced group, $10$, with a maximum of $100$ students in total. The monthly fee is $50\ \text{€}$ for beginner and $40\ \text{€}$ for advanced.
-
a) Formulate the constraints.
-
b) Determine how many groups of each level maximise the monthly revenue and calculate the maximum revenue.
Maximising profit or revenue
Maximising problems usually come from a company with limited resources (raw material, working hours, space) that wants to get the best possible economic return.
(Sample exam question.)* A company bottles fresh juice ($x$ litres) and juice from concentrate ($y$ litres). Each litre of fresh juice requires $3$ kg of orange, $1$ kg…
(Sample exam question.) A company bottles fresh juice ($x$ litres) and juice from concentrate ($y$ litres). Each litre of fresh juice requires $3$ kg of orange, $1$ kg of mango and $2$ minutes of bottling line time; each litre of concentrate requires $2$ kg of orange, $2$ kg of mango and $2$ minutes of bottling line time. Daily, there are $120$ kg of orange, $50$ kg of mango and $70$ minutes of line time available (constraints: $3x + 2y \leq 120$, $x + 2y \leq 50$, $x + y \leq 35$). The profit is $4\ \text{€}$ per litre of fresh juice and $5\ \text{€}$ per litre of concentrate.
-
a) Find the vertices of the feasible region.
-
b) Determine the daily production for maximum profit.
-
c) In the optimal production, is there any surplus resource? Calculate the leftover amount of each resource.
In a shared allotment, tomato plants ($x$) and lettuces ($y$) are going to be planted, with the data summarised in the figure. Each tomato plant occupies $1\ \text{m}^2$…
In a shared allotment, tomato plants ($x$) and lettuces ($y$) are going to be planted, with the data summarised in the figure.
Each tomato plant occupies $1\ \text{m}^2$ and each lettuce, $0,5\ \text{m}^2$, and there are $12\ \text{m}^2$ available (write the constraint as $2x + y \leq 24$). The weekly watering is $3$ litres per tomato plant and $1$ litre per lettuce, with a maximum of $30$ litres. The crop value is estimated at $5\ \text{€}$ per tomato plant and $2\ \text{€}$ per lettuce.
-
a) Formulate the system of constraints.
-
b) Calculate the vertices of the feasible region.
-
c) Find the planting combination that maximises the crop value.
Minimising cost
In minimising problems, the constraints are usually of the $\geq$ type (minimums that have to be met: nutrients, places, hours of service), and you look for the vertex with the lowest cost, not the highest. Because of the $\geq$ constraints, the region is usually unbounded upwards, but that does not prevent a minimum from existing.
A sports nutritionist combines energy bars ($x$) and shakes ($y$) for a cyclist's diet. The plan requires a minimum of $60$ units of carbohydrates (each bar provides $4$…
A sports nutritionist combines energy bars ($x$) and shakes ($y$) for a cyclist's diet. The plan requires a minimum of $60$ units of carbohydrates (each bar provides $4$ and each shake $3$) and $30$ units of protein (each bar provides $3$ and each shake $1$). Each bar costs $3\ \text{€}$ and each shake $2\ \text{€}$.
-
a) Formulate the system of constraints and represent the feasible region.
-
b) Find its vertices.
-
c) Calculate the weekly combination of minimum cost that meets the plan.
A school is organising the end-of-year trip and hires $9$-seater vans ($x$) and $18$-seater minibuses ($y$). At least $180$ students must be transported and the company…
A school is organising the end-of-year trip and hires $9$-seater vans ($x$) and $18$-seater minibuses ($y$). At least $180$ students must be transported and the company only has $14$ vehicles available in total. Each van costs $60\ \text{€}$ and each minibus, $150\ \text{€}$.
-
a) Formulate the system of constraints.
-
b) Find the vertices of the feasible region.
-
c) Determine how many vehicles of each type minimise the cost and calculate that minimum cost.
Less obvious constraints
Some problem statements hide a constraint inside a phrase that is not a simple sum or a simple minimum: proportions ("twice as many as", "no more than three times") or relationships between the two variables. You have to translate them carefully before going on.
A local shop organises its Saturday shifts: $x$ employees in the morning and $y$ in the afternoon. It needs at least $4$ employees in the morning and $3$ in the…
A local shop organises its Saturday shifts: $x$ employees in the morning and $y$ in the afternoon. It needs at least $4$ employees in the morning and $3$ in the afternoon; the employment agreement does not allow more than $12$ employees in total, and the afternoon shift cannot have more than twice as many people as the morning shift. The expected sales per employee are $300\ \text{€}$ in the morning and $400\ \text{€}$ in the afternoon.
-
a) Formulate the system of constraints.
-
b) Find the vertices of the feasible region.
-
c) Determine the distribution of shifts that maximises expected sales.
Lab: digital optimisation and sensitivity
A cooperative produces divisible quantities x and y of two mixes. It has constraints $x,y\ge0$, $x+y\le5$ and $2x+y\le8$; the margin is $F=3x+2y$. Draw the four inequalities in a graphing tool. In a spreadsheet with a linear optimiser, reserve two cells for x and y, a third one for =3*x+2*y (replace x and y with their cell references) and others for the constraints. Maximise $F$ by selecting a linear method and the four constraints. Predict the winning vertex first.
The diagram shows the level line that touches the polygon at the optimum:
Change the coefficient 3 of x to c. With $c=1$ the optimum is $(0,5)$; with $c=2$ the whole side from $(0,5)$ to $(3,2)$ is optimal; with $c=5$ the optimum is $(4,0)$. Conjecture the thresholds and prove them by comparing values at the vertices; also check $c=4$. Hand in a table, a graph, the output and the proof.
Alternative algorithm: list pairs of boundaries, solve each system if its determinant is not zero, discard intersections that break constraints and evaluate F at the remaining ones. Modify it to keep all ties and test an empty region. This vertex algorithm on its own only solves the bounded, non-empty case; in unbounded regions you have to study the directions of growth. If the quantities must be whole numbers, add that condition: rounding a continuous solution may break constraints or miss the optimum.