Linear Programming Problems (LLP): Preface
In this article, we will learn about the different types of linear programming problems such as manufacturing problems, diet problems, optimal assignment problems, and transportation problems. Finding the most efficient resource allocation is often done using linear programming.
A one-dimensional relationship between numerous variables is referred to as "linear" in this context. Programming is selecting the best option from a list of options. When a set of linear inequalities, known as linear constraints, are satisfied and all of the variables are non-negative, linear programming seeks to determine the optimal value of a linear function of many variables.
Diet Problems
Diet problems, as the name suggests, involves maximising the consumption of particular foods high in particular nutrients that can help with the application of a particular diet plan. Finding a collection of meals that will satisfy a set of daily nutritional needs while costing the least is the goal of a diet problem.
Limitation – Dietary requirements must be fulfilled, such as a specific calorie intake or a required amount of sugar or cholesterol.
The objective function is the price of food consumption.
Manufacturing Problems
The goal of manufacturing is to increase production rates or net profits, which may depend on a variety of factors, including the amount of space available, the number of workers, the number of machine hours used, the type of packaging used, the amount of raw materials needed, the market value of the product, and others. These are employed in the industrial sector and can be utilised to predict a company's potential future capital growth.
Limitations – Factors like labour hours, the price of packaging supplies, and so forth.
The objective function is the production rate.
Optimal Assignment Problems
The optimal assignment problems deal with a corporation finishing a particular task or assignment by choosing a particular number of employees to complete the assignment within the given deadline, provided that each person works on just one task inside the assignment. These problems can be found, among other places, in huge organisations’ event management and planning.
Limitations – The size of the workforce, the hours each person works, etc.
The objective function is represented by the total number of jobs finished.
Transportation Problems
The study of efficient transportation routes, or how effectively goods from diverse sources of production are transported to various markets in such a way that the overall transportation cost is minimised, is related to the study of transportation problems. Analysing such problems is crucial for large firms with numerous production units and a sizable client base.
Limitations – Specific supply and demand trends.
The objective function is the cost of transportation.
Applications of Linear Programming
Numerous sectors, including delivery services, the transportation sector, manufacturing firms, and financial institutions, mainly depend on linear programming. Let’s discuss some applications of Linear Programming problems in this section.
Production management can use linear programming to decide on the right product mix, smooth out products, and balance assembly times.
The people manager can analyse personnel policies using linear programming.
Based on the available advertising medium, linear programming aids in measuring the success of marketing campaigns and timing.
For physical distribution, the best place to site warehouses, manufacturing facilities, and distribution hubs are determined using the linear programming method.
Linear Programming Problems
1. Purchase some filing cabinets. You are aware that Cabinet X costs $10$ per unit, takes up six square feet of floor space, and has a file capacity of eight cubic feet. Cabinet Y costs $20$ each, takes up eight square feet of floor area, and has a file capacity of twelve cubic feet. Although you don't have to spend that much money, you have been granted $140$ to use toward this purchase. There is only enough room in the office for $72$ square feet of cupboards. Which model should you purchase the most in order to maximise the storage capacity? Put your maximum storage capacity in the box provided.
Ans:
Let the number of Y models be y and the number of X models be x, them
For floor 6x + 8y = 72 or 3x + 4y = 36
10x +20y ≤ 140
Volume is 8x + 12y
Now x + 2y ≤ 14
Therefore, 2x + 4y ≤ 14
Volume = 8x + 12y
= 8x +108 – 9x
= 108 – x
Now, 2x + 4y ≤ 28
2x + 36 – 3x ≤ 28
x ≥ 8
So, when x is minimum x = 8, the volume is maximum.
Therefore, maximum volume = 108 – 8 = 100.
2. Use the graphical approach to solve the linear programming problem below:
Maximise Z = 2x + 3y
x + y ≤ 30,
x ≤ 20, y ≤ 12
x, y ≥ 0
Ans. Equations resulting from the inequalities are as follows: x + y = 30 passing through (0, 30) and (30, 0). Points on or under this line will satisfy x + y ≤ 30
The y-axis and the line at x = 20 are parallel. Any point along this line or to its left will satisfy the condition x ≤ 20.
Line y = 12 is parallel to the x-axis. Any point above or below this line will meet the condition y ≤ 12. According to the graph,
Hence, Z has a maximum value of 72 and occurs at C. (18, 12)
Practice Questions
1. In a linear programming problem involving the variables x and y, what constraints are placed on the variables?
x, y ≥ 0
x, y ≤ 0
x, y = 0
x, y ≤ 0
Ans: Option (a)
2. Find the optimal(best) solution using linear programming.
Maximise Z = 50x + 120y
x + 2y ≤ 100
x + 3y ≤ 120
x + y ≤ 110
x, y ≥ 0
(60, 20)
(20, 10)
(5, 7)
(-12, -8)
Ans: Option (a)
Conclusion
Linear programming, commonly known as LP, is a straightforward technique for representing complex real-world interactions by means of a linear function. The components of the resulting mathematical model are linearly related to one another. In order to reach the optimal result, linear optimisation is carried out using linear programming. Example problems have also been solved in this article to boost your concept and clear your doubt about the topic.
FAQs on Types of Linear Programming Problems
1. What is a Linear Programming Problem (LPP) in Class 12 Maths?
A Linear Programming Problem (LPP) is a mathematical method used to find the best possible outcome or solution from a given set of parameters or requirements, which are represented in the form of linear relationships. In Class 12 Maths, it involves optimising (maximising or minimising) a linear objective function, subject to a set of linear constraints (inequalities or equations) on the decision variables.
2. What are the main types of linear programming problems found in real-world applications?
The main types of LPPs are designed to solve specific optimisation challenges across various industries. As per the CBSE 2025-26 syllabus, key examples include:
- Diet Problems: These aim to find the most cost-effective combination of foods that satisfies specific daily nutritional requirements.
- Manufacturing Problems: These focus on determining the production levels for various products to maximise profit, given constraints like labour hours, raw materials, and machine capacity.
- Transportation Problems: These deal with finding the cheapest way to transport goods from multiple sources (factories) to various destinations (markets) while meeting supply and demand needs.
- Optimal Assignment Problems: These are used to assign a specific number of tasks to an equal number of workers or machines to minimise total cost or time.
3. What are the three essential components of any linear programming problem?
Every linear programming problem is composed of three essential components:
- Decision Variables: These are the unknown quantities (e.g., x and y) that you need to determine. They represent the levels of activities, like the number of units of a product to manufacture.
- Objective Function: This is a linear mathematical expression (e.g., Z = ax + by) that defines the quantity to be maximised (like profit) or minimised (like cost).
- Constraints: These are the set of linear inequalities or equations (e.g., x + 2y ≤ 100) that represent the limitations or restrictions on the decision variables, such as resource availability or production capacity.
4. How do you distinguish 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 a linear programming problem. Any point within or on the boundary of this region represents a valid solution that satisfies all conditions. In contrast, an infeasible region means there is no common area where all constraints are satisfied simultaneously, indicating that the problem has no solution.
5. Why is linear programming considered such an important tool for businesses?
Linear programming is crucial for businesses because it provides a scientific and data-driven approach to decision-making. Instead of relying on intuition, managers can use LPP to optimally allocate scarce resources like money, materials, and manpower. This helps in maximising profits, minimising costs, improving operational efficiency, and making strategic choices in production planning, logistics, and financial portfolio management.
6. What are the common limitations when applying linear programming to real-world scenarios?
While powerful, linear programming has some key limitations. The most significant is the assumption of linearity; it assumes that the objective function and constraints are perfectly linear, which is not always true in the real world. Secondly, it assumes certainty, meaning all coefficients and values are known and constant, whereas in reality, they can be uncertain or variable. Lastly, it can be difficult to quantify all factors, such as worker morale or market dynamics, into a mathematical model.
7. What happens if a linear programming problem has no single optimal solution?
A linear programming problem might not have a single optimal solution due to certain special conditions. Two common cases are:
- Infeasibility: This occurs when the constraints are contradictory, and there is no point (x,y) that can satisfy all of them. Graphically, this means there is no feasible region.
- Unboundedness: This happens when the feasible region is not enclosed, allowing the objective function to be increased or decreased indefinitely without a limit. In this case, there is no finite maximum or minimum value.
8. How does an 'optimal assignment problem' differ from a 'transportation problem' in LPP?
Although both are types of LPPs, they solve different logistical puzzles. A transportation problem focuses on moving quantities of a product from multiple sources to multiple destinations at the minimum cost. In contrast, an optimal assignment problem is a special case where the goal is to assign tasks to agents on a one-to-one basis. Here, the supply from each source and the demand at each destination are exactly one unit.
