Simplex Algorithm
Input
pivot search: most negative
algorithm: revised
max f(x) = 2 x1 + 1 x2
R1: 3 x1 + 4 x2 ≤ 6
R2: 6 x1 + 1 x2 ≤ 3
x1, x2 ∈ ℚ
Initial Table
| b | ā | Q | |||
|---|---|---|---|---|---|
| z | 0 | 0 | 0 | -2 | |
| x3 | 1 | 0 | 6 | 3 | 2 |
| x4 | 0 | 1 | 3 | 6 | 1/2 |
Rx3 + (-1/2) · Rx4 → Rx3
Rx4 / 6 → Rx1
Iteration 1
| b | ā | Q | |||
|---|---|---|---|---|---|
| z | 0 | 1/3 | 1 | -2/3 | |
| x3 | 1 | -1/2 | 9/2 | 7/2 | 9/7 |
| x1 | 0 | 1/6 | 1/2 | 1/6 | 3 |
Rx3 / 7/2 → Rx2
Rx1 + (-1/21) · Rx3 → Rx1
Iteration 2
| b | |||
|---|---|---|---|
| z | 4/21 | 5/21 | 13/7 |
| x2 | 2/7 | -1/7 | 9/7 |
| x1 | -1/21 | 4/21 | 2/7 |
Solution
| f(x*) | 13/7 |
| x*1 | 2/7 |
| x*2 | 9/7 |
| x*3 | 0 |
| x*4 | 0 |
Maximum
| Cap | Δf(x) | Δx1 | Δx2 | |
|---|---|---|---|---|
| R1 | 4/21 | 4/21 | -1/21 | 2/7 |
| R2 | 5/21 | 5/21 | 4/21 | -1/7 |
Minimum
| Floor | Δf(x) | Δx1 | Δx2 | |
|---|---|---|---|---|
| x1 | 0 | 0 | 0 | 0 |
| x2 | 0 | 0 | 0 | 0 |
Economic Interpretation
2/7 item x1, and 9/7 item x2 should be produced and sold to achieve a value of 1.86 monetary units.
For an additional unit of x3, a maximum of 0.19 monetary units should be spent. This increases the amount of x1 items produced by -1/21 units, and x2 items produced by 2/7 units.
For an additional unit of x4, a maximum of 0.24 monetary units should be spent. This increases the amount of x1 items produced by 4/21 units, and x2 items produced by -1/7 units.
No additional units of x1 should be produced and sold.
No additional units of x2 should be produced and sold.