The University of Hong Kong · FACULTY OF MATHEMATICS

DASE7034 Chap.3 Simplex Foundations and Pivot Logic

- one subject, every graph, every model, every mark
5 Chapters4-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 3 of 12 · DASE7034

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.

In this chapter

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

Q [9 marks]. The marks used for these pivot steps are not the University's official assessment scheme. Choose an entering variable, apply the ratio test and update the basis.
A simplex pivot changes the basis and moves to an adjacent corner.A simplex pivot changes the basis and moves to an adjacent corner. The entering variable improves the objective while the leaving variable protects feasibility.BFS 0improveoptimal BFSone entering and one leaving variable per pivot
A simplex pivot changes the basis and moves to an adjacent corner. The entering variable improves the objective while the leaving variable protects feasibility.
  • 2Identify an improving non-basic variable.
  • 3Use only positive pivot-column entries in the ratio test.
  • 4Normalise and eliminate the pivot column.
Choose the entering variable according to the tableau's reduced-cost convention. Divide each nonnegative right side by a strictly positive entry in that column and select the smallest eligible ratio. Scale the pivot row to one, eliminate the remaining column entries and verify nonnegative basic values and the new objective. Marks shown beside these steps are an AskSia practice device rather than the University's official mark allocation.
Sia tip — Rows with zero or negative entering-column coefficients do not limit the increase and never enter the ratio test.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your DASE7034 tutor, unlimited, worked the way the exam marks it
The full 4-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works