Exercises: Optimisation problems using linear programming

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.

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.

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.

The organisers of a neighbourhood music festival order t-shirts ($x$) and tote bags ($y$) to sell at the market. The budget is $600\ \text{€}$: each t-shirt costs $8\ \text{€}$ and each bag, $3\ \text{€}$. The supplier cannot supply more than $150$ units in total. The profit from sales is $5\ \text{€}$ per t-shirt and $3\ \text{€}$ per bag.

• a) Formulate the constraints.

• b) Determine the order that maximises the profit and calculate this profit.

An artisan bakery makes tuna pies ($x$) and vegetable pies ($y$), whose production data are summarised in the figure.

The constraints are the available dough, $2x + 3y \leq 60$, and the baking trays, $x + y \leq 25$. The profit is $3\ \text{€}$ per tuna pie and $4\ \text{€}$ per vegetable pie.

• a) Write the complete system of constraints.

• b) Draw the feasible region and find its vertices.

• c) Calculate the production that maximises profit and interpret the result.

An animal shelter prepares bags of feed by mixing two ingredients, A ($x$ kg) and B ($y$ kg). Each bag must contain at least $30$ units of protein (ingredient A provides $3$ per kg and B, $2$ per kg) and at least $12$ units of fibre (each kg of either ingredient provides $1$). Ingredient A costs $2\ \text{€}$ per kg and B, $1,5\ \text{€}$ per kg.

• a) Formulate the constraints (use $F(x, y) = 4x + 3y$ as cost in half euros).

• b) Find the vertices of the feasible region.

• c) Determine the composition of the bag with minimum cost.

True or false, justifying your answer: "In a linear programming problem with a unique optimal solution $(12, 8)$, that point is necessarily a vertex of the feasible region."

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.

Marcos manages a small catering company in Toledo and has to prepare two types of platters for an event: Basic ($x$) and Gourmet ($y$). Each Basic platter requires $20$ minutes of preparation and yields a profit of $8\ \text{€}$. Each Gourmet platter requires $40$ minutes of preparation and yields a profit of $14\ \text{€}$. A maximum of $12$ hours of work ($720$ minutes) is available. In addition, the contract requires that the number of Gourmet platters prepared must be at least twice the number of Basic platters.

Marcos sets up the following model:

From these inequalities he obtains the vertices $(0,0)$, $(36,0)$, and $(24,12)$, and concludes that the maximum profit is achieved by preparing only $36$ Basic platters and no Gourmet platters, obtaining $288\ \text{€}$.

1. a) Identify and explain the conceptual error Marcos made when translating the conditions of the statement into algebraic language.
2. b) Correct the system of inequalities, sketch the true feasible region approximately, and determine the coordinates of its vertices.
3. c) Calculate the actual optimal solution by evaluating the objective function and compare the profit obtained with Marcos's erroneous conclusion.

A cooperative oil mill in Jaén packages extra virgin olive oil in two formats: $2$-liter jugs ($x$) and $5$-liter jugs ($y$). Today it has a quota of $600$ liters of oil and a maximum of $180$ empty containers in total in the warehouse. The commercial profit margin is $4\ \text{€}$ for each $2$-liter jug and $9\ \text{€}$ for each $5$-liter jug.

1. a) Before calculating anything, make a reasoned estimate: the small container leaves a margin of $4/2 = 2\ \text{€}$ per liter packaged, while the large one leaves $9/5 = 1,80\ \text{€}$ per liter. At first glance, do you think it will be advantageous to exhaust all the liters by making exclusively $2$-liter jugs to maximize profit? What obstacle could prevent this?
2. b) State the system of constraints, represent the feasible region, and find the coordinates of all its vertices.
3. c) Determine how many jugs of each type must be filled to maximize profit, and calculate that value.
4. d) Check your initial estimate: did the purely intuitive option turn out to be the winner? Explain which constraint acted as the decisive limiting factor.

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:

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 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 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.

A neighborhood carpentry workshop manufactures stools ($x$) and tables ($y$). Each stool requires $30$ minutes of cutting and $60$ of sanding; each table requires $60$ of cutting and $30$ of sanding. The saw can be used for $10$ hours per week and the sander for $11$ hours (write the constraints as $x + 2y \leq 20$ and $2x + y \leq 22$). The profit is $18\ \text{€}$ per stool and $30\ \text{€}$ per table.

• a) State the system of constraints.

• b) Graph the feasible region and find its vertices.

• c) Calculate the weekly production that maximizes profit.

