Linear programming problem (LPP)

Linear programming or linear optimization is a process which takes into consideration certain linear relationships to obtain the best possible solution to a mathematical model. It includes problems dealing with maximizing profits, minimizing costs, minimal usage of resources, etc. These problems are known as the linear programming problems (LPP). The LPP finds application in broad disciplines such as commerce, industry, etc. In this section, we will discuss an LPP and the mathematical formulation of the problem.

Problems on Linear Programming

Let us take a real life problem to understand linear programming. A home décor company received an order to manufacture cabinets. The first consignment requires up to 50 cabinets. There are two types of cabinets. The first type requires 15 hours of labour force (per piece) to be constructed and gives a profit of Rs 5000 per piece to the company. Whereas, the second type requires 9 hours of labour force and makes a profit of Rs 3000 per piece. However, the company has only 540 hours of workforce available for the manufacture of the cabinets. With this information given, you are required to find a deal which gives the maximum profit to the décor company.

Cabinet problem - Linear Programming

Given the situation, let us take up different scenarios to analyse how the profit can be maximized.

  • He decides to construct all the cabinets of the first type. In this case, he can create 540/15 = 36 cabinets. This would give him a profit of Rs 5000 x 36 = Rs 180,000.
  • He decides to construct all the cabinets of the second type. In this case, he can create 540/9 = 60 cabinets. But the first consignment requires only up to 50 cabinets. Hence, he can make profit of Rs 3000 x 50 = Rs 150,000.
  • He decides to make 15 cabinets of type 1 and 35 of type 2. In this case, his profit is (5000 x 15 + 3000 x 35) Rs 180,000.

Similarly, there can be many strategies which he can devise to maximize his profit by allocating different amount of labour force to the two types of cabinets. We do a mathematical formulation of the discussed LPP to find out the strategy which would lead to maximum profit.

Mathematical Formulation of an LPP

Let x and y be the number of cabinets of types 1 and 2 respectively that he must manufacture. They are non-negative and known as non-negative constraints.

The company can invest a total of 540 hours of labour force and is required to create up to 50 cabinets. Hence,

15x + 9y <= 540

x + y <= 50

The above two equations are known as linear constraints.

Let Z be the profit he earns from manufacturing x and y pieces of the cabinets of types 1 and 2. Thus,

Z = 5000x + 3000y

Our objective here is to maximize Z. Hence Z is known as the objective function. To find the answer to this question, we use graphs, which is known as the graphical method of solving LPP. We will cover this in the subsequent sections.

To learn more about solving LPP, download Byju’s The Learning App.

Practise This Question

Which of the following shows 114 and 258 on a number line?