{"id":1677,"date":"2021-05-26T12:04:50","date_gmt":"2021-05-26T06:34:50","guid":{"rendered":"https:\/\/www.goseeko.com\/blog\/?p=1677"},"modified":"2021-10-30T07:40:43","modified_gmt":"2021-10-30T07:40:43","slug":"what-is-linear-programming","status":"publish","type":"post","link":"https:\/\/www.goseeko.com\/blog\/what-is-linear-programming\/","title":{"rendered":"What is Linear Programming?"},"content":{"rendered":"\n

Overview<\/strong><\/h2>\n\n\n\n

Linear programming is the technique we use in mathematics to minimize or maximize a linear function when subjected to various constraints.<\/p>\n\n\n\n

The linear programming is used for optimization. In short, we use abbreviations for linear programming as LP or LPP.<\/p>\n\n\n\n

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

The method nowadays is used in various fields like, data science, data analytics, machine learning, commerce, business activities.<\/p>\n\n\n\n

Important definitions<\/strong><\/h2>\n\n\n\n

Linear programming problem-<\/strong><\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Objective functions-<\/strong><\/p>\n\n\n\n

This is a linear function of several variables, subject to the conditions.<\/p>\n\n\n\n

Optimal value-<\/strong><\/p>\n\n\n\n

This is a maximum or minimum value of an object function which is to be calculated in a LPP.<\/p>\n\n\n\n

Formulation of LPP<\/strong><\/h2>\n\n\n\n

Let\u2019s consider the following example-<\/p>\n\n\n\n

Example: <\/strong>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:<\/strong><\/p>\n\n\n\n

Cost<\/strong><\/td>nutrient P<\/strong><\/td>nutrient Q<\/strong><\/td>nutrient R<\/strong><\/td>nutrient S<\/strong><\/td><\/tr>
Food-A<\/strong><\/td>1<\/strong><\/td>1<\/strong><\/td>1<\/strong><\/td>2<\/strong><\/td><\/tr>
Food-B<\/strong><\/td>2<\/strong><\/td>1<\/strong><\/td>3<\/strong><\/td>1<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

One kg of food X costs Rs. 5, whereas one kg of food Y costs Rs. 8. Formulate the linear programming problem.<\/strong><\/p>\n\n\n\n

 Sol.<\/p>\n\n\n\n

Decision variables- <\/strong>Here decision variables are units of food A and B.<\/p>\n\n\n\n

Let food A in the mixture be x1and food B in the mixture x2.<\/p>\n\n\n\n

Objective function- <\/strong>To minimize the cost,<\/p>\n\n\n\n

Objective function- <\/strong>To minimize the cost,<\/p>\n\n\n\n

Total cost of food A and B  = 5x1<\/sub>+8x2<\/sub><\/p>\n\n\n\n

Or<\/p>\n\n\n\n

Z=5x1<\/sub>+8x2<\/sub><\/p>\n\n\n\n

Now we will write the constraints one by one-<\/p>\n\n\n\n

Constraint-1:  x1<\/sub>+ 2x2<\/sub> \u2265 6<\/p>\n\n\n\n

Constraint-2:  x1<\/sub> + x2<\/sub> \u2265 7<\/p>\n\n\n\n

Constraint-3:  x1+ 3×2 \u2265 12<\/p>\n\n\n\n

Constraint-4:  2×1+ 2×2 \u2265 9<\/p>\n\n\n\n

Constraint-5:  x1 \u2265 0, x2 \u2265 0<\/p>\n\n\n\n

Mathematical formation will be as follows-<\/strong><\/p>\n\n\n\n

To minimize,<\/p>\n\n\n\n

Z=5×1+8×2<\/p>\n\n\n\n

Subject to the constraints-<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Note- <\/strong>The variables that enter into the problem are called \u2018decision variables\u2019.<\/p>\n\n\n\n

Solution of LPP by using Graphical method<\/strong><\/h2>\n\n\n\n

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.<\/p>\n\n\n\n

Step by step procedure to solve LPP graphically-<\/strong><\/p>\n\n\n\n

1.     First we need to formulate the given problem as a LPP in mathematical form.<\/p>\n\n\n\n

2.     Now plot the given constraints on x1- x2  coordinate plane and find the convex region.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Note- <\/strong>The region satisfying all the constraints is called a feasible region.<\/p>\n\n\n\n

Example: Solve the following LPP graphically-<\/strong><\/p>\n\n\n\n

Maximize-<\/strong><\/p>\n\n\n\n

Z=3x1<\/sub>+2x2<\/sub><\/p>\n\n\n\n

Subject to the constraints-<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Solution.<\/p>\n\n\n\n

Change the given constraints into equations-<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

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 <\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

so that the half plane containing the origin represents the solution set of <\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

And<\/strong><\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Hence origin (0,0) satisfies the inequality <\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

so that the half plane containing the origin represents the solution set of <\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Now all the points in the first quadrant satisfies x1<\/sub>\u2265 0, x2<\/sub>\u2265 0<\/p>\n\n\n\n

So that first quadrant is the region represented by x1<\/sub>\u2265 0, x2<\/sub>\u2265 0.<\/p>\n\n\n\n

Hence the region OCEBO satisfies all the inequalities.<\/p>\n\n\n\n

And each point on the region is the feasible solution of the problem.<\/p>\n\n\n\n

 Feasible solution-<\/strong><\/p>\n\n\n\n

Here in this problem the feasible solution is (5,0), (4,3) and (0,5).<\/p>\n\n\n\n

 Now we can obtain the optimal solution to the problem.<\/p>\n\n\n\n

As we know that any point in the feasible region that gives the optimal value is called an optimal solution.<\/p>\n\n\n\n

.<\/p>\n\n\n\n

The value of the objective function Z=3x1<\/sub>+2x2<\/sub> <\/strong>at corner points of the feasible region is given below-<\/p>\n\n\n\n

vertex [ feasible region ]<\/td>Value of Z=3x1<\/sub>+2x2<\/sub><\/td><\/tr>
O(0,0)<\/td>0<\/td><\/tr>
C(5,0)<\/td>15<\/td><\/tr>
E(4,3)<\/td>18 [Maximum]<\/td><\/tr>
B(0,5)<\/td>10<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Here we see that the maximum value of Z is 18.<\/p>\n\n\n\n

Z=3x1<\/sub>+2x2<\/sub><\/p>\n\n\n\n

Note-<\/strong><\/p>\n\n\n\n