The Simplex Algorithm for Linear Programming

Specification:

Choice of method (Simplex or Revised Simplex):
Copy example specification:

Hint on the format of the input

m n
m+1 rows of n+1 numbers in fractional form
Optional row of m indices for the basis. (Valid range of an index: 1 to n)

Note: If the basis is not specified, Phase I will be performed.

Example:

Maximize z = 8 x1 + 7 x2
subject to
- x1 + x2 ≤ 1
x1 + 2 x2 ≤ 4
5 x1 + 3 x2 ≤ 15
and x1 ≥ 0, x2 ≥ 0.

After introducing slack variables for the inequalities, and expressing maximization as minimization of the negative, we get the following standard form.

Minimize -8 x1 - 7 x2
subject to
- x1 + x2 + x3 = 1
x1 + 2 x2 + x4 = 4
5 x1 + 3 x2 + x5 = 15
and x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, and x5 ≥ 0.

This is now ready to be entered in the following form. 

3 5
-1  1  1  0  0  1
1  2  0  1  0  4
5  3  0  0  1  15
-8 -7  0  0  0  0
3 4 5

Note that the very first row specifies m and n. Here m is the number of constraints, and n is the number of variables, including the slack variables introduced to convert inequalities to equations.

Then there are m+1 rows specifying the tableau, the objective function row being the last.

Finally, if a suitable basis is known, it can be specified. In this case, the indices 3, 4, 5 can serve as a basis for a feasible solution.

If the basis is not specified, Phase I will be done.