In the world of business, manufacturing, logistics, and even everyday decision-making, resources like time, money, and materials are often limited. The challenge lies in how to use these resources most efficiently to achieve the best possible outcome—whether that’s maximizing profits, minimizing costs, or improving productivity.
Linear Programming (LP) is a powerful mathematical method that helps in solving such optimization problems. By formulating problems into equations and inequalities, LP allows decision-makers to identify the most efficient way to allocate limited resources.
Download UNIT 5 – Linear Programming and Optimization Techniques Notes
Get simplified revision notes for this unit:
Download Unit 5 Notes PDF
What is Linear Programming?
Linear Programming is a quantitative technique used to determine the best possible outcome for a problem, given a set of constraints. These constraints could be limitations in raw materials, labor, budget, storage, or even production capacity.
In simple terms:
We maximize something (e.g., profit, sales, efficiency) or minimize something (e.g., cost, time, wastage).
We do this while respecting constraints (rules or limits).
Example: A factory making chairs and tables might want to maximize profit. The constraints could be limited labor hours and available wood. LP will help determine exactly how many chairs and tables they should produce to get the highest profit without exceeding available resources.
Assumptions of Linear Programming
Before applying LP, it’s important to understand the assumptions behind it:
Linearity – The relationship between variables is linear. This means doubling inputs will double the output.
Additivity – The total effect is the sum of the individual effects of each variable.
Divisibility – Variables can take fractional values (you can produce half a unit).
Certainty – All coefficients (profits, costs, resource limits) are known and fixed.
Non-negativity – Variables cannot be negative (you can’t produce -5 products).
These assumptions make LP suitable for many business scenarios, though not all real-life problems will perfectly fit these conditions.
Graphical Method for Solving LPP
For problems with two decision variables, the graphical method is the simplest way to find a solution.
Steps in the Graphical Method:
Plot each constraint on a graph.
Identify the feasible region – the area that satisfies all constraints.
Plot the objective function and move it in the direction of maximization or minimization.
The optimal solution will be at a corner point (vertex) of the feasible region.
Example:
If a company wants to maximize profit Z=40x+30y with given constraints on resources, we plot the constraints, shade the feasible area, and check the profit at each corner point to find the maximum.
Introduction to the Simplex Method
While the graphical method works well for two variables, real-world problems often have many variables and constraints. That’s where the Simplex Method comes in.
Developed by George Dantzig, the simplex method is an iterative algorithm that starts with an initial feasible solution and moves step by step toward the optimal solution.
Key advantages:
Works for problems with more than two variables.
Efficient for large-scale business applications.
Even though the simplex method can be complex to solve manually, software like Excel Solver, LINGO, or MATLAB can compute results quickly.
Real-World Applications of Linear Programming
Linear Programming is used in a wide range of industries, such as:
Manufacturing: Deciding the best product mix to maximize profits given limited machine time and raw materials.
Transportation: Minimizing shipping costs by finding optimal routes and loads.
Finance: Allocating investments in a way that maximizes returns while minimizing risks.
Workforce Scheduling: Assigning employees to shifts while meeting staffing requirements.
Diet Planning: Finding the cheapest combination of foods that meet all nutritional requirements.
Maximization vs. Minimization Problems
Maximization: Goal is to get the highest possible value for the objective function (e.g., maximize revenue).
Minimization: Goal is to reduce the value of the objective function as much as possible (e.g., minimize fuel costs).
While the process for solving both is similar, the interpretation of results differs.
Limitations of Linear Programming
Despite its usefulness, LP has limitations:
Linearity Assumption – Many real-life relationships are non-linear.
Certainty Requirement – Coefficients and constraints are assumed to be constant, which may not be realistic.
Divisibility – LP assumes fractional solutions are possible, but in some cases (like manufacturing cars), only whole units are feasible.
Single Objective – LP focuses on one objective, but real problems may require balancing multiple goals.