Linear Programming — Problem Formulation and Graphical Method

• Identify and define decision variables, objective function, and constraints from a word problem
• Plot linear inequalities on the coordinate plane and shade the feasible region
• Apply the Corner Point Theorem to locate the optimal solution
• Evaluate the objective function at each vertex and select the maximum or minimum value
• Use the isoprofit/isocost line method as an alternative graphical approach
• Verify solutions for both bounded and potentially unbounded feasible regions

Level 1 — Foundations

Components of an LP problem:

Feasible region: the set of all points $(x,y)$ satisfying ALL constraints simultaneously. It is always a convex set (any two points in the region can be joined by a line segment that stays in the region).

Corner Point Theorem: The maximum and minimum values of a linear objective function over a bounded convex feasible region are attained at corner points (vertices) of the region.

Steps to solve graphically:

1. Convert each inequality to equality and plot the line.
2. Determine which side satisfies the inequality (test the origin, unless the line passes through it).
3. Shade the feasible side for each constraint; the common shaded area is the feasible region.
4. Identify all corner points by solving pairs of boundary equations simultaneously.
5. Evaluate $Z$ at each corner point.
6. State the maximum or minimum value and the point where it occurs.

Isoprofit line method: Draw the line $Z = c$ for some convenient constant $c$. Slide it parallel to itself (keeping slope constant) outward (for maximisation) or inward (for minimisation) until it just touches the feasible region. The contact point is optimal.

Level 2 — JEE Depth

Why is the feasibility region convex? Each linear inequality defines a half-plane. The intersection of finitely many half-planes is a convex polygon (or unbounded convex set). The intersection of convex sets is convex.

Proof sketch of Corner Point Theorem: A linear function $Z = ax + by$ is a continuous function on a compact (closed and bounded) convex set. By the extreme value theorem, it attains its max and min. For a linear function on a convex polygon, the maximum must occur at a boundary point; on a linear boundary edge, the maximum occurs at an endpoint (vertex). Hence the optimum is always at a vertex.

Finding corner points systematically: For $n$ constraints (plus non-negativity), list all pairs of active constraints. Solve each pair. Keep only those solutions that satisfy ALL constraints (feasible vertices). For $n$ constraints you get at most $\binom{n+2}{2}$ candidates but typically far fewer feasible vertices.

Isoprofit slope analysis: Objective: $Z = ax + by$ → rearranged: $y = -\frac{a}{b}x + \frac{Z}{b}$. Slope of isoprofit line = $-a/b$. If this equals the slope of a constraint boundary, the entire edge (not just a vertex) may be optimal → infinitely many solutions.

Example 1: A factory makes tables (profit ₹200 each) and chairs (profit ₹100 each). Available: 60 m² wood and 40 labour-hours. One table needs 3 m² wood and 2 labour-hours; one chair needs 1 m² wood and 2 labour-hours. Find the production mix that maximises profit.

Step 1 — Define variables.
Let x = number of tables, y = number of chairs.

Step 2 — Write objective function.
Maximise Z = 200x + 100y.

Step 3 — Write constraints.
Wood:   3x + y ≤ 60
Labour: 2x + 2y ≤ 40  →  x + y ≤ 20
Non-negativity: x ≥ 0, y ≥ 0.

Step 4 — Plot boundaries.
Line L1: 3x + y = 60  →  x-intercept (20, 0), y-intercept (0, 60).
Line L2:  x + y = 20  →  x-intercept (20, 0), y-intercept (0, 20).

Step 5 — Identify feasible region (origin satisfies both ≤ inequalities).
Feasible region is bounded by L1, L2, x-axis, y-axis.

Step 6 — Find corner points.
O = (0, 0)
A = (20, 0): intersection of x + y = 20 and y = 0 → check 3(20)+0 = 60 ≤ 60 ✓
B = intersection of 3x + y = 60 and x + y = 20:
   Subtract: 2x = 40 → x = 10, y = 10. Check: 30+10=40≤60 ✓, 10+10=20 ✓
   B = (10, 10)
C = (0, 20): intersection of x + y = 20 and x = 0 → check 3(0)+20=20 ≤ 60 ✓

Step 7 — Evaluate Z at each corner.
O = (0,0):   Z = 0
A = (20,0):  Z = 200(20) + 100(0) = 4000
B = (10,10): Z = 200(10) + 100(10) = 2000 + 1000 = 3000
C = (0,20):  Z = 200(0) + 100(20) = 2000

Maximum Z = ₹4000 at (20, 0).

Answer: Make 20 tables and 0 chairs for maximum profit ₹4000.

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

Step 1 — Boundaries.
L1: x + y = 4  →  (4,0), (0,4).
L2: x + 3y = 6 →  (6,0), (0,2).

Step 2 — Feasible side (≥ constraints): away from origin.
Test origin (0,0): 0+0 = 0 < 4. Not feasible. Shade the OTHER side of each line.

Step 3 — Corner points.
Intersection of L1 and L2:
  x + y = 4
  x + 3y = 6
  Subtract: 2y = 2 → y = 1, x = 3. Point P = (3, 1). Check: 3+3=6≥6 ✓, 3+1=4≥4 ✓