• d) At the optimal solution, which machine has idle time left? Calculate how much.

A student has won a grant of $3.000\ \text{€}$ and wants to divide it between a safe deposit account ($x$ euros, at $4\ \%$ per annum) and a fund with some risk ($y$ euros, at $6\ \%$ per annum). Her family advises her that the amount in the fund should not exceed that in the deposit account.

• a) Formulate the system of constraints.

• b) Find the vertices of the feasible region.

• c) Determine how she should divide the money to maximise annual interest and calculate that interest.

An agricultural cooperative delivers boxes of fruit using small vans ($x$, carrying $40$ boxes) and large vans ($y$, carrying $60$ boxes). It must deliver at least $480$ boxes per day; the warehouse can only accommodate $10$ vehicles loading at the same time, and for long routes at least $2$ large vans are needed (use the constraints $2x + 3y \geq 24$, $x + y \leq 10$, $y \geq 2$). Each small van costs $25\ \text{€}$ per day and each large van $40\ \text{€}$ (work with $F(x, y) = 5x + 8y$).

• a) Represent the feasible region and find its vertices.

• b) Determine the daily fleet of minimum cost and calculate that cost.

A greengrocer buys oranges ($x$ kg) and apples ($y$ kg). It can store at most $400\ \text{kg}$ in total; its supplier requires it to buy at least $100\ \text{kg}$ of oranges, and due to cold room space it cannot buy more than $250\ \text{kg}$ of oranges. The profit is $2\ \text{€}$ per kg of oranges and $1,5\ \text{€}$ per kg of apples. An employee formulates the problem by writing $x + y \geq 400$ and $x \leq 100$.

• a) Find the two errors in the employee's formulation and write the correct system.

• b) Solve the correct problem: how many kg of each fruit maximise the profit?

A hiking club schedules short routes ($x$) and long routes ($y$) each month. Each short route requires $1$ guide and $2$ van hours; each long route, $2$ guides and $3$ van hours. The club has $10$ guides and $18$ van hours per month available. Each short route yields a net income of $150\ \text{€}$ and each long route $240\ \text{€}$ (use $F(x, y) = 5x + 8y$).

• a) Formulate the system of constraints.

• b) Find the vertices of the feasible region.

• c) Determine the monthly schedule for maximum revenue and calculate this revenue.

A transport company in Zaragoza must transport $480$ people to a sports event. To do so, it has two types of vehicles: standard coaches (type A), with a capacity of $60$ seats and a cost of $450\ \text{€}$ per trip; and minibuses (type B), with a capacity of $40$ seats and a cost of $250\ \text{€}$ per trip. The fleet available for that day is a maximum of $8$ type A coaches and $9$ type B minibuses. Furthermore, to reduce emissions in the city center, regulations require that the number of minibuses be at least half the number of standard coaches.

1. a) Model the problem using linear programming: clearly define the decision variables, write the system of inequalities that bounds the constraints, and express the total cost function to be minimized.
2. b) Draw the feasible region in the Cartesian plane and calculate the coordinates of all its vertices analytically.
3. c) Determine how many vehicles of each type should be assigned to minimize the cost while guaranteeing a seat for all attendees. Are there any spare seats in the hired vehicles?
4. d) Interpret the result from an economic point of view: the cost per seat on the large coach is $450/60 = 7,50\ \text{€}$ and on the minibus it is $250/40 = 6,25\ \text{€}$. Explain why the entire service is not covered solely with minibuses.

An agricultural cooperative in Campo de Cartagena has $60$ hectares of irrigated land to plant two winter crops: broccoli ($x$, in hectares) and artichoke ($y$, in hectares). It has a total of $160$ weekly hours of heavy machinery; each hectare of broccoli consumes $2$ hours and each hectare of artichoke consumes $4$ hours. To meet the commitments made with retail chains, it is mandatory to cultivate at least $10$ hectares of artichoke.

The profit per hectare of broccoli is fixed and amounts to $1.200\ \text{€}$, while the profit per hectare of artichoke depends on the weekly wholesale market price and is denoted by the parameter $k$ (in euros per hectare), so that the profit function is $B(x,y) = 1.200x + ky$.

1. a) Represent the feasible region of the problem and calculate the coordinates of all its vertices.
2. b) If the technical team notes that the optimal solution that maximized the cooperative's income was planting exactly $40$ hectares of broccoli and $20$ hectares of artichoke, algebraically deduce the range of values within which the market price $k$ of artichoke fluctuated.
3. c) What practical meaning does the extreme value $k = 1.200\ \text{€}$ have? What happens to the optimal solution of the problem for that specific value?

