Key Types of Linear Programming Problems Every Student Should Know
What is Linear Programming?
Linear programming is defined as the issues of maximizing or minimizing a linear function that is dependent on linear constraints. The constraints may be equalities or inequalities. The optimization problems include the profit and loss calculation. Linear programming problems are a crucial factor of optimization problems, that enable us to find the feasible area and optimize the solution with a view to achieve the highest or lowest value of a function.
Linear programming is the procedure of considering different inequalities relating to a situation and calculating the optimum value that is required to be obtained in those circumstances.
What is a Linear Programming Problem?
Linear programming or linear optimization is a method that considers certain variable relationships to obtain a feasible solution to a mathematical model. It is also represented by Lpp. It deals with various problems such as maximization of profit minimization of cost or minimum usage of resources. These issues can be solved through the simplex method or graphical method. The linear programming applications are present in different fields such as commerce, engineering, manufacturing sector, etc.
Types of Linear Programming problems
Explain the Types of Linear Programming with Examples
The different types of LPP are:
Transportation problem
Diet Problem
Optimal Assignment problem
Manufacturing problem
Transportation Problems
These issues are allied to the study of the efficient transportation routes i.e. how skilfully the product is transferred from distinct source of production to the different markets such that the total transportation cost is minimized. Analysis of such problems is an important factor for big companies with multiple production plants and widespread areas to cater the needs.
Constraints – The patterns of particular supply and demand Objective function- The transportation cost for transferring the product.
Example -
A firm has three different companies A, B and C. There are four different warehouses of the company situated at different locations namely CCD, QTR, SML and NNC. The average daily production of the product at A, B ,and C are 30, 40 ,and 50 units respectively. The average daily requirements of these products at CCD, QTR, SML, and NNC are 35,30,32,and 25 units respectively.
The transportation cost (in Rs.) for transferring product from each factory to each warehouse is represented below in the tabular form.
From the data given in the above table, calculate the total production cost of the product, subject to constraints due to the limited products and requirements. The aim here is to minimize the total transportation cost.
Optimal Assignment problems
These problems are concerned with the completion of a specific task, assignment of a company by selecting a certain number of employees to complete the assignment within the time-frame, considering that a single person works only one job within the given assignment. Such issues find their applications in event planning /management in big companies.
Constraints - The number of employees and the working hour of each employee
Objective function- The total assignment done by the employees within a given period
Example -
The Titan watch company has four men available for work for 4 different jobs. Only one man can work on any one of the given jobs. The cost of assigning each man to each job is represented in the below table:
Finding an optimal way of appointing each man to each job in such a way that the total cost of the project is minimum.
Diet Problems
Most of the time the dietician and nutrition are required to maintain health and diet charts for the patients.The aim of this diet is to include all types of nutrients that are needed by the human body to maintain health. The diet chart should be available at low cost. Thus in the diet chart, the dieticians are required to include all important types of minimum nutrients and accordingly the cost of such a diet should be minimum. Linear programming is widely applied in this sector.
Example -
A kitchen manager at Max hospital has to decide the food mix of the patient. Dietician instruction is that each patient should get:
One gram of nuts
3 grams of carbohydrates
One gram of fat
Additional guidelines mentioned by the dietician is that the carbohydrate content of each patient should not exceed six grams. The availability of protein, fat and carbohydrate in gms of per kg of chicken, rice and bread along with the market cost of each of these products is mentioned below.
Design a suitable diet mix by minimising the cost subject to give constraint, estimating 100 patients on that day.
Manufacturing Problems
These problems include optimizing the speed of the production or the net profit of the manufactured products which could be a task of availability of workspace, the number of laborers, packaging material used, raw material required, etc. These factors find application in the industry sector and hence the estimation of company possible capital increase in recent years.
Constraints - variables such as work hours,cost of packaging material used.
Objective function - The production capacity of the company.
Linear programming Problem and Solution Example
Here is an example of a linear programming problem and solution
A chocolate manufacturing company produces only two types of products Urban Coca and Cadbury pista. Both the chocolates only need choco and milk to produce chocolate. To manufacture each unit of Urban Coca and Cadbury pista the below-mentioned quantities are required.
Each unit of Urban Coca needs one unit of milk and 3 units of choco
Each unit of Cadbury pista needs one unit of milk and 2 units of choco.
The company kitchen has a total of five units of milk and 12 units of choco.The company makes a below-given profit on its every sale:
Rs.6 per unit Urban Coca sold
Rs. 5 per unit Cadbury pista sold.
Now, the company wants to maximise profit. How many units of Urban Coca and Cadbury pista should the company produce respectively?
Solution: The first step is to represent the problem in a tabulated form for better understanding:
Let the total number of unit Urban Coca produced in the factory is =X
Let the total number of unit Cadbury pista produced in the factory is = Y
Now, the total profit is represented by Z.
The total profit of the company is derived by the total number of units produced by Urban Coca and Cadbury pista multiplied by its per-unit profit of Rs 6 and Rs.5 respectively.
Profit: Max Z= 6x +5y
The company will produce as many units of Urban Coca and Cadbury pista to maximize profit. But resources such as milk and choco are available in limited amounts.
According to the above table, each unit of Urban Coca and Cadbury pista needs 1 unit of milk. The total quantity of milk available is 5 units. Representing this mathematically,
X + Y ≤ 5
Also, each unit of Urban Coca and Cadbury pista needs 3 units and 2 units of choco respectively. The total quantity of choco available is 12 units. Representing this mathematically,
3X + 2Y ≤ 12
Also, the values for units of Urban Coca can only be integers
Now we have two more constraints X ≥ 0, Y ≥ O
For the company to make maximum profit, the above inequalities have to be satisfied.
This is called formulating a real-world problem.
Solved Examples:
1. Find the maximum value for the following constraints
Maximise Z= 5x + 3y
Constraints:= 3x + 5y ≤ 15x, 5x+ 2y ≤ 10, x ≥ 0, y ≥ 0
Solution: Maximise Z= 5x + 3y
Subject to,
3x + 5y ≤ 15x
5x +2y ≤ 10
x ≥ 0
y ≥ 0
3x + 5y ≤ 15x
5x +2y ≤ 10
(image will be uploaded soon)
Hence, Z = 235/19 is maximum at (20/19), (45/19)
2. A manufacturer produces two products. The two products are nuts and bolts. It takes an hour of work on machine M and 1 hour of machine N to produce nuts. It takes 3 hours of work on machine M and 1hour of machine N to produce bolts. The manufacturer earns a profit of Rs. 17.50 per package on buts and Rs. 7 per package on bolts. How many packages of each should be produced in a day to maximize profit, if he operates his machine for at least 112 hours in a day?
Solution: Let the number of nuts produced be x
And, the number of bolts produced by y
According to the questions
Also x ≥ 0, y ≥ 0
As, we need to maximize profit
Hence, the function used here will be Maximise Z
Profit on each nut - Rs. 17.50
Profit on each bolt - Rs. 7.0
∵ Maximize Z = 17.50 + 7y
Combining all the constraints, we get
Maximize Z= 17.50 + 7y
Subject to constraints:
x + 3y ≤ 12
3x + y ≤ 12
x ≥ 0, y ≥ 0
x + 3y ≤ 12
3x + y ≤ 12
(image will be uploaded soon)
Hence, the profit will be maximize if the company produce
Total number of bolts- 3 packages
Total number of nuts - 3 packages
Maximum profit - 73.5.
Quiz Time
Which of the following is the property of all linear programming problems?
Use of graph in the solution
A computer program
Minimization of some objective
The alternative course of action to choose from
Usage of linear and non-linear equations and inequalities.
2. The first step in formulating a linear programming problem is
Graph the problem
Perform a sensitivity analysis
Identify the object and constraints
Define the decision variables
Understand the marginal issues been faces
3. In break- even analysis, we assume
Linear relationships
Non-linear relationships
Diminishing returns to the variable factors of production
Non- proportional relationships
FAQs on Types of Linear Programming: Definitions, Methods & Uses
1. What is Linear Programming (LP) and what is its main purpose?
Linear Programming is a mathematical method used for finding the best possible outcome or solution from a given set of parameters or constraints. Its main purpose is optimisation, which means either maximising a certain quantity (like profit or production) or minimising another (like cost or time), represented by a linear objective function.
2. What are the essential components of any linear programming problem (LPP)?
Every LPP is made up of three essential components as per the CBSE Class 12 Maths syllabus for 2025-26:
- Decision Variables: These are the unknown quantities (e.g., x, y) that need to be determined to solve the problem.
- Objective Function: This is a linear mathematical expression (e.g., Z = ax + by) that defines the quantity to be maximised or minimised.
- Constraints: These are linear inequalities or equations that represent the limitations or restrictions on the decision variables, such as resource availability or production limits.
3. What are the main types of linear programming problems based on the objective?
Linear programming problems are primarily categorised based on their objective. The main types are:
- Maximisation Problems: The goal is to maximise a quantity. These are common in scenarios like maximising company profit, production output, or revenue.
- Minimisation Problems: The goal is to minimise a quantity. This is often applied to problems like minimising production costs, transportation expenses, or the time taken for a task.
4. How are constraints and the objective function different in a linear programming model?
The objective function and constraints serve different roles. The objective function (e.g., Maximise P = 5x + 3y) is the single formula you aim to optimise; it represents the ultimate goal. In contrast, constraints (e.g., x + y ≤ 10) are a set of rules or limitations that your decision variables must obey. The constraints define the boundaries of what is possible (the feasible region), while the objective function helps you find the single best point within those boundaries.
5. What are some real-world examples that illustrate the importance of linear programming?
Linear programming is crucial in various fields. For example:
- In manufacturing, it helps determine the optimal number of products to produce to maximise profit, given constraints on labour hours and raw materials.
- In transportation, it is used to plan the shortest or most fuel-efficient routes for delivery networks, minimising costs.
- In finance, it assists in creating an investment portfolio that maximises returns while managing risk levels according to specific constraints.
- In agriculture, farmers use it to decide the mix of crops to plant to maximise revenue based on land availability and water resources.
6. What are the different types of solutions you can get from a linear programming problem?
When solving an LPP, you can encounter several types of solutions:
- A Unique Optimal Solution: There is only one point in the feasible region that provides the best value for the objective function.
- Multiple Optimal Solutions: More than one point provides the same optimal value. This usually happens when the objective function line is parallel to one of the constraint lines.
- An Unbounded Solution: The feasible region is not closed, and the objective function can be increased or decreased indefinitely without violating constraints. This often indicates an error in the problem formulation.
- An Infeasible Solution: There is no solution because the constraints are contradictory and no feasible region exists.
7. Why is the optimal solution in a graphical LPP typically located at a corner point of the feasible region?
This is due to the Corner Point Theorem of linear programming. The theorem states that if an optimal solution exists for a bounded linear programming problem, it must occur at one of the vertices (or corner points) of the feasible region. This is because the objective function is linear, and as you move its line across the feasible region, the last point(s) it touches will always be one or more of these extreme corners. Testing only the corner points is therefore a highly efficient way to find the optimal solution.
8. What happens if a linear programming problem has no feasible region?
If an LPP has no feasible region, it means that the set of constraints is contradictory and there are no points that can satisfy all the given conditions simultaneously. This situation leads to an infeasible solution. For example, if one constraint is x > 5 and another is x < 2, no value of x can satisfy both. In such a case, it is impossible to find any solution, let alone an optimal one, and the problem needs to be re-evaluated.