Intersection of L1 with x-axis (y=0): x = 4 → A = (4, 0). Check: 4+0=4≥6? NO. Not feasible.
Intersection of L2 with x-axis (y=0): x = 6 → B = (6, 0). Check: 6+0=6≥6 ✓, 6+0=6≥4 ✓
Intersection of L1 with y-axis (x=0): y = 4 → C = (0, 4). Check: 0+12=12≥6 ✓, 0+4=4≥4 ✓

Corner points of feasible region: B=(6,0), P=(3,1), C=(0,4).
(The region is unbounded above and to the right.)

Step 4 — Evaluate Z.
B = (6,0):  Z = 18 + 0 = 18
P = (3,1):  Z = 9 + 2 = 11
C = (0,4):  Z = 0 + 8 = 8

Minimum Z = 8 at (0, 4).
Since the region is unbounded, verify no feasible point gives Z < 8.
Draw Z = 8: 3x + 2y = 8 → (8/3, 0) and (0,4). Check if any feasible point is below this line:
The feasible region is above/right of both constraints; the isocost line Z=8 touches at (0,4)
and the rest of the feasible region has larger Z. Minimum confirmed.

Answer: x = 0, y = 4, minimum Z = 8.

• Q1: Write the LP formulation (variables, objective, constraints) for: "A school canteen makes samosas (profit ₹5 each) and sandwiches (profit ₹8 each). Flour available: 10 kg. Samosa needs 50 g, sandwich needs 100 g. Max 80 items total."
• Q2: Plot the feasible region for $x + 2y \leq 10$, $3x + y \leq 12$, $x \geq 0$, $y \geq 0$ and list all corner points.
• Q3: For the feasible region in Q2, maximise $Z = 5x + 4y$.
• Q4: What is the slope of the isoprofit line for $Z = 3x + 5y$? If a constraint boundary has the same slope, what does that imply?
• Stretch: Q5: A corner point of the feasible region is $(2, 3)$. The objective function $Z = px + qy$ gives $Z = 14$ at this point and $Z = 16$ at $(4, 1)$. Find $p$ and $q$ and state the objective function.

NCERT Chapter 12 link: Section 12.2 (Linear programming problem and its mathematical formulation); 12.3 (Graphical method — corner point method); Worked examples 12.1–12.4.

Exam connections: JEE Main: one full LP problem per paper (4 marks); tests formulation accuracy + corner point evaluation. JEE Advanced: rarely a standalone LP question but LP reasoning appears in optimisation.

Study strategy: Always write the formulation step-by-step before drawing any graph — wrong formulation loses all marks. Practise graphing two-variable LP in under 5 minutes by memorising the intercept-method for lines. Check your corner points arithmetically — one arithmetic error in a vertex leads to the wrong optimal solution.

• LP graph builder: drag constraint lines, watch the feasible region update in real time, and see the objective function value update at each corner point.
• Isoprofit slider: slide the objective function line across the feasible region and observe which vertex it last touches for maximisation vs minimisation.
• AI mentor reflection: "If the feasible region is a triangle with vertices $(0,0)$, $(4,0)$, and $(0,6)$, for what objective functions $Z = ax+by$ is the maximum at $(4,0)$? At $(0,6)$? Find the condition on $a$ and $b$."

• "Why does increasing the number of constraints generally reduce the feasible region? Can a new constraint ever enlarge it?"
• "In Example 1, the optimal solution was 20 tables and 0 chairs. Does this make sense in real life? What real-world constraint might we have missed?"
• Stretch: "Suppose the wood constraint in Example 1 changed from 60 m² to 80 m². Without re-solving from scratch, predict how the feasible region changes and which corner point will now be optimal."

• Complete the core practice + one extension activity (photo, table, short reflection, or mini-project) for base XP + topic badge.
• 5-7 day streak or family discussion note = multiplier + visible artifact in parent/principal dashboard.
• Best real-world application stories (anonymised) featured on class or national leaderboard.

• Build a physical "constraint board": use string to mark two constraint lines on a sheet of paper, shade the feasible region with coloured pencils, then slide a ruler (representing the isoprofit line) to find the optimal corner — photograph your board as portfolio evidence.
• Future Skill track: AI Mastery — Linear programming is the foundation of operations research and resource allocation in AI systems; connect LP to how recommendation engines allocate ad budgets under constraints (budget ≤ B, impressions ≥ target).
• Coding extension: Write a Python script using scipy.optimize.linprog to solve the factory problem from Example 1; compare the numerical result to your graphical answer and explain why linprog minimises by default (negate the objective to maximise).

This material emphasises experiential "learning by doing", competency (apply/create/analyse), vocational exposure, critical thinking, and multidisciplinary connections. Designed to feed live worlds, AI Mentor (with memory), gamification, robotics, parent analytics, and future skills — not just exam prep.

Portfolio Evidence Idea: Your photo/table/reflection/project + one sentence on "How this helps me in real life or a possible future path."

Open the Practice tab for aligned questions (easy/medium/hard + case-based) with full AI scaffolding.

See curriculum for cross-links and the full future-skills/robotics chapters.