Linear Programming

Linear programming (LP)  or Linear Optimisation may be defined as the problem of maximizing or minimizing a linear function subject 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. 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.

Components of Linear Programming

The basic components of the LP are as follows:

  • Decision Variables
  • Constraints
  • Data
  • 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 Problem

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.

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

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

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.

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.

Leave a Comment

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