Linear Programming

A linear programming may be defined as the problem of maximizing or minimizing a linear function subject to linear constraints. The constraints may be equalities or inequalities.

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

A real time example would be considering the limitations of labors and materials, and finding the best productive levels for maximum profit in particular circumstances.

In real life, linear programming is part of a vital area of mathematics known as optimization techniques. This field is applied every day in the resource allocation and organization. These real-life systems can have hundreds of variables.

Lets Work Out-

Example- Calculate the maximal and minimal value of z = 5x + 3y for the following constraints.

\(x + 2y \leq 14\)

\(3x – y \geq 0\)

\(x – y \leq 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 \leq 14\)  \(\Rightarrow y\leq -(1/2)x + 7\)

\(3x – y \geq 0\)  \(\Rightarrow y\leq 3x\)

\(x – y \leq 2\)  \(\Rightarrow y\geq x – 2\)

Here is the graph for the above equations.

Linear Programming

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

Byju’s also provides NCERT Solutions for Class 12 Maths, click on the link for NCERT Solutions for Linear Programming


Practise This Question

For which of the following matrices it is possible to find a determinant?