Simplex algorithm

In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.

The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial cones, and these become proper simplices with an additional constraint. The simplicial cones in question are the corners (i.e., the neighborhoods of the vertices) of a geometric object called a polytope. The shape of this polytope is defined by the constraints applied to the objective function.

The simplex algorithm operates on linear programs in standard form:

with x ${\displaystyle =(x_{1},\,\dots ,\,x_{n})}$ the variables of the problem, c ${\displaystyle =(c_{1},\,\dots ,\,c_{n})}$ are the coefficients of the objective function, A is a p×n matrix, and b ${\displaystyle =(b_{1},\,\dots ,\,b_{p})}$ constants with ${\displaystyle b_{j}\geq 0}$. There is a straightforward process to convert any linear program into one in standard form so this results in no loss of generality.

...
Wikipedia