Home / Mathematics / Chapter 12 — Linear Programming
Class 12 Maths · Chapter 12 · Bihar Board

Linear Programming

Master LPP with visual graphs — objective function, constraints, feasible region, corner point method, bounded/unbounded cases, step-marked solutions, MCQs, and PYQs.

6 Visual Graphs Corner Point Method Step Marking
6Core Concepts
20MCQs
10Assertion-Reason
8PYQs
Section 01

Basic Concepts

What is a Linear Programming Problem?

12.1 Introduction

Many real-life problems involve maximizing profit or minimizing cost, subject to certain limitations. These problems are called optimisation problems, and the special class involving linear functions and linear constraints is called Linear Programming Problems (LPP).

Definition — LPP

A Linear Programming Problem is one that is concerned with finding the optimal value (maximum or minimum) of a linear function (called objective function) of several variables (say $x$ and $y$), subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities (called linear constraints).

12.2 Key Terms

Objective Function

A linear function $Z = ax + by$, where $a, b$ are constants, which has to be maximised or minimised.

Decision Variables

The variables $x$ and $y$ in the objective function.

Constraints

The linear inequalities or restrictions on the variables. Conditions $x \geq 0, y \geq 0$ are called non-negative restrictions.

Feasible Region

The common region determined by all constraints including non-negative constraints. Every point in this region is a feasible solution.

Optimal Solution

Any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function.

Key Points
  • Feasible region is always a convex region.
  • Optimal solution (if it exists) occurs at a corner point (vertex) of the feasible region.
  • If two corner points give same optimal value → every point on line segment joining them also gives that value (multiple optimal solutions).

12.3 Mathematical Formulation

The furniture dealer problem:

Let $x$ = tables, $y$ = chairs.

Maximise $Z = 250x + 75y$ (Objective Function)

Subject to:

$5x + y \leq 100$   (Investment constraint)
$x + y \leq 60$   (Storage constraint)
$x \geq 0, y \geq 0$   (Non-negative)
Section 02

🎨 Visual Graphs

Understanding the feasible region

V1 Bounded Feasible Region

Maximise $Z = 4x + y$ subject to $x + y \leq 50$, $3x + y \leq 90$ X Y O 10 20 30 40 50 10 20 30 40 50 x + y = 50 3x + y = 90 O A(30,0) B(20,30) C(0,50) Max Z = 4x + y. Corner points: O(0,0), A(30,0), B(20,30), C(0,50)
The shaded region OABC is the bounded feasible region. The optimal value occurs at one of the corner points.

V2 Corner Point Method — Flowchart

Step-by-Step Approach
Step 1
Find the feasible region by graphing all constraints.
Step 2
Determine all corner points (vertices) of the feasible region.
Step 3
Evaluate the objective function Z at each corner point.
Step 4
Pick the largest/smallest value — that's your answer. If feasible region is unbounded, verify with open half-plane test.
The Corner Point Method is the standard technique for solving linear programming problems in two variables.

V3 Unbounded Feasible Region

Minimise $Z = -50x + 20y$ — no minimum exists X Y O Unbounded region — verify with open half-plane test
If the feasible region is unbounded, a maximum/minimum may or may not exist. Verify using the open half-plane test.

V4 No Feasible Region

Constraints $x + y \geq 8$ and $3x + 5y \leq 15$ — no common solution X Y x + y ≥ 8 3x + 5y ≤ 15 No common region → No feasible solution
When constraints contradict each other (no overlap), the LPP has no feasible solution.

V5 Multiple Optimal Solutions

Two corner points give same max/min value X Y C (optimal) D (optimal) Every point on CD also optimal Z has same optimal value at C and D → infinite optimal solutions
If two corner points give the same optimal value, then every point on the line segment joining them also gives that same optimal value.

V6 Types of Solutions — Summary

Four Possible Outcomes
Unique Solution
One corner point gives the optimal value. Most common case.
Multiple Solutions
Two corner points give same optimal value → infinitely many solutions on the edge between.
Unbounded
Feasible region is unbounded. Optimal value may or may not exist — verify with open half-plane test.
No Solution
Constraints contradict each other → no feasible region exists.
Section 03

📐 Corner Point Method

Systematic approach to solve LPPs

