Intermediate

26 min read

Linear Programming — Formulation, Feasible Region & Corner Points

Master Linear Programming for JEE Main and Board Exams. Covers LP terminology decision variables objective function constraints feasible region corner points, graphical method 6 steps draw boundary lines determine feasible half-plane identify feasible region find corners evaluate Z at corners, Corner Point Theorem bounded region max and min exist, formulation of LP from word problems at least ≥ at most ≤, manufacturing diet and resource allocation examples, multiple optimal solutions same Z at adjacent corners, with fully verified JEE Main Board practice questions.

New

Linear Programming (LP) is the mathematical technique for finding the best outcome — maximum profit, minimum cost, optimal allocation — from a set of linear constraints. Every LP problem has the same structure: a linear objective function to be maximised or minimised, subject to a set of linear constraints (inequalities). The powerful insight at the heart of LP is the Corner Point Theorem: the optimal value of the objective function always occurs at a corner (vertex) of the feasible region. This reduces an infinite optimisation problem to checking just a few points. For JEE Main and CBSE Board, LP problems appear every year — typically 1–2 questions involving formulation, graphical method, and corner point evaluation.

1. Key Terminology

Term	Definition
Decision variables	The unknowns to be determined (e.g., x = units of product A, y = units of product B)
Objective function	The linear expression to be maximised or minimised: Z = ax + by
Constraints	Linear inequalities that restrict the decision variables (resource limits, requirements)
Non-negativity constraints	x ≥ 0, y ≥ 0 — always included (quantities can't be negative)
Feasible region	The set of all (x, y) satisfying ALL constraints simultaneously; always a convex polygon (or unbounded region)
Feasible solution	Any point (x, y) inside or on the boundary of the feasible region
Optimal solution	The feasible solution that gives the maximum (or minimum) value of Z
Corner points (vertices)	The vertices of the feasible region polygon; the optimal solution always occurs at one of these

2. Standard Form of an LP Problem

Maximise (or Minimise) $Z = a x + b y$
Subject to: $a_{1} x + b_{1} y \leq c_{1}$ , $a_{2} x + b_{2} y \leq c_{2}$ , …
and $x \geq 0$ , $y \geq 0$

Constraints may also be ≥ or = depending on the problem. Resource constraints are typically ≤; requirement constraints are typically ≥.

3. Graphical Method — Step-by-Step

Convert each constraint to an equation (replace ≤ or ≥ with =) and draw the boundary line.
Determine the feasible half-plane for each constraint: test the origin (0,0). If it satisfies the constraint, shade the origin side; otherwise shade the opposite side.
Identify the feasible region — the intersection of all shaded half-planes (including x ≥ 0 and y ≥ 0).
Find all corner points of the feasible region: these are at intersections of boundary lines (solve pairs of equations).
Evaluate Z at each corner point.
The optimal value is the largest (for max) or smallest (for min) among all corner point values.

4. Corner Point Theorem (Fundamental Theorem of LP)

If a feasible region is bounded (enclosed), the objective function Z attains both its maximum and minimum values, and both occur at corner points of the feasible region.

If the feasible region is unbounded, maximum or minimum may or may not exist — must check (covered in Topic 2).

Multiple optimal solutions: If Z takes the same value at two adjacent corner points, then the entire edge between them is optimal (infinitely many solutions).

5. Worked Example 1 — Maximisation (JEE Main / Board)

Problem: Maximise Z = 5x + 4y subject to: 6x + 4y ≤ 24, x + 2y ≤ 6, x ≥ 0, y ≥ 0.

Step 1: Draw boundary lines.

L1: 6x+4y=24 → intercepts (4,0) and (0,6).

L2: x+2y=6 → intercepts (6,0) and (0,3).

Step 2: Find corner points.

O = (0,0); A = (4,0) [L1 meets x-axis]; B = intersection of L1 and L2; C = (0,3) [L2 meets y-axis].

Intersection B: From L2: x = 6−2y. Substitute into L1: 6(6−2y)+4y = 24 → 36−12y+4y = 24 → y = 3/2. Then x = 6−3 = 3. B = (3, 3/2).

Step 3: Evaluate Z = 5x + 4y at each corner.

Corner Point	Z = 5x + 4y
O = (0, 0)	0
A = (4, 0)	20
B = (3, 3/2)	5(3)+4(3/2) = 15+6 = 21 ← Maximum
C = (0, 3)	12

Maximum Z = 21 at (3, 3/2).

6. Worked Example 2 — Minimisation (Board)

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

Corner points:

L1: x+2y=3 → (3,0) and (0,3/2). L2: x+y=2 → (2,0) and (0,2).

Intersection of L1 and L2: x+2y=3 and x+y=2 → subtracting: y=1, x=1. So (1,1).

Feasible region is to the upper-right of both lines (satisfies ≥). Corner points: (3,0), (1,1), (0,2).

Corner Point	Z = x + 2y
(3, 0)	3 ← Minimum (tied)
(1, 1)	3 ← Minimum (tied)
(0, 2)	4

Minimum Z = 3 — attained at both (3,0) and (1,1), so every point on the segment joining them is also optimal (multiple optimal solutions).

7. Formulation — Translating Word Problems to LP

Step-by-Step Formulation Method

Identify the decision variables — what are you choosing? (e.g., x = number of units of product A)
Write the objective function — what are you maximising/minimising? (profit, cost, time)
List all constraints — what limits the variables? (capacity, budget, requirements)
Add non-negativity constraints — x ≥ 0, y ≥ 0 (always).

Worked Formulation (JEE Main / Board)

A factory makes two products A and B. Each unit of A requires 2 hours of machine time and 1 hour of labour; each unit of B requires 1 hour of machine and 3 hours of labour. Machine time available: 10 hours; labour available: 15 hours. Profit per unit: A = ₹5, B = ₹8. Maximise profit.

Let x = units of A, y = units of B.

Objective: Maximise Z = 5x + 8y

Constraints: 2x + y ≤ 10 (machine), x + 3y ≤ 15 (labour), x ≥ 0, y ≥ 0.

Corner points: (0,0), (5,0), (3,4), (0,5).

Intersection of 2x+y=10 and x+3y=15: multiply first by 3: 6x+3y=30; subtract: 5x=15 → x=3, y=4.

Z values: 0, 25, 47, 40. Maximum profit = ₹47 at x=3, y=4.

Corner Point Evaluation — Organised Table Method

Step	Action	Common Error to Avoid
1	Draw each constraint line; find x-intercept (y=0) and y-intercept (x=0)	Don't forget to include the axes (x=0 and y=0) as constraints
2	Test (0,0) for each constraint; shade the feasible side	If (0,0) is ON the line, test another point like (0,1)
3	Identify ALL corner points — solve each pair of intersecting boundary lines	Verify each corner point satisfies ALL constraints before including it
4	Compute Z at each corner; present in a table	Don't stop at the first large/small value — check all corners
5	State the optimal value and the optimal point(s)	If two adjacent corners give same Z, mention the entire edge is optimal

JEE Main / Board Power Tips — LP Formulation & Corner Points

Always verify that each corner point satisfies ALL the constraints, not just the two lines whose intersection you solved. A common error: finding the intersection of two boundary lines and treating it as a corner without checking it lies within the feasible region.
The origin (0,0) is a corner point only if both x=0 and y=0 satisfy all constraints. For ≥ constraints, the origin often violates them — don't automatically include it.
For a bounded feasible region: both max and min always exist. For an unbounded region: max may not exist for maximisation, min may not exist for minimisation — need special checks (Topic 2).
If Z is the same at two adjacent corner points, the segment between them is the optimal set. State: "The objective function attains maximum (or minimum) value at every point on segment AB."
In formulation problems, read every constraint carefully. "At least" → ≥; "At most" or "not more than" → ≤; "Exactly" → =. Mixing these up is the most common formulation error.

Practice Questions

Q1 (JEE Main / Board): Maximise $Z = 3 x + 2 y$ subject to the constraints: $x + y \leq 4$ , $x - y \leq 2$ , $x \geq 0, y \geq 0$ .

Explanation:

First, find the boundary lines by treating the inequalities as equations:
Line $L_{1}$ : $x + y = 4 ⟹$ Intercepts are $(4, 0)$ and $(0, 4)$ .
Line $L_{2}$ : $x - y = 2 ⟹$ Intercepts are $(2, 0)$ and $(0, - 2)$ .

Find the intersection of $L_{1}$ and $L_{2}$ :
$x + y = 4$
$x - y = 2$
Adding both: $2 x = 6 ⟹ x = 3$ . Substituting $x$ : $3 + y = 4 ⟹ y = 1$ .
Intersection point: $B (3, 1)$ .

The corner points of the bounded feasible region (satisfying all constraints including $x, y \geq 0$ ) are $O (0, 0)$ , $A (2, 0)$ , $B (3, 1)$ , and $C (0, 4)$ .

Corner Point	Value of $Z = 3 x + 2 y$
$O (0, 0)$	0
$A (2, 0)$	6
$B (3, 1)$	11 ← Maximum
$C (0, 4)$	8

Therefore, the maximum value is $Z = 11$ at the point $(3, 1)$ .

Q2 (Board): A diet problem: A person needs at least 24 units of protein and 9 units of vitamin daily. Food A costs ₹5 per unit and provides 4g protein and 3g vitamin. Food B costs ₹4 per unit and provides 6g protein and 1g vitamin. Formulate and solve to minimise daily cost.

Explanation:

Let $x$ be the units of Food A, and $y$ be the units of Food B.
Objective function to minimise: $C = 5 x + 4 y$

Constraints:
$4 x + 6 y \geq 24$ (Protein requirement)
$3 x + y \geq 9$ (Vitamin requirement)
$x \geq 0, y \geq 0$ (Non-negativity)

Find the intersection of $4 x + 6 y = 24$ and $3 x + y = 9$ :
From the second equation, $y = 9 - 3 x$ . Substitute into the first:
$4 x + 6 (9 - 3 x) = 24$
$4 x + 54 - 18 x = 24 ⟹ - 14 x = - 30 ⟹ x = \frac{15}{7}$
$y = 9 - 3 (\frac{15}{7}) = \frac{63 - 45}{7} = \frac{18}{7}$

The corner points of the unbounded feasible region are $(0, 9)$ , $(\frac{15}{7}, \frac{18}{7})$ , and $(6, 0)$ .

Evaluate $C = 5 x + 4 y$ at these points:
At $(0, 9)$ : $C = 5 (0) + 4 (9) = 36$
At $(\frac{15}{7}, \frac{18}{7})$ : $C = 5 (\frac{15}{7}) + 4 (\frac{18}{7}) = \frac{75}{7} + \frac{72}{7} = \frac{147}{7} = 21$
At $(6, 0)$ : $C = 5 (6) + 4 (0) = 30$

The minimum cost is ₹21, achieved by consuming $\frac{15}{7}$ units of Food A and $\frac{18}{7}$ units of Food B.

Q3 (JEE Main MCQ): The corner points of the feasible region of an LP problem are $(0, 0)$ , $(0, 3)$ , $(5, 0)$ , and $(3, 2)$ . If the objective function is $Z = 4 x + 3 y$ , the maximum value of $Z$ is:

A) 9 B) 20 C) 26 D) 18

