PrepKiYour AI companion for entrance exam preparation
MHT-CET MATHEMATICS NOTES

Graphical Solution of LPP

MHT-CET · Mathematics · Linear Programming · Std XII

Summary

The feasible region of an LPP is a convex polygon (bounded or open). The key theorem: if the objective function Z = px + qy has an optimum value (maximum or minimum), it occurs at a corner point of the feasible region. So there is no need to test the infinite number of points inside: test only the corners.

Multiple optimal solutions happen when the line Z = constant is parallel to an edge of the region. If Z = px + qy and that edge is ax + by = c, then p : q = a : b. Then both end corners give the same Z, and every point of the edge does too.

Key formulas

Objective function
Z = px + qy
Optimum
At a corner point of the feasible region
Meeting point of a₁x + b₁y = c₁ and a₂x + b₂y = c₂
x = (c₁b₂ − c₂b₁)/(a₁b₂ − a₂b₁), y = (a₁c₂ − a₂c₁)/(a₁b₂ − a₂b₁)
Multiple optimum (edge ax + by = c)
p : q = a : b
Two corners tie at (x₁, y₁) and (x₂, y₂)
px₁ + qy₁ = px₂ + qy₂
Unbounded maximum test
Z grows along an open edge: no maximum

What this note covers

  • Corner point method
  • Bounded and unbounded feasible regions
  • Problems on maximisation and minimisation

Solved past-paper question (MHT-CET 2021, 2017)

The objective function of an LPP defined over a convex set attains its optimum value at:

  1. (A) at least two of the corner points
  2. (B) all the corner points
  3. (C) at least one of the corner points
  4. (D) none of the corner points

Solution

  1. The fundamental theorem of LPP: when the objective function has an optimum over a convex feasible region, the optimum is reached at a corner point.

    Optimum is at a corner point

  2. It may be at just one corner, so 'at least two' and 'all corners' are not guaranteed. It is never only at an interior point.

    One corner is enough; two corners give a whole edge

  3. So the safe statement is that the optimum occurs at at least one corner point.

Answer: (C) at least one of the corner points

Common mistake: Choosing 'all the corner points' or 'at least two'. The theorem only guarantees at least one.

The full note has 9 solved questions, 9 practice questions, figures and a topic test. Reading it on PrepKi is free after you log in.

PDF download is included in PrepKi plans. See plans.

More notes in Linear Programming