Simplex Algorithm
Input
pivot search: most negative
algorithm: default
max f(x) = 5 x1 + 8 x2
R1: 3 x1 + 2 x2 ≥ 3
R2: 1 x1 + 4 x2 ≥ 4
R3: 1 x1 + 1 x2 ≤ 5
x1, x2 ∈ ℚ
Initial Table (phase one)
| x1 | x2 | x3 | x4 | x5 | y1 | y2 | b | ||
|---|---|---|---|---|---|---|---|---|---|
| z~ | -4 | -6 | 1 | 1 | 0 | 0 | 0 | -7 | |
| z | -5 | -8 | 0 | 0 | 0 | 0 | 0 | 0 | |
| x5 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 5 | 5 |
| y1 | 3 | 2 | -1 | 0 | 0 | 1 | 0 | 3 | 3/2 |
| y2 | 1 | 4 | 0 | -1 | 0 | 0 | 1 | 4 | 1 |
Rx5 + (-1/4) · Ry2 → Rx5
Ry1 + (-1/2) · Ry2 → Ry1
Ry2 / 4 → Rx2
Iteration 1
| x1 | x2 | x3 | x4 | x5 | y1 | y2 | b | ||
|---|---|---|---|---|---|---|---|---|---|
| z~ | -5/2 | 0 | 1 | -1/2 | 0 | 0 | 3/2 | -1 | |
| z | -3 | 0 | 0 | -2 | 0 | 0 | 2 | 8 | |
| x5 | 3/4 | 0 | 0 | 1/4 | 1 | 0 | -1/4 | 4 | 16/3 |
| y1 | 5/2 | 0 | -1 | 1/2 | 0 | 1 | -1/2 | 1 | 2/5 |
| x2 | 1/4 | 1 | 0 | -1/4 | 0 | 0 | 1/4 | 1 | 4 |
Rx5 + (-3/10) · Ry1 → Rx5
Ry1 / 5/2 → Rx1
Rx2 + (-1/10) · Ry1 → Rx2
Iteration 2
| x1 | x2 | x3 | x4 | x5 | y1 | y2 | b | ||
|---|---|---|---|---|---|---|---|---|---|
| z~ | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | |
| z | 0 | 0 | -6/5 | -7/5 | 0 | 6/5 | 7/5 | 46/5 | |
| x5 | 0 | 0 | 3/10 | 1/10 | 1 | -3/10 | -1/10 | 37/10 | 37 |
| x1 | 1 | 0 | -2/5 | 1/5 | 0 | 2/5 | -1/5 | 2/5 | 2 |
| x2 | 0 | 1 | 1/10 | -3/10 | 0 | -1/10 | 3/10 | 9/10 | inf |
Rx5 + (-1/2) · Rx1 → Rx5
Rx1 / 1/5 → Rx4
Rx2 + 3/2 · Rx1 → Rx2
Iteration 1 (phase two)
| x1 | x2 | x3 | x4 | x5 | b | ||
|---|---|---|---|---|---|---|---|
| z | 7 | 0 | -4 | 0 | 0 | 12 | |
| x5 | -1/2 | 0 | 1/2 | 0 | 1 | 7/2 | 7 |
| x4 | 5 | 0 | -2 | 1 | 0 | 2 | inf |
| x2 | 3/2 | 1 | -1/2 | 0 | 0 | 3/2 | inf |
Rx5 / 1/2 → Rx3
Rx4 + 4 · Rx5 → Rx4
Rx2 + 1 · Rx5 → Rx2
Iteration 2
| x1 | x2 | x3 | x4 | x5 | b | |
|---|---|---|---|---|---|---|
| z | 3 | 0 | 0 | 0 | 8 | 40 |
| x3 | -1 | 0 | 1 | 0 | 2 | 7 |
| x4 | 3 | 0 | 0 | 1 | 4 | 16 |
| x2 | 1 | 1 | 0 | 0 | 1 | 5 |
Solution
| f(x*) | 40 |
| x*1 | 0 |
| x*2 | 5 |
| x*3 | 7 |
| x*4 | 16 |
| x*5 | 0 |
Maximum
| Cap | Δf(x) | Δx1 | Δx2 | |
|---|---|---|---|---|
| R1 | 0 | 0 | 0 | 0 |
| R2 | 0 | 0 | 0 | 0 |
| R3 | 8 | 8 | 0 | 1 |
Minimum
| Floor | Δf(x) | Δx1 | Δx2 | |
|---|---|---|---|---|
| x1 | 3 | 3 | 1 | -1 |
| x2 | 0 | 0 | 0 | 0 |
Economic Interpretation
0 item x1, and 5 item x2 should be produced and sold to achieve a value of 40.00 monetary units.
No additional units of x3 should be provided.
No additional units of x4 should be provided.
For an additional unit of x5, a maximum of 8.00 monetary units should be spent. This increases the amount of x1 items produced by 0 units, and x2 items produced by 1 units.
An additional unit of x1 should be sold for at least 3.00 monetary units. This increases the quantity of x1 items sold by 1 units, x2 items sold by -1 units, and .
No additional units of x2 should be produced and sold.