"Special cases: unique solution, multiple solutions, unbounded or infeasible"
So far, every problem you have seen had one clearly winning vertex. But in an EvAU exam you may be given a region where the "tie" between two vertices is the question itself, or a region that looks normal but has no maximum, or a system that has no solution at all. Recognising these special cases —and explaining them, which is what really earns the marks— is just as important as knowing how to calculate vertices.
Unique solution: the usual case
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."…
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$.
Multiple solutions: an entire side is optimal
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…
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.
Unbounded region: there may be no optimum
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…
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.
Infeasible region: the system has no solution
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…
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?
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…
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.