M1 Steps for Corner Point Method

  1. Graph the feasible region using all constraints.
  2. Find all corner points (vertices) — by inspection or by solving the pairs of lines that intersect at each corner.
  3. Evaluate the objective function Z = ax + by at each corner point.
  4. Determine the optimal value:
    • If feasible region is bounded: The largest/smallest value is the maximum/minimum of Z.
    • If feasible region is unbounded:
      • $M$ (largest corner value) is the maximum iff the open half-plane $ax + by > M$ has NO point in common with the feasible region.
      • $m$ (smallest corner value) is the minimum iff the open half-plane $ax + by < m$ has NO point in common with the feasible region.
Section 04

📖 Fundamental Theorems

Why the corner point method works

T1 Theorem 1 — Optimal Value at Corner Point

Theorem 1

Let R be the feasible region (convex polygon) for a linear programming problem and let $Z = ax + by$ be the objective function. When Z has an optimal value (maximum or minimum), it must occur at a corner point (vertex) of the feasible region.

T2 Theorem 2 — Bounded Region

Theorem 2

If the feasible region R is bounded, then the objective function Z has both a maximum and a minimum value on R and each of these occurs at a corner point (vertex) of R.

T3 Remark — Unbounded Region

Remark

If R is unbounded, then a maximum or a minimum value of the objective function may not exist. However, if it exists, it must occur at a corner point of R.

Quick Reference

🧮 All Important Concepts

Summary of Chapter 12

F1 Standard Form of LPP

Maximise/Minimise $Z = ax + by$

Subject to constraints:

$c_1 x + d_1 y \leq e_1$
$c_2 x + d_2 y \leq e_2$
$x \geq 0, \ y \geq 0$

F2 Key Definitions

  • Objective Function: The linear function to be optimised
  • Decision Variables: Variables $x, y$
  • Constraints: Linear inequalities defining the problem
  • Feasible Region: Common region satisfying all constraints
  • Feasible Solution: Any point in the feasible region
  • Optimal Solution: Feasible solution giving the optimal value

F3 Properties of Feasible Region

  • Feasible region is always convex.
  • Optimal value occurs at a corner point.
  • If two corner points give same optimal value, the whole edge between them also gives that value.
  • Feasible region may be bounded or unbounded.
  • In some cases, no feasible region exists.

F4 Corner Point Method Steps

  1. Graph all constraints → find feasible region.
  2. Find all corner points.
  3. Compute Z at each corner point.
  4. Pick max/min — verify with open half-plane test if unbounded.
Shortcuts

💡 Tricks & Shortcuts

Speed techniques for board exams

Trick 1 — Identify Objective vs Constraints

"Maximise/Minimise = Objective | Inequalities = Constraints"

  • Objective function is what we want to optimise (e.g., $Z = 250x + 75y$)
  • Constraints are the inequalities (limits on resources, storage, etc.)
Trick 2 — Graph Fast

Convert each inequality to equation, find intercepts

  • For $5x + y = 100$: x-intercept when $y=0$ → $x=20$; y-intercept when $x=0$ → $y=100$
  • Join the two intercepts — that's the line
  • Shade the side satisfying the inequality
Trick 3 — Find Corner Points Smartly

Corner points come from intersections of pairs of lines

  • Origin (0,0) if it's a corner
  • Where line meets x-axis (y=0)
  • Where line meets y-axis (x=0)
  • Where two constraint lines intersect
Trick 4 — Only Evaluate at Corner Points

Skip interior and edge points!

  • Theorem 1 guarantees optimum is at a corner point
  • Evaluate Z at each corner, compare
Trick 5 — Check If Region is Bounded

"All inequalities ≤ with all +ve coefficients → bounded"

  • If region is fully enclosed → bounded
  • If it extends infinitely → unbounded
Trick 6 — Unbounded Region Test

Draw the line $ax + by = $ candidate value

  • If the open half-plane (for max: $> M$; for min: $< m$) doesn't touch feasible region → candidate is optimal
  • Otherwise → no optimal solution
Trick 7 — Multiple Optimal Solutions

If Z is same at two corner points → whole edge is optimal

  • Check if the objective function is parallel to a constraint line
  • If so, multiple optimal solutions on that edge
Trick 8 — No Feasible Region

Shading directions don't overlap

  • If constraint shadings don't have any common region → no solution
  • Check by finding contradictory constraints
Trick 9 — Objective Function Slope

Slope of $ax + by = 0$ is $-a/b$

  • Compare with slopes of constraint lines
  • If equal → multiple solutions along that edge
