use simplex method solbe LPP
maximize Z=2x1+4x2+x3+x4
subject to x1+3x2+x4<4
2x1+x2<3
x2+4x3+x4<3
x1,x2,x3,x4>0
bkvckkb
To solve the given linear programming problem using the simplex method, follow these steps:
Step 1: Convert the problem into standard form:
Maximize Z = 2x1 + 4x2 + x3 + x4
Subject to:
x1 + 3x2 + x4 <= 4
2x1 + x2 <= 3
x2 + 4x3 + x4 <= 3
x1, x2, x3, x4 >= 0
Step 2: Introduce slack variables to convert the inequalities into equations:
x1 + 3x2 + x4 + s1 = 4
2x1 + x2 + s2 = 3
x2 + 4x3 + x4 + s3 = 3
x1, x2, x3, x4, s1, s2, s3 >= 0
Step 3: Create the initial tableau:
| Cb | x1 | x2 | x3 | x4 | s1 | s2 | s3 | RHS |
--------------------------------------------------------------
| 0 | 1 | 3 | 0 | 1 | 1 | 0 | 0 | 4 |
| 0 | 2 | 1 | 0 | 0 | 0 | 1 | 0 | 3 |
| 0 | 0 | 1 | 4 | 1 | 0 | 0 | 1 | 3 |
|------------------------------------------------------------|
| -Zj | -2 | -4 | -1 | -1 | 0 | 0 | 0 | 0 |
| Cj | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Step 4: Find the variable to enter the basis:
- Select the most negative entry in the bottom row.
- The most negative entry is -2, which corresponds to x1.
Step 5: Find the variable to leave the basis:
- This can be determined by finding the minimum ratio of the right-hand side (RHS) values to the pivot column values.
- Divide RHS values by the corresponding pivot column values.
- Minimum ratio is 4/1 = 4, corresponding to s1.
Step 6: Perform the pivot operation:
- Divide the pivot row by the pivot element to make it equal to 1.
- Perform row operations to make all other elements in the pivot column zero.
- | Cb | x1 | x2 | x3 | x4 | s1 | s2 | s3 | RHS |
--------------------------------------------------------------
| 0 | 1 | 3 | 0 | 1 | 1 | 0 | 0 | 4 |
| 0 | 2 | 1 | 0 | 0 | 0 | 1 | 0 | 3 |
| 0 | 0 | 1 | 4 | 1 | 0 | 0 | 1 | 3 |
|------------------------------------------------------------|
| -Zj | 0 | 2/3 | 0 | -1/3 | -2/3 | 0 | 0 | -8/3 |
| Cj | 0 | 2 | 0 | 0 | 2 | 0 | 0 | |
Step 7: Determine if the current solution is optimal:
- If all entries in the bottom row are non-negative or zero, the current solution is optimal.
- In this case, the current solution is not optimal yet.
Step 8: Repeat Steps 4-7 until an optimal solution is reached:
- Continue performing the pivot operation until all entries in the bottom row are non-negative or zero.
- Repeat Steps 4-7 using the updated tableau:
| Cb | x1 | x2 | x3 | x4 | s1 | s2 | s3 | RHS |
--------------------------------------------------------------
| 0 | 1 | 3 | 0 | 1 | 1 | 0 | 0 | 4 |
| 0 | 2 | 1 | 0 | 0 | 0 | 1 | 0 | 3 |
| 0 | 0 | 1 | 4 | 1 | 0 | 0 | 1 | 3 |
|------------------------------------------------------------|
| -Zj | 0 | 0 | 8/5 | 1/5 | 0 | -3/5 | 0 | -7/5 |
| Cj | 0 | 4 | 0 | 0 | 2 | 0 | 0 | |
Step 9: The final tableau shows the optimal solution:
- The maximum value of Z is -7/5.
- The optimal solution is x1 = 4/5, x2 = 0, x3 = 3/5, x4 = 0.
- The maximum value of Z is -7/5.
- The solution is optimal.
Therefore, the optimal solution to the given linear programming problem is:
Z = -7/5
x1 = 4/5
x2 = 0
x3 = 3/5
x4 = 0
To solve this linear programming problem (LPP) using the simplex method, follow these steps:
Step 1: Identify the decision variables and write down the objective function.
The decision variables in this problem are x1, x2, x3, and x4. The objective function is to maximize Z=2x1+4x2+x3+x4.
Step 2: Write down the constraints.
The given constraints are:
1. x1 + 3x2 + x4 < 4
2. 2x1 + x2 < 3
3. x2 + 4x3 + x4 < 3
4. x1, x2, x3, x4 > 0
Step 3: Convert inequalities into equations by introducing slack variables.
By introducing slack variables, the inequalities can be transformed into equations. Slack variables (s1, s2, s3) represent the surplus/redundancy values in the constraints. Rewrite the given constraints as follows:
1. x1 + 3x2 + x4 + s1 = 4
2. 2x1 + x2 + s2 = 3
3. x2 + 4x3 + x4 + s3 = 3
4. x1, x2, x3, x4, s1, s2, s3 > 0
Step 4: Set up the initial Simplex tableau.
Create a Simplex tableau by arranging the coefficients of the decision variables, slack variables, and the right-hand side values. The initial tableau will have the following structure:
| Cb | x1 | x2 | x3 | x4 | s1 | s2 | s3 | RHS |
|----|----|----|----|----|----|----|----|-----|
|Z | | | | | | | | |
|c1 | | | | | | | | |
|c2 | | | | | | | | |
|c3 | | | | | | | | |
Step 5: Determine the initial feasible solution.
Assign initial values to the decision variables (x1, x2, x3, x4) and the slack variables (s1, s2, s3) to obtain a feasible solution. Usually, setting all variables to zero is a good starting point.
Step 6: Calculate the coefficients of the objective function row (Z).
For the objective function row (Z), calculate the coefficients using the given objective function.
Step 7: Calculate the coefficient row for each constraint.
For each constraint, calculate the coefficient row using the variables' coefficients on the left side of the equation. Set the coefficients corresponding to the slack variables to zero.
Step 8: Identify the pivot column.
In the coefficient row of the objective function (Z), identify the column with the most negative coefficient. This is the pivot column.
Step 9: Identify the pivot row.
Calculate the ratios between the constant terms (RHS) and the corresponding pivot column values. The pivot row will be the one with the smallest positive ratio.
Step 10: Determine the pivot element.
The pivot element is the value at the intersection of the pivot row and pivot column.
Step 11: Perform row operations to make the pivot element equal to 1.
Divide the pivot row by the pivot element to make the pivot element equal to 1. Adjust other elements in the pivot column accordingly to maintain the equality.
Step 12: Perform row operations to make other elements in the pivot column equal to zero.
Make other elements in the pivot column equal to zero through row operations. Adjust other rows to maintain the equalities.
Step 13: Repeat steps 8 to 12 until there are no negative elements in the objective function row.
Continue iterating through steps 8 to 12 until there are no negative elements in the objective function row. This ensures an optimal solution has been reached.
Step 14: Extract the optimal solution.
The optimal solution can be read from the final tableau after all the iterations are completed. The values corresponding to the decision variables (x1, x2, x3, x4) will give you the optimal solution.
That's how you solve a linear programming problem using the simplex method.