This is a basic C implementation of the simplex algorithm. This algorithm can solve linear programming problems in standard/cannonical form: $$ \text{max} \ c^Tx \ \text{s.t.} \ Ax \leq b $$ Which can be useful for solving several optimisation problems such as profit maximisation under certain constraints and even finding the optimal diet plan.
The program can be executed by compiling the simplex.c file using any C-compiler. The executable can then be executed through a terminal with a list of files to run. For example:
simplex "basic.txt" "prob1.txt"
The input program must be of the format:
variables N
{max,min} C_1, C_2, ... C_N
constraints M
A[1,1], A[1, 2], ... A[1, N] {<=,>=,=} B_1
...
A[M,1], A[M, 2], ... A[M, N] {<=,>=,=} B_M See the basic.txt file for a complete example. Running the basic problem results in the output:
Solving problem: basic.txt
Initial Dictionary:
x1 x2 x3
Zeta = 0.0000 + 5.0000 + 4.0000 + 3.0000
w1 = 5.0000 - 2.0000 - 3.0000 - 1.0000
w2 = 11.0000 - 4.0000 - 1.0000 - 2.0000
w3 = 8.0000 - 3.0000 - 4.0000 - 2.0000
--- Now Solving ---
x1 entering and w1 leaving:
w1 x2 x3
Zeta = 12.5000 - 2.5000 - 3.5000 + 0.5000
x1 = 2.5000 - 0.5000 - 1.5000 - 0.5000
w2 = 1.0000 + 2.0000 + 5.0000 - -0.0000
w3 = 0.5000 + 1.5000 + 0.5000 - 0.5000
x3 entering and w3 leaving:
w1 x2 w3
Zeta = 13.0000 - 1.0000 - 3.0000 - 1.0000
x1 = 2.0000 - 2.0000 - 2.0000 + 1.0000
w2 = 1.0000 + 2.0000 + 5.0000 - 0.0000
x3 = 1.0000 + 3.0000 + 1.0000 - 2.0000
--- Simplex Terminating (Success) ---
Maximum Value: 13.000000
Variables: x1 = 2.0000, w2 = 1.0000, x3 = 1.0000