Exercises: Special cases: unique solution, multiple solutions, unbounded or infeasible

The figure shows two feasible regions: that of panel A and that of panel B, as shown in the diagram.

State which of them is bounded and which is unbounded, explaining the criterion you used to decide.

True or false, giving reasons for your answer: "If the feasible region of a linear programming problem is unbounded, the problem never has an optimal solution." Illustrate your reasoning with the example of $F(x, y) = x + y$ in the region $x \geq 0$, $y \geq 0$, $x + y \geq 2$.

The figure shows a feasible region and a level line of the objective function $F(x, y) = 2x + y$ corresponding to the value $8$, as shown in the diagram.

• a) Explain what feature the position of this line presents relative to the region.

• b) State the maximum value of $F$ and give two different optimal solutions.

Plot the lines $x + y = 2$ and $x + y = 5$ and justify, from the drawing, that the system formed by $x \geq 0$, $y \geq 0$, $x + y \leq 2$ and $x + y \geq 5$ has no solution. How do we say in linear programming that the feasible region is empty?

Lucas is dealing with the following linear programming problem: maximize the function $F(x, y) = 3x + 2y$ subject to the constraints $x \geq 0$, $y \geq 0$, and $x + y \geq 4$.

Lucas sketches the feasible region, computes the vertices $A(4, 0)$ and $B(0, 4)$, evaluates the objective function at both ($F(4, 0) = 12$ and $F(0, 4) = 8$), and concludes: “The maximum value is $12$ and it is reached at the point $(4, 0)$”.

1. a) Explain in detail why Lucas's procedure contains a serious conceptual error, describing the geometric shape of the feasible region.
2. b) Formally justify why the function $F(x, y)$ does not have a maximum in this region and propose the coordinates of a feasible point where the value of $F$ is strictly greater than $100$.
3. c) If the problem statement had asked to minimize $F(x, y)$ instead of maximizing it, would Lucas's calculation have been valid to find the optimal solution? Justify your answer, stating the minimum value if it exists.

Consider the closed and bounded feasible region defined by the constraints:

$x \geq 0$, $y \geq 0$, $x + 2y \leq 6$, and $2x + y \leq 6$.

Its vertices are $O(0, 0)$, $A(3, 0)$, $B(2, 2)$, and $C(0, 3)$.

We wish to maximize the objective function $F(x, y) = k \cdot x + 4y$, where $k$ is an unknown real constant.

1. a) Determine the value of the parameter $k$ such that the problem has multiple solutions (infinitely many optimal solutions) that include the vertex $C(0, 3)$.
2. b) For that value of $k$, identify the boundary segment where these solutions are attained and calculate the common maximum value of the function.
3. c) Write down the coordinates of a feasible point with non-integer coordinates that is also an optimal solution to the problem.

Maximise the objective function $F(x, y) = 2x + 4y$ subject to $x \geq 0$, $y \geq 0$, $x + 2y \leq 8$ and $x + y \leq 5$.

• a) Find the vertices of the feasible region and evaluate $F$ at them.

• b) You will notice that the maximum value is repeated at two vertices: explain what this means and write the expression of all optimal points as a line segment.

• c) Give two optimal solutions with integer coordinates.

Let the region be defined by $x \geq 0$, $y \geq 0$, $x + y \geq 3$ and $3x + y \geq 5$.

• a) Verify that it is unbounded and find its vertices.

• b) Determine whether the objective function $F(x, y) = 3x + 2y$ reaches a maximum in the region.

• c) Determine whether it reaches a minimum and, if so, calculate it.

A bakery receives an order for at least $50$ cakes and $40$ Swiss rolls for a week. Each cake requires $2$ hours in the bakehouse and each Swiss roll $1$ hour, and the bakehouse only has $60$ hours per week available.

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

• b) Propose a modification of a single value in the problem statement that makes the problem feasible, and verify it.

Let the unbounded region be defined by $x \geq 0$, $y \geq 0$, $x + 2y \geq 4$ and $2x + y \geq 4$, and let the objective function be $F(x, y) = ax + 2y$ with $a > 0$.

