Types of Linear Programming Problems with Definitions Examples and Solution Methods
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 Different Types of Linear Programming Problems in Mathematics
1. What are the different types of linear programming problems?
The different types of linear programming problems (LPP) are classified based on objective, constraints, and solution characteristics. The main types include:
- Maximization problems – aim to maximize profit or output.
- Minimization problems – aim to minimize cost or time.
- Feasible and Infeasible problems – depending on whether solutions satisfy all constraints.
- Bounded and Unbounded problems – based on whether the optimal value is finite.
- Standard form and Canonical form LPP – based on mathematical structure.
These classifications help in choosing the correct solving method such as the graphical method or simplex method.
2. What is a maximization problem in linear programming?
A maximization problem in linear programming is one where the objective is to find the largest possible value of a linear objective function. It is generally written as:
Maximize Z = ax + by
subject to linear constraints like:
- c₁x + d₁y ≤ k₁
- x ≥ 0, y ≥ 0
Example: Maximize profit Z = 5x + 3y subject to resource constraints. The goal is to find values of x and y that give the highest Z while satisfying all constraints.
3. What is a minimization problem in linear programming?
A minimization problem in linear programming is one where the objective is to find the smallest possible value of a linear objective function. It is generally written as:
Minimize Z = ax + by
subject to constraints such as:
- c₁x + d₁y ≥ k₁
- x ≥ 0, y ≥ 0
These problems commonly arise in cost reduction, transportation, and diet problems where the aim is to minimize expenses while meeting requirements.
4. What is the difference between bounded and unbounded linear programming problems?
A bounded LPP has a finite optimal solution, while an unbounded LPP does not have a finite maximum or minimum value.
- Bounded solution: The feasible region is closed, and the objective function reaches a maximum or minimum at a corner point.
- Unbounded solution: The feasible region is open in the direction of optimization, so the objective value increases or decreases indefinitely.
In graphical terms, if the objective line can move infinitely without leaving the feasible region, the problem is unbounded.
5. What is a feasible and infeasible linear programming problem?
A feasible LPP has at least one solution that satisfies all constraints, whereas an infeasible LPP has no solution satisfying all constraints simultaneously.
- Feasible region: The common area satisfying all inequalities.
- Infeasible problem: Occurs when constraints contradict each other (e.g., x ≥ 5 and x ≤ 3).
If the feasible region is empty, the linear programming problem has no solution.
6. What is the standard form of a linear programming problem?
The standard form of an LPP is when all constraints are expressed as equations with non-negative variables. It is written as:
Maximize Z = c₁x₁ + c₂x₂ + ... + cₙxₙ
- Subject to: a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ = b₁
- x₁, x₂, ..., xₙ ≥ 0
Inequalities are converted into equations by adding slack variables. This form is mainly used in the simplex method.
7. What is the canonical form of a linear programming problem?
The canonical form of an LPP is when all constraints are of the type ≤ and all variables are non-negative. It is written as:
Maximize Z = c₁x₁ + c₂x₂
- a₁₁x₁ + a₁₂x₂ ≤ b₁
- x₁, x₂ ≥ 0
This form is convenient for solving problems using the graphical method in two variables.
8. Can you give an example of a linear programming problem?
A simple example of a linear programming problem is maximizing profit from two products.
Maximize Z = 4x + 3y
- x + y ≤ 5
- 2x + y ≤ 8
- x ≥ 0, y ≥ 0
Here, x and y are quantities of two products. The solution is found at a corner point of the feasible region using the graphical or simplex method.
9. What is a unique, multiple, or no optimal solution in linear programming?
A linear programming problem may have a unique solution, multiple solutions, or no optimal solution depending on the objective function and feasible region.
- Unique solution: Objective function touches the feasible region at one corner point.
- Multiple solutions: Objective function is parallel to a boundary segment, giving infinitely many optimal points.
- No optimal solution: Occurs in unbounded problems.
This classification is important when interpreting results of graphical or simplex methods.
10. How do you identify the type of a linear programming problem?
You identify the type of a linear programming problem by examining its objective function, constraints, and feasible region.
- Check if the objective is maximize or minimize.
- Determine whether constraints are ≤, ≥, or =.
- Plot the feasible region to see if it is bounded or unbounded.
- Verify whether the constraints produce a feasible or infeasible region.
These steps help classify the LPP before applying solving techniques like the graphical method or simplex algorithm.
