Linear Programming

Graphical Method of Solution

Understand

Draw each constraint line, shade the side that satisfies the inequality (test the origin), and find the common region — the feasible region. Its vertices are the corner points.

Feasible region of \(x+y\le8,\ 2x+y\le12,\ x,y\ge0\) with its corner points.

Corner-point method. (i) Find all corner points (intersections of boundary lines). (ii) Evaluate \(Z\) at each. (iii) For a bounded region the largest value is the maximum and the smallest the minimum. For the region above: \(Z=4x+3y\) takes 0, 24, 28, 24 at \((0,0),(6,0),(4,4),(0,8)\), so \(Z_{\max}=28\) at \((4,4)\).

Unbounded regions

Unbounded feasible region of \(2x+y\ge6,\ x+2y\ge6,\ x,y\ge0\).

If the region is unbounded, a candidate value \(M\) from the table is the true maximum only if the open half-plane \(px+qy>M\) has no point in common with the region (for a minimum, test \(px+qy<M\)). Otherwise the LPP has no maximum (or minimum).

If two adjacent corner points give the same optimal value, every point on the segment joining them is optimal — the LPP has infinitely many optimal solutions.

Key Concepts

Optimum (if it exists) is at a corner point.
Bounded region ⇒ both max and min exist.
Unbounded ⇒ check the open half-plane beyond the candidate value.
Equal optimal values at two corners ⇒ whole edge optimal.

Formula Bank

Corner-point theorem

If an LPP has an optimal value, it is attained at a corner point of the feasible region. A bounded feasible region always has both a maximum and a minimum value of \(Z\).

Key Points

Testing a half-plane

To decide which side of \(ax+by=c\) to shade, substitute a point not on the line (usually the origin). If it satisfies the inequality, shade its side.

Multiple optimal solutions

If \(Z\) has the same optimal value at two adjacent corners, all points on the edge joining them are optimal.

Common Mistakes

Concluding too early on an unbounded region

On an unbounded region the largest value in the table need not be a maximum. Draw \(px+qy>M\) and check whether it meets the region.

Solved Examples

Potter’s problem

Maximise \(Z=60x+90y\) subject to \(x+2y\le16,\ x+y\le10,\ x,y\ge0\).

Corner points: \((0,0),(10,0),(4,6),(0,8)\). Values: 0, 600, 780, 720. The region is bounded, so \(Z_{\max}=₹780\) at \((4,6)\): make 4 mugs and 6 bowls.

Practice & Topic Test

Topic Practice

A fresh set of questions from this topic. Change answers freely – solutions appear after you submit.

Start Practice

Topic Test

Timed: up to 10 questions in 15 minutes.

Start Test

Topic Summary

Draw, find corners, tabulate Z, decide — and check unboundedness before concluding.

Ready to practise this topic?

Create a free account to take practice sessions and tests, see detailed explanations and track your progress.

Create Student Account