QT/U3 Topic 3 Formulation of Linear Programming
Let’s understand the maximization case with the help of a problem. Suppose a firm produces two products A and B. For producing the each unit of product A, 4 Kg of Raw material and 6 labor hours are required. While, for the production of each unit of product B, 4 kg of raw material and 5 labor hours is required. The total availability of raw material and labor hours is 60 Kg and 90 Hours respectively (per week). The unit price of Product A is Rs 35 and of product, B is Rs 40.
This problem can be converted into linear programming problem to determine how many units of each product should be produced per week to have the maximum profit. Firstly, the objective function is to be formulated. Suppose x1 and x2 are units produced per week of product A and B respectively. The sale of product A and product B yields Rs 35 and Rs 40 respectively. The total profit will be equal to
Z = 35×1+ 40×2 (objective function)
Since the raw material and labor is in limited supply the mathematical relationship that explains this limitation is called inequality. Therefore, the inequality equations will be as follows:
Product A requires 4 kg of raw material and product B also requires 4 Kg of Raw material; thus, total consumption is 4×1+4×2, which cannot exceed the total availability of 60 kg. Thus, this constraint can be expressed as:
4×1 + 4×2 ≤ 60
Similarly, the second constraint equation will be:
6×1 + 5×2 ≤ 90
Where 6 hours and 5hours of labor is required for the production of each unit of product A and B respectively, but cannot exceed the total availability of 90 hours.
Thus, the linear programming problem will be:
Maximize Z = 35×1+ 40×2 (profit)
4×1 + 4×2 ≤ 60 (raw material constraint)
6×1 + 5×2 ≤ 90 (labor hours constraint)
x1, x2 ≥ 0 (Non-negativity restriction)
Note: It is to be noted that “≤” (less than equal to) sign is used as the profit maximizing output may not fully utilize all the resources, and some may be left unused. And the non-negativity condition is used since the x1 and x2 are a number of units produced and cannot have negative values.
The minimization case can be well understood through a problem. Let’s say; the agricultural research institute recommended a farmer to spread out at least 5000 kg of phosphate fertilizer and not less than 7000 kg of nitrogen fertilizer to raise the productivity of his crops on the farm. There are two mixtures A and B, weighs 100 kg each, from which these fertilizers can be obtained.
The cost of each Mixture A and B is Rs 40 and 25 respectively. Mixture A contains 40 kg of phosphate and 60 kg of nitrogen while the Mixture B contains 60 kg of phosphate and 40 kg of nitrogen. This problem can be represented as a linear programming problem to find out how many bags of each type a farmer should buy to get the desired amount of fertilizers at the minimum cost.
Firstly, the objective function is to be formulated. Suppose, x1 and x2are the number of bags of mixture A and mixture B. The cost of both the mixture is 40×1 + 25×2 and thus, the objective function will be:
Z = 40×1+25×2
In this problem, there are two constraints, minimum 5000 kg of phosphate and minimum 7000 kg of nitrogen is required. The Bag A contains 40 kg of phosphate while Bag B contains 60 kg of phosphate. Thus, the phosphate constraint can be expressed as:
40×1 + 60×2 ≥ 5000
Similarly, the second constraint equation can be expressed as:
60×1 + 40×2 ≥ 7000
Where, Bag A contains 60 kg of nitrogen and Bag B contains 40 kg of nitrogen, and The minimum requirement of nitrogen is 7000 kg.
Thus, the linear programming problem is:
Minimize Z = 40×1+25×2 (cost)
40×1 + 60×2 ≥ 5000 (Phosphate Constraint)
60×1 + 40×2 ≥ 7000 (Nitrogen Constraint)
x1, x2 ≥ 0 (Non-negativity Restriction)
Note: It is to be noted that, “≥” (greater than equal to) sign shows the full utilization of resources at the minimum cost. The non-negativity condition is used, since x1 and x2 represent the number of bags of both the mixture and hence cannot have the negative values.