(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.

A small workshop produces two items with constraints $2x + y \leq 40$, $x + 2y \leq 40$, $x \geq 0$, $y \geq 0$. The second item yields a fixed profit of $10\ \text{€}$ per unit, but the first depends on the market price: $p$ euros per unit, with $p > 0$. The objective function is $F(x, y) = px + 10y$.

• a) Find the vertices of the feasible region.

• b) Show that if $p < 5$, the best option is to manufacture only the second item.

• c) Show that if $p > 20$, the best option is to manufacture only the first item.

• d) What production maximises profit when $5 < p < 20$? And what happens exactly at $p = 5$ and at $p = 20$?

It is desired to prepare bird food by mixing two feeds, A ($x$ kg) and B ($y$ kg). The mixture must contain at least $24$ units of nutrient N1 (A provides $2$, B provides $1$), at least $18$ of nutrient N2 (A provides $1$, B provides $2$) and at least $10$ of nutrient N3 (both provide $1$). Feed A costs $1,2\ \text{€}$ per kg and feed B costs $0,8\ \text{€}$ per kg.

• a) Formulate the system of constraints and verify that the feasible region is unbounded.

• b) Find its vertices (be careful: not all intersections of boundary lines are vertices of the region).

• c) Determine the minimum-cost mixture and calculate that cost.

• d) Explain why in this problem it makes sense to speak of a minimum even though the region is unbounded.

A 3D printer produces chess pieces ($x$) and plant pots ($y$) with constraints $3x + 2y \leq 36$ (grams of filament, in tens), $x + y \leq 15$ (available printing hours, in half-hours) and $x \geq 0$, $y \geq 0$. The profit is $6\ \text{€}$ per chess piece and $4\ \text{€}$ per plant pot.

• a) Find the vertices of the feasible region and evaluate the profit at each of them.

• b) Show that there are infinitely many production amounts that yield the maximum profit and identify the solution segment.

• c) Give three optimal production amounts with integer coordinates.

• d) Explain the relationship between the objective function and the filament constraint that causes this phenomenon.

A charity concert sells general admission tickets ($x$, at $12\ \text{€}$) and premium tickets ($y$, at $25\ \text{€}$), under the conditions summarised in the diagram.

The venue has a maximum capacity of $500$ people; the premium area only accommodates $200$ people, and the organisation has committed to putting at least $100$ general admission tickets on sale.

• a) Formulate the system of constraints.

• b) Represent the feasible region and find its vertices.

• c) Calculate the combination of tickets that maximises revenue and its total amount.

• d) If the local council increases the capacity to $550$ people, by how much does the maximum revenue increase? Solve it and explain why the increase is not proportional to the new capacity.

A sports club orders standard T-shirts ($x$) and technical T-shirts ($y$) from a workshop. The workshop has $40$ hours of tailoring available (each T-shirt takes $1$ hour: $x + y \leq 40$) and $60$ metres of fabric (standard T-shirts use $2$ metres and technical ones use $1$: $2x + y \leq 60$). By agreement with the club, technical T-shirts cannot exceed $60\ \%$ of total production.

• a) Express the percentage condition as a linear inequality in $x$ and $y$.

• b) Find the vertices of the feasible region.

• c) If each standard T-shirt yields $10\ \text{€}$ profit and each technical T-shirt $8\ \text{€}$, determine the production for maximum profit.

• d) Is the percentage constraint active (satisfied with equality) in the optimal solution? Interpret your answer.

A local council wants to plant at least $100$ shade trees ($x$) and $80$ flowering trees ($y$) in a park. Each shade tree costs $80\ \text{€}$ and each flowering tree costs $40\ \text{€}$, and the budget allocation is $6.000\ \text{€}$ (constraint $2x + y \leq 150$).

• a) Formulate the complete system and show that the feasible region is empty.

• b) Calculate the minimum budget that makes the problem feasible while keeping the other data unchanged, and check that with this budget the feasible region consists of a single point.

• c) With a budget of $12.000\ \text{€}$, find the vertices of the region and determine the planting that maximises the total number of trees.

A parent-teacher association (PTA) is organising the school trip and negotiating with a coach company: large coaches ($x$, with $55$ seats, at $400\ \text{€}$) and small coaches ($y$, with $35$ seats, at $300\ \text{€}$). At least $385$ people must travel and the company only has $5$ large coaches available.

• a) Formulate the system of constraints (simplify the seating constraint to $11x + 7y \geq 77$).

