What happens if the feasible region is empty?

Chapter 16 of 18

89%

CBSE Class 12 Mathematics★ 5-6 marks · CBSE Class 12 Mathematics Chapter 12

Linear Programming

You have LIMITED resources. You want to MAXIMISE profit (or MINIMISE cost). LINEAR PROGRAMMING is the mathematical method for OPTIMISATION under constraints. CBSE Class 12 Mathematics Chapter 12.

⏱ 16 min readMedium difficulty✓ Free · NCERT-aligned

Ask AI about this

🔤Build your vocabulary from this chapterLexiGenome mines the key words, explains them in your language, and schedules them with spaced repetition.Mine words →

By the end of this chapter you'll be able to…

1Identify the decision variables, objective function, and constraints in a linear programming problem
2Graph linear inequalities on the coordinate plane and identify the feasible region
3List the corner points (vertices) of the feasible region by solving pairs of boundary equations
4Apply the Corner Point Theorem: the optimal value of Z = ax + by occurs at a corner point of the feasible region
5Distinguish between bounded and unbounded feasible regions and handle the unbounded case

💡

Why this chapter matters

Linear Programming is the most algorithmic chapter in Class 12 Mathematics — it tests a fixed, repeatable procedure: graph the constraints, identify the feasible region, list corner points, evaluate the objective function. Students who know the Corner Point Theorem and practice graphing constraints accurately score full marks reliably.

Linear Programming

"Linear Programming is the mathematics of doing the best you can with what you have."

1. Chapter Overview

LINEAR PROGRAMMING (LP) is a method to find the OPTIMAL (maximum or minimum) value of a linear OBJECTIVE FUNCTION, subject to a set of linear INEQUALITIES (constraints). This chapter covers: formulating an LP problem, the GRAPHICAL METHOD of solution (feasible region, corner points), and different types of solutions (unique optimal, multiple optimal, unbounded, infeasible).

2. Key Concepts

Objective Function (Z): The linear function to be maximised or minimised. Example: Z = 3x + 4y (profit). Z = 5x + 2y (cost).
Constraints: Linear inequalities that RESTRICT the values of the decision variables. Example: x ≥ 0, y ≥ 0, 2x + y ≤ 100, x + 3y ≤ 150.
Decision Variables (x, y): The variables we CONTROL.

3. Graphical Method — Step by Step

Graph the constraints as EQUALITIES (straight lines). Shade the FEASIBLE REGION (the region satisfying ALL inequalities). Always: x ≥ 0, y ≥ 0 (first quadrant).
The feasible region is a CONVEX POLYGON.
Find the corner points (vertices) of the feasible region.
Evaluate Z at each corner point.
The point giving the MAXIMUM (or minimum) Z is the OPTIMAL SOLUTION.

Theorem

'If the feasible region is BOUNDED, the optimum occurs at a CORNER POINT.'

4. Types of Solutions

Type	What Happens
Unique optimal	Z maximised at ONE corner point
Multiple optimal	Z maximised at TWO adjacent corners (entire edge segment is optimal)
Unbounded	Feasible region is NOT bounded. Z can increase indefinitely (no finite maximum). OR Z has a minimum but no maximum.
Infeasible	No point satisfies ALL constraints. Feasible region is EMPTY.

5. Exam Focus

Formulating LP — identify objective function and constraints from a word problem.
Graphical method — plot constraints, shade feasible region, find corner points.
Evaluate Z at corners. Identify optimal solution.
Bounded vs. unbounded feasible regions.

6. Conclusion

Linear Programming is OPTIMISATION 101:

SET UP: What are you maximising? What constraints limit you?
GRAPH: The feasible region is where ALL constraints are satisfied. 'It's a polygon — the intersection of half-planes.'
SOLVE: Check the corners. 'The best answer is ALWAYS at a corner.'

'In the real world, resources are finite and objectives compete. Linear programming is how we make the best possible choice.'

Key formulas & results

Everything you need to memorise, in one card. Screenshot this for revision.

Structure of a Linear Programming Problem

STANDARD FORM: Maximise (or Minimise) Z = ax + by [OBJECTIVE FUNCTION] subject to constraints: c₁x + d₁y ≤ e₁, c₂x + d₂y ≤ e₂, ..., x ≥ 0, y ≥ 0 [NON-NEGATIVITY]. TERMINOLOGY: Decision variables: x and y (what we control). Objective function: Z = ax + by (what we optimise). Constraints: inequalities defining feasible region. Feasible region: the set of all points satisfying ALL constraints simultaneously. Feasible solution: any point in the feasible region. Optimal solution: feasible point that maximises/minimises Z.

