Linear Programming

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 as an important technique which is used to find the optimum resource utilisation. The term “linear programming” consists of two words such 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 field such as economics, business, telecommunication, and manufacturing fields. In this article, let us discuss the definition of linear programming, its components, a 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 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.

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 assumption taken while working with linear programming are:

  • The number of constraints should be expressed in the quantitative terms
  • The relationship between the constraints and the objective function should be linear
  • The linear function (i.e., objective function) is to be optimised

Components of Linear Programming

The basic components of the LP are as follows:

  • Decision Variables
  • Constraints
  • Data
  • Objective Functions

Characteristics of Linear Programming

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.

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 optimisation 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 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.

Plenty of algorithms for different types of optimisation difficulties work by working on LP problems as sub-problems.

Linear Programming Example

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.

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 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.

Linear Programming problem

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 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

(2, 6) :

z = 5(2) + 3(6) = 10 + 18 = 28

(6, 4):

z = 5(6) + 3(4) = 30 + 12 = 42

(–1, –3):

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)

Frequently Asked Questions on Linear Programming

Define the concept of Linear Programming.

Linear programming is a process of optimising the problems which are subjected under 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.

Mention the different types of linear programming.

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 open solver.

What are the requirements of linear programming?

The five basic requirements of linear programming are:
Objective function

Mention the advantages of Linear programming

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

What is meant by linear programming problems?

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.

Leave a Comment

Your email address will not be published. Required fields are marked *