Linear Programming (LP) is a method to find the optimal value (maximum or minimum) of a linear objective function, subject to a set of linear constraints. LP is widely used in industry, economics, and operations research for decision-making.
---
Key Terminology
- Decision variables: The unknowns to be determined (e.g., x and y).
- Objective function: The linear function to be optimized (e.g., Z = 3x + 5y).
- Constraints: Linear inequalities or equations that the variables must satisfy.
- Non-negativity constraints: x ≥ 0, y ≥ 0 (variables represent quantities that cannot be negative).
- Feasible region: The set of all points (x, y) that satisfy all constraints simultaneously. It is always a convex polygon (or convex set).
- Feasible solution: Any point in the feasible region.
- Optimal solution: The feasible solution that maximizes or minimizes the objective function.
- Corner point (vertex): A vertex of the feasible region polygon.
---
Fundamental Theorem of LP
Corner Point Theorem: If a linear objective function Z = ax + by has an optimal value (maximum or minimum) in the feasible region, it occurs at one of the corner points (vertices) of the feasible region.
If the feasible region is unbounded, the maximum may not exist, but a minimum might. Always verify using the open half-plane test.
---
Steps to Solve an LP Problem
- 1.Identify decision variables x and y.
- 2.Write the objective function Z = ax + by.
- 3.Write all constraints as linear inequalities.
- 4.Graph the constraints to find the feasible region.
- 5.Find all corner points of the feasible region.
- 6.Evaluate Z at each corner point.
- 7.The point giving the maximum/minimum Z is the optimal solution.
---
Worked Examples
Maximise Z = 5x + 3y subject to: 3x + 5y ≤ 15, 5x + 2y ≤ 10, x ≥ 0, y ≥ 0.
Corner points: O(0,0), A(2,0), B(20/19, 45/19), C(0,3).
Z at O = 0, Z at A = 10, Z at B = 100/19 + 135/19 = 235/19 ≈ 12.4, Z at C = 9.
Maximum Z = 235/19 at (20/19, 45/19).
Minimise Z = x + 2y subject to x + y ≥ 3, x ≥ 0, y ≥ 0.
Feasible region is unbounded (above the line x + y = 3).
Corner points: (3, 0) and (0, 3).
Z at (3,0) = 3; Z at (0,3) = 6.
Since the region is unbounded, check if Z < 3 is possible: x + 2y < 3 with x + y ≥ 3 has no common point.
Minimum Z = 3 at (3, 0).
A manufacturer makes two types of toys A and B. Type A requires 2 hours of machine time and 1 hour of labour; type B requires 1 hour of machine time and 3 hours of labour. Machine time available: 80 hours; labour: 90 hours. Profit on A = Rs 20, on B = Rs 30. How many of each to maximise profit?
Let x = toys A, y = toys B. Objective: Maximise Z = 20x + 30y.
Constraints: 2x + y ≤ 80, x + 3y ≤ 90, x, y ≥ 0.
Corners: O(0,0), A(40,0), B(30,20), C(0,30).
Z: O=0, A=800, B=1200, C=900. Maximum profit = Rs 1200 by making 30 type A and 20 type B.
Identify the type of feasible region for: x + y ≤ 4, x ≥ 1, y ≥ 1.
The constraints form a bounded triangular region with vertices (1,1), (3,1), (1,3).
What is the maximum value of Z = 3x + 5y at the corner point (4, 3)?
Z = 3(4) + 5(3) = 12 + 15 = 27
For Z = -x + 2y, find the minimum over the region with corners (0,0), (4,0), (2,4), (0,5).
Z: (0,0)=0, (4,0)=-4, (2,4)=6, (0,5)=10.
Minimum Z = -4 at (4, 0).
What does an infeasible LP problem mean?
If there are no points satisfying all constraints simultaneously, the feasible region is empty — the problem has no solution. This is called an infeasible LP problem.
---
Common mistakes
- Not checking all corner points: Students often skip finding intersection points of constraint lines, missing the true optimal corner.
- Unbounded region: For an unbounded feasible region, always use the open half-plane test to confirm a minimum (or maximum) exists.
- Wrong direction of inequalities: When graphing, shade the correct side of each constraint line. Always verify by testing a point (like the origin).
---
Summary
Linear programming solves optimization problems with a linear objective function and linear constraints. The optimal solution always lies at a corner (vertex) of the feasible region. Graph the constraints, find all corner points, evaluate the objective function there, and pick the best value.