Simplex Method for GATE Maths: A 2-Pivot Worked Example

GATE Mathematics does, and the CSIR NET syllabus does not ask mathematics candidates to answer it. The GATE 2027 syllabus for the Mathematics (MA) paper lists the simplex method in Section 11, Linear Programming. The CSIR NET common syllabus lists "Linear programming problem, simplex methods, duality" in Unit IV.

The same CSIR file says: "Students in mathematics are expected to answer additional question from Unit II and III." As of the CSIR syllabus file dated November 2018, linear programming sits in Unit IV, which is for statistics candidates, so mathematics candidates are not asked to answer it. Our CSIR NET exam pattern for Maths page covers how the units are examined.

Section 11 of the GATE 2027 syllabus names these topics: linear programming models, convex sets and extreme points, basic feasible solutions, the graphical method, the simplex method, two phase methods, the revised simplex method, infeasible and unbounded models, alternate optima, and weak and strong duality. It also names transportation and assignment problems, which use separate algorithms and are outside this page. The GATE 2026 syllabus has the same paragraph. For how many marks Section 11 has carried, see the marks each syllabus section has carried in recent GATE Mathematics papers.

If an LP has an optimum, one occurs at a corner of that region, and the simplex method walks from corner to corner, improving the objective at each step. If you are studying for a university operations research paper instead, the same seven checks apply.

Run these seven checks in order on every problem. Each has a pass condition and a fail action. The method works on a simplex table, called a tableau: one row per constraint, one column per variable, a right-hand side (RHS) column, and an objective row at the bottom.

For the problem maximise Z = 3x + 2y subject to x + y ≤ 4, x + 3y ≤ 6, x ≤ 3 and x, y ≥ 0, the optimum is Z = 11 at (3, 1), reached in two pivots.

Start. Slacks s1, s2, s3 are the basis. The most negative objective entry is −3, so x enters. The ratios are 4, 6 and 3, so the s3 row leaves.

After pivot 1. The point is (3, 0) and Z = 9. Now y enters. The ratios are 1/1 = 1 for the s1 row and 3/3 = 1 for the s2 row. The x row has a 0 in the y column, so it has no ratio. This is the tie. We let s1 leave.

After pivot 2. No negative entry remains, so the solution is optimal. y = 1, x = 3 and s2 = 0, and Z = 11.

Graph check: the corners of the feasible region are (0, 0), (3, 0), (3, 1) and (0, 2), with Z = 0, 9, 11 and 4. The method visited (0, 0), then (3, 0), then (3, 1), and stopped at the best one.

A tied ratio means the pivot is degenerate, and a basic variable ends up at 0. In the example, s2 = 0 in the last table because the lines x = 3, x + y = 4 and x + 3y = 6 all pass through (3, 1). The point (3, 1) is already fixed by the first two lines. The third line touches it without being needed to define it.

The dual values come from the slack columns of the final objective row: 2 for s1, 1 for s3, and 0 for s2, which is basic. Check 7 then gives 4 × 2 + 6 × 0 + 3 × 1 = 11, equal to Z. The dual constraints also hold: for x, 2 + 0 + 1 = 3 ≥ 3, and for y, 2 + 3 × 0 = 2 ≥ 2. If your arithmetic slipped in a pivot, this check almost always fails, which is why it earns a place in the routine.

Students pick the wrong row because they apply the ratio rule without knowing what it measures. The ratio RHS ÷ entry is how far the entering variable can rise before that row's basic variable reaches 0. The smallest ratio is the first limit you hit. Take a larger one and an earlier row goes negative. In the start table, raising x to 4 would give s3 = 3 − 4 = −1, which is infeasible.

Only positive entries count because a zero or negative entry never limits the rise. That row's variable stays the same or grows as the entering variable grows. A negative pivot would also make the new basic variable RHS ÷ (negative) < 0.

When a tableau puzzles you, turn a row back into an equation. The y row of the final table says y + s1 − s3 = 1, so y = 1 − s1 + s3. Raising s1 lowers y, and raising s3 raises it. You can then see what each non-basic variable would do if it entered, which is what the objective row summarises.

Yes, it can cycle, though it rarely does. Cycling is rare in practice. Bland's rule (1977) prevents it. The worst case is exponential (the Klee–Minty example, 1972, a constructed LP on which the simplex method visits every corner), although the method is fast in practice.

Beale's classic problem shows a cycle. Maximise ¾x₁ − 20x₂ + ½x₃ − 6x₄ subject to ¼x₁ − 8x₂ − x₃ + 9x₄ ≤ 0, ½x₁ − 12x₂ − ½x₃ + 3x₄ ≤ 0 and x₃ ≤ 1. With "most negative entry enters" and the lowest-numbered variable leaving on a tie, the basis returns to its starting point after 6 pivots with Z stuck at 0, and then repeats. Bland's rule picks the lowest-numbered eligible variable to enter and to leave. With it the problem finishes in 6 pivots at Z = 5/4, with x₁ = 1 and x₃ = 1.

Bland's rule pays for its safety. On random small problems with all constraints ≤ and positive coefficients, Bland's rule usually needs more pivots than the most-negative rule. These are easy problems, so read the result as an illustration only. In an exam, use the most-negative rule, and switch to the lowest-index rule if you notice a pivot sequence repeating.

Linear Programming is on the syllabus list of our CSIR-NET and GATE Mathematics 2027 course, next to Linear Algebra, Abstract Algebra, Real Analysis, Complex Analysis, Ordinary and Partial Differential Equations, Numerical Analysis and General Aptitude. The course has live interactive classes, recorded lectures for revision, assignments by chapter and topic, previous-year-question discussions, full-length mock tests with performance analysis, and weekly doubt sessions with personal mentorship. See our course page.

As of October 2026 the course costs ₹15,999 as a one-time payment, or four instalments of ₹3,999.75 (₹15,999 in total). A ₹999 demo plan is also available. Our overview of what full-syllabus GATE Mathematics coaching covers explains what to look for in any course.

Work the seven checks on every simplex problem in your assignments, and bring the ones that fail check 7 to a doubt session. Before you pay, try our free study content, which includes demo classes and PDF Drive resources. Questions about the course can go to sbtechmath@gmail.com or +91 81265 45455, between 9am and 7pm, Monday to Saturday.