Trick 10 — Verify Answer

Plug optimal point back into all constraints

  • Optimal point must satisfy ALL constraints
  • If it violates any → recheck graphs/solution
Practice

📝 Solved Examples with Step Marking

Click "Show Answer" to reveal step-by-step solutions with marks

📋 Total: 4 Marks · Board Pattern

Q1. Maximise $Z = 4x + y$ subject to $x + y \leq 50$, $3x + y \leq 90$, $x \geq 0, y \geq 0$.

Step 1 — Graph feasible region1 Mark

Plot both lines. The feasible region OABC is bounded with corner points:

O(0,0), A(30,0), B(20,30), C(0,50)

Step 2 — Evaluate Z at each corner2 Marks

At O(0,0): $Z = 0$

At A(30,0): $Z = 4(30) + 0 = 120$

At B(20,30): $Z = 4(20) + 30 = 110$

At C(0,50): $Z = 0 + 50 = 50$

Step 3 — Maximum value1 Mark

Largest value = 120 at A(30, 0).

Maximum Z = 120 at (30, 0)
📋 Total: 4 Marks

Q2. Minimise $Z = 200x + 500y$ subject to $x + 2y \geq 10$, $3x + 4y \leq 24$, $x \geq 0, y \geq 0$.

Step 1 — Corner points1 Mark

Feasible region is bounded with corner points:

A(0,5), B(4,3), C(0,6)

Step 2 — Evaluate Z2 Marks

At A(0,5): $Z = 0 + 2500 = 2500$

At B(4,3): $Z = 800 + 1500 = 2300$

At C(0,6): $Z = 0 + 3000 = 3000$

Step 3 — Minimum value1 Mark

Smallest = 2300 at B(4, 3).

Minimum Z = 2300 at (4, 3)
📋 Total: 5 Marks

Q3. Solve graphically: Minimise and Maximise $Z = 3x + 9y$ subject to $x + 3y \leq 60$, $x + y \geq 10$, $x \leq y$, $x \geq 0, y \geq 0$.

Step 1 — Graph and corner points1.5 Marks

Feasible region ABCD (bounded) has corner points:

A(0,10), B(5,5), C(15,15), D(0,20)

Step 2 — Evaluate Z2 Marks

At A(0,10): $Z = 90$

At B(5,5): $Z = 15 + 45 = 60$

At C(15,15): $Z = 45 + 135 = 180$

At D(0,20): $Z = 0 + 180 = 180$

Step 3 — Interpret results1.5 Marks

Minimum Z = 60 at B(5, 5).

Maximum Z = 180 at both C(15, 15) and D(0, 20).

Since two corner points give same max → multiple optimal solutions along segment CD.

Min Z = 60 at (5,5); Max Z = 180 (multiple solutions)
Test Yourself

✍️ MCQ Practice — 20 Questions

Select your answer and click "Check Answers"

1. A Linear Programming Problem deals with finding:

Correct: B — LPP seeks to maximize or minimize a linear objective function.

2. The linear function $Z = ax + by$ is called:

Correct: C — The function to be optimised is called the objective function.

3. The feasible region of an LPP is always:

Correct: A — A key property: feasible region determined by linear inequalities is always convex.

4. In LPP, the optimal value (if it exists) occurs at:

Correct: D — Theorem 1 guarantees optimum at a corner point.

5. The conditions $x \geq 0, y \geq 0$ in an LPP are called:

Correct: B — These are standard non-negative restrictions.

6. If the feasible region is bounded, then the objective function has:

Correct: C — Theorem 2: bounded region guarantees both max and min.

7. If two corner points give the same optimal value, then:

Correct: A — This is the "multiple optimal solutions" case.

8. If the feasible region is unbounded, then:

Correct: D — Need to verify with open half-plane test.

9. In the corner point method, we evaluate Z at:

Correct: B — Only corner points need to be evaluated.

10. The variables $x$ and $y$ in an LPP are called:

Correct: C — Variables we choose to optimize are decision variables.

11. The set of inequalities in LPP are called:

Correct: A — Linear inequalities restricting the problem are constraints.

12. The common region determined by all constraints is called:

Correct: D — It's the region of all feasible points.

13. Any point outside the feasible region is called:

Correct: B — Points not satisfying constraints are infeasible.

14. If the constraints contradict each other, then:

