What is Linear Programming?

Overview

Linear programming is the technique we use in mathematics to minimize or maximize a linear function when subjected to various constraints.

The linear programming is used for optimization. In short, we use abbreviations for linear programming as LP or LPP.

LPP is the popular mathematical technique which is used to make maximum profit and minimum loss, in various business problems, government plans etc.

The method nowadays is used in various fields like, data science, data analytics, machine learning, commerce, business activities.

Important definitions

Linear programming problem-

We need to optimize the linear function Z subject to certain conditions, these types of problems are called Linear programming problem or in short LPP.

Objective functions-

This is a linear function of several variables, subject to the conditions.

Optimal value-

This is a maximum or minimum value of an object function which is to be calculated in a LPP.

Formulation of LPP

Let’s consider the following example-

Example: A dietician mixes together two kinds of food, say, A and B in such a way that the mixture contains at least 6 units of nutrient P, 7 units of nutrient Q, 12 units of nutrient R and 9 units of nutrient S. The vitamin contents of 1 kg of food A and 1 kg of food B are given below:

Cost	nutrient P	nutrient Q	nutrient R	nutrient S
Food-A	1	1	1	2
Food-B	2	1	3	1

One kg of food X costs Rs. 5, whereas one kg of food Y costs Rs. 8. Formulate the linear programming problem.

 Sol.

Decision variables- Here decision variables are units of food A and B.

Let food A in the mixture be x1and food B in the mixture x2.

Objective function- To minimize the cost,

Objective function- To minimize the cost,

Total cost of food A and B  = 5x₁+8x₂

Or

Z=5x₁+8x₂

Now we will write the constraints one by one-

Constraint-1:  x₁+ 2x₂ ≥ 6

Constraint-2:  x₁ + x₂ ≥ 7

Constraint-3:  x1+ 3×2 ≥ 12

Constraint-4:  2×1+ 2×2 ≥ 9

Constraint-5:  x1 ≥ 0, x2 ≥ 0

Mathematical formation will be as follows-

To minimize,

Z=5×1+8×2

Subject to the constraints-

Note- The variables that enter into the problem are called ‘decision variables’.

Solution of LPP by using Graphical method

LPP having two variables can be easily solved by a graphical method which provides a pictorial representation of the solution and we get insights into the basic concept used in solving LPP.

Step by step procedure to solve LPP graphically-

1.     First we need to formulate the given problem as a LPP in mathematical form.

2.     Now plot the given constraints on x1- x2  coordinate plane and find the convex region.

3.     Now determine the convex region and find the value of the objective function at each vertex. The vertex which gives the max or min value of the objective function gives the optimal solution of the LPP.

Note- The region satisfying all the constraints is called a feasible region.

Example: Solve the following LPP graphically-

Maximize-

Z=3x₁+2x₂

Subject to the constraints-

Solution.

Change the given constraints into equations-

The line x1+ 2×2 = 10 meets the x-axis at the point A(10,0) and meets the y-axis at the point B(0,5). Join A and B to get the graph for the line.  Hence origin (0,0) satisfies the inequality

so that the half plane containing the origin represents the solution set of

And

The line 3×1+ x2 = 15 meets the x-axis at the point C(5,0) and meets the y-axis at the point D(0,15). Join C and D to get the graph for the line.

Hence origin (0,0) satisfies the inequality

so that the half plane containing the origin represents the solution set of

Now all the points in the first quadrant satisfies x₁≥ 0, x₂≥ 0

So that first quadrant is the region represented by x₁≥ 0, x₂≥ 0.

Hence the region OCEBO satisfies all the inequalities.

And each point on the region is the feasible solution of the problem.

 Feasible solution-

Here in this problem the feasible solution is (5,0), (4,3) and (0,5).

 Now we can obtain the optimal solution to the problem.

As we know that any point in the feasible region that gives the optimal value is called an optimal solution.

.

The value of the objective function Z=3x₁+2x₂ at corner points of the feasible region is given below-

vertex [ feasible region ]	Value of Z=3x1+2x2
O(0,0)	0
C(5,0)	15
E(4,3)	18 [Maximum]
B(0,5)	10

Here we see that the maximum value of Z is 18.

Z=3x₁+2x₂

Note-

• This method is called corner point method.
• The optimal value of objective function must occur at a corner point (vertex) of the feasible region.
• If the feasible region is bounded then the objective function Z has both maximum and minimum values on corner points of the bounded region.

Interested in learning about similar topics? Here are a few hand-picked blogs for you!

• What is hypothesis testing?
• What is Fourier series?
• What is Taylor’s series?
• What is skewness?