Non-negativity constraints (x ≥ 0, y ≥ 0) restrict to the first quadrant. The feasible region is ALWAYS a convex polygon (or empty, or unbounded). The objective function Z = ax + by represents a family of parallel lines — the optimal solution is the line that is farthest from origin (max) or closest (min) while still touching the feasible region.

Corner Point Theorem (Fundamental Theorem of LPP)

THEOREM: If the feasible region is bounded (and non-empty), the objective function Z = ax + by attains its MAXIMUM and MINIMUM values at the CORNER POINTS (vertices) of the feasible region. PROCEDURE: (1) Graph all constraints to find feasible region. (2) Find all corner points (vertices) by solving adjacent boundary equations simultaneously. (3) Evaluate Z at each corner point. (4) The largest Z-value is the maximum; smallest is the minimum. FOR UNBOUNDED REGION: (a) Find max/min Z at corner points. (b) Draw the open half-plane ax + by > M (for maximum M). (c) If this half-plane has NO point in common with feasible region, M is the maximum. Otherwise, maximum does not exist.

For BOUNDED region: always exactly one maximum and one minimum (possibly attained at multiple corners if objective line is parallel to a constraint — 'infinite solutions'). For UNBOUNDED region: minimum may exist but maximum may not (or vice versa). Always perform the additional check for unbounded regions.

Graphing Constraints and Identifying Feasible Region

GRAPHING INEQUALITIES: For ax + by ≤ c: (1) Draw the line ax + by = c. (2) Shade the side containing the origin if a(0)+b(0) ≤ c (i.e., if c ≥ 0). Shade the other side if origin does NOT satisfy the inequality. For strict inequalities (<, >): dashed line. For ≤ or ≥: solid line. FEASIBLE REGION: the intersection of ALL shaded regions plus the non-negativity constraints (first quadrant or parts of it). CORNER POINTS: found by solving each pair of adjacent boundary lines simultaneously (two equations, two unknowns).

Always test the origin (0,0) first: if it satisfies all constraints, shade the side containing origin. Common constraints and their intercepts: 3x + 4y = 24 → x-intercept (8,0), y-intercept (0,6). Plot both intercepts, draw the line, test (0,0): 0 ≤ 24 ✓ → shade the origin side. The feasible region is where ALL shaded regions overlap.

⚠️

Common mistakes & fixes

These are the exact errors that cost students marks in board exams. Read them once, save yourself the trouble.

WATCH OUT

✗ Finding corner points by reading off the graph instead of solving equations

✓ Corner points must be found algebraically (by solving the two boundary equations simultaneously), not by visual estimation from the graph. For example, if the boundary lines are x + y = 4 and 2x + y = 6, solve: x = 2, y = 2. If you read (2.1, 1.9) from the graph, Z-values will be wrong. Always write and solve the equations.

WATCH OUT

✗ Forgetting to include the corner point at the origin (0, 0) and axis-intercept corners

✓ The feasible region often has corners at (0, 0), on the x-axis, and on the y-axis (from the non-negativity constraints). These are legitimate corner points. List ALL corners: for each boundary line, find where it intersects the x-axis (y=0) and y-axis (x=0), and where it intersects other constraint lines. Then determine which intersections are vertices of the feasible region.

WATCH OUT

✗ Not checking the unbounded region condition for maximisation/minimisation

✓ For UNBOUNDED feasible regions: after finding the optimal value M at a corner point, check whether the open half-plane Z > M (for maximum) has any common point with the feasible region. If YES, then the maximum does not exist (Z can be made arbitrarily large). State this explicitly: 'Since the open half-plane 2x+3y>18 has points in the feasible region, Z has no maximum.' CBSE problems specify 'unbounded' to signal this check is needed.

NCERT exercises (with solutions)

Every NCERT exercise from this chapter — what it covers and how many questions to expect.

Ex s 12.1 and 12.2

Exercises 12.1 and 12.2

Graphical method for LPP; bounded and unbounded feasible regions; manufacturing/diet/allocation word problems; maximise profit, minimise cost; optimal solution interpretation

Questions

Practice problems

Try each one yourself before tapping "Show solution". Active recall > rereading.

Q1EASY· bounded-maximise

Maximise Z = 3x + 4y subject to: x + y ≤ 4; x + 2y ≤ 6; x ≥ 0; y ≥ 0.

▶ Show solution

