Linear Programming Problems

What is Linear Programming? A linear programming problem (LPP) deals with the optimization problem of two linear variables. The function formed using those two linear variables is called an objective function.

In our day-to-day lives, we encounter many problems forming a linear equation and/or its inequalities. And many applications in mathematics also involve linear equations/inequalities. Hence, those application-based problems which seek to maximize or minimize are optimization problems. In this article, we come across solving linear programming problems also. 

What Is LPP?

LPP is subject to constraints of linear variables which are non-negative and satisfy the sets of inequalities.

Objective Functions: z = ax + by,

where a and b are to be maximized or minimized depending upon the condition.

Common terminologies used in Linear Programming:

Decision variables: x and y are the decision variables in an objective function.

Non-negative constraints: These conditions x, y ≥ 0 are called non-negative constraints.

Constraints: The linear inequalities or equations on the variables of a linear programming problem are called constraints.

Optimisation problem: This is a problem which seeks to minimise or maximise a linear function subject to certain constraints as found by a set of linear inequalities. LPP are special types of optimization problems. 

Feasible region: The region which is common to all the constraints including the non-negative constraints is referred to as feasible region.

Infeasible region: It is the region other than the feasible region.

Feasible solutions: Points within and on the boundary of a feasible region denote feasible solutions of the constraints. 

Infeasible solutions: Any point which is outside the feasible region is known as infeasible solution.

Optimal solution: If any point in the feasible region gives minimum or maximum value of the objective function, it is called an optimal solution.

Important Results:

Theorem 1: Let R be the feasible region for an LPP and be the objective function. The optimal value of Z must occur at the corner point of the feasible region.

Theorem 2: Let R be the feasible region. If the R is bounded, then the objective function Z, has both maximum and minimum value in region R. And both of them occur at the corner points of R.

If R is unbounded , then a minimum  or maximum value of the objective function may not exist. If it exists, it should come at a corner point of R (by theorem 1)

Solving Linear Programming Problems

Corner Point Method

This is a method of solving LLP. Following are the steps of this method.

1. First find the feasible region of the LLP and find its corner points either by checking or by solving two equations of the lines intersecting at that point. 

2. Find objective function Z = ax+by at each corner point. Let M and m represent the largest and smallest values at these points, respectively.

3. If the feasible region is bounded, M and m are the maximum and minimum values of Z. If the feasible region is unbounded, then

a. M will be the maximum value of Z, if the open half plane determined by ax+by>M which has no point in common with the feasible region. Otherwise, Z will not have maximum value.

b. M will be the minimum value of Z, if the open half plane determined by ax+by<m which has no point in common with the feasible region. Otherwise, Z will not have minimum value.

Linear Programming Applications

The most important applications of linear programming are seen in the following areas:

Manufacturing Problems

These problems are related to industry problems, such as some industries are required to produce the number of units of different products, requiring fixed manpower, operating hours, labour hour per unit of product, etc. Such that maximum profit is produced while selling these products.

Example 1:

A company produces two types of TVs, one is black and white, while the other is colour. The company has the resources to make at most 200 sets a week. Creating a black and white set costs Rs. 2700 and Rs. 3600 to create a coloured set. The business should spend no more than Rs. 648000 a week producing TV sets. If it benefits from Rs. 525 per set of black and white and Rs. 675 per set of colours, How many sets of black/white and coloured sets should it produce in order to get maximum profit? Formulate this using LPP.

Solution: Let x and y be the number of black/white and coloured TVs, respectively

Subject to constraints:

x, y ≥ 0 (Non-negative constraint)

x + y ≤ 200 (Quantity constraints)

2700x + 3600y ≤ 648000 (Cost constraints)

Objective function: Z = 525x + 675y (objective is to maximize profit)

Feasible region R are bounded as shown in the figure above.

Thus maximum value of Z occurs at C(80,120), i.e., 123000. So the company should manufacture 80 black/white and 120 coloured TV sets to get maximum profit.

Diet Problems

In such kind of problems, a person is required to produce a diet checking the different nutrients required  to minimize the cost of the desired diet.

Example 2:

A health enthusiast wishes to mix two types of foods in his diet, in such a way that vitamin content of the mixture contains at least 10 units of vitamin B and 13 units of vitamin C. Food (F1) contains 1 unit/kg of vitamin B and 2 units/kg of vitamin C. Food (F2) contains 2 unit/kg of vitamin B and contains 1 unit/kg of vitamin C. F1 costs Rs 60/kg and F2 costs Rs 80/kg. Frame his diet plan making a linear programming problem in order to minimize the cost of the mixture.

Solution: Let x and y represent the number of units of vitamin B and C, respectively.

Subject to constraints:

x, y ≥ 0 (Non-negative constraints)

x + 2y ≥ 10 (Vitamin B constraint)

2x + y ≥ 13 (Vitamin C constraint)

Objective function: Z = 60x + 80y (objective is to minimize cost)

Feasible region R unbounded as shown in the figure above.

Therefore, the minimum value of Z occurs at C(9,2) i.e. 700. So the person should mix 9 kg of food (F1) and 2 kg of food (F2) to obtain a minimum cost.

Transportation problems

In these kind of problems, we determine the transportation schedule in order to find the cheapest way of transporting the product from different plants located in different markets.

Example 3:

A jet fuel company has two X and Y depots with 7000 L and 4000 L capacities, respectively. The firm is distributing fuel to three jet fuel pumps, D, E and F, respectively in three cities containing 4500L, 3000L, and 3500L. In the following table, the distances (in km) between the depots and jet fuel pumps are given within the following desk:

If the transport cost of 10 litres of jet fuel is Re. 1 per km, how should the distribution be planned to mitigate the transport cost? What’s the lowest cost?

Solution 3:

Let X supply the fuel pumps, D and E with x and y litres of jet fuel.

So, (7000 − x − y) from X to fuel pump F will be delivered. At fuel pump D, the requirement is 4500 L.

The remaining (4500 − x) L will be transferred from fuel pump Y while L is transported from depot X.

Similarly, (3000 − y) L and 3500 − (7000 − x − y) = (x + y − 3500) L will be transported from depot Y to F fuel pump.

Subject to constraints:

x, y ≥ 0

7000 – x – y ≥ 0 (XF constraint)

4500 – x ≥ 0 (YD constraint)

3000 – y ≥ 0 (YE constraint)

x + y – 3500 ≥ 0 (YF constraint)

Cost of transporting 10 L of jet fuel is 1 rupee.

Objective function:

The feasible region can be drawn using the subject to constraints condition. The problem can be formulated as follows

Corner Point table:

The minimum value of Z is 4400 at E (500, 3000).

Thus, the jet fuel supplied from depot A is 500 L, 3000 L, and 3500 L and from depot B is 4000 L, 0 L, and 0 L to fuel pumps D, E, and F, respectively.

Therefore, the minimum transportation cost is Rs. 4400.

Example 4: Minimize

Solution:

Condition (i),

Condition (ii),

Total constraints = m + n.

Also Read,

Bayes Theorem of Probability

Truth Tables and Logical Statements

Daily-Linear Programming Problems – Video Lesson