calculate the lower bound from
min z= 4x1 + 2x2
2x1 - 3x2 => 4
x1 + 5x2 <= 6
2x1 - 6x2 = 10
x1=>0
To calculate the lower bound of the objective function, we can use the Simplex Method to solve the linear programming problem. The Simplex Method is an iterative algorithm for solving linear programming problems where the objective is to maximize or minimize a linear function subject to linear constraints.
Step 1: Convert the given linear programming problem into standard form:
min z = 4x1 + 2x2
2x1 - 3x2 + s1 = 4 (Convert inequality constraint into equality constraint by adding a slack variable, s1)
x1 + 5x2 + s2 = 6 (Convert inequality constraint into equality constraint by adding a slack variable, s2)
2x1 - 6x2 = 10 (Equality constraint remains unchanged)
Step 2: Write the initial tableau:
| x1 | x2 | s1 | s2 | z |
--------------------------------------
Row 1 | 2 | -3 | 1 | 0 | 4 |
Row 2 | 1 | 5 | 0 | 1 | 6 |
Row 3 | 2 | -6 | 0 | 0 | 10|
Step 3: Perform the Simplex Method operations until an optimal solution is reached:
- Identify the pivot column by selecting the most negative coefficient in the bottom row. In this case, column x2 is the pivot column.
- Calculate the ratios of the values in the rightmost column to the corresponding values in the pivot column. The smallest non-negative ratio corresponds to the pivot row. In this case, row 1 has the smallest non-negative ratio.
- Perform the pivot operation to make the pivot element equal to 1 and all other elements in the pivot column equal to 0:
- Divide row 1 by -3 (pivot element)
- Multiply row 1 by 5 and add it to row 2
- Multiply row 1 by -6 and add it to row 3
The updated tableau becomes:
| x1 | x2 | s1 | s2 | z |
----------------------------------------------
Row 1 | -2/3 | 1 | -1/3 | 0 | 8/3 |
Row 2 | 11/3 | 0 | 5/3 | 1 | 22/3 |
Row 3 | -4/3 | 0 | 2/3 | 0 | 2/3 |
Continue these steps until the bottom row no longer contains negative coefficients. The optimal solution is reached when all coefficients in the bottom row are non-negative.
Step 4: Read the solution from the final tableau:
The optimal solution is:
x1 = 4/3
x2 = 0
z = 8/3
Therefore, the lower bound for the objective function min z = 4x1 + 2x2, subject to the given constraints, is 8/3.
Note: The given constraint x1 >= 0 was incorporated in the constraint equations during the conversion to standard form.