CORNER POINTS: (1) (0,0): from x≥0, y≥0. (2) (4,0): from x+y=4 and y=0. (3) (0,3): from x+2y=6 and x=0 (y=3). (4) Intersection of x+y=4 and x+2y=6: subtract: y=2, x=2 → (2,2). FEASIBLE REGION: bounded polygon with vertices (0,0), (4,0), (2,2), (0,3). Z VALUES: Z(0,0)=0. Z(4,0)=12. Z(2,2)=6+8=14. Z(0,3)=12. MAXIMUM Z = 14 at (2, 2).

Q2MEDIUM· word-problem-manufacturing

A factory makes two products A and B. Product A requires 2 hours of machine time and 1 hour of labour; product B requires 1 hour of machine time and 2 hours of labour. Machine time available: 10 hours; labour available: 8 hours. Profit: A gives ₹4 per unit, B gives ₹3 per unit. How many units of A and B maximise profit?

▶ Show solution

Let x = units of A, y = units of B. OBJECTIVE: Maximise Z = 4x + 3y. CONSTRAINTS: Machine: 2x + y ≤ 10. Labour: x + 2y ≤ 8. Non-negativity: x ≥ 0, y ≥ 0. CORNER POINTS: (0,0), (5,0) [2x=10, y=0], (0,4) [x=0, 2y=8]. Intersection of 2x+y=10 and x+2y=8: multiply second by 2: 2x+4y=16. Subtract: 3y=6 → y=2, x=4. Corner: (4,2). Z VALUES: Z(0,0)=0. Z(5,0)=20. Z(4,2)=16+6=22. Z(0,4)=12. MAXIMUM Z = ₹22 at x=4, y=2. Produce 4 units of A and 2 units of B.

Q3HARD· minimisation-unbounded

Minimise Z = 5x + 10y subject to: x + 2y ≥ 120; x + y ≥ 60; x − 2y ≤ 0; x ≥ 0; y ≥ 0.

▶ Show solution

CONSTRAINTS (all ≥ → feasible region is ABOVE these lines — likely unbounded): (1) x+2y=120: intercepts (120,0) and (0,60). (2) x+y=60: intercepts (60,0) and (0,60). (3) x−2y=0 → x=2y. (4) x≥0, y≥0. CORNER POINTS: Find intersections in feasible region. Intersection of x+2y=120 and x−2y=0: add: 2x=120 → x=60, y=30. Point (60,30). Intersection of x+y=60 and x=2y: 2y+y=60 → y=20, x=40. Point (40,20). Intersection of x+2y=120 and x+y=60: subtract: y=60, x=0. Point (0,60). EVALUATE Z: Z(60,30) = 300+300=600. Z(40,20) = 200+200=400. Z(0,60) = 0+600=600. Minimum Z = 400 at (40,20). CHECK (unbounded): Open half-plane 5x+10y < 400 — test any interior point. At (50,10): 250+100=350 < 400, but check if (50,10) is in feasible region: x+2y=70 < 120 ✗ (not feasible). No feasible point gives Z < 400. Minimum Z = 400 at x=40, y=20. ✓

5-minute revision

The whole chapter, distilled. Read this the night before the exam.

•LPP components: decision variables, objective Z = ax+by, constraints, non-negativity x≥0,y≥0.
•Feasible region = intersection of all constraint regions (always convex).
•Corner Point Theorem: optimal Z always at a corner point of feasible region.
•Corner points: solve pairs of adjacent boundary equations simultaneously.
•Evaluate Z at every corner point — tabulate all values.
•Bounded feasible region: both max and min exist at corner points.
•Unbounded feasible region: check whether open half-plane (ax+by>M) overlaps feasible region.
•Parallel constraint lines → optimal Z at multiple corners (infinite solutions) or unbounded.

CBSE marks blueprint

Where the marks come from in this chapter — so you can plan your prep.

Typical chapter weightage: 5-6 marks

Question type	Marks each	Typical count	What it tests
Graphical LPP (Manufacturing/Diet Word Problem)	5-6	1	Set up objective function and constraints; graph and find feasible region; find corner points; evaluate Z; state optimal solution

Prep strategy

Standard 5-step solution: (1) Define variables. (2) Write objective function. (3) Write all constraints with non-negativity. (4) Graph — mark intercepts, shade correct side for each constraint, identify feasible region. (5) Find all corner points algebraically, tabulate Z values, state optimal solution. Missing any step loses the mark for that step.
For graphing: always plot both intercepts of each constraint line on the axes before drawing. Find x-intercept (set y=0) and y-intercept (set x=0). These two points define the boundary line. The feasible region is on one side — test with (0,0).
Word problems: read carefully to identify what is being maximised (profit, revenue) or minimised (cost, time). The constraints are always resource limitations (≤ for available resources, ≥ for minimum requirements).

