Entering column
most negative objective entry: −3 (x)
Choose the variable to enter.
In a simplex step the entering column is the one with the most negative entry in the objective row (largest improvement per unit), and the leaving row is chosen by the minimum ratio over positive entries of that column, which keeps the solution feasible.
This page is easier if you are comfortable with:
Maximise subject to , . The objective row is : entries and , so enters (reduced cost ). The ratios are and ; the minimum, 4, selects row 1, so leaves. After pivoting, and the objective is ; no negative entries remain, so the solution is optimal.
The minimum ratio test prevents any basic variable becoming negative: if row 2 had been chosen, would give . A pivot moves from one vertex of the feasible region to an adjacent one (the optimum at a vertex), each time improving or keeping the objective. The pivot itself is Gaussian elimination on the tableau (Gaussian elimination cost).
Reading the final tableau gives the solution and shadow prices (reading the simplex tableau, LP duality). Degenerate ties in the ratio test can cause cycling, handled by anti-cycling rules.
A simplex pivot moves to a neighbouring corner of the feasible region with a better objective value.
Choosing the smaller ratio keeps all variables non-negative.
These examples are worked by hand, step by step, so you can compare your own working.
Which objective-row entry is chosen in ?
Find the minimum ratio for the column of with right-hand sides 4 and 6 (entries 1 and 1).
Find the objective value after the pivot.
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
most negative objective entry: −3 (x)
Choose the variable to enter.
rhs ÷ column entry: 4 ÷ 1 = 4, 6 ÷ 1 = 6
Smallest ratio leaves.
row 2 rhs 6 − 4 = 2
Subtract row 1.
z = 12 after the pivot
3 × 4.
A simplex pivot picks an entering variable (most negative objective-row entry), a leaving row by the minimum ratio rhs/column entry (positive entries only), then eliminates the column using row operations.
Objective row (−3, −2). Which column enters?
Column (1, 1), rhs (4, 6). Which row leaves?
Update row 2 rhs after pivoting on row 1 (entry 1).
Update z: add 3 × row 1 to the objective row rhs.
max rhs/entry ✗
minimum ratio ✓
Otherwise feasibility breaks.
dividing by 0 or negatives ✗
only positive entries ✓
Ignore them in the ratio test.
pivot ≠ 1 ✗
divide the row by the pivot ✓
Make it 1.
a negative entry remains ✗
continue until all ≥ 0 ✓
Optimality test.
Try each one on paper, then open the answer. Use the solver above to see the full working.
4
3
4
20
4
4
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
One step swapping a basic and non-basic variable.
The most negative objective entry.
Smallest rhs ÷ positive column entry.
When the objective row has no negatives.
LP duality.
reading the solution.
More in Numerical methods and optimisation and the formula sheets.