Correct: C — No common region → no solution.

15. The term "Linear" in Linear Programming means:

Correct: A — "Linear" implies all mathematical relations used are linear.

16. In an LPP, if the feasible region is bounded, the optimal value occurs at:

Correct: D — Standard result for bounded feasible regions.

17. If the feasible region is unbounded and maximum of Z exists, then it occurs at:

Correct: B — Even for unbounded regions, optimum (if exists) is at a corner point.

18. The collection of all feasible solutions of an LPP is called:

Correct: C — Feasible region contains all feasible solutions.

19. In the LPP, the phrase "programming" refers to:

Correct: A — Programming = determining a plan/programme of action.

20. If $Z = ax + by$ has the same value at two adjacent corner points of feasible region, the LPP has:

Correct: B — Every point on the edge joining them also gives optimal value → infinitely many optimal solutions.
Score: 0 / 20
New Pattern

🎯 Assertion & Reasoning — 10 Questions

Each question has an Assertion (A) and a Reason (R). Choose the correct option.

📖 Standard Options

(A) Both A and R are true, and R is the correct explanation of A.

(B) Both A and R are true, but R is NOT the correct explanation of A.

(C) A is true, but R is false.

(D) A is false, but R is true.

1
Assertion (A) The feasible region of an LPP is a convex region.
Reason (R) The feasible region is determined by linear inequalities, whose intersection is always convex.
Correct: A — Both true, R explains the convexity property.
2
Assertion (A) The optimal value of an LPP occurs at a corner point of the feasible region.
Reason (R) For any linear objective function, the maximum or minimum is achieved at a vertex of the convex feasible polygon.
Correct: A — Both true. R is the underlying reason (Theorem 1).
3
Assertion (A) If the feasible region is unbounded, then the objective function always has a maximum.
Reason (R) For unbounded regions, the maximum may or may not exist.
Correct: D — A is false (may or may not exist). R is true.
4
Assertion (A) The constraints $x \geq 0, y \geq 0$ are called non-negative restrictions.
Reason (R) In real-world LPPs, variables represent quantities that cannot be negative.
Correct: A — Both true, R explains why these restrictions exist.
5
Assertion (A) If two corner points of feasible region give same maximum value of Z, then there are infinite optimal solutions.
Reason (R) Every point on the line segment joining the two corner points also gives the same maximum value.
Correct: A — Both true, R explains the multiple-solution property.
6
Assertion (A) Every point in the feasible region is an optimal solution.
Reason (R) Only the point(s) giving the optimal value of Z are called optimal solutions.
Correct: D — A is false (only optimal point(s)). R is true (defines optimal solution).
7
Assertion (A) If feasible region is bounded, the objective function has both maximum and minimum values.
Reason (R) For a bounded convex polygon, a linear function attains both its max and min at corner points.
Correct: A — Both true, this is the statement of Theorem 2.
8
Assertion (A) An LPP always has a feasible region.
Reason (R) Constraints may contradict each other, leading to no feasible region.
Correct: D — A is false (some LPPs have no feasible region). R is true.
9
Assertion (A) The Corner Point Method is sufficient to solve any two-variable LPP.
Reason (R) By Theorem 1, the optimum value (if it exists) is attained at a corner point of feasible region.
Correct: A — Both true. R justifies using the Corner Point Method.
10
Assertion (A) The term "linear" in LPP refers to the linearity of the objective function and constraints.
Reason (R) All mathematical relations in an LPP are linear (degree 1 in the variables).
Correct: A — Both true, R is the definition of "linear".
Score: 0 / 10
Exam Focus

📊 Previous Year Questions

Frequently asked questions in board exams

2024

Q. Solve graphically: Maximise $Z = 3x + 4y$ subject to $x + y \leq 4$, $x \geq 0, y \geq 0$.

Step 1 — Corner points1 Mark

Feasible region has corner points: O(0,0), A(4,0), B(0,4)

Step 2 — Evaluate Z1.5 Marks

At O(0,0): $Z = 0$

At A(4,0): $Z = 12$

At B(0,4): $Z = 16$

Step 3 — Maximum0.5 Mark

Largest = 16 at B(0, 4)

Max Z = 16 at (0, 4)
2024

Q. Minimise $Z = 3x + 5y$ subject to $x + 3y \geq 3$, $x + y \geq 2$, $x, y \geq 0$.