• b) Solve the problem as if the variables were continuous: find the vertices and the theoretical minimum cost.

• c) Since the number of coaches must be integers, find the best integer solution and calculate the extra cost relative to the continuous optimum.

• d) Explain why the best integer solution is not obtained simply by rounding the continuous optimal vertex.

A Galician wastewater treatment plant uses two biodegradable agents, X ($x$, in kg) and Y ($y$, in kg), to neutralize chemical discharges. Environmental requirements demand that the following be simultaneously satisfied:

Two independent studies are proposed:

• Study 1: Minimize the cost of treatment, given by $C(x,y) = 30x + 20y$ (in euros).

• Study 2: Maximize the bacterial regeneration index, estimated at $R(x,y) = 4x + 5y$ points.

When solving the exercise, two students disagree on the method to use:

• Lucía states: "The method of evaluating all vertices is universal; it is enough to find the vertices, substitute them, and the highest value will always be the maximum and the lowest the minimum."

• David replies: "In this problem, the method of evaluating only the vertices can lead to a mathematically false conclusion; it is essential to represent the region and rely on the method of level lines and their direction vector."

1. a) Draw the feasible region, calculate its vertices, and classify it with justification as bounded or unbounded.
2. b) Analyze who is right in Study 1 (minimize cost): apply the vertex method and justify why in this case it is indeed legitimate to ensure that the absolute minimum has been found.
3. c) Analyze the debate in Study 2 (maximize regeneration): demonstrate the error Lucía would make if she applied her criterion and use the level lines to justify what the correct answer is regarding the existence of a maximum.
4. d) Summarize: formulate a general criterion that allows a Bachillerato student to decide when it is sufficient to evaluate vertices and when it is mandatory to resort to level lines.

During the seasonal vaccination campaign in a health area of Andalusia, two types of mobile teams are designed: Rapid Team ($x$) and Full Team ($y$).

• Resources available per working day: $60$ nursing professionals and $120$ hours of care vehicles.

• Requirements per team: each Rapid Team requires $1$ nurse and $3$ vehicle hours; each Full Team requires $2$ nurses and $2$ vehicle hours.

• Service requirements: for minimum coverage in isolated rural areas, at least $10$ Rapid Teams and at least $5$ Full Teams must operate. Likewise, to avoid imbalances in care quality, the number of Rapid Teams cannot exceed three times the number of Full Teams, and the number of Full Teams cannot exceed the number of Rapid Teams.

• Performance: each Rapid Team administers $80$ vaccines per day and each Full Team administers $110$ vaccines per day.

1. a) Write the complete system of linear inequalities and determine the coordinates of all the vertices of the feasible region.
2. b) Find how many teams of each type should be deployed daily to maximize the total number of vaccines administered, and calculate this maximum value.
3. c) Sensitivity analysis and bottleneck: the health authority has an extraordinary budget and must choose between only two improvements for the next phase:

• Option 1: Hire $10$ additional vehicle hours (going from $120$ to $130$ hours).

• Option 2: Add $4$ additional nurses (going from $60$ to $64$ professionals).

Without needing to draw the entire region again, calculate the new optimum for each of the two options and explain which of the two resources provides a greater marginal return per additional unit.

Topic challenge. Imagine you are managing the snack stall for the end-of-year school trip. Your goal is to determine how many batches of two types ($x$ and $y$) you should prepare to maximize net profit.

1. Phase 1: Data collection. Check the website of a supermarket in your neighborhood and write down the actual price of two base ingredients (for example, fruit and nuts). Design two different batches with these ingredients and calculate the unit cost of each.

2. Phase 2: Model formulation. Set a maximum available budget of $60$ € and a maximum transportable weight of $12,5$ kg. Formulate the objective function $F(x, y)$ for profit and the system of linear inequalities that includes the constraints for cost, weight, and non-negative stock ($x \ge 0$, $y \ge 0$).

3. Phase 3: Graphical resolution with GeoGebra. Enter the inequalities to delimit the feasible region, calculate the exact coordinates of its vertices, and evaluate the objective function at each of them.

4. Phase 4: Reasoned proposal. Write a brief executive report (one page) that includes the table of vertices, the exported graph, and your justified final recommendation on the optimal distribution.

Assessment criteria:

• Rigor in obtaining real data and formulating the system of inequalities.

• Skill in using GeoGebra to represent the feasible region and identify vertices.

• Correct application of the fundamental theorem of linear programming and interpretation of the solution.

• Clarity of explanation and presentation of the final proposal.