• a) Find the vertices of the region.

• b) Evaluate $F$ at each vertex.

• c) Discuss, depending on the values of $a$, at which point the minimum of $F$ is reached, indicating cases with multiple solutions.

An agricultural cooperative in the Antequera region (Málaga) plans the monthly production of extra virgin olive oil ($x$, in hundreds of liters) and virgin olive oil ($y$, in hundreds of liters). It has the following resource limitations and commercial commitments:

• Maximum bottling capacity: $x + y \leq 50$.

• Available milling hours: $2x + y \leq 80$.

• Minimum supply commitment to a distributor: $x + y \geq 60$.

• Non-negativity conditions: $x \geq 0$, $y \geq 0$.

1. a) Before carrying out any analytical calculation or graphical representation, analyze the constraints $x + y \leq 50$ and $x + y \geq 60$ together. Estimate with reasoning whether the cooperative will be able to find any viable production plan that satisfies all the conditions.
2. b) Check your estimate analytically by analyzing the consistency of the system of inequalities and classify the type of feasible region obtained.
3. c) If the distributor renegotiates its contract and reduces the minimum commitment to $x + y \geq 30$, while keeping the other constraints unchanged, determine whether the problem of maximizing revenue $I(x, y) = 400x + 300y$ comes to have a unique, multiple, or unbounded solution, or if it remains infeasible. Justify your conclusion.

An urgent parcel logistics and distribution company operating between Madrid and the Henares corridor plans its daily fleet using electric vans ($x$) and low-emission diesel vans ($y$).

The operational conditions and environmental agreements are:

• The total number of delivery vehicles cannot exceed $14$ per day ($x + y \leq 14$).

• Due to charging point limitations and permitted emissions, $x + 2y \leq 20$ must be met.

• Due to fixed contractual commitments, at least $2$ electric vehicles ($x \geq 2$) and at least $4$ diesel vehicles ($y \geq 4$) must operate.

The net daily profit generated is estimated at $150$ euros for each electric van and $300$ euros for each diesel van, with the objective function being $B(x, y) = 150x + 300y$.

1. a) Model the feasible region mathematically, determine the coordinates of all its vertices, and verify that it is a bounded polygon.
2. b) Prove analytically that the profit function $B(x, y)$ reaches its maximum value at infinitely many points of the feasible region (multiple solutions). Justify the geometric relationship between the level lines of $B$ and the edges of the region.
3. c) Find all optimal solutions that use an integer number of vehicles of each type. If the management team wishes to maximize profit but, all else being equal, prefers to minimize the overall carbon footprint by using the greatest possible number of electric vehicles, which specific combination should they choose?

A charity festival sells general admission passes ($x$) and passes with camping ($y$). Under the contract with the venue, $2x + 3y \leq 120$ (space units) and $x + y \leq 50$ (capacity) must be met, and the organisers commit to the sponsor to sell at least $12$ general admission passes: $x \geq 12$. The revenue is $F(x, y) = 20x + 30y$ euros.

• a) Formulate the complete system and find the vertices of the feasible region.

• b) Calculate the maximum revenue.

• c) Verify that the maximum is reached at two vertices simultaneously and explain the special relationship between the objective function and one of the constraints.

• d) Give three different integer combinations of passes that produce the maximum revenue.

Show that under the constraints $x \geq 0$, $y \geq 0$, $x + y \leq 4$ and $x + 2y \leq 5$, the objective function $F(x, y) = x + 2y$ reaches its maximum value at infinitely many points in the feasible region.

• a) Find the vertices of the region and the maximum value of $F$.

• b) Identify the line segment of optimal points by writing its endpoints.

• c) Give three different optimal solutions, two of which have integer coordinates.

Consider the system formed by $x \geq 0$, $y \geq 0$, $x + y \geq 6$ and $x + 2y \leq k$, where $k$ is a real parameter.

• a) Represent the situation for $k = 4$, $k = 6$ and $k = 10$.

• b) Determine for which values of $k$ the feasible region is empty, for which it consists of a single point, and for which it has positive area.

