Use simplex method to solve
Maximize p = 30x + 20y+30z subject to
x + y+z <= 9
4x + 2y-2z <= 30
5x + 10y+3z <= 60
x, y, z >=0
see other post to the simplex tutorial.
To solve the given linear programming problem using the simplex method, we need to follow these steps:
Step 1: Convert the linear programming problem into standard form by introducing slack variables.
Step 2: Set up the initial simplex tableau.
Step 3: Perform iterations and identify the pivot element.
Step 4: Update the tableau by performing row operations.
Step 5: Repeat steps 3 and 4 until there are no negative values in the bottom row of the tableau.
Let's go through the steps one by one:
Step 1: Convert the linear programming problem into standard form by introducing slack variables:
The original problem is already in standard form.
Step 2: Set up the initial simplex tableau:
Write the equations in matrix form and set up the initial tableau.
Maximize: Z = 30x + 20y + 30z
Subject to:
x + y + z + s1 = 9
4x + 2y - 2z + s2 = 30
5x + 10y + 3z + s3 = 60
| x | y | z | s1 | s2 | s3 | RHS |
----------------------------------------------
Eq1 | 1 | 1 | 1 | 1 | 0 | 0 | 9 |
Eq2 | 4 | 2 |-2 | 0 | 1 | 0 | 30 |
Eq3 | 5 | 10 | 3 | 0 | 0 | 1 | 60 |
Z |-30|-20|-30 | 0 | 0 | 0 | 0 |
Step 3: Perform iterations and identify the pivot element:
Look at the bottom row of the tableau and identify the most negative value. In this case, the most negative value is -30 in the first column (x). So, x is the entering variable, and 9 in the first column (RHS) is the pivot element.
Step 4: Update the tableau by performing row operations:
Divide the pivot row by the pivot element (9) to make the pivot element equal to 1.
| x | y | z | s1 | s2 | s3 | RHS |
----------------------------------------------
Eq1 | 1 | 1 | 1 | 1 | 0 | 0 | 9 |
Eq2 | 4 | 2 |-2 | 0 | 1 | 0 | 30 |
Eq3 | 5 | 10 | 3 | 0 | 0 | 1 | 60 |
Z |-30|-20|-30 | 0 | 0 | 0 | 0 |
Next, perform row operations to make the other numbers in the pivot column (x) equal to zero.
Multiply the pivot row by the coefficient in the pivot column for each row and subtract from the corresponding row.
| x | y | z | s1 | s2 | s3 | RHS |
----------------------------------------------
Eq1 | 0 |-5 |-5 | 1 | 0 | 0 |-27 |
Eq2 | 1 | 0 | 2 | 0 |-1 | 0 | 6 |
Eq3 | 0 | 5 | -2 | 0 | 0 | 1 | 33 |
Z | 0 |50 |0 | 0 |-30 | 0 | 270 |
Step 5: Repeat steps 3 and 4 until there are no negative values in the bottom row of the tableau:
There are no negative values in the bottom row of the tableau, so the optimization is complete.
The optimal solution is:
x = 6, y = 0, z = 33
And the maximum value of p is 270.
Note: The steps outlined here are generalized for solving linear programming problems using the simplex method. The actual implementation may vary depending on the software or tool you are using.