Linear Programming

Every business wants maximum profit with limited resources. That is linear programming.

Factory Example: A factory makes chairs and tables. Chair gives ₹20 profit, table ₹30. Wood limited 100 units, labour 80 hours. Chair needs 1 wood + 2 labour, table needs 3 wood + 1 labour. How many chairs (x) and tables (y) to make? Objective: Maximize Z=20x+30y subject to x+3y≤100, 2x+y≤80, x≥0,y≥0. This is LPP.

Diet Problem: You want minimum cost diet with enough protein and vitamins. Food A costs ₹5, Food B ₹8. Protein need: A gives 2 units, B gives 4 units, minimum 40 units. This becomes Minimize Cost.

Transportation: Sending goods from factories to shops cheapest way. Also allocation, manufacturing, farming - all use LPP.

So LPP = decision variables (x,y) + objective function (Max/Min) + linear constraints (≤,≥).

Decision Variables: What you decide - e.g. x = number of chairs, y = number of tables. Must be ≥0 (non-negative).

Objective Function: What you want to optimize. Z = c1x + c2y. If profit, maximize. If cost, minimize. Linear - power of x,y is 1 only, no x², xy.

Constraints: Limitations. Wood: x+3y≤100, Labour: 2x+y≤80. Also linear, with ≤ or ≥. Equality also allowed.

Standard form: Maximize Z = c1x1+c2x2+...+cnxn subject to a11x1+a12x2≤b1, ..., xj≥0.

Example: Max Z=3x+2y subject to x+2y≤10, x+y≤6, x≥0,y≥0. Here c1=3,c2=2, constraints 2.

Slack variable: To convert ≤ to equality, add slack s≥0: x+2y+s=10. This is used in simplex later but not needed for graphical.

Plot each constraint as line on graph. Inequality tells which side is allowed.

Feasible Solution: Any point (x,y) satisfying ALL constraints including x≥0,y≥0. If you have x+2y≤10, point (2,2) satisfies 2+4=6≤10, so feasible. (5,5) gives 15>10 not feasible.

Feasible Region: Set of all feasible points. It is always a convex polygon (including interior). Corner points are where two constraint lines intersect.

Bounded vs Unbounded: If feasible region is closed like rectangle/triangle, it is bounded - you can encircle it. If it goes infinite (e.g. x≥1,y≥1 no upper limit), it is unbounded. Max may not exist in unbounded but Min may.

Infeasible: If constraints contradict, e.g. x+y≤2 and x+y≥5, no point satisfies both, so no feasible region.

Graph example: x≥0,y≥0 first quadrant, x+2y≤10 line from (10,0) to (0,5), x+y≤6 line from (6,0) to (0,6). Overlapping shaded area is quadrilateral O-A-B-C.

For 2 variables, best way to solve LPP is graphical corner point method. Steps NCERT:

Step 1: Plot constraints, find feasible region, label corner points A,B,C,D.

Step 2: Find coordinates of each corner by solving intersection of lines. Example: Intersection of x+2y=10 and x+y=6 => subtract => y=4, x=2 => point (2,4).

Step 3: Evaluate objective Z=c1x+c2y at each corner point.

Step 4: For maximization, corner with maximum Z is optimal. For minimization, minimum Z.

Example: Max Z=3x+2y. Corners: O(0,0) Z=0, A(6,0) Z=18, B(2,4) Z=3*2+2*4=14, C(0,5) Z=10. Max is 18 at A(6,0). So make 6 units of first product, 0 of second.

Theorem: Optimal value occurs at a corner point (if feasible region bounded). If unbounded, check if max/min actually exists.

NCERT gives 4 classic types:

1. Manufacturing: How much of each product to make for max profit with limited machines/materials. Eg chairs/tables.

2. Diet: Minimize cost of food with nutrition constraints ≥. Objective minimize, constraints ≥ type.

3. Transportation: Minimize shipping cost from i factories to j stores. Variables xij = units from i to j. Constraints supply ≤, demand ≥.

4. Allocation: Assign jobs to machines for max efficiency.

All have same math: linear objective + linear constraints. Difference is whether we maximize or minimize, and whether constraints are ≤ (resource limit) or ≥ (minimum need).

Trick: If diet says at least 40 protein, constraint is 2x+4y ≥40. Graph shading is away from origin.

Not every LPP has unique solution.

Multiple Optimal Solutions: If objective line Z is parallel to a side of feasible region, then every point on that side gives same Z. Example: Max Z= x+y, feasible region with side x+y=5 as boundary, then all points on that side have Z=5 max. Infinite optimal points, but all give same max value.

Unbounded: Feasible region infinite and Z can go to infinity. Example: Max Z= x+y, constraints only x≥0,y≥0 (no upper bound). Z can be infinite, so no max. But Min Z= x+y would have min 0 at origin.

Infeasible: No region. Example: x+y≤2 and x+y≥10 cannot both happen. So LPP has no solution.

How to check unbounded? In corner method, if region unbounded, evaluate Z at corners, but also check if Z can increase beyond corners arbitrarily. NCERT says if feasible region unbounded, max/min may not exist unless you can show open half-plane Z>... has no common point.

Another graphical way to think: iso-profit line.

Iso-Profit: Line c1x+c2y = k where profit is constant k. Different k give parallel lines with slope -c1/c2. As k increases, line moves outward parallel.

Procedure: Draw one iso-profit for small k inside feasible region. Then slide it outward parallel till it just touches feasible region at farthest point. That touching corner is optimal for max. For min cost, iso-cost line slides inward.

Iso-Cost: Same idea for cost w1x1+w2x2=C. All combos costing same lie on line. Lower cost lines are closer to origin. Slide inward till last touching point = minimum cost.

Why corner? Because parallel sliding last touch will always be at a corner (or whole edge). This visual proves corner point theorem.

Example: Max Z=2x+3y. Iso-profit 2x+3y=6 line. Slope -2/3. Slide out, last touch at corner (2,4) gives max 16.

One page to remember whole chapter:

LPP form: Optimize Z=c·x subject to Ax ≤/≥ b, x≥0.

Feasible: satisfies all. Region = convex polygon. Bounded vs unbounded.

Corner method: Evaluate Z at each corner, pick max/min.

Special: Parallel edge → infinite optimal same Z, Unbounded → Z→∞, Infeasible → no region.

Iso-profit: Slide parallel lines, last touch = optimum.

Exam tip: Always mention x≥0,y≥0, shade feasible, find intersection by solving two equations, evaluate Z in table.