Curriculum

Mathematics Grade XII

0/13

Text lesson

Chapter 12: Linear Programming

Class 12 • Mathematics • Chapter 12

Linear Programming

Squeezing the best possible profit or cost out of a set of straight-line constraints.

CBSE / NCERT Aligned

School Revise

Chapter Roadmap

What an LPP Is • Constraints and the Feasible Region • Corner Points • The Corner Point Method • Bounded and Unbounded Regions • Formulating Word Problems

Getting the Most from Limited Resources

Every business and factory works under limits: only so much material, so many hours, so much money. Linear programming is the mathematics of getting the best outcome, the largest profit or the smallest cost, when both the goal and the limits are straight-line (linear) relationships in the variables.

A linear programming problem, or LPP, has an objective function to maximise or minimise and a set of constraints written as inequalities. At this level we solve two-variable problems graphically: shade the region allowed by the constraints, find its corner points, and test the objective at each corner. The best value always sits at a corner, which makes the search short and certain.

Foundation

An LPP maximises or minimises a linear objective function Z = ax + by subject to linear constraints. The set of points satisfying all constraints is the feasible region, and the optimum, if it exists, occurs at a corner point of that region.

Key Terms You Must Know

Term

Meaning

Example

Objective function

The quantity Z = ax + by to be optimised.

Z = 3x + 4y

Constraint

A linear inequality limiting the variables.

x + y ≤ 4

Feasible region

All points satisfying every constraint.

a shaded polygon

Corner point

A vertex of the feasible region.

where two boundaries meet

Bounded region

A feasible region of finite size.

a closed polygon

Optimal solution

The point giving the best value of Z.

always at a corner

Core Concepts, Step by Step

1. What a Linear Programming Problem Is

An LPP has three ingredients: decision variables (often x and y), an objective function Z = ax + by to maximise or minimise, and a list of linear constraints together with the non-negativity conditions x ≥ 0 and y ≥ 0. Everything is linear, which is exactly what makes the graphical method work.

2. Constraints and the Feasible Region

Each linear inequality cuts the plane into an allowed half and a forbidden half. The feasible region is the overlap of all the allowed halves, the set of points satisfying every constraint at once. We find it by drawing each boundary line and shading the correct side, then taking the common area.

The feasible region is the overlap of all constraints; its corners are the candidates

Shaded feasible region bounded by constraint lines with corner points at (0,0), (4,0), (2,3) and (0,4)

3. Corner Points

The corners (vertices) of the feasible region are where two boundary lines cross. They are found by solving the relevant pairs of boundary equations together. These corner points are the only places we need to test, which is the whole reason the method is so efficient.

4. The Corner Point Method

To solve an LPP: draw the feasible region, list all its corner points, evaluate the objective Z at each corner, and pick the largest value for a maximisation problem or the smallest for a minimisation problem. Because Z is linear, its best value over the whole region is guaranteed to occur at one of these corners.

5. Bounded and Unbounded Regions

A bounded feasible region is enclosed on all sides, so both a maximum and a minimum exist at corners. An unbounded region stretches to infinity in some direction; a maximum (or minimum) may then fail to exist, and we must check whether the objective can grow without limit before declaring an answer.

6. Formulating Word Problems

Real problems must first be turned into an LPP. Identify the decision variables, write the quantity to optimise as Z = ax + by, and translate every limit, on materials, time, demand or budget, into a linear inequality. Adding x ≥ 0 and y ≥ 0 completes the model, ready for the graphical method.

Key Results with Proofs

Result 1: The Corner Point Theorem

Statement. If an LPP has an optimal value, it is attained at a corner point of the feasible region.

Proof

The level lines of a linear objective leave the region last at a vertex.

The objective Z = ax + by is constant along each line ax + by = k. – level lines of Z

As k increases these parallel lines sweep across the region. – sweep the family

The last point of contact as the line leaves the region is on the boundary, at a vertex. – contact at a corner

So the optimum is reached at a corner point. – conclusion

This is why we only ever test the corners, never the interior.

Result 2: Bounded Regions Have Both Extremes

