`star` Different Types of Linear Programming Problems

A few important linear programming problems are listed below:

1. Manufacturing problems In these problems, we determine the number of units of different products which should be produced and sold by a firm when each product requires a fixed manpower, machine hours, labour hour per unit of product, warehouse space per unit of the output etc., in order to make maximum profit.

2. Diet problems In these problems, we determine the amount of different kinds of constituents/nutrients which should be included in a diet so as to minimise the cost of the desired diet such that it contains a certain minimum amount of each constituent/nutrients.

3. Transportation problems In these problems, we determine a transportation schedule in order to find the cheapest way of transporting a product from plants/factories situated at different locations to different markets.

1. Manufacturing problems In these problems, we determine the number of units of different products which should be produced and sold by a firm when each product requires a fixed manpower, machine hours, labour hour per unit of product, warehouse space per unit of the output etc., in order to make maximum profit.

2. Diet problems In these problems, we determine the amount of different kinds of constituents/nutrients which should be included in a diet so as to minimise the cost of the desired diet such that it contains a certain minimum amount of each constituent/nutrients.

3. Transportation problems In these problems, we determine a transportation schedule in order to find the cheapest way of transporting a product from plants/factories situated at different locations to different markets.

Q 3177180986

(Diet problem): A dietician wishes to mix two types of foods in such a

way that vitamin contents of the mixture contain atleast 8 units of vitamin A and 10

units of vitamin C. Food ‘I’ contains 2 units/kg of vitamin A and 1 unit/kg of vitamin C.

Food ‘II’ contains 1 unit/kg of vitamin A and 2 units/kg of vitamin C. It costs

Rs 50 per kg to purchase Food ‘I’ and Rs 70 per kg to purchase Food ‘II’. Formulate

this problem as a linear programming problem to minimise the cost of such a mixture.

Class 12 Chapter 12 Example 6

way that vitamin contents of the mixture contain atleast 8 units of vitamin A and 10

units of vitamin C. Food ‘I’ contains 2 units/kg of vitamin A and 1 unit/kg of vitamin C.

Food ‘II’ contains 1 unit/kg of vitamin A and 2 units/kg of vitamin C. It costs

Rs 50 per kg to purchase Food ‘I’ and Rs 70 per kg to purchase Food ‘II’. Formulate

this problem as a linear programming problem to minimise the cost of such a mixture.

Class 12 Chapter 12 Example 6

Let the mixture contain x kg of Food ‘I’ and y kg of Food ‘II’. Clearly, x ≥ 0,

y ≥ 0. We make the following table from the given data:

Since the mixture must contain at least 8 units of vitamin A and 10 units of

vitamin C, we have the constraints:

2x + y ≥ 8

x + 2y ≥ 10

Total cost Z of purchasing x kg of food ‘I’ and y kg of Food ‘II’ is

Z = 50x + 70y

Hence, the mathematical formulation of the problem is:

Minimise Z = 50x + 70y ... (1)

subject to the constraints:

2x + y ≥ 8 ... (2)

x + 2y ≥ 10 ... (3)

x, y ≥ 0 ... (4)

Let us graph the inequalities (2) to (4). The feasible region determined by the

system is shown in the Fig 12.7. Here again, observe that the feasible region is

unbounded.

Let us evaluate Z at the corner points A(0,8), B(2,4) and C(10,0).

In the table, we find that smallest value of Z is 380 at the point (2,4). Can we say

that the minimum value of Z is 380? Remember that the feasible region is unbounded.

Therefore, we have to draw the graph of the inequality

50x + 70y < 380 i.e., 5x + 7y < 38

to check whether the resulting open half plane has any point common with the feasible

region. From the Fig 12.7, we see that it has no points in common.

Thus, the minimum value of Z is 380 attained at the point (2, 4). Hence, the optimal

mixing strategy for the dietician would be to mix 2 kg of Food ‘I’ and 4 kg of Food ‘II’,

and with this strategy, the minimum cost of the mixture will be Rs 380.

Q 3107180988

(Allocation problem) A cooperative society of farmers has 50 hectare

of land to grow two crops X and Y. The profit from crops X and Y per hectare are

