Linear Programming
Linear Programming (LP) is a mathematical technique used to determine the best possible outcome in situations where resources are limited and multiple constraints exist.
It helps organizations decide how to allocate resources efficiently to achieve objectives such as maximum profit or minimum cost.
Linear programming is one of the most tested topics in business mathematics, operations research, and competitive examinations.
Why Linear Programming Is Important
In real life, resources are always limited.
Examples:
- Limited money
- Limited time
- Limited labor
- Limited raw materials
Linear programming helps use these limited resources in the most efficient way.
What Problems Can Linear Programming Solve?
Linear programming is used when:
- The objective is clear (maximize or minimize)
- Relationships are linear
- Constraints can be written as equations or inequalities
LP converts business problems into solvable math models.
Key Assumptions of Linear Programming
Linear programming is based on four important assumptions:
- Linearity – relationships are linear
- Additivity – total effect is the sum of individual effects
- Divisibility – variables can take fractional values
- Certainty – coefficients are known and fixed
Understanding assumptions is critical for exams.
Components of a Linear Programming Problem
Every linear programming problem has:
- Decision variables
- Objective function
- Constraints
- Non-negativity conditions
These components form the LP model.
Decision Variables
Decision variables represent the quantities we want to determine.
Examples:
- Number of units to produce
- Amount of resources to allocate
They are usually denoted by x, y, etc.
Objective Function
The objective function represents what we want to optimize.
It is written as a linear equation.
Examples:
- Maximize profit
- Minimize cost
The objective function guides the solution.
Constraints
Constraints represent real-world limitations.
They are written as linear inequalities or equations.
Examples:
- Limited labor hours
- Limited raw materials
- Budget restrictions
Constraints restrict the feasible solutions.
Non-Negativity Condition
Decision variables cannot be negative because negative production or allocation has no real-world meaning.
x ≥ 0, y ≥ 0
This condition is always included in LP problems.
Formulating a Linear Programming Problem
Formulation means converting a word problem into a mathematical model.
Steps:
- Identify decision variables
- Write the objective function
- Write constraints
- Add non-negativity conditions
Correct formulation is the most important step.
Example: Simple LP Formulation
A company produces two products A and B.
- Profit per unit of A = ₹40
- Profit per unit of B = ₹30
Objective:
Maximize Z = 40x + 30y
Subject to resource constraints.
Feasible Region
The feasible region is the set of all solutions that satisfy all constraints.
Only points inside this region are valid solutions.
This concept is crucial for graphical solutions.
Graphical Method of Solving LP Problems
The graphical method is used when there are only two decision variables.
Steps:
- Plot constraint lines on a graph
- Identify the feasible region
- Find corner (vertex) points
- Evaluate objective function at each corner
The best value occurs at a corner point.
Corner Point Theorem
The corner point theorem states:
The optimal solution of a linear programming problem lies at one of the corner points of the feasible region.
This theorem makes graphical solutions possible.
Types of Solutions in Linear Programming
LP problems can have:
- Unique optimal solution
- Multiple optimal solutions
- Unbounded solution
- No feasible solution
Each case has different implications.
Multiple Optimal Solutions
Occurs when the objective function is parallel to a constraint line along the feasible region.
In such cases, more than one solution gives the same optimal value.
Unbounded Solution
Occurs when the objective function can increase indefinitely without violating constraints.
This indicates a modeling issue.
No Feasible Solution
Occurs when constraints are contradictory.
No point satisfies all constraints simultaneously.
This means the problem has no practical solution.
Linear Programming in Business
Businesses use LP for:
- Production planning
- Product mix decisions
- Cost minimization
- Profit maximization
LP improves efficiency and profitability.
Linear Programming in Analytics
Analytics teams use LP to:
- Optimize marketing budgets
- Allocate resources optimally
- Improve operational KPIs
LP turns data insights into actions.
Linear Programming in Data Science
In data science:
- LP supports optimization problems
- Used in scheduling and resource allocation
- Complements machine learning predictions
Optimization completes the analytics pipeline.
Linear Programming in Competitive Exams
Exams frequently test:
- LP formulation
- Graphical method
- Corner point evaluation
Clear structure saves time and avoids mistakes.
Common Mistakes to Avoid
- Incorrect objective function
- Missing constraints
- Ignoring non-negativity conditions
Always check the model carefully.
Practice Questions
Q1. What is linear programming?
Q2. Where does the optimal solution occur in graphical method?
Q3. Can LP problems have multiple optimal solutions?
Quick Quiz
Q1. Is linear programming used only in manufacturing?
Q2. Are all LP relationships linear?
Quick Recap
- Linear programming optimizes under constraints
- Objective function defines the goal
- Feasible region contains valid solutions
- Optimal solution lies at corner points
With linear programming mastered, you are now ready to study Queuing Theory, which analyzes waiting lines and service systems.