Statement. On a bounded feasible region, Z attains both a maximum and a minimum, each at a corner.

Proof

Finitely many corners on a closed region guarantee both extremes exist.

A bounded region is closed and finite, so it has finitely many corners. – finite vertices

By the corner point theorem the extreme values occur among these corners. – extremes at corners

Evaluating Z at every corner therefore reveals both the largest and the smallest value. – test all corners

Hence both a maximum and a minimum exist. – conclusion

On an unbounded region one of these may be missing.

Result 3: Unbounded Regions May Lack an Optimum

Statement. If the feasible region is unbounded, the objective may have no maximum (or no minimum).

Proof

On an open region the objective can sometimes increase forever.

Suppose Z = x + y on the region x ≥ 0, y ≥ 0 with no upper limit. – an open example

Moving further out increases x + y without bound. – Z keeps rising

So no finite maximum exists, although a minimum at the origin does. – no maximum

Thus unboundedness must be checked before declaring an optimum. – caution

Always confirm whether the region is bounded in the direction Z is being optimised.

Worked Examples

Example 1

Question: Maximise Z = 3x + 4y subject to x + y ≤ 4, x ≥ 0, y ≥ 0.

▶ Show full working

Corners then evaluate.

The feasible region is the triangle with corners (0, 0), (4, 0), (0, 4). – find corners

Z values: at (0,0) it is 0; at (4,0) it is 12; at (0,4) it is 16. – evaluate Z

The largest is 16 at (0, 4). – pick maximum

Answer: Maximum Z = 16 at (0, 4).

Example 2

Question: Minimise Z = 2x + 3y subject to x + y ≥ 5, x ≥ 0, y ≥ 0.

▶ Show full working

Corners on the boundary line.

The relevant corners are (5, 0) and (0, 5). – corners

Z at (5, 0) = 10; Z at (0, 5) = 15. – evaluate

The smallest is 10 at (5, 0). – pick minimum

Answer: Minimum Z = 10 at (5, 0).

Example 3

Question: Maximise Z = x + y subject to x + 2y ≤ 8, 3x + 2y ≤ 12, x, y ≥ 0.

▶ Show full working

Find all four corners.

Corners: (0, 0), (4, 0), (2, 3), (0, 4). – feasible region

Z values: 0, 4, 5, 4 respectively. – evaluate

Maximum is 5 at (2, 3). – pick maximum

Answer: Maximum Z = 5 at (2, 3).

Example 4

Question: Maximise Z = 5x + 3y subject to x + y ≤ 6, x ≥ 0, y ≥ 0.

▶ Show full working

Triangle corners.

Corners (0, 0), (6, 0), (0, 6). – corners

Z values: 0, 30, 18. – evaluate

Maximum is 30 at (6, 0). – maximum

Answer: Maximum Z = 30 at (6, 0).

Example 5

Question: Minimise Z = 4x + 5y subject to 2x + y ≥ 6, x + y ≥ 4, x, y ≥ 0.

▶ Show full working

Find the corners of the unbounded region’s boundary.

Boundary corners: (0, 6), (2, 2), (4, 0). – corners

Z values: 30, 18, 16. – evaluate

The smallest is 16 at (4, 0). – minimum

Answer: Minimum Z = 16 at (4, 0).

Example 6

Question: Find the corner where x + 2y = 8 meets 3x + 2y = 12.

▶ Show full working

Solve the two equations together.

Subtract: (3x + 2y) − (x + 2y) = 12 − 8 gives 2x = 4, so x = 2. – eliminate y

Then 2 + 2y = 8 gives y = 3. – back-substitute

Answer: (2, 3).

Example 7

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

▶ Show full working

Rectangle corners.

Corners (0, 0), (4, 0), (4, 3), (0, 3). – corners

Z values: 0, 8, 11, 3. – evaluate

Maximum is 11 at (4, 3). – maximum

Answer: Maximum Z = 11 at (4, 3).

Example 8

Question: A toy maker earns 5 on a car and 6 on a doll. Each car needs 2 hours, each doll 3 hours, with 12 hours available. Write the LPP.

▶ Show full working

Define variables and translate.

