No solution, many solutions and a check with linprog

What you will be able to do

• recognise a problem with no feasible solution;
• recognise a problem with many optimal solutions, and say why;
• use scipy.optimize.linprog to check a solution, and read its status.

No feasible solution

If the rules contradict each other, the feasible region is empty. For example, $x + y \le 4$ and $x + y \ge 6$ cannot both hold. There are no corner points, so there is nothing to compare. We say the problem has no feasible solution. In a real problem this means that the demands cannot all be met at once.

Many optimal solutions

Take the bakery region again, with $Z = x + y$. The values at the corners are $0$ at $(0, 0)$, $6$ at $(6, 0)$, $6$ at $(4, 2)$ and $4$ at $(0, 4)$. The maximum is $6$, and two corners give it.

The line $x + y = 6$ is also the edge of the region that joins those two corners. The lines $Z = k$ are parallel to that edge. When the sliding line reaches the edge, it lies along it. Every point of the edge gives $Z = 6$. For example, $(5, 1)$ gives $5 + 1 = 6$.

So there are infinitely many optimal solutions, and the maximum value is $6$. If a problem asks for "the" optimal plan, give the maximum value and say that it is reached at both corners and everywhere between them.

When does this happen? When the objective function is a multiple of the left side of one boundary line. Here $x + y$ is the left side of the rule $x + y \le 6$.

Checking with linprog

The function linprog in the module scipy.optimize solves a linear programme. It always minimises $c_1x + c_2y$ subject to rules of the form $\text{(left side)} \le \text{(limit)}$. Three habits make it work.

• To maximise, give it the negative objective. To maximise $2x + 3y$, minimise $-2x - 3y$. Then the maximum is $-$res.fun.
• To use a rule with $\ge$, multiply it by $-1$. The rule $x + y \ge 6$ becomes $-x - y \le -6$.
• Say that $x$ and $y$ are at least $0$, with bounds=[(0, None), (0, None)].

The result res has a code res.status. It is 0 when a best point was found, 2 when there is no feasible solution and 3 when the problem is unbounded. If it is 0, res.x holds the best point and res.fun the best value. When there are many optimal solutions, linprog reports only one of them.

Practise with new numbers

Common mistakes

• Forgetting the minus sign when you ask linprog to maximise. It will then give you the minimum.
• Not turning a $\ge$ rule round. A rule with $\ge$ must be multiplied by $-1$.
• Reading res.fun as the maximum. For a maximisation it is the negative of the maximum.
• Reporting only one point when there is a tie. Say that every point of the edge is optimal.

Remember these

• Clashing rules leave an empty region: no feasible solution.
• Two corners with the same best value mean the whole edge between them is optimal.
• linprog minimises. Negate to maximise. Multiply a $\ge$ rule by $-1$.
• res.status is 0 for solved, 2 for no feasible solution and 3 for unbounded.
• A hand solution is checked by linprog, and linprog is checked by the corners.

References

• NCERT, Mathematics Textbook for Class XII, Part II, Chapter 12, Linear Programming (remarks on multiple optimal solutions and on infeasible problems).
• SciPy documentation, scipy.optimize.linprog (the arguments A_ub, b_ub and bounds, and the status codes).

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Does the region $x + y \le 3$, $x + y \ge 5$, $x \ge 0$, $y \ge 0$ have a feasible solution?

2. At the corners $(0, 5)$ and $(4, 3)$ the objective $Z = x + 2y$ takes the same maximum value. What is it, and how many optimal points are there?

3. How do you ask linprog for the maximum of $4x + 5y$?

4. How do you write the rule $2x + y \ge 8$ for linprog?

5. linprog returns status = 3. What does it mean?