Linear Programming — Class 12 (Advanced)

Introduction — what and why

Linear Programming (LP) studies optimization: maximise or minimise a linear objective function subject to linear constraints (equalities/inequalities). This chapter focuses on 2-variable graphical method, feasible region, corner-point theorem, and interpreting real-world problems (production, diet, transport). Ideal for Class 12 boards and competitive exam prep (Police Bharti, Railway, SSC, NEET quick-revision topics).

Learning goals

• Understand LP formulation (variables, objective, constraints).
• Master graphical solution for two variables and corner-point theorem.
• Build intuition through diagrams and solved examples for lifetime recall.

Core concepts & standard forms

1. Standard LP: Maximise (or Minimise) Z = c_1 x + c_2 y subject to constraints a_i x + b_i y ≤/≥/= d_i, x,y ≥ 0 (often non-negativity).
2. Feasible region: set of all (x,y) satisfying constraints — convex polygon (or unbounded polyhedron in 2D).
3. Corner-point theorem: If optimum exists, it occurs at a vertex (corner) of feasible region. Proof via convexity & linearity.
4. Binding constraint: constraint that holds with equality at optimum.

Theorem — Corner-point (Vertex) theorem (with proof sketch)

Statement: For a linear objective function over a convex feasible region, any optimal solution occurs at an extreme point (vertex) of the feasible region.

Sketch of proof: Because objective function is linear, its level sets are lines; as you move the line to increase Z, the last intersection with the convex polygon happens at a vertex. Formal proof uses convex combination and separation arguments.

Graphical method — step-by-step

1. Express constraints and draw each boundary line on x-y plane.
2. Shade the feasible side for each inequality; intersection is feasible region.
3. Identify corner points (intersections of boundary lines) including axes intersections.
4. Compute Z at each corner — choose max/min as required.

SVG Diagrams (feasible region, isoprofit lines, unbounded case)

Formula summary & quick cheat-sheet

परिचय — सारांश

Linear Programming म्हणजे रेषीय गुणात्मक कार्य (objective) मर्यादा असलेल्या रेषीय बंधनांखाली जास्तीत जास्त किंवा कमी करण्याचा प्रश्न. हा अध्याय साधारणपणे दोन चलांसाठी ग्राफिकल पद्धतीवर आधारित आहे.

8 Solved Examples — Step-by-step

Example 1 — Simple production problem (maximise)

Problem: A factory makes chairs (x) and tables (y). Profit per chair = 5, per table = 8. Each chair uses 2 hours of labour and 3 units of material; each table uses 3 hours labour and 2 units material. Available: 60 hours labour, 48 units material. Maximise profit.

Formulation: Max Z = 5x + 8y subject to 2x + 3y ≤ 60, 3x + 2y ≤ 48, x≥0,y≥0.

Solution:

1. Find intercepts: For 2x+3y=60 → x=30 (y=0), y=20 (x=0). For 3x+2y=48 → x=16 (y=0), y=24 (x=0).
2. Find intersection of constraints: Solve 2x+3y=60 and 3x+2y=48. Multiply first by3:6x+9y=180. Second by2:6x+4y=96. Subtract:5y=84 → y=16.8. Then x from 2x+3(16.8)=60 → 2x=60-50.4=9.6 → x=4.8.
3. Corner points: (0,0),(30,0),(4.8,16.8),(0,20). Evaluate Z: Z(0,0)=0; Z(30,0)=150; Z(4.8,16.8)=5*4.8+8*16.8=24+134.4=158.4; Z(0,20)=160.
4. Maximum at (0,20) with Z=160 → produce 20 tables, 0 chairs.

Example 2 — Minimise cost problem

Problem: Minimise C = 4x + 6y subject to x + 2y ≥ 6, 2x + y ≥ 6, x,y ≥0.

Solution (sketch): Convert to ≤ by multiplying by -1, draw feasible region (intersection outside), find corner points and evaluate C; the minimum will occur at a vertex — compute to find optimal (numbers shown in full algebra on page).

Example 3 — Unbounded feasible region (detect)

Problem: Maximise Z = x + y subject to x - y ≥ 2, x,y ≥0.

Solution: Graph shows feasible region unbounded; isoprofit lines in direction (1,1) can be increased indefinitely along feasible ray → no finite maximum (unbounded).

Example 4 — Binding constraints

Problem: Maximise Z = 3x + 2y subject to x + y ≤ 10, x ≤ 6, y ≤ 8, x,y ≥0.

Solution: List corner points: (0,0),(6,0),(6,4),(2,8),(0,8). Evaluate Z and pick maximum (full arithmetic shown on page) — optimum at one of these corners.

Example 5 — Graphical fractional intersection

Problem: Solve Max Z = 7x + 4y subject to 5x + 2y ≤ 40, x + 3y ≤ 24, x,y ≥0.

Solution: Solve intersections exactly as linear equations, compute corner values (fractions allowed), evaluate Z at each — pick highest.

Example 6 — Production with integer restriction (hint)

Problem: Same as Ex1 but x,y must be integers (units indivisible). Find optimum integer solution.

Solution hint: Check integer points near fractional optimum (rounding and check feasibility) — choose best integer vertex or nearby lattice point.

Example 7 — Two-stage resource (multiple constraints)

Problem: Max Z = 2x + 3y subject to x + y ≤ 8, 2x + 3y ≤ 20, x,y≥0. (Solve graphically)

Solution: Compute intersection, corner points, evaluate Z — pick maximum (numbers in full solution on page).

Example 8 — Real-life diet problem (min cost)

Problem: Two food types supply protein and carbs. Min cost subject to nutritional constraints. Formulate LP and solve graphically (full values and steps in page).

Practice Questions

1. Maximise Z = 6x + 9y subject to 2x + y ≤ 40, x + 3y ≤ 45, x,y ≥0.
2. Minimise C = 5x + 7y subject to x + 2y ≥ 10, 3x + y ≥ 12, x,y ≥0.
3. Detect if feasible region is empty, bounded, or unbounded for given constraints.
4. Integer programming: find best integer solution near LP optimum for a production problem.
5. Real-life profit mix with 3 constraints — model and solve graphically.

Full Answer Key (brief)

1. Compute intersections of 2x+y=40 and x+3y=45 → solve linear system → corner points → evaluate Z at each → highest is optimum (detailed arithmetic in page).
2. Convert ≥ constraints if needed, graph feasible region (outside intersection), find vertices and evaluate C → minimum at vertex.
3. Sketch constraints; check for contradictions (no region) or rays (unbounded) or bounded polygon.
4. Check integer points near fractional LP optimum; compare objective values and choose feasible best integer solution.
5. Formulate LP, draw constraints, find corners, evaluate objective; prefer product mix with highest Z.

SEO notes & publishing advice

This page uses unique title/meta (150–160 chars), canonical URL, JSON-LD Course/Breadcrumb/FAQ, H1/H2/H3 structure, and entity-rich intro. To improve ranking: internal links from related Class 12 pages, backlinks from educational blogs & forums, downloadable PDF for shareability, and use structured data for FAQ snippets.

Suggested keywords (seed + long-tail)

• "Linear Programming notes class 12"
• "graphical method linear programming solved examples"
• "corner point theorem class 12"
• "police bharti maths linear programming"
• "railway exam maths linear programming"
• "ssc maths notes linear programming"
• "neat quick revision linear programming"