Simplex
If the problem is
max x1 + 3x2
subj to
x1 + 2x2 ≤ 10
x1, x2 ≥ 0
then you should enter:
No. of constraints = 1 (not counting nonnegativity constraints),
No. of variables =2.
The table should be:
1 2 | 10
------+----
-1 -3 | 0
Interactive calculator
|
Tableau:
| Rule:
|
| In our case:
|
The algorithm
Phase I
Go on doing these steps in this order in a loop.
- Step 1:
- Find a blue row. (On failure go to phase II: found feasible
solution.)
Details: The blue row is the first row with a negative number in the
right margin.
- Step 2:
- Find a pivotal column. (On failure give up: no feasible
solution.)
Details: Find any negative number in the main part of the row identified in the last step.
Take its column as the pivotal column.
- Step 3:
- Find a pivotal row. (Never fails.)
Details: For this go down the pivotal column.
Everytime we meet a negative number, we shall divide the
the right margin number (if nonpos) in the row by it.
The row producing the minimum number is the
pivotal row.
- Step 4:
- Do pivoting. (Never fails.)
Phase II
Go on doing these steps in this order in a loop.
- Step 30:
- Find a pivotal column. (On failure stop: found optimal
solution.)
Details: Find the pivotal column as any column
with negative entry in the bottom margin.
- Step 31:
- Find a pivotal row. (On failure give up: unbounded feasible
region.)
Details: Work down the pivotal column.
For each positive number, divide the right margin number
in the row by it. The row producing the minimum answer
is taken as the pivotal row.
- Step 32:
- Do pivoting. (Never fails.)
Pivoting
| Intially | (1) Swap labels. |
(2) Change general elements. |
|---|
|
|
|
|
| (3) Change non-pivot elements in pivotal row. |
(4) Change non-pivot elements in pivotal column. |
(5) Change pivot element. |
|
|
|
| | Row | |
|---|
| c-(ab/p) |
-a/p |
|
|---|
| Col | b/p |
1/p |
|
|---|
| |
|
|
|---|
|