What is Linear Programming Problem or LPP?
Linear Programming problem is a technique that helps to find the optimal solution for a given problem modeled as a set of linear relationships. It is a type of optimization problem that determines the feasible region (a region that contains all the possible solutions of an LPP) and optimizes the solution to get the maximum or minimum function value.
In simple terms, a linear programming problem is a set of linear equations that are used to find the value of variables to optimize the objective functions.
Basic Terminologies
- Decision Variable: These are quantities to be determined.
- Decision variables are interrelated and have linear relationships.
- Objective Function: The function (value) that need to optimized.
- The objective function must be clear and well-defined.
- Constraints: Represents on decision variables how to use the available resource (amount of time, number of people, etc.)
- Feasible Solution: Set all the possible solutions that satisfy the given constants.
- Optimal Solution: It is the best possible solution among all the possible feasible solutions.
Characteristics of LPP
- Decision variables will decide the output.
- The objective function should be specified quantitatively.
- Constraints (limitations) should be expressed in mathematical form.
- Relationships between two or more variables should be linear.
- i.e., the degree of the variable is 1.
- The values of the variables should always be non-negative or zero.
- There should always be finite and infinite inputs and output numbers.
- The solution is not feasible if the function has an infinite factor.
For a Linear Programming problem, Decision Variable, Objective Function, and Constraint function should always be linear functions.
Types of Linear Programming Problems
Following are the types of Linear Programming Problems:
- Manufacturing Problem
- Problem evaluates the number of units of various items produced or sold when we have:
- It involves maximizing the production rate or net profits
- Constraints: The number of workforces, machine hours, warehouse space, labor hours, etc., are given.
- Objective Function: Production Rate
- Diet Problem
- Evaluates the amount of nutrition that is required to include in the diet.
- The purpose of the diet problem is to set the daily nutrition needs at a minimal cost.
- Constraints: Calorie intake, level of sugar
- Objective Function: Cost of food Consumption
- Transportation Problem
- Used to evaluate the most cost-effective method of carrying or delivering products from the factory to the market.
- Constraints: Amount of material, cost of products
- Objective Function: Transportation cost
- Optimal Assignment Problem
- It is used to assign a task or an assignment to a company at a minimal cost in the minimum time.
- Constraints: Number of employees, number of work hours
- Objective Function: Number of tasks to be completed at a minimal cost.
- Optimal Assignment Problem
- It is used to assign a task or an assignment to a company at a minimal cost in the minimum time.
- Constraints: Number of employees, number of work hours
- Objective Function: Number of tasks to be completed at a minimal cost.
There are different methods to solve any Linear Programming Problem.
- Graphical Method
- Simplex Method
- North West Corner Method
- Least Square Methods
For now, we will discuss only Graphical method to solve LPP
Graphical Method
Steps for Graphical Method:
- Formulate the LPP.
- Construct the graph and plot all the constraint lines.
- Determine the valid side of each constraint line.
- Identify the feasible solution region.
- Find the optimum points.
- Calculate the coordinates of optimum points.
- Evaluate the objective function at the optimum point.
Example: Solve the given linear programming problem by graphical method.
Max Z = f(x, y) = 3x + 2y
Constraints: 2x + y <= 18
2x + 3y <= 42
3x + y <= 24
x >= 0, y >= 0
Now, let’s plot the graph of the given constraints and find the feasible region.
The above-shaded region (blue color) is the feasible region for the given lpp.
Now, we will find the value of the objective function at the corner points of the feasible region.
| Corner Point | f(x,y) = 3x+2y |
| (0, 0) | 0 |
| (8, 0) | 24 |
| (6, 6) | 30 |
| (3, 12) | 33 |
| (0, 14) | 28 |
From the above table, we got that the objective function obtains its maximum value at (3, 12).
Hence, the maximum value of the objective function f(x,y) = 3x + 2y = 33.