Simplex Method

Simplex Method Introduction

Simplex Method is an algorithm for solving the classical linear programming problem; developed by George B.Dantzig in 1947. The simplex method is an iterative procedure, solving asystem of linear equations in each of its steps, andstopping when either the optimum is reached, or thesolution proves infeasible. The basic method remainedpretty much the same over the years, though therewere many refinements targeted at improvingperformance (eg. using sparse matrix techniques),numerical accuracy and stability, as well as solvingspecial classes of problems, such as mixed-integerprogramming.
Basic Terminology - Simplex Method

Slack variable

It is a variable that is added to the left-hand side of a less than or equal type of constraint to convert the constraint into an equality. In economic terms, slack variables represent left-over or unused capacity.

Specifically:
a_i1x₁ + a_i2x₂ + a_i3x₃ + .........+ a_inx_n ≤ b_i can be written as
a_i1x₁ + a_i2x₂ + a_i3x₃ + .........+ a_inx_n + s_i = b_i
Where i = 1, 2, ..., m

Surplus variable

It is a variable subtracted from the left-hand side of a greater than or equal to type constraint to convert the constraint into an equality. It is also known as negative slack variable. In economic terms, surplus variables represent overfulfillment of the requirement.
Specifically:
a_i1x₁ + a_i2x₂ + a_i3x₃ + .........+ a_inx_n ≥ b_i can be written as
a_i1x₁ + a_i2x₂ + a_i3x₃ + .........+ a_inx_n - s_i = b_i
Where i = 1, 2, ..., m

Artificial variable

It is a non negative variable introduced to facilitate the computation of an initial basic feasible solution. In other words, a variable added to the left-hand side of a greater than or equal to type constraint to convert the constraint into an equality is called an artificial variable. 

From: Operation Research Simplified