Where this shows up in the real world

This chapter isn't just an exam topic — it lives in the world around you.

Supply Chain and Resource Allocation

Every major company — Amazon, Walmart, airlines — uses linear programming to optimise resource allocation. An airline must decide how many seats to allocate to business class vs economy to maximise revenue, subject to aircraft capacity constraints — exactly the structure of an LPP. Supply chain managers use LP to minimise transportation costs across multiple warehouses and destinations. The SIMPLEX ALGORITHM (the standard industrial LP solver) solves problems with millions of variables in seconds — a direct extension of the corner-point method, but in multi-dimensional space.

Exam strategy

Battle-tested tips from teachers and toppers for this chapter.

CBSE allots 1 mark for the graph (feasible region correctly shaded). Draw the graph neatly: use a ruler, label the axes, mark the coordinates of each intercept, shade the feasible region with light hatching, and mark corner points with their coordinates. This visual step earns marks independently of the Z-calculation.
After finding Z at corner points, present the answer in a table: | Corner Point | Z = ax+by | — list all points and their Z values. Circle or underline the maximum/minimum. This tabular presentation is what CBSE marking schemes look for.

Going beyond the textbook

For olympiad aspirants and curious learners — topics that build on this chapter.

Study the SIMPLEX METHOD (George Dantzig, 1947): the standard algorithm for solving LP with n variables and m constraints. It moves from corner point to adjacent corner point along edges of the feasible polytope, always improving Z. In 2D (Class 12), checking all corners is easy — in 1000 dimensions (industrial LP), the simplex method is the key to efficiency
Explore INTEGER LINEAR PROGRAMMING (ILP): LPP where decision variables must be integers (you can't produce 2.7 cars). The LP relaxation (ignoring integrality) gives a bound; then branch-and-bound algorithms find the integer optimum. ILP is NP-hard — scheduling, routing, and the travelling salesman problem are all ILP problems

Where else this chapter is tested

CBSE board isn't the only one — other exams test this chapter too.

CBSE Class 12 Board (Mathematics)High

JEE Main (Linear Programming)Low

CUET (Mathematics)Medium

AI helpers for this chapter

Generate more practice on the fly, or have the chapter explained at a different level.

⚡

Generate 5 more questions

Fresh MCQs + short-answer items based on this chapter, plus answer keys.

🧠

Explain at a different level

Re-explain the chapter at the level you actually want.

📝 My notes

Saved on this device — sign in to sync · how this works

0/600

Questions students ask

The real ones — pulled from the Q&A community and tutor sessions.

If no point satisfies all constraints simultaneously, the feasible region is EMPTY. This means the LPP has NO SOLUTION (infeasible). On the graph, the shaded regions of all constraints have no common overlap area. This occurs when constraints are contradictory — e.g., x + y ≤ 2 and x + y ≥ 5 simultaneously have no solution. State: 'The feasible region is empty; the LPP has no feasible solution.' CBSE board problems always have a non-empty feasible region.

Practice more, ask doubts, find a tutor

CBSE Class 12 mock tests

CBSE Class 12 PYQs

Ask in Q&A

Mathematics flashcards

Related chapters

Students who read Linear Programming usually read these next.

Relations and Functions

A RELATION links elements of two sets. A FUNCTION is a special relation where EVERY input has EXACTLY ONE output. This chapter builds the foundation — types of relations, types of functions, composition of functions and invertible functions, and binary operations. CBSE Class 12 Mathematics Chapter 1.

Relations and Functions (Class 12)

A deeper dive into RELATIONS (reflexive, symmetric, transitive — equivalence relations) and FUNCTIONS (one-one, onto, bijective — composition, invertibility). CBSE Class 12 Mathematics Chapter 1.

Inverse Trigonometric Functions

If sin(x) = y, what is x in terms of y? The answer is sin⁻¹(y) — but with a TWIST: since trig functions are NOT one-one, we must RESTRICT their domains to define inverses. CBSE Class 12 Mathematics Chapter 2.

Matrices

A MATRIX is a rectangular array of numbers — and it is one of the most POWERFUL tools in mathematics. This chapter covers types of matrices, operations (addition, multiplication, transpose), symmetric and skew-symmetric matrices, and finding an inverse using elementary operations. CBSE Class 12 Mathematics Chapter 3.