Step 1 — Corner points1 Mark

Feasible region (unbounded) has corner points:

A(3,0), B(1.5, 0.5), C(0, 2)

Step 2 — Evaluate Z1.5 Marks

At A(3,0): $Z = 9$

At B(1.5,0.5): $Z = 4.5 + 2.5 = 7$

At C(0,2): $Z = 10$

Step 3 — Minimum1 Mark

Smallest = 7 at B(1.5, 0.5)

Min Z = 7 at (1.5, 0.5)
2023

Q. Solve graphically: Maximise $Z = 5x + 3y$ subject to $3x + 5y \leq 15$, $5x + 2y \leq 10$, $x \geq 0, y \geq 0$.

Step 1 — Corner points1 Mark

Feasible region has corner points: O(0,0), A(2,0), B(20/19, 45/19), C(0,3)

Step 2 — Evaluate Z1.5 Marks

At O(0,0): $Z = 0$

At A(2,0): $Z = 10$

At B(20/19, 45/19): $Z \approx 12.37$

At C(0,3): $Z = 9$

Step 3 — Maximum0.5 Mark

Largest = 235/19 at B(20/19, 45/19)

Max Z = 235/19 at (20/19, 45/19)
2023

Q. Minimise and Maximise $Z = 5x + 10y$ subject to $x + 2y \leq 120$, $x + y \geq 60$, $x - 2y \geq 0$, $x, y \geq 0$.

Step 1 — Corner points1 Mark

Feasible region has corner points: A(60,0), B(120,0), C(60,30), D(40,20)

Step 2 — Evaluate Z2 Marks

At A(60,0): $Z = 300$

At B(120,0): $Z = 600$

At C(60,30): $Z = 600$

At D(40,20): $Z = 400$

Step 3 — Interpret1 Mark

Min Z = 300 at A(60, 0)

Max Z = 600 at B(120, 0) and C(60, 30) → multiple optimal solutions

Min Z = 300 at (60,0); Max Z = 600 (multiple)
2022

Q. Maximise $Z = 3x + 2y$ subject to $x + 2y \leq 10$, $3x + y \leq 15$, $x, y \geq 0$.

Step 1 — Corner points1 Mark

Feasible region has corner points: O(0,0), A(5,0), B(4,3), C(0,5)

Step 2 — Evaluate Z1.5 Marks

At O(0,0): $Z = 0$

At A(5,0): $Z = 15$

At B(4,3): $Z = 12 + 6 = 18$

At C(0,5): $Z = 10$

Step 3 — Maximum0.5 Mark

Largest = 18 at B(4, 3)

Max Z = 18 at (4, 3)
2022

Q. Minimise $Z = x + 2y$ subject to $2x + y \geq 3$, $x + 2y \geq 6$, $x, y \geq 0$.

Step 1 — Corner points1 Mark

Feasible region (unbounded) has corner points:

A(6,0), B(0,3)

Step 2 — Evaluate Z1 Mark

At A(6,0): $Z = 6$

At B(0,3): $Z = 6$

Step 3 — Conclusion1 Mark

Min Z = 6, occurring at both A(6,0) and B(0,3).

Since both give same value, every point on AB also gives minimum → infinitely many solutions.

Min Z = 6 (multiple solutions)
2021

Q. Solve: Maximise $Z = -x + 2y$ subject to $x \geq 3$, $x + y \geq 5$, $x + 2y \geq 6$, $y \geq 0$.

Step 1 — Corner points1 Mark

Feasible region has corner points: A(6,0), B(4,1), C(3,2)

Step 2 — Evaluate Z1.5 Marks

At A(6,0): $Z = -6$

At B(4,1): $Z = -4 + 2 = -2$

At C(3,2): $Z = -3 + 4 = 1$

Step 3 — Maximum0.5 Mark

Largest = 1 at C(3, 2)

Max Z = 1 at (3, 2)
2020

Q. Maximise $Z = x + y$ subject to $x - y \leq -1$, $-x + y \leq 0$, $x, y \geq 0$.

Step 1 — Analyze constraints1 Mark

$x - y \leq -1 \Rightarrow y \geq x + 1$

$-x + y \leq 0 \Rightarrow y \leq x$

Combined: $x + 1 \leq y \leq x$ — impossible (contradiction).

Step 2 — Conclusion1 Mark

No common feasible region exists. The problem has no feasible solution.

No feasible solution