Linear Programming Problem (LPP)
- What is LPP?
Linear Programming Problem (LPP) is a mathematical technique used to achieve the best possible
outcome in a given situation, often involving maximization of profits or minimization of costs.
Think about running a business—what is the main goal? The primary objective is usually profit
maximization or cost minimization.
For example, a company might want to maximize its profit or minimize its costs given a set of limitations or resources. In LPP, the objective function is the formula that represents this goal. - Objective Function:
In LPP, we typically encounter two types of problems:
- Maximization: An objective function might look like Z = x + 2y, where the goal is to maximize Z (profit, output, etc.).
- Minimization: Another example could be Z = 2x + 3y, where the objective is to minimize Z (cost, time, etc.).
- Constraints:
Every business operates under certain limitations, such as limited resources like manpower, money,
time, land, or raw materials. These limitations are known as **constraints** in LPP.
Constraints are represented as inequalities because they indicate the limits within which the decision variables must operate. For example:
2x + 3y ≥ 5 (resource must be more than or equal to 5)
x + y ≤ 7 (resource must be less than or equal to 7) - Non-negativity Restriction:
In most real-world scenarios, the decision variables (like products, resources, etc.) cannot be
negative. Therefore, in LPP, we assume:
x ≥ 0, y ≥ 0
This condition ensures that the solution is realistic and practical. - Summary of LPP Components:
In summary, a Linear Programming Problem consists of two main components:
- Objective Function: This is the function you aim to maximize or minimize (profit, cost, time, etc.).
- Constraints: These are the limitations or restrictions on the resources available, usually in the form of inequalities.
Graphical Method to Solve LPP
Problem Statement:
Maximize Z = 3x1 + 4x2
Subject to the constraints:
x1 + 2x2 ≤ 4
3x1 + 2x2 ≤ 6
x1, x2 ≥ 0 (Non-negativity constraint)
- Step 1: Plot the constraints on a graph
We start by finding the points where the constraints intersect the axes, as these points will help us plot the lines representing the constraints.
For the constraint x1 + 2x2 ≤ 4:
To find the points where the line intersects the x1 and x2 axes:- If x2 = 0, then x1 = 4, giving the point (4, 0).
- If x1 = 0, then x2 = 2, giving the point (0, 2).
- If x2 = 0, then x1 = 2, giving the point (2, 0).
- If x1 = 0, then x2 = 3, giving the point (0, 3).
- Step 2: Draw the lines and identify the feasible region
We now plot the lines x1 + 2x2 = 4 and 3x1 + 2x2 = 6 on a graph using the points found earlier.
The feasible region is the area where both constraints overlap, and it represents the possible values of x1 and x2 that satisfy all constraints.
Since both constraints have ≤, the feasible region will be the area below both lines, towards the origin (0, 0).
- Step 3: Identify the corner points of the feasible region
The optimal solution of an LPP in the graphical method will always lie at one of the corner points (vertices) of the feasible region.
The corner points in this example are:- O: (0, 0) – the origin
- A: (2, 0) – where 3x1 + 2x2 = 6 intersects the x1-axis
- C: (0, 2) – where x1 + 2x2 = 4 intersects the x2-axis
- B: The intersection of the two constraints
x1 + 2x2 = 4 and
3x1 + 2x2 = 6. To find B, we solve both
equations
simultaneously:
Solve the system:
x1 + 2x2 = 4
3x1 + 2x2 = 6
Subtract the first equation from the second:
(3x1 + 2x2) - (x1 + 2x2) = 6 - 4
This simplifies to:
2x1 = 2, so x1 = 1.
Substitute x1 = 1 into x1 + 2x2 = 4:
1 + 2x2 = 4, so x2 = 3/2.
The intersection point B is (1, 3/2).
- Step 4: Evaluate the objective function at each corner point
Now, we substitute the coordinates of each corner point into the objective function Z = 3x1 + 4x2 to find the value of Z at each point:- At O: Z = 3(0) + 4(0) = 0
- At A: Z = 3(2) + 4(0) = 6
- At B: Z = 3(1) + 4(3/2) = 3 + 6 = 9
- At C: Z = 3(0) + 4(2) = 8
- Step 5: Determine the optimal solution
Since the problem is a maximization problem, the optimal solution will be the point that gives the maximum value of Z.
From the calculations, we see that the maximum value of Z is 9, which occurs at point B (1, 3/2).
Thus, the optimal solution is:- x1 = 1
- x2 = 3/2
- Step 6: Minimization (if required)
If we were tasked with minimizing Z instead of maximizing it, the minimum value would occur at the origin O (0, 0), where Z = 0.
Graphical Method to Solve LPP (Minimization Problem)
Problem Statement:
Minimize Z = 3x1 + 4x2
Subject to the constraints:
x1 + 2x2 ≥ 4
3x1 + 2x2 ≥ 6
x1, x2 ≥ 0 (Non-negativity constraint)
- Step 1: Plot the constraints on a graph
Since the constraints have “≥” signs, the feasible region will be away from the origin.
To plot the constraints, we first find the points where the lines intersect the axes.
For the constraint x1 + 2x2 ≥ 4:- If x2 = 0, then x1 = 4, giving the point (4, 0).
- If x1 = 0, then x2 = 2, giving the point (0, 2).
For the constraint 3x1 + 2x2 ≥ 6:- If x2 = 0, then x1 = 2, giving the point (2, 0).
- If x1 = 0, then x2 = 3, giving the point (0, 3).
- Step 2: Draw the lines and identify the feasible region
We now plot the lines x1 + 2x2 = 4 and 3x1 + 2x2 = 6 using the points found earlier.
The feasible region in this case will be above both lines (away from the origin), as the constraints are in the form of “≥”.
The common area between the two constraints will give us the feasible region where both constraints are satisfied.
- Step 3: Identify the corner points of the feasible region
Just like in the maximization case, the optimal solution for a minimization problem also lies at one of the corner points (vertices) of the feasible region.
The corner points of the feasible region are:- P: (4, 0) – where x1 + 2x2 = 4 intersects the x1-axis
- Q: (0, 3) – where 3x1 + 2x2 = 6 intersects the x2-axis
- R: The intersection of the two constraints. To find this point, we
solve both equations simultaneously:
Solve the system:
x1 + 2x2 = 4
3x1 + 2x2 = 6
Subtract the first equation from the second:
(3x1 + 2x2) - (x1 + 2x2) = 6 - 4
This simplifies to:
2x1 = 2, so x1 = 1.
Substitute x1 = 1 into x1 + 2x2 = 4:
1 + 2x2 = 4, so x2 = 3/2.
The intersection point R is (1, 3/2).
- Step 4: Evaluate the objective function at each corner point
Now we substitute the coordinates of each corner point into the objective function Z = 3x1 + 4x2 to find the value of Z at each point:- At P: Z = 3(4) + 4(0) = 12
- At Q: Z = 3(0) + 4(3) = 12
- At R: Z = 3(1) + 4(3/2) = 3 + 6 = 9
- Step 5: Determine the optimal solution
Since the problem is a minimization problem, the optimal solution will be the point that gives the minimum value of Z.
From the calculations, we see that the minimum value of Z is 9, which occurs at point R (1, 3/2).
Thus, the optimal solution is:- x1 = 1
- x2 = 3/2
- Note: Unbounded Solution (if the question was for maximization)
If this problem were a maximization problem, the solution would be unbounded.
This is because, as we move away from the origin in the feasible region, the value of Z increases indefinitely.
Thus, there is no maximum value for Z, and we say the solution is unbounded.
Alternative solutions
Problem Statement:
Maximize Z = 3x1 + 2x2
Subject to the constraints:
x1 + 2x2 ≤ 4
3x1 + 2x2 ≤ 6
x1, x2 ≥ 0 (Non-negativity constraint)
- Step 1: Plot the constraints on a graph
We start by finding the points where the constraints intersect the axes, which will help us plot the lines representing the constraints. For the constraint x1 + 2x2 ≤ 4:
To find the points where the line intersects the x1 and x2 axes:- If x2 = 0, then x1 = 4, giving the point (4, 0).
- If x1 = 0, then x2 = 2, giving the point (0, 2).
For the constraint 3x1 + 2x2 ≤ 6:- If x2 = 0, then x1 = 2, giving the point (2, 0).
- If x1 = 0, then x2 = 3, giving the point (0, 3).
- Step 2: Draw the lines and identify the feasible region
We now plot the lines x1 + 2x2 = 4 and 3x1 + 2x2 = 6 on a graph using the points found earlier.
The feasible region is the area where both constraints overlap, representing the possible values of x1 and x2 that satisfy all constraints.
Since both constraints have ≤, the feasible region will be the area below both lines, towards the origin (0, 0).
- Step 3: Identify the corner points of the feasible region
The optimal solution of an LPP in the graphical method will always lie at one of the corner points (vertices) of the feasible region.
The corner points in this example are:- O: (0, 0) – the origin
- A: (2, 0) – where 3x1 + 2x2 = 6 intersects the x1-axis
- C: (0, 2) – where x1 + 2x2 = 4 intersects the x2-axis
- B: The intersection of the two constraints
x1 + 2x2 = 4 and
3x1 + 2x2 = 6. To find B, we solve both
equations
simultaneously:
Solve the system:
x1 + 2x2 = 4
3x1 + 2x2 = 6
Subtract the first equation from the second:
(3x1 + 2x2) - (x1 + 2x2) = 6 - 4
This simplifies to:
2x1 = 2, so x1 = 1.
Substitute x1 = 1 into x1 + 2x2 = 4:
1 + 2x2 = 4, so x2 = 3/2.
The intersection point B is (1, 3/2).
- Step 4: Evaluate the objective function at each corner point
Now, we substitute the coordinates of each corner point into the objective function Z = 3x1 + 2x2 to find the value of Z at each point:- At O: Z = 3(0) + 2(0) = 0
- At A: Z = 3(2) + 2(0) = 6
- At B: Z = 3(1) + 2(3/2) = 3 + 3 = 6
- At C: Z = 3(0) + 2(2) = 4
- Step 5: Determine the optimal solution
In this case, we have two points (A and B) that give the same maximum value of Z:- A (2, 0): Z = 6
- B (1, 3/2): Z = 6
- Step 6: Discuss the type of solution
Since both points A and B yield the same maximum value for Z (which is 6), we can conclude that:- This problem has alternative solutions, as there are multiple combinations of x1 and x2 that maximize the objective function.
- Moreover, if we extend the feasible region further, we may find that there are infinite solutions along the line segment connecting points A and B. Hence, the solution can also be described as having infinite optimal solutions.
Graphical Method to Solve LPP (No Solution Case)
Problem Statement:
Maximize Z = 6x1 + 4x2
Subject to the constraints:
2x1 + 4x2 ≤ 4
4x1 + 8x2 ≥ 16
x1, x2 ≥ 0 (Non-negativity constraint)
- Step 1: Plot the constraints on a graph
We start by finding the points where the constraints intersect the axes.
For the constraint 2x1 + 4x2 ≤ 4:
To find the points where the line intersects the x1 and x2 axes:- If x2 = 0, then 2x1 = 4, giving the point (2, 0).
- If x1 = 0, then 4x2 = 4, giving the point (0, 1).
To find the points where the line intersects the axes:- If x2 = 0, then 4x1 = 16, giving the point (4, 0).
- If x1 = 0, then 8x2 = 16, giving the point (0, 2).
- Step 2: Draw the lines and identify the feasible region
We now plot the lines 2x1 + 4x2 = 4 and 4x1 + 8x2 = 16 on a graph using the points found earlier.
The feasible region for the first constraint is the area below the line, while for the second constraint, it is the area above the line.
Since one constraint is ≤ and the other is ≥, we are looking for an intersection of these two regions.
- Step 3: Analyze the feasible region
Upon examining the plotted constraints, we see that there is no overlap between the feasible regions defined by the two constraints.
Thus, there is no common area where both conditions are satisfied simultaneously. This indicates that:- The problem has no feasible solution.
- The constraints are contradictory, as one requires values below a certain level while the other requires values above a certain level.
- Step 4: Conclusion
In this case, since there is no feasible region where all constraints are satisfied, the linear programming problem does not have a solution.
It illustrates the importance of properly formulating constraints to ensure they can coexist without conflict in optimization problems.
Simplex Method to Solve LPP
Maximize Z = 5x1 + 3x2
Subject to the constraints:
3x1 + 5x2 ≤ 15
5x1 + 2x2 ≤ 10
x1, x2 ≥ 0
- To solve an LPP using the Simplex Method, we must ensure that the objective function is in maximization form. If it is a minimization problem, we first convert it to a maximization problem.
- Next, we need to balance the constraints. For constraints with ≤ signs, we add slack variables to convert inequalities into equalities. For example, if we have a ≤ constraint, we add a slack variable. Similarly, if we have a ≥ constraint, we subtract a surplus variable to achieve equality.
- Now, converting the given problem:
Maximize Z = 5x1 + 3x2 + 0x3 + 0x4 (introducing slack variables x3 and x4)
Subject to:
3x1 + 5x2 + x3 = 15
5x1 + 2x2 + x4 = 10
All variables x1, x2, x3, x4 ≥ 0 - The variables x3 and x4 are known as the basic variables, as they form the identity matrix in the system of equations. The basic variables usually include the slack variables we introduced. The objective now is to make the decision variables (x1, x2) the basic variables through iterations.
- We now create the initial Simplex tableau as follows:
| Cj | 5 | 3 | 0 | 0 | CB | Xb | b | x1 | x2 | x3 | x4 | ---------------------------------------------- 0 | x3 | 15 | 3 | 5 | 1 | 0 | 0 | x4 | 10 | 5 | 2 | 0 | 1 |- CB represents the cost of the basic variables in the objective function (initially zero for slack variables).
- Xb represents the basic variables.
- Cj represents the cost coefficients of the decision variables x1, x2, and slack variables x3, x4 in the objective function.
- Next, we perform the Simplex iteration. We want to bring x1 and x2 into the basis:
| Cj | 5 | 3 | 0 | 0 | CB | Xb | b | x1 | x2 | x3 | x4 | ---------------------------------------------- 0 | x3 | 15 | 3 | 5 | 1 | 0 | (Row 1) 0 | x4 | 10 | 5 | 2 | 0 | 1 | (Row 2) ---------------------------------------------- Zj | | 0 | 0 | 0 | 0 | Cj | | 5 | 3 | 0 | 0 | Zj - Cj | | -5 | -3 | 0 | 0 || Cj | 5 | 3 | 0 | 0 | CB | Xb | b | x1 | x2 | x3 | x4 | min ratio -------------------------------------------------------- 0 | x3 | 15 | 3 | 5 | 1 | 0 | 15/3 = 5 0 | x4 | 10 | 5 | 2 | 0 | 1 | 10/5 = 2 → smallest ratio - Now, we pivot on the key element (5 in the x1 column, row 2). After performing row
operations, the updated tableau looks like this:
| Cj | 5 | 3 | 0 | 0 | CB | Xb | b | x1 | x2 | x3 | x4 | ---------------------------------------------- 0 | x3 | 9 | 0 | 19/5 | 1 | -3/5 | (Row 1) 5 | x1 | 2 | 1 | 2/5 | 0 | 1/5 | (Row 2) ---------------------------------------------- - Next, we compute Zj - Cj again:
| Cj | 5 | 3 | 0 | 0 | CB | Xb | b | x1 | x2 | x3 | x4 | min ratio -------------------------------------------------------- 0 | x3 | 9 | 0 | 19/5 | 1 | -3/5 | 45/19 → smallest ratio 5 | x1 | 2 | 1 | 2/5 | 0 | 1/5 | 10/2 -------------------------------------------------------- Zj | | 5 | 2 | 0 | 1 | Cj | | 5 | 3 | 0 | 0 | Zj - Cj | | 0 | -1 | 0 | 1 | - After performing the row operations, the final tableau is:
| Cj | 5 | 3 | 0 | 0 | CB | Xb | b | x1 | x2 | x3 | x4 | -------------------------------------------------------- 3 | x2 | 45/19 | 0 | 1 | 5/19 |-3/19 | (Row 1) new 5 | x1 | 20/19 | 1 | 0 | -2/19 | 5/19 | (Row 2) -------------------------------------------------------- Zj | | 5 | 3 | 5/19 | 16/19 Cj | | 5 | 3 | 0 | 0 Zj - Cj | | 0 | 0 | 5/19 | 16/19 - Finally, the optimal solution is:
x1 = 20/19, x2 = 45/19
Optimal value of Z = 5(20/19) + 3(45/19) = 225/19 ≈ 11.84
Maximize Z = 3x1 + 2x2 + 5x3
Subject to the constraints:
x1 + x2 + x3 ≤ 9
2x1 + 3x2 + 5x3 ≤ 30
2x1 - x2 - x3 ≤ 8
xi ≥ 0
- Convert the constraints by adding slack variables:
Maximize Z = 3x1 + 2x2 + 5x3 + 0x4 + 0x5 + 0x6
Subject to:
x1 + x2 + x3 + x4 = 9
2x1 + 3x2 + 5x3 + x5 = 30
2x1 - x2 - x3 + x6 = 8
xi ≥ 0 - Create the initial Simplex tableau:
| Cj | 3 | 2 | 5 | 0 | 0 | 0 | CB | Xb | b | x1 | x2 | x3 | x4 | x5 | x6 | ---------------------------------------------- 0 | x4 | 9 | 1 | 1 | 1 | 1 | 0 | 0 | (Row 1) 0 | x5 | 30 | 2 | 3 | 5 | 0 | 1 | 0 | (Row 2) 0 | x6 | 8 | 2 | -1 | -1 | 0 | 0 | 1 | (Row 3) - Perform the Simplex iteration by identifying the entering and exiting variables:
| Cj | 3 | 2 | 5 | 0 | 0 | 0 | CB | Xb | b | x1 | x2 | x3 | x4 | x5 | x6 | ---------------------------------------------- 0 | x4 | 9 | 1 | 1 | 1 | 1 | 0 | 0 | (Row 1) 0 | x5 | 30 | 2 | 3 | 5 | 0 | 1 | 0 | (Row 2) 0 | x6 | 8 | 2 | -1 | -1 | 0 | 0 | 1 | (Row 3) ---------------------------------------------- Zj | | 0 | 0 | 0 | 0 | 0 | 0 | Cj | | 3 | 2 | 5 | 0 | 0 | 0 | Zj - Cj | | -3 | -2 | -5 | 0 | 0 | 0 |
Row 1: 9/1 = 9
Row 2: 30/5 = 6 (smallest ratio)
Row 3: 8/-1 (ignored because it’s negative)
Thus, x5 exits, and x3 replaces x5 in the basis. - Perform the pivot on the key element (5 in Row 2, x3 column), and update the tableau:
for row 2 we are dividing it by 5
for row 1 we are doing row 1 - row 2 (new)
for row 3 we are doing row 3 + row 2 (new)| Cj | 3 | 2 | 5 | 0 | 0 | 0 | CB | Xb | b | x1 | x2 | x3 | x4 | x5 | x6 | ------------------------------------------------------------------- 0 | x4 | 3 | 3/5| 2/5| 0 | 1 | -1/5| 0 | (Row 1) 5 | x3 | 6 | 2/5| 3/5| 1 | 0 | 1/5| 0 | (Row 2) 0 | x6 | 14 | 12/5| -2/5| 0 | 0 | 1/5| 1 | (Row 3) -------------------------------------------------------------------- - Compute Zj - Cj again:
| Cj | 3 | 2 | 5 | 0 | 0 | 0 | CB | Xb | b | x1 | x2 | x3 | x4 | x5 | x6 | --------------------------------------------------------------------- 0 | x4 | 3 | 3/5| 2/5| 0 | 1 | -1/5| 0 | (Row 1) 5 | x3 | 6 | 2/5| 3/5| 1 | 0 | 1/5| 0 | (Row 2) 0 | x6 | 14 | 12/5| -2/5| 0 | 0 | 1/5| 1 | (Row 3) --------------------------------------------------------------------- Zj | | 2 | 3 | 5 | 0 | 1 | 0 | Cj | | 3 | 2 | 5 | 0 | 0 | 0 | Zj - Cj | | -1 | 1 | 0 | 0 | 1 | 0 |
Row 1: 3/(3/5) = 5 (smallest ratio)
Row 2: 30/2 = 15
Row 3: 14/(12/5) = 5.833
Thus, x4 exits, and x1 replaces x4 in the basis. -
now we wil put 1 at key element place which is 3/5 and at row 2 and row 3 we will put 0
below the key element.
for row 1 we will do row 1 * 5/3
for row 2 we will do row 2 - 2/5 * row 1(new)
for row 3 we will do row 3 - 12/5 * row 1 (new)
| Cj | 3 | 2 | 5 | 0 | 0 | 0 | CB | Xb | b | x1 | x2 | x3 | x4 | x5 | x6 | ------------------------------------------------------------------- 3 | x1 | 5 | 1 | 2/3| 0 | 5/3 | -1/3| 0 | (Row 1) new 5 | x3 | 4 | 0 | 1/3| 1 | -2/3 | 1/3| 0 | (Row 2) 0 | x6 | 2 | 0 | -2 | 0 | -4 | 1 | 1 | (Row 3) -------------------------------------------------------------------- Zj - Cj | | 0 | 5/3| 0 | 5/3| 2/3| 0 |
so, x1 = 5, x2 = 0 and x3 = 4
We put this in Z cost function we get max Z = 35
Big M method
The Big M Method is an approach used to solve linear programming problems (LPP) involving artificial variables when the problem includes greater-than-or-equal-to (≥) or equality (=) constraints. It allows converting such constraints into a standard form suitable for solving using the Simplex method.
Min Z = x1 + x2
Constraints:
2x1 + x2 ≥ 4
x1 + 7x2 ≥ 7
x1 ≥ 0
- First, we have to convert it into a maximization function.
For that, we will multiply it by -1.
Max z' = -x1 - x2
Since we have ≥, we need to subtract a surplus variable.
2x1 + x2 - x3 + 0x4 = 4
x1 + 7x2 + 0x3 - x4 = 7
Now, the problem is that we don't have a unit matrix, so we add 2 more variables called artificial variables.
Max z' = -x1 - x2 + 0x3 + 0x4 - Mx5 - Mx6
2x1 + x2 - x3 + 0x4 + x5 + 0x6 = 4
x1 + 7x2 + 0x3 - x4 + 0x5 + x6 = 7
This M is a very large value, which is why we call it the Big M method. -
| Cj | -1 | -1 | 0 | 0 | -M | -M | CB | Xb | b | x1 | x2 | x3 | x4 | x5 | x6 | ------------------------------------------------------------------------ -M | x5 | 4 | 2 | 1 | -1 | 0 | 1 | 0 | (Row 1) -M | x6 | 7 | 1 | 7 | 0 | -1 | 0 | 1 | (Row 2) ------------------------------------------------------------------------ Zj | | -3M | -8M | M | M | -M | -M | Cj | | -1 | -1 | 0 | 0 | 0 | 0 | Zj - Cj | | -3M+1 | -8M+1 | M | M | 0 | 0 |
Now, we will find the minimum ratio to identify the outgoing variable.
Row 1 ratio of b/x2 = 4/1 = 4
Row 2 ratio of b/x2 = 7/7 = 1 (this is the minimum ratio value).
Thus, 7 becomes our key value, and we need to make it 1.
x6 is the outgoing variable. - Remember, in the Big M method, we don't write the outgoing variable in the next table, so we
will not write the x6 column.
To make 7 into 1, we will perform the following operations:
For row 2, divide row 2 by 7.
For row 1, subtract the new row 2 from row 1.| Cj | -1 | -1 | 0 | 0 | -M CB | Xb | b | x1 | x2 | x3 | x4 | x5 --------------------------------------------------------------- -M | x5 | 3 | 13/7 | 0 | -1 | 1/7 | 1 (Row 1) -1 | x2 | 1 | 1/7 | 1 | 0 | -1/7 | 0 (Row 2) new --------------------------------------------------------------- Zj | |(-13M-1)/7 | -1 | M |(-M+1)/7 | -M Cj | | -1 | -1 | 0 | 0 | 0 Zj - Cj | |(-13M-8)/7 | 0 | M |(-M+1)/7 | 0
Now, find the ratio of b and x1 to identify the outgoing variable.
Row 1 ratio of b/x1 = 21/13
Row 2 ratio of b/x1 = 7
Thus, 21/13 is the smallest ratio, making x5 the outgoing variable, and 13/7 is the key value. - For row 1, we will multiply row 1 by 7/13.
For row 2, we will perform the following operation: row 2 = row 2 - 1/7 * row 1 (new).| Cj | -1 | -1 | 0 | 0 CB | Xb | b | x1 | x2 | x3 | x4 --------------------------------------------------- -1 | x1 | 21/13 | 1 | 0 | -7/13 | 1/13 (Row 1) new -1 | x2 | 10/13 | 0 | 1 | 1/13 | -2/13 (Row 2) ---------------------------------------------------- Zj | | -1 | -1 | 6/13 | 1/13 Cj | | -1 | -1 | 0 | 0 Zj - Cj | | 0 | 0 | 6/13 | 1/13
x1 = 21/13
x2 = 10/13
Min Z = (21/13) + (10/13) = 31/13
Two Phase Method
The Two-Phase Method is used to solve Linear Programming Problems (LPP) when the problem involves artificial variables, typically in the case of equality constraints or greater-than-or-equal-to (≥) constraints. It ensures that a feasible solution is found even when such variables are introduced. The method is divided into two phases:
- Phase 1:
- The goal is to minimize the sum of artificial variables, ensuring that they are driven to zero.
- The original LPP is modified by adding artificial variables and creating an auxiliary objective function (minimizing the sum of these variables).
- Solve the modified problem using the simplex method. If the optimal solution of the auxiliary problem has a value of zero for the artificial variables, it means a feasible solution is found.
- Phase 2:
- After obtaining a feasible solution from Phase 1, the artificial variables are removed from the problem.
- The original objective function is restored, and the feasible solution is used as the starting point for solving the original LPP using the simplex method.
Min Z = x1 + x2
Constraints:
2x1 + x2 ≥ 4
x1 + 7x2 ≥ 7
x1 ≥ 0
- First, we have to convert it into a maximization function.
For that, we will multiply it by -1.
Max z' = -x1 - x2
Since we have ≥, we need to subtract a surplus variable.
2x1 + x2 - x3 + 0x4 = 4
x1 + 7x2 + 0x3 - x4 = 7
Now, the problem is that we don't have a unit matrix, so we add 2 more variables called artificial variables.
Max z' = -x1 - x2 + 0x3 + 0x4 - x5 - x6
Phase 1:
for phase 1 our max z' function becomes 0x1 + 0x2 + 0x3 + 0x4 - x5 - x6
Max z' = -x5 - x6
Following are the constraints
2x1 + x2 - x3 + 0x4 + x5 + 0x6 = 4
x1 + 7x2 + 0x3 - x4 + 0x5 + x6 = 7 -
| Cj | 0 | 0 | 0 | 0 | -1 | -1 | CB | Xb | b | x1 | x2 | x3 | x4 | x5 | x6 | ------------------------------------------------------------------------ -1 | x5 | 4 | 2 | 1 | -1 | 0 | 1 | 0 | (Row 1) -1 | x6 | 7 | 1 | 7 | 0 | -1 | 0 | 1 | (Row 2) ------------------------------------------------------------------------ Zj | | -3 | -8 | 1 | 1 | -1 | -1 | Cj | | 0 | 0 | 0 | 0 | -1 | -1 | Zj - Cj | | -3 | -8 | 1 | 1 | 0 | 0 |
Now, we will find the minimum ratio to identify the outgoing variable.
Row 1 ratio of b/x2 = 4/1 = 4
Row 2 ratio of b/x2 = 7/7 = 1 (this is the minimum ratio value).
Thus, 7 becomes our key value, and we need to make it 1.
x6 is the outgoing variable. - Remember, in the 2 phase method also, we don't write the outgoing variable in the next
table, so we
will not write the x6 column.
To make 7 into 1, we will perform the following operations:
For row 2, divide row 2 by 7.
For row 1, subtract the new row 2 from row 1.| Cj | 0 | 0 | 0 | 0 | -1 CB | Xb | b | x1 | x2 | x3 | x4 | x5 --------------------------------------------------------------- -1 | x5 | 3 | 13/7 | 0 | -1 | 1/7 | 1 (Row 1) 0 | x2 | 1 | 1/7 | 1 | 0 | -1/7 | 0 (Row 2) new --------------------------------------------------------------- Zj | | -13/7 | -1 | 1 | -1/7 | -1 Cj | | 0 | 0 | 0 | 0 | -1 Zj - Cj | | -13/7 | -1 | 1 | -1/7 | 0
Now, find the ratio of b and x1 to identify the outgoing variable.
Row 1 ratio of b/x1 = 21/13
Row 2 ratio of b/x1 = 7
Thus, 21/13 is the smallest ratio, making x5 the outgoing variable, and 13/7 is the key value. - For row 1, we will multiply row 1 by 7/13.
For row 2, we will perform the following operation: row 2 = row 2 - 1/7 * row 1 (new).| Cj | 0 | 0 | 0 | 0 CB | Xb | b | x1 | x2 | x3 | x4 --------------------------------------------------- 0 | x1 | 21/13 | 1 | 0 | -7/13 | 1/13 (Row 1) new 0 | x2 | 10/13 | 0 | 1 | 1/13 | -2/13 (Row 2) ---------------------------------------------------- Zj | | 0 | 0 | 0 | 0 Cj | | 0 | 0 | 0 | 0 Zj - Cj | | 0 | 0 | 0 | 0 - Phase 2:
now for phase 2 our objective function becomes:
Max z' = -x1 - x2 + 0x3 + 0x4 -
| Cj | -1 | -1 | 0 | 0 CB | Xb | b | x1 | x2 | x3 | x4 --------------------------------------------------- -1 | x1 | 21/13 | 1 | 0 | -7/13 | 1/13 (Row 1) new -1 | x2 | 10/13 | 0 | 1 | 1/13 | -2/13 (Row 2) ---------------------------------------------------- Zj - Cj | | 0 | 0 | 6/13 | 1/13
x1 = 21/13 and x2 = 10/13
min z = 31/13
Transportation Problem
- In the transportation problem, we aim to minimize transportation costs for a business while maximizing overall profit.
- Suppose you are running a business, and you need to transport materials to 4 different destinations from 4 supply locations. You are aware of the transportation costs from each location, the demand at each destination, and the available supply at each source. The model used to minimize the transportation cost while balancing supply and demand is known as the Transportation Model.
- Usually, the transportation problem involves minimization, but in some cases, we may need to maximize certain factors, such as profit. In such scenarios, a different approach or method is applied to solve the problem effectively.
Methods of finding the inital feasible solution
- Nort-west corner rule
- Least cost method
- Vogel's Approximation Method
Basic Feasible Solution (BFS):
- The Transportation Problem is a special case of Linear Programming Problems (LPP), so the definition of a Basic Feasible Solution (BFS) is similar to that in LPP.
- In the case of the Transportation Problem, there are only (m + n - 1) basic variables out of a total of m * n variables. Here, m represents the number of rows (suppliers) and n represents the number of columns (destinations) in the transportation problem. Therefore, the BFS of a transportation problem consists of at most (m + n - 1) variables, with the remaining variables being zero.
Example Problem - Find the Initial BFS (Basic Feasible Solution) of the Following Transportation Problem:
| Warehouse
Factory | w1 | w2 | w3 | w4 | Capacity
----------------------------------------------------
F1 | 19 | 30 | 50 | 10 | 7
F2 | 70 | 30 | 40 | 60 | 9
F3 | 40 | 8 | 70 | 20 | 18
----------------------------------------------------
Warehouse | 5 | 8 | 7 | 14 |
Requirement |
- We will solve this using the North-West Corner Rule.
- First, we check if the supply and demand are balanced. This means the total supply should equal the total demand. In this case, the total capacity (7 + 9 + 18 = 34) is equal to the total requirement (5 + 8 + 7 + 14 = 34), so the problem is balanced.
- In the North-West Corner method, we start at the top-left (north-west) corner of the cost matrix and assign the supply or demand, whichever is smaller, to that cell. We then subtract the smaller value from the larger one and move to the next cell, following the north-west direction until all supplies and demands are met.
-
Start with top-left and assign smallest supply or demand.
Factory | w1 | w2 | w3 | w4 | Capacity ---------------------------------------------------- F1 | 19 (5) | 30 | 50 | 10 | 7-5=2 F2 | 70 | 30 | 40 | 60 | 9 F3 | 40 | 8 | 70 | 20 | 18 ---------------------------------------------------- Requirement | 5-5=0 | 8 | 7 | 14 |
again we assignFactory | w2 | w3 | w4 | Capacity ---------------------------------------------------- F1 | 30(2) | 50 | 10 | 2-2=0 F2 | 30 | 40 | 60 | 9 F3 | 8 | 70 | 20 | 18 ---------------------------------------------------- Requirement | 8-2=6 | 7 | 14 |Factory | w2 | w3 | w4 | Capacity ---------------------------------------------------- F2 | 30(6) | 40 | 60 | 9-6=3 F3 | 8 | 70 | 20 | 18 ---------------------------------------------------- Requirement | 6-6=0 | 7 | 14 |Factory | w3 | w4 | Capacity -------------------------------------------- F2 | 40(3) | 60 | 3-3=0 F3 | 70 | 20 | 18 -------------------------------------------- Requirement | 7-3=4 | 14 |
Now only 2 values are left so we can directly assign.Factory | w3 | w4 | Capacity ----------------------------------------------- F3 | 70(4) | 20(14) | 18-4-14=0 ----------------------------------------------- Requirement | 4-4=0 | 14-14=0 |Factory | w1 | w2 | w3 | w4 | Capacity ---------------------------------------------------------------- F1 | 19 (5) | 30(2) | 50 | 10 | 7 F2 | 70 | 30(6) | 40(3) | 60 | 9 F3 | 40 | 8 | 70(4) | 20(14) | 18 ---------------------------------------------------------------- Requirement | 5 | 8 | 7 | 14 |
(19 * 5) + (30 * 2) + (30 * 6) + (40 * 3) + (70 * 4) + (20 * 14)
= 1015
Solving the Same Question Using the Least Cost Method
-
In this method, we find the minimum cost and assign the minimum value from either the supply or
demand.
Here, the minimum cost is 8, so we allocate accordingly.Factory | w1 | w2 | w3 | w4 | D ------------------------------------------------- F1 | 19 | 30 | 50 | 10 | 7 F2 | 70 | 30 | 40 | 60 | 9 F3 | 40 | 8(8) | 70 | 20 | 18-8=10 ------------------------------------------------- S | 5 | 8-8=0 | 7 | 14 | 34
Then, we assign the next smallest cost.Factory | w1 | w3 | w4 | D ------------------------------------------------- F1 | 19 | 50 | 10(7) | 7-7=0 F2 | 70 | 40 | 60 | 9 F3 | 40 | 70 | 20 | 10 ------------------------------------------------- S | 5 | 7 | 14-7=7 | 34
Then, we assign the next smallest cost.Factory | w1 | w3 | w4 | D ----------------------------------------- F2 | 70 | 40 | 60 | 9 F3 | 40 | 70 | 20(7) | 10-7=3 ----------------------------------------- S | 5 | 7 | 7-7=0 | 34
Since we have two minimum values, we can allocate to either one of them.Factory | w1 | w3 | D ------------------------------- F2 | 70 | 40(7) | 9-7=2 F3 | 40 | 70 | 3 ------------------------------- S | 5 | 7-7=0 |Factory | w1 | D ----------------------- F2 | 70(2) | 2-2=0 F3 | 40(3) | 3-3=0 ----------------------- S | 5-2-3=0 |Factory | w1 | w2 | w3 | w4 ---------------------------------------------- F1 | 19 | 30 | 50 | 10(7) F2 | 70(2) | 30 | 40(7) | 60 F3 | 40(3) | 8(8) | 70 | 20(7)
3 + 4 - 1 = 6
And we also have 6 allocations, so we did it correctly.
Now, we will find the transportation cost using the Least Cost Method:
(10 * 7) + (70 * 2) + (40 * 7) + (40 * 3) + (8 * 8) + (20 * 7)
70 + 140 + 280 + 120 + 64 + 140 = 814
So, we know that using the North-West Corner Rule, the transportation cost was 1015, and using the Least Cost Method, the cost is 814. When we solve this same question using Vogel's Approximation Method, the cost will decrease further, making it the best method for solving transportation problems.