Linear Programming
Easy Overview
Ever wondered how companies decide what to produce to make the most profit with limited resources? That's linear programming. You take constraints (budget, time, materials) and find the best outcome. It's like a puzzle: given all these restrictions, what's the smartest move?
What is LPP?
A Linear Programming Problem (LPP) has three parts: a goal (maximize profit or minimize cost), variables (things you can control), and constraints (limits on those variables). Everything is linear — no x², no xy, just nice straight lines. Think of it like: 'I have 10 hours and ₹500 — what combo of products should I make?'
Formulating an LPP
Step 1: Identify the decision variables (let x = number of chairs, y = number of tables). Step 2: Write the objective function (Z = 50x + 80y — profit per item). Step 3: Write all constraints (time limit, material limit) as inequalities. Step 4: Non-negativity constraints: x ≥ 0, y ≥ 0 (can't make negative stuff). Done.
Graphical Method — Feasible Region
Plot each constraint as a line on the graph. The area where ALL constraints are satisfied is the 'feasible region'. It's usually a polygon. Shade it. Anything outside is impossible — you'd break some constraint. This region is your playground; the optimal solution lives somewhere on its boundary.
Finding the Optimal Solution
The optimal point is always at a corner (vertex) of the feasible region. Calculate Z = objective function at every corner. The corner with the highest (for max) or lowest (for min) Z value is your answer. This is the 'corner point method'. Check all vertices, pick the best one. No need to check inside — the maths guarantees it's on the edge.
Types of Solutions
LPP can have: (a) a unique optimal solution (one corner wins), (b) multiple optimal solutions (two corners give same Z, and so does the entire edge between them), (c) unbounded solution (feasible region goes on forever and Z keeps increasing — bad news), or (d) infeasible (no region exists — constraints contradict each other).
Key Points
- •LPP = maximize/minimize a linear function under linear constraints
- •Non-negativity: x ≥ 0, y ≥ 0 always
- •Feasible region = area satisfying all constraints
- •Optimal solution is always at a corner of the feasible region
- •Corner point method: find Z at each vertex, pick best
- •Multiple optimal solutions exist if objective line is parallel to a constraint edge
- •Unbounded = feasible region doesn't close; infeasible = no common area
Practice Questions
- A company makes two products A and B. Profit per unit is ₹60 for A and ₹40 for B. Each requires 2 hours on machine M1 and 1 hour on M2. M1 works max 80 hours, M2 max 60 hours. Formulate LPP and solve graphically.
- Minimize Z = 3x + 2y subject to x + y ≥ 8, 3x + y ≥ 12, x, y ≥ 0.
- Maximize Z = 5x + 7y subject to x + y ≤ 10, 2x + 3y ≤ 24, x, y ≥ 0. Find all corner points and the optimal solution.
- Explain with an example how an LPP can have multiple optimal solutions.