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 widely used in Mathematics and some other field such as economics, business, telecommunication, and manufacturing fields. In this article, let us discuss the definition of linear programming, its components, simplex method with linear programming problems.
Table of Contents:
What is Linear Programming?
Linear programming (LP) or Linear Optimisation may be defined as the problem of maximizing or minimizing a linear function which is subjected to linear constraints. The constraints may be equalities or inequalities. The optimization problems involve the calculation of profit and loss. Linear programming problems are an important class of optimization problems, that helps to find the feasible region and optimize the solution in order to have the highest or lowest value of the function.
Components of Linear Programming
The basic components of the LP are as follows:
- Decision Variables
- Objective Functions
Linear Programming Simplex Method
To solve linear programming models, the simplex method is used to find the optimal solution to a problem. It involves slack variables, tableau and pivot variables for the optimisation of a problem. The algorithm used here is
- Change of variables and normalise the sign of independent terms
- Normalise restrictions
- Match the objective functions to zero
- Write the initial tableau of the simplex method
- Stopping condition
- Input and output variable choices
- Again update tableau.
- Continue the iteration until to get the optimal solution
Linear Programming Applications
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 optimization techniques. The applications of LP in some other fields are
- Engineering – It solves design and manufacturing problems as it is helpful for doing shape optimisation
- Efficient Manufacturing – To maximise profit, companies use linear expressions
- Energy Industry – It provides methods to optimise the electric power system.
- Transportation Optimisation – For cost and time efficiency.
Importance of Linear Programming
Linear programming is broadly applied in the field of optimization 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 multicommodity flow queries are deemed to be important to have produced much research on functional algorithms for their solution.
Plenty of algorithms for different types of optimization difficulties work by working on LP problems as sub-problems.
Linear Programming Example
Lets 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.
x + 2y ≤ 14
3x – y ≥ 0
x – y ≤ 2
Solution: The three inequalities indicate the constraints. The area of the plane that will be marked is the feasible region.
The optimization equation (z) = 5x + 3y. You have to find the (x,y) corner points that gives 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.
y = -(½) x + 7
y = 3x
Solving the above equations, we get the corner points as (2, 6)
y = -1/2 x + 7
y = x – 2
Solving the above equations, we get the corner points as (6, 4)
y = 3x
y = x – 2
Solving the above equations, we get the corner points as (-1, -3)
For linear systems, the maximum and minimum values of the optimization 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
(2, 6) :
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)
To learn all concepts in Math in a more engaging way, register at BYJU’S. Also, watch interesting videos on various Maths topics by downloading BYJU’S– The Learning App from Google Play Store or the app store.