Linear Programming (LPP) is a mathematical method used to optimize a given objective function under a set of constraints.
It plays a crucial role in solving real-world problems related to business, economics, and operations research.
This guide covers the key concepts of LPP, including graphical solutions, inequalities, feasible regions, and the corner point method, to help you understand the topic efficiently.
I hope, you found my previous articles and the handwritten downloadable notes helpful. I would love to hear from you and here also, you can download a handwritten PDF summarizing the concepts for quick revision.
1. Basics of Linear Programming
At the core of Linear Programming, we deal with:
Objective Function: A function that needs to be maximized or minimized (e.g., profit or cost) is known as the objective function,
Decision Variables: The variables whose values we determine to optimize the objective function are called the decision variables.
Constraints: These are given in the form of linear inequalities or equations that restrict the values of decision variables e.g. x and y.
I suggest you downloading the handwritten PDF at the end for the quick notes before the exam.
2. Linear Inequations & Equations
Strict Inequalities (e.g., x + y < 5): These represent open half-planes, which do not include the points lying on the corresponding line itself.
Slack Inequalities (e.g., x + y ≤ 5): These represent closed half-planes, along with the points lying on the corresponding line.
Equations (e.g., x + y = 5): Represent the boundary lines.
Graphical Representation: It is the shaded region based on the inequality signs.
Checking Feasibility: The origin (0,0) is often used to determine the feasible side.
3. Graphical Method for Bounded Region
Feasible Region: It is the common region that satisfies all the given constraints in an LPP.
Optimal Solution: Lies within this region, usually at a corner point.
Fundamental Theorem of LPP. For a bounded region, both the maximum as well as minimum values exist and they will be at the corner points.
As you can see in the image below and moreover you can download the handwritten PDF.
4. Graphical Method for Unbounded Region
Unbounded Feasible Region: If it extends infinitely in any direction.
Fundamental Theorem of LPP: In case of any unbounded regions, the optimal solution may not exist. But, if it exists, it is at a corner point.
5. Corner Point Method: Finding Maximum/Minimum Value of a Linear Programming Problem
The graphical method involves:
- Identifying the feasible region.
- Finding the corner points.
- Evaluating the objective function at each corner.
- Selecting the optimal value.
Checkout the step-by-step method in the attached file at the end.
6. Corner Point Method: Multiple Solutions
If two corner points give the same value of the objective function, say Z, then the entire line segment joining the two points gives the same optimal value for the objective function. In such a case, multiple (infinite) solutions exist, as all the points lying on that line segment will give the same optimum value.
This is very well explained with an example in the image below:
7. Corner Point Method: Unbounded Region
If the optimal solution lies on a boundary and the objective function line (Z-line) does not extend infinitely within the feasible region, then optimization is possible.
Understand the concept clearly by downloading the handwritten PDF.
8. Corner Point Method: Unbounded Region with No Solution
If the Z-line intersects the feasible region at infinite points, the solution may not be optimizable.
9. No Feasible Region
If the given constraints in a Linear Programming Problem do not overlap to form a common feasible region, then no solution exists.
10. Miscellaneous Concepts in Linear Programming
Convex Polygon: A feasible region in LPP always forms a convex shape.
Feasibility and Circles: If a feasible region can fit inside a circle, it is bounded.
Infeasible Solution: If constraints contradict each other, LPP has no solution.
Final Thoughts
Linear Programming is an essential tool for optimization in various fields. Understanding the graphical method, corner point method, and feasibility conditions helps solve real-world problems efficiently. Mastering LPP helps solve complex mathematical problems efficiently.
This guide has introduced the fundamental concepts of Linear Programming in a structured way. By practicing different cases of bounded and unbounded regions, corner point methods, and infeasibility, you will develop a strong understanding of LPP for Class 12 Maths. See you in the next topic on Differential Equations. Happy learning!
