Linear Programming Problem (LPP)

Linear Programming Problem Meaning (LPP meaning)

In mathematics, we deal with both, linear equations and linear inequality. Linear equations with two variables such as Y = 2x + 1, 5x = 3+6y, etc. confirm that the right side of the sign ‘=’ is equal to its left side. Linear inequalities are not equations where both sides are equal. Here, the concept of greater than and lesser than comes into play. For example, 5x + y <100, in this equation, we can say that 5x+y is less than 100 which means the value of x and y can fluctuate only up to a certain extent to keep the entire term (5x+y) less than 100. 

Problems that seek to maximize or minimize the profits (or cost) and form a general class of problems are called optimization problems. Thus, an optimization problem may involve finding maximum profit, minimum cost or minimum use of resources, etc.

A special yet very important class of problems is called linear programming problems. (Example: a furniture dealer deals in only two items- tables and chairs. He has Rs 50,000 to invest and has a storage space of 60 items. A table costs Rs 2500 and a chair costs Rs 500. He estimates that from the sale of one table, he can make a profit of Rs 250 and that from the sale of one table a profit of Rs 75. He can use the method of linear programming to find out how many tables and chairs he should buy from the available money so as to maximize his total profit, assuming that he can sell all the items which he buys.

Mathematical Formulations of Linear Programming Problems

In the example given above, the furniture dealer can formulate his problems mathematically in two variables. He can invest his money in buying tables or chairs or both depending on the profit he would earn in each case. There are few constraints also like 

(i) His investment is limited to a maximum of Rs 50,000. 

(ii) His storage space can take a maximum of 60 items.

Case 1 - He Decides to Buy Only Tables:

If each table costs Rs 2,500 and he has a budget of Rs 50,000 then,

No of chairs he can buy = Rs 50000 / Rs 2500 = 20 tables.

If the profit from each table is 250 then,

Profit from 20 tables = Rs 250 x 20 = Rs 5000.

Case 2 - He Decides to Buy Only Chairs:

If each chair costs Rs 500 and he has a budget of Rs 50,000 then,

No of chairs he can buy = Rs 50000 / Rs 500 = 100 chairs.

But, he can store only 60 pieces of furniture so if he buys 60 chairs then,

Profit from each chair = Rs 75. 

Profit from 60 chairs = Rs 75 x 60 = Rs 4,500.

Case 3 - He Decides to Buy Both Tables and Chairs:

Often, there are many other possibilities, like for instance, he might choose to buy 10 tables and 50 chairs, as he can store only 60 pieces. In this case, the total profit would be Rs (10 × 250 + 50 × 75), i.e., Rs 6250 and so on. Thus, we can see that the dealer can invest his money in different ways by which he would earn different profits by following different investment strategies. 

Now the problem is: How should he invest his money in order to get the maximum profit? To answer this question, let us try to formulate the problem mathematically.

Mathematical Formulation of the Problem:

Let the number of tables is x and the number of chairs is y that the dealer buys. Obviously, x and y must be non-negative, i.e.,

                                    X    0……….(1) (Non-negative constraints)

                                    Y    0……….(2)

The dealer is constrained with the maximum amount he can invest (Here it is Rs 50,000) and by the maximum number of items he can store (Here it is 60).

 Stated mathematically,

                                    2500x + 500y ≤ 50000 (investment constraint) 

                               or 5x + y ≤ 100….... (3)

                             Thereby, x + y ≤ 60 (storage constraint)....... (4)

The dealer would want to invest in such a way as to maximise his profit. So as to say, Z which stated as a function of x and y is given by

                                    Z = 250x + 75y (can be called as objective function) ... (5)

Mathematically, the given problems now reduces to: 

                    Maximise Z = 250x + 75y

 The Subject to constraints: 5x + y ≤ 100

                                           x + y ≤ 60

                                           x ≥ 0, y ≥ 0 

So, it is important to maximize the linear function Z subject to certain conditions determined by a set of linear inequalities with variables as non-negative. There are also few other problems where we need to minimize a linear function subject so that certain conditions that are determined by a set of linear inequalities with variables are non-negative. Such problems are called Linear Programming Problems.