Let x cars and y dolls; profit Z = 5x + 6y. – objective

Time limit: 2x + 3y ≤ 12, with x, y ≥ 0. – constraint

Answer: Maximise Z = 5x + 6y subject to 2x + 3y ≤ 12, x, y ≥ 0.

Example 9

Question: Solve the LPP from Example 8 if only whole corners are checked: corners (0, 0), (6, 0), (0, 4).

▶ Show full working

Evaluate Z at the corners.

Z at (0,0)=0; at (6,0)=30; at (0,4)=24. – evaluate

Maximum profit 30 at (6, 0). – maximum

Answer: Maximum Z = 30 at (6, 0).

Example 10

Question: Maximise Z = x + 2y subject to 2x + y ≤ 4, x, y ≥ 0.

▶ Show full working

Triangle corners.

Corners (0, 0), (2, 0), (0, 4). – corners

Z values: 0, 2, 8. – evaluate

Maximum is 8 at (0, 4). – maximum

Answer: Maximum Z = 8 at (0, 4).

Example 11

Question: Is the region x ≥ 0, y ≥ 0, x + y ≥ 2 bounded?

▶ Show full working

Check for a finite enclosure.

The region lies above the line x + y = 2 and in the first quadrant. – describe

It stretches to infinity, so it is unbounded. – conclude

Answer: No, it is unbounded.

Example 12

Question: Minimise Z = x + y subject to x + y ≥ 3, x, y ≥ 0.

▶ Show full working

Test the boundary corners.

On the line x + y = 3, every point gives Z = 3. – Z is constant on the edge

So the minimum value is 3, attained all along that edge. – minimum

Answer: Minimum Z = 3 (along x + y = 3).

Where You Meet This in Real Life

Manufacturing

Factories decide how many of each product to make to maximise profit within material and machine limits.

Diet and nutrition

Planners minimise the cost of a diet while meeting minimum requirements for each nutrient.

Transport and logistics

Shipping companies minimise cost while meeting delivery demands across routes.

Agriculture

Farmers allocate land between crops to maximise yield within water and budget limits.

Finance

Investors choose a mix of assets to maximise return subject to risk and budget constraints.

Practice Sets A–D

Practice Set A – Basics

A1. Name the function we optimise in an LPP.

▶ Reveal full working

Term.

The objective function.

Answer: The objective function.

A2. Evaluate Z = 2x + 3y at (1, 2).

▶ Reveal full working

Substitute.

2(1) + 3(2) = 8.

Answer: 8.

A3. Where in the feasible region does the optimum occur?

▶ Reveal full working

Theorem.

At a corner point.

Answer: At a corner point.

A4. Write the non-negativity constraints.

▶ Reveal full working

Standard.

x ≥ 0 and y ≥ 0.

Answer: x ≥ 0, y ≥ 0.

Practice Set B – Conceptual

B1. Why do we only test corner points?

▶ Reveal full working

Corner point theorem.

A linear objective takes its extreme values at the vertices of the feasible region. – reason

Answer: Because the optimum of a linear objective is always at a corner.

B2. What is the feasible region?

▶ Reveal full working

Definition.

The set of all points satisfying every constraint at once.

Answer: The overlap of all constraints.

B3. Why might an unbounded region have no maximum?

▶ Reveal full working

Objective can grow.

The objective can keep increasing as you move outward without limit.

Answer: Because the objective can increase without bound.

B4. How do you find a corner point?

▶ Reveal full working

Solve boundaries.

Solve the two boundary line equations that meet there.

Answer: By solving the two intersecting boundary equations.

Practice Set C – Application / Numerical

C1. Maximise Z = 4x + 3y subject to x + y ≤ 5, x, y ≥ 0.

▶ Reveal full working

Triangle corners.

Corners (0,0),(5,0),(0,5); Z = 0, 20, 15. – evaluate

Maximum 20 at (5, 0). – maximum

Answer: Maximum Z = 20 at (5, 0).

C2. Minimise Z = 3x + 2y subject to x + y ≥ 4, x, y ≥ 0.

▶ Reveal full working

Boundary corners.