Let the unbounded region be defined by $x \geq 0$, $y \geq 0$, $x + y \geq 2$ and $2x + y \geq 2$, and let the objective function be $F(x, y) = x - 2y$.

• a) Find the vertices of the region.

• b) Provide a family of feasible points that shows that $F$ does not reach a maximum.

• c) Provide another family of feasible points that shows that $F$ does not reach a minimum either.

• d) What condition on the coefficients of the objective function and the direction in which the region grows explains this behaviour?

To analyze linear programming problems involving special cases (unbounded regions or multiple solutions), two strategies are commonly proposed:

• Method 1 (Exclusive evaluation of vertices): Find the intersection points of the boundary lines and algebraically evaluate the objective function at them, choosing the highest and lowest values.

• Method 2 (Family of level lines and direction vector): Plot the direction of the objective function's coefficient vector $(a, b)$ and shift the line $ax + by = k$ in the direction of optimization across the feasible region.

Consider the feasible region bounded by:

$x \geq 0$, $y \geq 0$, $x + 2y \geq 6$, $x - y \leq 3$.

1. a) Schematically represent the feasible region, calculate its vertices, and justify why it is an unbounded region.
2. b) We wish to maximize the function $F(x, y) = 2x + y$. If a student mechanically applies Method 1, what erroneous conclusion do they reach? Explain how Method 2 immediately detects that the problem has no finite maximum.
3. c) If we are now asked to minimize the function $G(x, y) = x + 2y$ over that same region, compare the effectiveness of both methods in detecting that the problem has infinitely many optimal solutions (multiple solutions), and write the analytical expression of all points that minimize $G$.

Consider the system of inequalities in the affine plane that defines a feasible region subject to a real parameter $m$:

$x \geq 0$, $y \geq 0$, $x + y \leq 6$, $y - x \leq 2$, $x \geq m$.

The objective function is defined as $F(x, y) = a \cdot x + y$, where $a$ is a real parameter.

1. a) Reasonably determine for which values of the parameter $m$ the problem is infeasible (the feasible region is the empty set).
2. b) Setting the parameter $m = 1$, find the coordinates of the four vertices that bound the resulting feasible polygon.
3. c) Keeping $m = 1$, study what values the parameter $a$ must take in the function $F(x, y) = a \cdot x + y$ so that the problem of maximizing $F$:

• Has multiple solutions, indicating on which edge of the polygon the optimal solutions lie for each value of $a$ found.

• Has a unique solution exactly at the vertex with the highest $y$-coordinate of the region.

1. d) Without modifying the objective function $F(x, y) = x + y$, propose changing a single inequality of the initial system (with $m = 1$) so that the maximization problem becomes unbounded (without a finite optimal solution) and justify why this behavior occurs.

Topic challenge. How can you optimize the energy expenditure of a local business? Take on the role of financial advisor for an artisan bakery and design its baking schedule to minimize energy costs.

1. Real data: Go to the Red Eléctrica website (REE/ESIOS) and note yesterday's average price per $kWh$ during off-peak hours ($x$) and peak hours ($y$), using decimals (for example, $0,09$ €/$kWh$).

2. Modeling and GeoGebra: Define two variables (batches produced during off-peak and peak hours) and establish at least four real constraints (oven capacity, minimum daily demand, and budget). Represent the feasible region in GeoGebra and analytically calculate the coordinates of its vertices, determining the unique optimal solution.

3. Simulation of special cases: Reasonably modify the constraints to generate two alternative scenarios: one with an unbounded (or infeasible) region and another where the objective function parallel to a constraint produces infinitely many solutions (multiple solutions).

4. Executive report: Prepare a brief proposal (one page) with the graph, the table of vertices, the optimal solution, and the interpretation of the simulated special cases.

Assessment criteria:

• Rigor in obtaining data from REE and translating it into the system of inequalities.

• Accuracy in the analytical calculation of vertices and representation of the feasible region in GeoGebra.

• Correct mathematical justification of the analyzed special cases.

• Communicative clarity and consistency of the final proposal.