Linear Programming Problem Meaning (LPP meaning)
In mathematics, we deal with both, linear equations and linear inequality. Linear equations with two variables such as Y = 2x + 1, 5x = 3+6y, etc. confirm that the right side of the sign ‘=’ is equal to its left side. Linear inequalities are not equations where both sides are equal. Here, the concept of greater than and lesser than comes into play. For example, 5x + y <100, in this equation, we can say that 5x+y is less than 100 which means the value of x and y can fluctuate only up to a certain extent to keep the entire term (5x+y) less than 100.
Problems that seek to maximize or minimize the profits (or cost) and form a general class of problems are called optimization problems. Thus, an optimization problem may involve finding maximum profit, minimum cost or minimum use of resources, etc.
A special yet very important class of problems is called linear programming problems. (Example: a furniture dealer deals in only two items- tables and chairs. He has Rs 50,000 to invest and has a storage space of 60 items. A table costs Rs 2500 and a chair costs Rs 500. He estimates that from the sale of one table, he can make a profit of Rs 250 and that from the sale of one table a profit of Rs 75. He can use the method of linear programming to find out how many tables and chairs he should buy from the available money so as to maximize his total profit, assuming that he can sell all the items which he buys.
Mathematical Formulations of Linear Programming Problems
In the example given above, the furniture dealer can formulate his problems mathematically in two variables. He can invest his money in buying tables or chairs or both depending on the profit he would earn in each case. There are few constraints also like
(i) His investment is limited to a maximum of Rs 50,000.
(ii) His storage space can take a maximum of 60 items.
Case 1 - He Decides to Buy Only Tables:
If each table costs Rs 2,500 and he has a budget of Rs 50,000 then,
No of chairs he can buy = Rs 50000 / Rs 2500 = 20 tables.
If the profit from each table is 250 then,
Profit from 20 tables = Rs 250 x 20 = Rs 5000.
Case 2 - He Decides to Buy Only Chairs:
If each chair costs Rs 500 and he has a budget of Rs 50,000 then,
No of chairs he can buy = Rs 50000 / Rs 500 = 100 chairs.
But, he can store only 60 pieces of furniture so if he buys 60 chairs then,
Profit from each chair = Rs 75.
Profit from 60 chairs = Rs 75 x 60 = Rs 4,500.
Case 3 - He Decides to Buy Both Tables and Chairs:
Often, there are many other possibilities, like for instance, he might choose to buy 10 tables and 50 chairs, as he can store only 60 pieces. In this case, the total profit would be Rs (10 × 250 + 50 × 75), i.e., Rs 6250 and so on. Thus, we can see that the dealer can invest his money in different ways by which he would earn different profits by following different investment strategies.
Now the problem is: How should he invest his money in order to get the maximum profit? To answer this question, let us try to formulate the problem mathematically.
Mathematical Formulation of the Problem:
Let the number of tables is x and the number of chairs is y that the dealer buys. Obviously, x and y must be non-negative, i.e.,
X 0……….(1) (Non-negative constraints)
Y 0……….(2)
The dealer is constrained with the maximum amount he can invest (Here it is Rs 50,000) and by the maximum number of items he can store (Here it is 60).
Stated mathematically,
2500x + 500y ≤ 50000 (investment constraint)
or 5x + y ≤ 100….... (3)
Thereby, x + y ≤ 60 (storage constraint)....... (4)
The dealer would want to invest in such a way as to maximise his profit. So as to say, Z which stated as a function of x and y is given by
Z = 250x + 75y (can be called as objective function) ... (5)
Mathematically, the given problems now reduces to:
Maximise Z = 250x + 75y
The Subject to constraints: 5x + y ≤ 100
x + y ≤ 60
x ≥ 0, y ≥ 0
So, it is important to maximize the linear function Z subject to certain conditions determined by a set of linear inequalities with variables as non-negative. There are also few other problems where we need to minimize a linear function subject so that certain conditions that are determined by a set of linear inequalities with variables are non-negative. Such problems are called Linear Programming Problems.
FAQs on Linear Programming Problem (LPP)
1. What is a Linear Programming Problem (LPP) in Maths?
A Linear Programming Problem (LPP) is a mathematical technique used to find the best possible outcome or solution from a given set of parameters or requirements, which are represented as linear relationships. It involves optimising (maximising or minimising) a linear objective function, subject to a set of linear constraints and non-negativity restrictions.
2. What are the key components of a Linear Programming Problem?
Every LPP consists of three fundamental components:
- Objective Function: A linear function, typically denoted as Z = ax + by, that we aim to maximise (e.g., profit) or minimise (e.g., cost).
- Constraints: A set of linear inequalities or equations (e.g., x + 2y ≤ 10) that represent limitations or restrictions on resources like time, money, or materials.
- Non-Negativity Restrictions: The assumption that the decision variables (e.g., x and y) must be non-negative (x ≥ 0, y ≥ 0), as they usually represent real-world quantities.
3. How is the graphical method used to solve a Linear Programming Problem?
The graphical method is used for LPPs with two variables and involves the following steps:
- First, formulate the LPP by defining the objective function and constraints.
- Plot each constraint as a straight line on a graph and shade the region that satisfies the inequality.
- Identify the common shaded area, known as the feasible region. This region represents all valid solutions to the problem.
- Determine the coordinates of the vertices (or corner points) of this feasible region.
- Substitute the coordinates of each corner point into the objective function. The point that yields the highest value is the maximum solution, and the one that yields the lowest is the minimum solution.
4. What is the difference between a feasible region and an infeasible region in an LPP?
A feasible region is the common area on a graph determined by all the given constraints of an LPP. Every point within this region is a potential solution to the problem. Conversely, an infeasible region is the area where the constraints are not simultaneously satisfied. If there is no common area shared by all constraints, the LPP is said to have no feasible solution.
5. What is the significance of the corner points of a feasible region?
The corner points (or vertices) of a feasible region are crucial because of the Corner Point Theorem. This fundamental theorem of linear programming states that if an optimal solution (maximum or minimum) for an LPP exists, it will always occur at one of these corner points. This simplifies the problem significantly, as we only need to test the finite number of vertices rather than the infinite points within the region to find the best solution.
6. What are some real-world applications of Linear Programming?
Linear Programming is widely used to solve optimisation problems across various fields. Some common applications include:
- Manufacturing and Production: To maximise profits by determining the optimal number of units to produce with limited resources.
- Diet Planning: To create a balanced diet at a minimum cost while meeting specific nutritional requirements.
- Transportation and Logistics: To minimise shipping costs and time by optimising routes and delivery schedules.
- Financial Portfolio Management: To maximise returns by allocating funds to different investment options under certain risk constraints.
7. How do you handle an unbounded feasible region in an LPP?
An unbounded feasible region is one that extends indefinitely in at least one direction. In such cases:
- If the goal is to minimise the objective function, an optimal solution usually exists at one of the corner points.
- If the goal is to maximise the objective function, an optimal solution may or may not exist. We still evaluate the objective function at the corner points. However, if the function value can increase indefinitely along an edge of the unbounded region, then no maximum solution exists. As per the CBSE 2025-26 syllabus, this check is a key step for unbounded problems.
8. Why is it called 'Linear' Programming?
The method is called 'Linear' Programming because all the mathematical relationships involved are linear. This means the objective function is a linear expression, and all the constraints are represented by linear equations or inequalities. Graphically, this results in straight lines and flat planes, ensuring that the relationships between variables are directly proportional and do not involve any exponents or curves.
