Simulation · Maths · Class 12

Slide the profit line

From the lesson Multiple optimal solutions in Linear Programming. Change the values and watch what happens.

The idea behind it

NCERT §12.2.2, Example 3

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.

1 more