The Simplex method is an algorithm to solve linear programming problems. It was developed by George Dantzig and consists of moving along vertices of the feasible region (in variable space), improving the objective function value at each step until reaching the optimum or detecting that the problem is unbounded or infeasible.

Standard form. Simplex works with problems in standard form: maximization (or minimization converted to max), equality constraints and non-negative variables. Inequalities are transformed using slack variables (≤), surplus and artificial variables (≥ and =).

Big-M method. When there are ≥ or = constraints, artificial variables are added and penalized in the objective function with a coefficient -M (in maximization) so they leave the basis; this yields an initial feasible basis or detects infeasibility.

Tableau and pivoting. The algorithm is applied on a tableau (table) representing the system in canonical form with respect to the current basis. At each iteration an entering variable is chosen (by most negative reduced cost) and a leaving variable (by the minimum ratio rule), and Gauss-Jordan pivoting is performed. The process ends when there are no negative reduced costs (optimum), no leaving row (unbounded) or artificial variables remain in the basis (infeasible).