estimated as Rs 10,500 and Rs 9,000 respectively. To control weeds, a liquid herbicide

has to be used for crops X and Y at rates of 20 litres and 10 litres per hectare. Further,

no more than 800 litres of herbicide should be used in order to protect fish and wild life

using a pond which collects drainage from this land. How much land should be allocated

to each crop so as to maximise the total profit of the society?

Class 12 Chapter 12 Example 7

of land to grow two crops X and Y. The profit from crops X and Y per hectare are

estimated as Rs 10,500 and Rs 9,000 respectively. To control weeds, a liquid herbicide

has to be used for crops X and Y at rates of 20 litres and 10 litres per hectare. Further,

no more than 800 litres of herbicide should be used in order to protect fish and wild life

using a pond which collects drainage from this land. How much land should be allocated

to each crop so as to maximise the total profit of the society?

Class 12 Chapter 12 Example 7

Let x hectare of land be allocated to crop X and y hectare to crop Y. Obviously,

x ≥ 0, y ≥ 0.

Profit per hectare on crop X = Rs 10500

Profit per hectare on crop Y = Rs 9000

Therefore, total profit = Rs (10500x + 9000y)

The mathematical formulation of the problem is as follows:

Maximise Z = 10500 x + 9000 y

subject to the constraints:

x + y ≤ 50 (constraint related to land) ... (1)

20x + 10y ≤ 800 (constraint related to use of herbicide)

i.e. 2x + y ≤ 80 ... (2)

x ≥ 0, y ≥ 0 (non negative constraint) ... (3)

Let us draw the graph of the system of inequalities (1) to (3). The feasible region

OABC is shown (shaded) in the Fig 12.8. Observe that the feasible region is bounded.

The coordinates of the corner points O, A, B and C are (0, 0), (40, 0), (30, 20) and

(0, 50) respectively. Let us evaluate the objective function Z = 10500 x + 9000y at

these vertices to find which one gives the maximum profit.

Hence, the society will get the maximum profit of Rs 4,95,000 by allocating 30

hectares for crop X and 20 hectares for crop Y.

Q 3117191080

(Manufacturing problem) A manufacturing company makes two models

A and B of a product. Each piece of Model A requires 9 labour hours for fabricating

and 1 labour hour for finishing. Each piece of Model B requires 12 labour hours for

fabricating and 3 labour hours for finishing. For fabricating and finishing, the maximum

labour hours available are 180 and 30 respectively. The company makes a profit of

Rs 8000 on each piece of model A and Rs 12000 on each piece of Model B. How many

pieces of Model A and Model B should be manufactured per week to realise a maximum

profit? What is the maximum profit per week?

Class 12 Chapter 12 Example 8

A and B of a product. Each piece of Model A requires 9 labour hours for fabricating

and 1 labour hour for finishing. Each piece of Model B requires 12 labour hours for

fabricating and 3 labour hours for finishing. For fabricating and finishing, the maximum

labour hours available are 180 and 30 respectively. The company makes a profit of

Rs 8000 on each piece of model A and Rs 12000 on each piece of Model B. How many

pieces of Model A and Model B should be manufactured per week to realise a maximum

profit? What is the maximum profit per week?

Class 12 Chapter 12 Example 8

Suppose x is the number of pieces of Model A and y is the number of pieces

of Model B. Then

Total profit (in Rs) = 8000 x + 12000 y

Let Z = 8000 x + 12000 y

We now have the following mathematical model for the given problem.

Maximise Z = 8000 x + 12000 y ... (1)

subject to the constraints:

9x + 12y ≤ 180 (Fabricating constraint)

i.e. 3x + 4y ≤ 60 ... (2)

x + 3y ≤ 30 (Finishing constraint) ... (3)

x ≥ 0, y ≥ 0 (non-negative constraint) ... (4)

The feasible region (shaded) OABC determined by the linear inequalities (2) to (4)

is shown in the Fig 12.9. Note that the feasible region is bounded.

Let us evaluate the objective function Z at each corner point as shown below:

We find that maximum value of Z is 1,68,000 at B (12, 6). Hence, the company

should produce 12 pieces of Model A and 6 pieces of Model B to realise maximum

profit and maximum profit then will be Rs 1,68,000.