Lesson 6 of 9 · 10 min
Multiple optimal solutions
NCERT §12.2.2, Example 3
A parent offers to buy every cookie tray at a higher price, so a cookie tray now earns Rs 150, the same as a cupcake tray. Which plan wins now?
The lesson in notes
In short
Sometimes two corners give the same best value. Then every point of the edge joining them gives it too, so the problem has infinitely many optimal solutions.
This happens when the lines Z = k run parallel to that edge: the sliding line leaves the region along a whole side, not at a single point.
Example: Z = 3x + 9y where x ≤ y, x + y ≥ 10 and x + 3y ≤ 60, with x, y ≥ 0. Z is 90 at corner A(0, 10), 60 at B(5, 5), and 180 at both C(15, 15) and D(0, 20).
So the minimum is 60 at B(5, 5), and the maximum 180 is reached at both C and D, and at every point of CD, such as (7.5, 17.5). Here 3x + 9y is 3 times x + 3y, which is exactly the boundary line through C and D.
The same holds for minima: two corners with the same smallest value make the whole edge between them optimal.