In Mathematics, linear programming is a method of optimising operations with some constraints. The main objective of linear programming is to maximize or minimize the numerical value. It consists of linear functions which are subjected to the constraints in the form of linear equations or in the form of inequalities. Linear programming is considered an important technique that is used to find the optimum resource utilisation. The term “linear programming” consists of two words as linear and programming. The word “linear” defines the relationship between multiple variables with degree one. The word “programming” defines the process of selecting the best solution from various alternatives.
Linear Programming is widely used in Mathematics and some other fields such as economics, business, telecommunication, and manufacturing fields. In this article, let us discuss the definition of linear programming, its components, and different methods to solve linear programming problems.
Table of Contents:
Linear programming (LP) or Linear Optimisation may be defined as the problem of maximizing or minimizing a linear function that is subjected to linear constraints. The constraints may be equalities or inequalities. The optimisation problems involve the calculation of profit and loss. Linear programming problems are an important class of optimisation problems, that helps to find the feasible region and optimise the solution in order to have the highest or lowest value of the function.
In other words, linear programming is considered as an optimization method to maximize or minimize the objective function of the given mathematical model with the set of some requirements which are represented in the linear relationship. The main aim of the linear programming problem is to find the optimal solution.
Linear programming is the method of considering different inequalities relevant to a situation and calculating the best value that is required to be obtained in those conditions. Some of the assumptions taken while working with linear programming are:
The basic components of the LP are as follows:
The following are the five characteristics of the linear programming problem:
Constraints – The limitations should be expressed in the mathematical form, regarding the resource.
Objective Function – In a problem, the objective function should be specified in a quantitative way.
Linearity – The relationship between two or more variables in the function must be linear. It means that the degree of the variable is one.
Finiteness – There should be finite and infinite input and output numbers. In case, if the function has infinite factors, the optimal solution is not feasible.
Non-negativity – The variable value should be positive or zero. It should not be a negative value.
Decision Variables – The decision variable will decide the output. It gives the ultimate solution of the problem. For any problem, the first step is to identify the decision variables.
The Linear Programming Problems (LPP) is a problem that is concerned with finding the optimal value of the given linear function. The optimal value can be either maximum value or minimum value. Here, the given linear function is considered an objective function. The objective function can contain several variables, which are subjected to the conditions and it has to satisfy the set of linear inequalities called linear constraints. The linear programming problems can be used to get the optimal solution for the following scenarios, such as manufacturing problems, diet problems, transportation problems, allocation problems and so on.
The linear programming problem can be solved using different methods, such as the graphical method, simplex method, or by using tools such as R, open solver etc. Here, we will discuss the two most important techniques called the simplex method and graphical method in detail.
The simplex method is one of the most popular methods to solve linear programming problems. It is an iterative process to get the feasible optimal solution. In this method, the value of the basic variable keeps transforming to obtain the maximum value for the objective function. The algorithm for linear programming simplex method is provided below:
Step 1 : Establish a given problem. (i.e.,) write the inequality constraints and objective function.
Step 2: Convert the given inequalities to equations by adding the slack variable to each inequality expression.
Step 3 : Create the initial simplex tableau. Write the objective function at the bottom row. Here, each inequality constraint appears in its own row. Now, we can represent the problem in the form of an augmented matrix, which is called the initial simplex tableau.
Step 4 : Identify the greatest negative entry in the bottom row, which helps to identify the pivot column. The greatest negative entry in the bottom row defines the largest coefficient in the objective function, which will help us to increase the value of the objective function as fastest as possible.
Step 5 : Compute the quotients. To calculate the quotient, we need to divide the entries in the far right column by the entries in the first column, excluding the bottom row. The smallest quotient identifies the row. The row identified in this step and the element identified in the step will be taken as the pivot element.
Step 6: Carry out pivoting to make all other entries in column is zero.
Step 7: If there are no negative entries in the bottom row, end the process. Otherwise, start from step 4.
Step 8: Finally, determine the solution associated with the final simplex tableau.
The graphical method is used to optimize the two-variable linear programming. If the problem has two decision variables, a graphical method is the best method to find the optimal solution. In this method, the set of inequalities are subjected to constraints. Then the inequalities are plotted in the XY plane. Once, all the inequalities are plotted in the XY graph, the intersecting region will help to decide the feasible region. The feasible region will provide the optimal solution as well as explains what all values our model can take. Let us see an example here and understand the concept of linear programming in a better way.
Example:
Calculate the maximal and minimal value of z = 5x + 3y for the following constraints.
Solution:
The three inequalities indicate the constraints. The area of the plane that will be marked is the feasible region.
The optimisation equation (z) = 5x + 3y. You have to find the (x,y) corner points that give the largest and smallest values of z.
To begin with, first solve each inequality.
x + 2y ≤ 14 ⇒ y ≤ -(1/2)x + 7
3x – y ≥ 0 ⇒ y ≤ 3x
x – y ≤ 2 ⇒ y ≥ x – 2
Here is the graph for the above equations.
Now pair the lines to form a system of linear equations to find the corner points.
Solving the above equations, we get the corner points as (2, 6)
Solving the above equations, we get the corner points as (6, 4)
Solving the above equations, we get the corner points as (-1, -3)
For linear systems, the maximum and minimum values of the optimisation equation lie on the corners of the feasibility region. Therefore, to find the optimum solution, you only need to plug these three points in z = 3x + 4y
z = 5(2) + 3(6) = 10 + 18 = 28
z = 5(6) + 3(4) = 30 + 12 = 42
z = 5(-1) + 3(-3) = -5 -9 = -14
Hence, the maximum of z = 42 lies at (6, 4) and the minimum of z = -14 lies at (-1, -3)
A real-time example would be considering the limitations of labours and materials and finding the best production levels for maximum profit in particular circumstances. It is part of a vital area of mathematics known as optimisation techniques. The applications of LP in some other fields are
Linear programming is broadly applied in the field of optimisation for many reasons. Many functional problems in operations analysis can be represented as linear programming problems. Some special problems of linear programming are such as network flow queries and multi-commodity flow queries are deemed to be important to have produced much research on functional algorithms for their solution.
Solve the following linear programming problems:
Linear programming is a process of optimising the problems which are subjected to certain constraints. It means that it is the process of maximising or minimizing the linear functions under linear inequality constraints. The problem of solving linear programs is considered as the easiest one.
The different types of linear programming are:
Solving linear programming by Simplex method
Solving linear programming using R
Solving linear programming by graphical method
Solving linear programming with the use of an open solver.
The five basic requirements of linear programming are:
Objective function
Constraints
Linearity
Non-negativity
Finiteness
The advantages of linear programming are:
Linear programming provides insights to the business problems
It helps to solve multi-dimensional problems
According to the condition change, LP helps in making the adjustments
By calculating the cost and profit of various things, LP helps to take the best optimal solution
The linear programming problems (LPP) helps to find the best optimal solution of a linear function (also, known as the objective function) which are placed under certain constraints (set of linear inequality constraints)
To learn all concepts in Maths in a more engaging way, register at BYJU’S. Also, watch interesting videos on various Maths topics by downloading BYJU’S– The Learning App.
| MATHS Related Links | |
| Integer Worksheet | Data Handling Worksheets |
| Derivative Of Volume Of A Cone | Area And Circumference Of A Circle |
| Pareto Chart | Rational Number Between Two Rational Numbers |
| A Intersection B Formula | Cos 60 |
| Polynomial Examples | Chain Rule Problems |
