Different Types of Linear Programming Problems

A few important linear programming problems are listed below:
1. Manufacturing problems.
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 cost problems.

📌 Problem 1 (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 USD50 per kg to purchase Food ‘I’ and USD70 per kg to purchase Food ‘II’. Formulate this problem as a linear programming problem to minimise the cost of such a mixture.
✍ Solution:
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:

Resources	Food		Requirements
	I	II
	(x)	(y)
Vitamin A (units/kg)	2	1	8
Vitamin C (units/kg)	1	2	10
Cost (USD/kg)	50	70

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 1. 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).

Corner Point	Z=50x+70y
(0, 8) (2, 4) (10, 0)	560 380 ← Minimum 500

[Fig 1]

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 … (÷10) 5x+7y<38
to check whether the resulting open half plane has any point common with the feasible region. From the Fig 1, 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 ‘H’ , and with this strategy, the minimum cost of the mixture will be USD380.

Problem 2 shows how a system of linear inequalities can arise in an applied problem.

📌 Problem 2: An Application of a System of Inequalities

The liquid portion of a diet is to provide at least 300 calories, 36 units of vitamin A, and 90 units of vitamin C daily. A cup of dietary drink X provides 60 calories, 12 units of vitamin A, and 10 units of vitamin C. A cup of dietary drink Y provides 60 calories, 6 units of vitamin A, and 30 units of vitamin C. Set up a system of linear inequalities that describes the minimum daily requirements for calories and vitamins.

✍ Solution:
Let

x=number of cups of dietary drink X and

y=number of cups of dietary drink Y.

To meet the minimum daily requirements, the inequalities listed below must be satisfied.
For calories: 60x+60y≥300
For vitamin A: 12x+6y≥36
For vitamin C: 10x+30y≥90

x≥0; y≥0

REMARK:
Any point inside the shaded region (or on its boundary) meets the minimum daily requirements for calories and vitamins. For example, 3 cups of dietary drink X and 2 cups of dietary drink Y supply 300 calories, 48 units of vitamin A, and 90 units of vitamin C.

The last two inequalities are included because x and y cannot be negative.
The graph of this system of linear inequalities is shown at the right.

📌 Problem 3: An Application: Optimal Cost
Problem 2 set up a system of linear equations for the problem below.
The liquid portion of a diet is to provide at least 300 calories, 36 units of vitamin A, and 90 units of vitamin C daily. A cup of dietary drink X provides 60 calories, 12 units of vitamin A, and 10 units of vitamin C. A cup of dietary drink Y provides 60 calories, 6 units of vitamin A, and 30 units of vitamin C. Now, assume that dietary drink X costs $0.12 per cup and drink Y costs $0.15 per cup. How many cups of each drink should be consumed each day to minimize the cost and still meet the daily requirements?
✍ Solution:
Begin by letting x be the number of cups of dietary drink X and y be the number of cups of dietary drink Y. Moreover, to meet the minimum daily requirements, the inequalities listed below must be satisfied.

For calories: 60x+60y≥300 For vitamin A: 12x+6y≥36) For vitamin C: 10x+30y≥90 x≥0 y≥0

}Constraints

The cost C is

C=0.12x+0.15y. [Objective function]

The graph of the region corresponding to the constraints is shown in Figure 2,

To determine the minimum cost, test C at each vertex of the region, as shown below.

At (0, 6): C=0.12(0)+0.15(6)=0.90

At (1, 4); C=0.12(1)+0.15(4)=0.72

At (3, 2); C=0.12(3)+0.15(2)=0.66 (Minimum value of C)

At (9, 0); C=0.12(9)+0.15(0)=1.08

So, the minimum cost is $0.66 per day, and this occurs when three cups of drink X and two cups of drink Y are consumed each day.

📌 Problem 4 (Diet problem).
A dietician has to develop a special diet using two foods P and Q. Each packet (containing 30 g) of food P contains 12 units of calcium, 4 units of iron, 6 units of cholesterol and 6 units of vitamin A. Each packet of the same quantity of food Q contains 3 units of calcium, 20 units of iron, 4 units of cholesterol and 3 units of vitamin A. The diet requires atleast 240 units of calcium, atleast 460 units of iron and at most 300 units of cholesterol. How many packets of each food should be used to minimise the amount of vitamin A in the diet? What is the minimum amount of vitamin A?
✍ Solution:
Let x and y be the number of packets of food P and Q respectively. Obviously x≥0, y≥0. Mathematical formulation of the given problem is as follows: Minimise Z=6x+3y (vitamin A)
subject to the constraints

12x+3y≥240 … (÷3) (constraint on calcium)
→4x+y≥80 … (1)
4x+20y≥460 … (÷4) (constraint on iron)
→x+5y≥115 … (2)
6x+4y≤300 … (÷2) (constraint on cholesterol)
→3x+2y≤150 … (3)
x≥0,y≥0 … (4)
Let us graph the inequalities (1) to (4).

The feasible region (shaded) determined by the constraints (1) to (4) is shown in Fig 3 and note that it is bounded.

[Fig 3]

The coordinates of the corner points L, M and N are (2, 72), (15, 20) and (40, 15) respectively. Let us evaluate Z at these points:

Corner Point	Z=6x+3y
(2, 72) (15, 20) (40, 15)	228 150 ← Minimum 285

From the table, we find that Z is minimum at the point (15, 20). Hence, the amount of vitamin A under the constraints given in the problem will be minimum, if 15 packets of food P and 20 packets of food Q are used in the special diet. The minimum amount of vitamin A will be 150 units.
Let you read post • Transportation Cost Problems.