Corners (4,0),(0,4); Z = 12, 8. – evaluate

Minimum 8 at (0, 4). – minimum

Answer: Minimum Z = 8 at (0, 4).

C3. Find the corner where 2x + y = 4 meets x + y = 3.

▶ Reveal full working

Solve together.

Subtract: x = 1; then y = 2. – solve

Answer: (1, 2).

C4. Maximise Z = x + y subject to x ≤ 3, y ≤ 2, x, y ≥ 0.

▶ Reveal full working

Rectangle corners.

Corner (3, 2) gives Z = 5, the largest. – evaluate

Answer: Maximum Z = 5 at (3, 2).

Practice Set D – HOTS / Multi-step

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

▶ Reveal full working

Find all corners including the intersection.

x + y = 4 meets x + 3y = 6 at (3, 1). – intersection

Corners (0,0),(4,0),(3,1),(0,2); Z = 0, 12, 11, 4. – evaluate

Maximum 12 at (4, 0). – maximum

Answer: Maximum Z = 12 at (4, 0).

D2. A shopkeeper stocks x radios and y phones. Each radio earns 100, each phone 170. Space allows x + y ≤ 20 and budget allows 600x + 1200y ≤ 12000. Write the LPP.

▶ Reveal full working

Translate to inequalities.

Objective Z = 100x + 170y. – profit

Constraints x + y ≤ 20, 600x + 1200y ≤ 12000, x, y ≥ 0. – limits

Answer: Maximise Z = 100x + 170y subject to x + y ≤ 20, 600x + 1200y ≤ 12000, x, y ≥ 0.

D3. Maximise Z = 5x + 7y subject to x + y ≤ 4, 3x + 8y ≤ 24, x, y ≥ 0.

▶ Reveal full working

Find the interior corner too.

x + y = 4 meets 3x + 8y = 24 at (1.6, 2.4). – intersection

Corners (0,0),(4,0),(1.6,2.4),(0,3); Z = 0, 20, 24.8, 21. – evaluate

Maximum 24.8 at (1.6, 2.4). – maximum

Answer: Maximum Z = 24.8 at (1.6, 2.4).

D4. Minimise Z = 200x + 500y subject to x + 2y ≥ 10, 3x + 4y ≥ 24, x, y ≥ 0.

▶ Reveal full working

Test the boundary corners.

x + 2y = 10 meets 3x + 4y = 24 at (4, 3). – intersection

Corners (0,6),(4,3),(10,0); Z = 3000, 2300, 2000. – evaluate

Minimum 2000 at (10, 0). – minimum

Answer: Minimum Z = 2000 at (10, 0).

Chapter Summary

Everything in One Glance

LPP

Optimise a linear objective Z = ax + by under linear constraints with x, y ≥ 0.

Feasible Region

The overlap of all constraint half-planes.

Corner Points

Vertices where boundary lines meet; found by solving pairs of equations.

Corner Point Method

Evaluate Z at every corner; choose the largest or smallest.

Bounded vs Unbounded

Bounded regions guarantee both extremes; unbounded ones may lack one.

Formulation

Turn a word problem into variables, an objective and linear constraints.

Are You Exam-Ready?

8-Point Exam Quick-Check

Evaluate Z = 3x + 5y at (2, 1).

Where does the optimum of an LPP occur?

Find the corner where x + y = 4 meets x = 1.

Maximise Z = x + y on the triangle (0,0), (3,0), (0,3).

What makes a feasible region unbounded?

Write the non-negativity constraints.

Minimise Z = 2x + y at corners (4,0) and (0,4).

Why test only corner points?

School Revise Virtual Lab

Practice the concepts in this chapter with interactive simulations and visual tools.

Open the Virtual Lab →

Class 12 Mathematics Chapter 12: Linear Programming, Complete Notes and Practice

These free Class 12 Maths Linear Programming notes follow the NCERT 2026 to 27 syllabus and cover the objective function, constraints, the feasible region, corner points, the corner point method, bounded and unbounded regions and problem formulation, with twelve worked examples and sixteen graded practice questions. Includes worked examples, step-by-step proofs and graded practice, free on SchoolRevise.com.