Formulation of Linear Programming Problem
In this article, we will discuss about how to formulate a linear programming problem.
Problem formulation is the most important step in the operations research.
In order to formulate the word problem as a linear programming problem follow the following steps:
Step 1
Read and understand the word problem thoroughly.
Step 2
Identify the decision variables.
Step 3
Describe the objective function and write it in the form of linear equation in the decision variables.
Step 4
Describe each constraints.
Step 5
Write down the non-negativity constraints.
Step 6
Write down the entire problem.
Formulation of LPP Example 1
A firm manufactures two types of products A and B and sells them at a profit of Rs.2 on type A and Rs.3 on type B. Each product is processed on two machines G and H. Type A requires one minute of processing time on G and 2 minutes on H, type B requires 2 minute on G and 2 minute on H. The machine G is available for not more than 8 hours and 20 minutes while machine H is available for 800 minutes during one working day. Formulate the problem as a linear programming problem.
Solution
Let $x_1$ units of type A product be manufactured and $x_2$ units of type B product be manufactured.
Given information can be summarized in the following table:
| Machine / Product | Type A | Type B | Availability |
|---|---|---|---|
| Machine G | 1 | 2 | 500 min |
| Machine H | 2 | 2 | 800 min |
| Profit (In Rs.) | 2 | 3 |
Profit on one unit of type A product is Rs. 2, so the profit for $x_1$ units of type A product will be $2x_1$.
Profit on one unit of type B product is Rs. 3, so the profit for $x_2$ units of type B product ill be $3x_2$.
The total profit on $x_1$ units of type A product and $x_2$ units of type B product will be Rs. $2x_1+3x_2$. Thus the objective function is
$$\max z = 2x_1 +3x_2$$
Type A product require one minute of processing time on machine G and type B product require 2 minutes of processing time on machine G. Thus the total time required for $x_1$ units of type A product and $x_2$ units of type B product will be $x_1+2x_2$. But machine G is available for not more than 8 hours and 20 minutes (i.e. 500 minutes). Thus the constraint is
$$x_1+2x_2\leq 500.$$
Type A product require 2 minute of processing time on machine H and type B product require 2 minutes of processing time on machine H. Thus the total time required for $x_1$ units of type A product and $x_2$ units of type B product will be $2x_1+2x_2$. But machine H is available for 800 minutes. Thus the constraint is
$$2x_1+2x_2\leq 800.$$
Since it is not possible to manufacture any product in negative quantity, we have $x_1,x_2\geq 0$.
Thus the complete formulated linear programming problem is
$$ \begin{eqnarray*} \max\; z= 2x_1 +3x_2 & & \\ \mbox{s.t. } x_1+ 2x_2&\leq & 500 \\ 2x_1+2x_2 &\leq &800 \\ \mbox{and }x_1 , x_2 & \geq & 0 \end{eqnarray*} $$
Formulation of LPP Example 2
A person requires at least 12 and 18 units of chemicals A and B respectively for his garden. A liquid product contains 2 and 4 units of A and B respectively per jar. A dry Product contains 4 and 2 units of A and B per carton. If the liquid product sells for Rs.4 per jar and the dry product sells for Rs.3 per carton, how many of each should be purchased, in order to minimize the cost and meet his requirements? Formulate this problem as LPP.
Solution
Let $x_1$ jars of liquid products and $x_2$ cartoons of dry product be purchased.
Given information can be summarized in the following table:
| Chemical / Product | Jars of Liquid Product | Cartoons of Dry Product | Requirement |
|---|---|---|---|
| Chemical A | 2 | 4 | 12 units |
| Chemical B | 4 | 2 | 18 units |
| Cost (In Rs.) | 4 | 3 |
The cost of liquid product is Rs. 4 per jar and the cost of dry product is Rs. 3 per cartoon. So to purchase $x_1$ jars of liquid product the cost will be Rs. $4x_1$ and to purchase $x_2$ cartoons the cost will be Rs. $3x_2$. Since the objective is to minimize the total cost, the objective function will be
$$\min z = 4x_1 + 3x_2.$$
The liquid product contains 2 units of chemical A per jar and dry product contains 4 units of chemical A per cartoon. The requirement of chemical A is at least 12. Thus the constraint for chemical A will be
$$2x_1+4x_2\geq 12.$$
Similarly, the liquid product contains 4 units of chemical B per jar and dry product contains 2 units of chemical B per cartoon. The requirement of chemical B is at least 18 units. Thus the constraint for chemical B will be
$$4x_1+2x_2\geq 18.$$
Since the number of jars and number of cartoons to be purchase can not be negative, we have $x_1,x_2\geq 0$.
Thus the complete formulated linear programming problem is
$$ \begin{eqnarray*} \min\; z= 4x_1 +3x_2 & & \\ \mbox{s.t. } 2x_1+ 4x_2&\geq & 12 \\ 4x_1+2x_2 &\geq &18 \\ \mbox{and }x_1 , x_2 & \geq & 0 \end{eqnarray*} $$
Formulation of LPP Example 3
An Air Force is experimenting with three types of bombs P, Q, and R in which three kinds of explosives, A, B and C will be used. Taking the various factors into consideration, it has been decided to use at most 600 Kg of explosive A, at least 480 Kg of explosive B and exactly 540 Kg of explosive C. Bomb P requires 3, 2, 2 Kg of A, B and C respectively. Bomb Q requires 4, 3, 2 Kg of A, B and C, and Bomb R requires 6, 2, 3 Kg of A, B and C respectively. Now bomb P will give the equivalent of a 2 ton explosion, bomb Q will give a 3 ton explosion and bomb R will give a 4 ton explosion. Under what schedule can the Air Force make the biggest bomb. Formulate as LPP.
Solution
Let $x_1$, $x_2$ and $x_3$ be the number of bombs made of type P, Q and R respectively.
Given information can be summarized in the following table:
| Explosive / Bomb Type | Type P | Type Q | Type R | Available/ Required |
|---|---|---|---|---|
| A | 3 | 1 | 4 | maximum 600 Kg |
| B | 2 | 4 | 2 | minimum 480 Kg |
| C | 2 | 3 | 3 | exactly 540 Kg |
| Explosion | 2 | 3 | 4 |
Bomb P gives a 2 ton explosion, bomb Q gives 3 ton explosion, and bomb R gives 4 ton explosion. This has to be maximized. This the objective function can be written as
$$\max z = 2x_1 +3x_2 + 4x_3$$
Bomb P requires: 3 kg A, 2 kg B, 2 kg C;
Bomb Q requires: 1 kg A, 4 kg B, 3 kg C;
Bomb R requires: 4 kg A, 2 kg B, 3 kg C
Explosives available:
Maximum 600 kg of explosive A is available.
Minimum 480 kg of explosive B is available and
Exactly 540 kg of explosive C is available.
Constraints:
Explosive A: $3x_1 + 1x_2 + 4x_3 \leq 600$
Explosive B: $2x_1 + 4x_2 + 2x_3 \geq 480$
Explosive C: $2x_1 + 3x_2 + 3x_3 = 540$.
It is not possible to produce number of bombs in negative quantity, we have $x_1 , x_2, x_3 \geq 0$.
Thus the complete formulated linear programming problem is
$$ \begin{eqnarray*} \max\; z= 2x_1 +3x_2 + 4x_3 & & \\ \mbox{s.t. } 3x_1+ 1x_2 + 4x_3&\leq & 600 \\ 2x_1+4x_2 +2x_3&\geq & 480 \\ 2x_1+3x_2 +3x_3& = & 540 \\ \mbox{and }x_1 , x_2, x_3 & \geq & 0 \end{eqnarray*} $$
Formulation of LPP Example 4
A company produces two products that are produced on 2 assembly lines. Assembly line 1 has 100 available hours and assembly line 2 has 42 available hours. Each product requires 10 hours of processing time on line one, while on line 2, product 1 requires 7 hours and product 2 requires 3 hours. The profit of product 1 is \$6 per unit, and the profit for product 2 is \$4 per unit.
Formulate a linear programming model for this problem.
Solution
Let the company produces $x_1$ and $x_2$ units of First type product and second type of product respectively.
Given information can be summarized in the following table:
| Assembly \Product | First Type Product | Second Type Product | Availability |
|---|---|---|---|
| Assembly Line 1 | 10 hours | 10 hours | 100 hours |
| Assembly Line 2 | 7 hours | 3 hours | 42 hours |
| Profit per unit | \$6 | $4 |
Profit per unit for first type product is \$6, so for $x_1$ units of first type product the profit will be \$ $6x_1$.
Profit per unit for second type product is \$4, so for $x_2$ units of second type product will be \$4 $x_2$.
So the total profit will be \$ $(6x_1 + 4x_2)$. The objective of the company is to maximize the profit. Hence the objective function is
$$Max Z = 6x_1 + 4x_2$$
First type product requires 10 hours on assembly line 1 and second type of product require 10 hours on assembly line 1. So for $x_1$ units of first type product and $x_2$ units of second type product requires $10x_1 + 10x_2$ hours on assembly line 1. But assembly line 1 is available for 100 hours only. Hence the constraint for first assembly line is
$$10x_1 + 10x_2 \leq 100$$
First type product requires 7 hours on assembly line 2 and second type of product require 3 hours on assembly line 2. So for $x_1$ units of first type product and $x_2$ units of second type product requires $7x_1 + 4x_2$ hours on assembly line 2. But assembly line 2 is available for 42 hours only. Hence the constraint for assembly line 2 is
$$7x_1 + 4x_2 \leq 42$$
It is not possible to produce any product in negative quantity, hence we have $x_1 \geq 0$ and $x_2 \geq 0$.
Hence the complete formulated Linear Programming Model is
$$ \begin{eqnarray*} Max\; z= 6x_1 +4x_2 & & \\ \mbox{s.t. } 10x_1+10x_2&\leq& 100 \\ 7x_1 +4x_2 &\leq & 42 \\ \mbox{and }x_1 , x_2 & \geq & 0 \end{eqnarray*} $$
Endnote
In this tutorial you learn about formulation of linear programming problem with some examples on formulation.
To learn more about linear programming problem, please refer to the following tutorials:
Let me know in the comments if you have any questions on standard form of linear programming problem and your thoughts on this article.