Answer: B) 20

Explanation: Evaluate the objective function $Z = 4 x + 3 y$ at each given corner point:
$Z (0, 0) = 4 (0) + 3 (0) = 0$
$Z (0, 3) = 4 (0) + 3 (3) = 9$
$Z (5, 0) = 4 (5) + 3 (0) = 20$
$Z (3, 2) = 4 (3) + 3 (2) = 12 + 6 = 18$

The maximum value is $20$ , which occurs at $(5, 0)$ .

Q4 (Board): Formulate and solve: A manufacturer makes two types of toys — A and B. Toy A requires 3 hours of painting and 1 hour of assembly; Toy B requires 1 hour of painting and 2 hours of assembly. Total painting time available: 12 hours; assembly time: 8 hours. Profit: ₹20 per toy A, ₹15 per toy B. Maximise profit.

Explanation:

Let $x$ = number of Toy A produced, and $y$ = number of Toy B produced.

Objective Function: Maximise $Z = 20 x + 15 y$

Constraints:
$3 x + y \leq 12$ (Painting time constraint)
$x + 2 y \leq 8$ (Assembly time constraint)
$x \geq 0, y \geq 0$ (Non-negativity constraint)

Find the intersection of $3 x + y = 12$ and $x + 2 y = 8$ :
$y = 12 - 3 x ⟹ x + 2 (12 - 3 x) = 8 ⟹ x + 24 - 6 x = 8 ⟹ - 5 x = - 16 ⟹ x = \frac{16}{5}$
$y = 12 - 3 (\frac{16}{5}) = \frac{60 - 48}{5} = \frac{12}{5}$

