Linear Programming
1. Introduction
Linear programming (LP) is a mathematical method for optimizing a linear objective function subject to linear constraints. It has applications in business, economics, transportation, and resource allocation.
2. Basic Concepts
Objective Function: The function Z = ax + by to be maximized or minimized. Constraints: Linear inequalities that restrict the variables. Non-negativity Restrictions: x ≥ 0, y ≥ 0. Feasible Region: The set of all points satisfying all constraints. Feasible Solution: A point in the feasible region. Optimal Solution: A feasible solution that optimizes Z. Corner Point: A vertex of the feasible region.
'In ISC syllabus, only LP problems with two variables solved by the graphical method are covered.'
3. Formulation of LP Problems
Steps: (1) Identify decision variables. (2) Write the objective function. (3) Express all constraints as linear inequalities. (4) Add non-negativity restrictions.
4. Graphical Method
4.1 Steps
- Graph all constraints as lines, then shade the feasible region.
- Find all corner points of the feasible region.
- Evaluate Z at each corner point.
- Select the corner point that gives the optimal (max or min) value.
4.2 Theorem
If the feasible region is bounded, the optimal solution exists at a corner point. If the region is unbounded, check whether Z has a maximum/minimum.
4.3 Types of Solutions
Unique Solution: Exactly one corner point gives the optimum. Multiple Optimal Solutions: Two or more corner points give the same optimum value (occurs when Z line is parallel to a constraint boundary). No Solution: The feasible region is empty. Unbounded Solution: Z can increase/decrease indefinitely.
5. Important Cases
- If the feasible region is empty, no solution exists.
- In a minimization problem with an unbounded feasible region, a minimum may still exist.
- For a maximization problem with an unbounded feasible region, check if any constraint prevents indefinite increase.
5. Duality in Linear Programming
Every LP problem (primal) has an associated dual problem. If the primal is a maximization, the dual is a minimization and vice versa.
Primal: Maximize Z = c₁x₁ + c₂x₂ subject to constraints Ax ≤ b, x ≥ 0. Dual: Minimize W = b₁y₁ + b₂y₂ subject to Aᵀy ≥ c, y ≥ 0.
The optimal values of Z and W are equal (strong duality theorem). This relationship helps in solving complex LP problems through their simpler duals.
6. Special Cases in Graphical Method
6.1 Infeasible Solution
When constraints contradict each other, the feasible region is empty. No solution exists.
Example: Maximize Z = x + y subject to x + y ≤ 2, x + y ≥ 5, x, y ≥ 0. No point satisfies both constraints simultaneously.
6.2 Unbounded Solution
When the feasible region extends indefinitely and Z can increase without bound.
Example: Maximize Z = 3x + 2y subject to x + y ≥ 4, x, y ≥ 0. The region is unbounded in the positive direction.
6.3 Multiple Optimal Solutions
When the objective function is parallel to a constraint boundary at the optimum. Every point on that boundary segment is optimal.
Example: Maximize Z = 4x + 4y subject to x + y ≤ 5, x ≥ 0, y ≥ 0. The line Z = 20 is parallel to x + y = 5.
7. Worked Problems
Problem 1: Maximize Z = 3x + 4y subject to x + y ≤ 4, x ≥ 0, y ≥ 0. Solution: Feasible region is a triangle with corners (0, 0), (4, 0), (0, 4). Z(0, 0) = 0, Z(4, 0) = 12, Z(0, 4) = 16. Maximum Z = 16 at (0, 4).
Problem 2: Minimize Z = 20x + 10y subject to x + 2y ≤ 40, 3x + y ≥ 30, 4x + 3y ≥ 60, x, y ≥ 0. Solution: Plot constraints. The corner points are (10, 0), (2, 19), (6, 12), (15, 0). Z(10,0)=200, Z(2,19)=40+190=230, Z(6,12)=120+120=240, Z(15,0)=300. Minimum Z = 200 at (10, 0).
Problem 3: A dealer sells two types of chairs. Type A costs ₹500 with profit ₹50. Type B costs ₹600 with profit ₹60. He has space for 50 chairs and capital ₹30,000. Maximize profit. Solution: Let x chairs of type A, y of type B. Maximize P = 50x + 60y subject to x + y ≤ 50, 500x + 600y ≤ 30000, x, y ≥ 0. Solve graphically.
7. Common Mistakes
'Students often incorrectly shade the feasible region. Test a point (like the origin) to check which side of a line satisfies the inequality.'
'For ≥ constraints, the region is away from the origin. For ≤ constraints, it includes the origin (unless the origin violates another constraint).'
8. ISC Exam Focus
| Topic | Theory Marks | Practical Marks |
|---|---|---|
| Formulation | 3 | 2 |
| Graphical method | 4 | 4 |
| Corner point evaluation | 2 | 2 |
| Special cases | 2 | 1 |
9. Self-Test Questions
- Maximize Z = x + 2y subject to x + y ≥ 4, x - y ≤ 2, x, y ≥ 0.
- Minimize Z = 3x + 2y subject to x + y ≥ 8, 3x + 2y ≥ 18, x, y ≥ 0.
- A factory makes two products P and Q requiring 2 hours and 3 hours on machine M, and 3 hours and 2 hours on machine N. M runs 10 hours/day, N runs 12 hours/day. Profit on P is ₹40, Q is ₹30. Find max profit.
- Maximize Z = 2x + 4y subject to x + 2y ≤ 10, x + y ≤ 6, x, y ≥ 0. Are there multiple optimal solutions?
- Solve graphically: Minimize Z = 10x + 15y subject to 2x + y ≥ 20, x + 3y ≥ 30, x, y ≥ 0.
