DASE7034 Chap.3 Simplex Foundations and Pivot Logic
Simplex Foundations and Pivot Logic
The simplex method expresses LP geometry through bases and pivots. Standard form introduces slack or transformed variables, a basis identifies a basic solution and nonnegativity determines whether it is feasible.
Each valid pivot selects an improving entering variable and a leaving variable through the positive ratio test, moving to an adjacent basic feasible solution.
Connect a basis to a corner point
After a model is written in standard form, a basis chooses one variable for each independent equality. Setting the remaining variables to zero and solving for the basic variables gives a basic solution.
It is a basic feasible solution only when all required nonnegative variables satisfy their domains. Geometrically, a nondegenerate basic feasible solution corresponds to a corner of the feasible polyhedron.
This link explains why simplex can search corner points without enumerating every possible intersection.
Interpret the tableau rather than memorising signs
Tableau conventions differ in the sign used for reduced costs, so state the convention before applying an entering-variable rule. The relevant question is whether increasing a non-basic variable can improve the objective.
Once the entering column is chosen, only strictly positive pivot-column coefficients restrict an increase.
Divide each nonnegative right-hand side by its positive coefficient and select the smallest eligible ratio; zero or negative entries do not provide an upper bound and must not enter the ratio test.
Perform and audit a pivot
Scale the pivot row so the pivot element becomes one, then eliminate the other entries in that column. The entering variable replaces the leaving variable in the basis.
After row operations, verify the canonical column, identify the new basic values, check nonnegativity and compute the new objective under the same convention. Rechecking the original constraints guards against arithmetic errors.
A pivot is not merely row reduction: it represents a controlled move to an adjacent basis while preserving the equality system.
Know when the iterations may stop
Optimality occurs when no eligible non-basic variable offers improvement under the chosen convention, provided the current basis is feasible.
The final response should report decision-variable values, objective value and useful slack or binding information rather than copying an entire tableau. A zero ratio may produce a degenerate pivot with no objective improvement; this is valid but needs careful basis tracking.
A missing leaving row signals an unbounded improving direction, while failure to obtain an initial feasible basis leads to the artificial-variable methods developed separately.
What this chapter covers
- 01
Standard-form transformations
- 02
Basic and non-basic variables
- 03
Basic feasible solutions
- 04
Entering and leaving variables
- 05
Pivot and optimality tests
Worked example · free
Run a protected simplex pivot
- 2Identify an improving non-basic variable.
- 3Use only positive pivot-column entries in the ratio test.
- 4Normalise and eliminate the pivot column.
Key terms
- Basis
- A selection of columns used to solve the equality system for the current basic variables.
- Pivot
- The row operation that exchanges one basic variable for one non-basic variable.
- Degeneracy
- A basic feasible solution in which at least one basic variable equals zero.
Simplex Foundations and Pivot Logic FAQ
Why is the smallest positive ratio selected?
Increasing the entering variable reduces current basic variables. The smallest eligible ratio identifies the first one to reach zero, so making that variable leave preserves nonnegativity and keeps the next basis feasible.
Can a basic solution be infeasible?
Yes. A basis produces a basic solution algebraically, but it becomes a basic feasible solution only when all basic values satisfy their nonnegativity requirements and the transformed system corresponds to the original constraints.
What should be checked after a pivot?
Confirm that the entering column is a unit vector, basic right sides are nonnegative, the objective matches substitution and the original constraints remain satisfied. These invariants catch sign and elimination errors early.
Exam move
Practise one tableau slowly with a four-line audit after every pivot: basis, basic values, objective and feasibility. Say why each excluded ratio row is ineligible. Speed should come only after the sign convention and feasibility protection are automatic. Maintain a pivot ledger with the entering variable, every eligible ratio, the leaving variable, pivot element and new objective.
Mark the convention used for reduced costs at the top of the page so that a remembered sign rule cannot silently replace the tableau's logic. Keep enough exact precision to reconstruct each row operation and verify that the pivot column becomes canonical. At the end, translate basic variables back to the original decisions, including variables transformed during standardisation.
Substitute them into the original constraints and calculate slack in original units. State the optimality test explicitly rather than presenting a terminal tableau without a conclusion. If the model represents divisible activity only as a relaxation of discrete choices, identify that limit.
As a final drill, deliberately choose an ineligible ratio once and trace how it makes a basic value negative; this makes the feasibility protection behind the ratio test memorable.
Working through Simplex Foundations and Pivot Logic in DASE7034? Sia is AskSia’s AI Mathematics tutor — ask any DASE7034 Simplex Foundations and Pivot Logic question and get a clear, step-by-step explanation grounded in how DASE7034 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.