There is no way we can work this in ASCIii, so here is an example in detail:
http://math.uww.edu/~mcfarlat/s-prob.htm
Maximize P=60x+50y.
x+y≤80
5x+10y≤560
50x+20y≤1600
x≥0
y≥0
Use the simplex method to solve the problem. Use s, t, and u as your slack variables for the first, second, and third inequalities respectively. Use the final simplex tableau to identify the values below.
x =
y =
s =
t =
u =
P =
http://math.uww.edu/~mcfarlat/s-prob.htm
2x+5y<=10
>=0,y>=0
We have the objective function:
P = 60x + 50y
And the following constraints:
x + y ≤ 80 (converted to x + y + s = 80)
5x + 10y ≤ 560 (converted to 5x + 10y + t = 560)
50x + 20y ≤ 1600 (converted to 50x + 20y + u = 1600)
x ≥ 0, y ≥ 0
Now, let's set up the initial simplex tableau:
| x | y | s | t | u | RHS |
----------------------------------------------------------------------
s | 1 | 1 | 1 | 0 | 0 | 80 |
t | 5 | 10 | 0 | 1 | 0 | 560 |
u | 50 | 20 | 0 | 0 | 1 | 1600 |
-----------------------------------------------------------
Now, we'll perform the simplex method to solve the problem step by step.
Step 1: Identify the pivot column. This is the column with the most negative coefficient in the objective row (P-row). In this case, the pivot column is y.
Step 2: Identify the pivot row. This is the row with the smallest non-negative ratio of the RHS value to the corresponding value in the pivot column. In this case, the pivot row is s.
Step 3: Perform elementary row operations to make the pivot element equal to 1 and all other elements in the pivot column equal to zero.
- Divide the pivot row by the pivot element (1).
- Multiply the pivot row by -10 and add it to the t-row.
- Multiply the pivot row by -20 and add it to the u-row.
The updated tableau after Step 3:
| x | y | s | t | u | RHS |
----------------------------------------------------------------------
s | 1 | 0 | -1 | 1 | 0 | 40 |
t | 0 | 0 | 5 | -10 | 0 | 160 |
u | 0 | 0 | 30 | -20 | 1 | 400 |
-----------------------------------------------------------
Step 4: Repeat steps 1-3 until the P-row coefficients are no longer negative.
Next, let's perform the remaining steps:
Step 1: The pivot column is x.
Step 2: The pivot row is t.
Step 3: Perform elementary row operations to make the pivot element equal to 1 and all other elements in the pivot column equal to zero.
The updated tableau after Step 3:
| x | y | s | t | u | RHS |
----------------------------------------------------------------------
s | 0 | 0 | -1 | 1 | -0.2 | 20 |
x | 0 | 0 | 1 | -2 | 0.4 | 32 |
u | 0 | 0 | 30 | -20 | 1 | 400 |
-----------------------------------------------------------
Step 1: The pivot column is s.
Step 2: The pivot row is u.
Step 3: Perform elementary row operations to make the pivot element equal to 1 and all other elements in the pivot column equal to zero.
The updated tableau after Step 3:
| x | y | s | t | u | RHS |
----------------------------------------------------------------------
u | 0.2 | 0 | -1 | 0.67 | 0.03 | 13 |
x | -0.4 | 0 | 1 | -1.33 | -0.07 | 19 |
s | 0.17 | -0.05 | 0 | 0.07 | -0.02 | 12 |
----------------------------------------------------------------------
Now, we have finished the simplex method iterations.
From the final simplex tableau, we can identify the values:
x = 19
y = 0
s = 12
t = 0
u = 13
P = 60(19) + 50(0) = 1140
Basic Variables | x y s t u P |
________________________________________
s | 1 0 1 0 0 0 |
t | 0 1 0 1 0 0 |
u | 0 0 0 0 1 0 |
P | -60 -50 0 0 0 1 |
Now, perform the iteration steps following the simplex method until an optimal solution is found.
1. Select the most negative coefficient in the P row, which is -60 in this case. The corresponding column is x.
Pivot Element: |-60|
2. Calculate the ratios b_i/a_i, where b_i is the value in the P column, and a_i is the values in the x column. Select the smallest positive ratio as the pivot row.
Ratios:
s: 0/1 = undefined
t: 0/5 = undefined
u: 0/50 = undefined
The smallest positive ratio is undefined for all rows. This indicates that the solution is unbounded, and the problem does not have an optimal solution.
Therefore, this linear programming problem does not have a feasible solution using the simplex method. The values of x, y, s, t, u, and P cannot be determined in this case.