The corner points of the feasible region are $(0, 0)$ , $(4, 0)$ , $(\frac{16}{5}, \frac{12}{5})$ , and $(0, 4)$ .

Evaluate $Z$ at each corner point:
At $(0, 0)$ : $Z = 0$
At $(4, 0)$ : $Z = 20 (4) + 15 (0) = 80$
At $(\frac{16}{5}, \frac{12}{5})$ : $Z = 20 (\frac{16}{5}) + 15 (\frac{12}{5}) = 64 + 36 = 100$
At $(0, 4)$ : $Z = 20 (0) + 15 (4) = 60$

Maximum profit = ₹100 at $x = 3.2$ and $y = 2.4$ . (Note: In a strict integer programming scenario, you would test nearby whole numbers, but in standard continuous LPP, the mathematical maximum is exactly 100).

Related Study Material

More Mathematics Notes More Vectors And Linear Programming Notes All Linear Programming Topics

Practice Questions

Mathematics Practice Linear Programming Questions

Topic Information

DifficultyIntermediate

Est. Read Time26 minutes

CategoryLinear Programming

Quick Actions

Track Your Learning

Study Tips

Take notes of key points while reading

Practice related questions after studying

Review topics marked as "Learning" regularly

Test your knowledge with practice questions

Edvaya Target

Detailed Notes & Solved Examples

Master complex concepts with our rich, topic-wise study notes. Access hundreds of step-by-step solved examples and interactive flashcards right from your phone.

Edvaya Target

Edvaya Aspire

Take a Free Mock Test

Target Subjects

Aspire Subjects

Subject Mastery

Linear Programming — Formulation, Feasible Region & Corner Points

1. Key Terminology

2. Standard Form of an LP Problem

3. Graphical Method — Step-by-Step

4. Corner Point Theorem (Fundamental Theorem of LP)

5. Worked Example 1 — Maximisation (JEE Main / Board)

6. Worked Example 2 — Minimisation (Board)

7. Formulation — Translating Word Problems to LP

Step-by-Step Formulation Method

Worked Formulation (JEE Main / Board)

Corner Point Evaluation — Organised Table Method

Practice Questions

Related Study Material

Practice Questions

Topic Information

Quick Actions

Track Your Learning

Study Tips

Edvaya Target

We Value Your Privacy