Simplex Algorithm
Input
pivot search: most negative
algorithm: default
max f(x) = 3 x1 + 5 x2 + 4 x3
R1: 2 x1 + 3 x2 + 0 x3 ≤ 8
R2: 0 x1 + 2 x2 + 5 x3 ≤ 10
R3: 3 x1 + 2 x2 + 4 x3 ≤ 15
x1, x2, x3 ∈ ℚ
Initial Table
| x1 | x2 | x3 | x4 | x5 | x6 | b | ||
|---|---|---|---|---|---|---|---|---|
| z | -3 | -5 | -4 | 0 | 0 | 0 | 0 | |
| x4 | 2 | 3 | 0 | 1 | 0 | 0 | 8 | 8/3 |
| x5 | 0 | 2 | 5 | 0 | 1 | 0 | 10 | 5 |
| x6 | 3 | 2 | 4 | 0 | 0 | 1 | 15 | 15/2 |
Rx4 / 3 → Rx2
Rx5 + (-2/3) · Rx4 → Rx5
Rx6 + (-2/3) · Rx4 → Rx6
Iteration 1
| x1 | x2 | x3 | x4 | x5 | x6 | b | ||
|---|---|---|---|---|---|---|---|---|
| z | 1/3 | 0 | -4 | 5/3 | 0 | 0 | 40/3 | |
| x2 | 2/3 | 1 | 0 | 1/3 | 0 | 0 | 8/3 | inf |
| x5 | -4/3 | 0 | 5 | -2/3 | 1 | 0 | 14/3 | 14/15 |
| x6 | 5/3 | 0 | 4 | -2/3 | 0 | 1 | 29/3 | 29/12 |
Rx2 + 0 · Rx5 → Rx2
Rx5 / 5 → Rx3
Rx6 + (-4/5) · Rx5 → Rx6
Iteration 2
| x1 | x2 | x3 | x4 | x5 | x6 | b | ||
|---|---|---|---|---|---|---|---|---|
| z | -11/15 | 0 | 0 | 17/15 | 4/5 | 0 | 256/15 | |
| x2 | 2/3 | 1 | 0 | 1/3 | 0 | 0 | 8/3 | 4 |
| x3 | -4/15 | 0 | 1 | -2/15 | 1/5 | 0 | 14/15 | inf |
| x6 | 41/15 | 0 | 0 | -2/15 | -4/5 | 1 | 89/15 | 89/41 |
Rx2 + (-10/41) · Rx6 → Rx2
Rx3 + 4/41 · Rx6 → Rx3
Rx6 / 41/15 → Rx1
Iteration 3
| x1 | x2 | x3 | x4 | x5 | x6 | b | |
|---|---|---|---|---|---|---|---|
| z | 0 | 0 | 0 | 45/41 | 24/41 | 11/41 | 765/41 |
| x2 | 0 | 1 | 0 | 15/41 | 8/41 | -10/41 | 50/41 |
| x3 | 0 | 0 | 1 | -6/41 | 5/41 | 4/41 | 62/41 |
| x1 | 1 | 0 | 0 | -2/41 | -12/41 | 15/41 | 89/41 |
Solution
| f(x*) | 765/41 |
| x*1 | 89/41 |
| x*2 | 50/41 |
| x*3 | 62/41 |
| x*4 | 0 |
| x*5 | 0 |
| x*6 | 0 |
Maximum
| Cap | Δf(x) | Δx1 | Δx2 | Δx3 | |
|---|---|---|---|---|---|
| R1 | 45/41 | 45/41 | -2/41 | 15/41 | -6/41 |
| R2 | 24/41 | 24/41 | -12/41 | 8/41 | 5/41 |
| R3 | 11/41 | 11/41 | 15/41 | -10/41 | 4/41 |
Minimum
| Floor | Δf(x) | Δx1 | Δx2 | Δx3 | |
|---|---|---|---|---|---|
| x1 | 0 | 0 | 0 | 0 | 0 |
| x2 | 0 | 0 | 0 | 0 | 0 |
| x3 | 0 | 0 | 0 | 0 | 0 |
Economic Interpretation
89/41 item x1, 50/41 item x2, and 62/41 item x3 should be produced and sold to achieve a value of 18.66 monetary units.
For an additional unit of x4, a maximum of 1.10 monetary units should be spent. This increases the amount of x1 items produced by -2/41 units, x2 items produced by 15/41 units, and x3 items produced by -6/41 units.
For an additional unit of x5, a maximum of 0.59 monetary units should be spent. This increases the amount of x1 items produced by -12/41 units, x2 items produced by 8/41 units, and x3 items produced by 5/41 units.
For an additional unit of x6, a maximum of 0.27 monetary units should be spent. This increases the amount of x1 items produced by 15/41 units, x2 items produced by -10/41 units, and x3 items produced by 4/41 units.
No additional units of x1 should be produced and sold.
No additional units of x2 should be produced and sold.
No additional units of x3 should be produced and sold.