Simplex Method Solver

In the UVic course, CSC 445: Operations Research: Linear Programming, I developed the program simplex.java for solving a linear program.

In brief, the program takes a linear program like so:

max.      $x$   $+$     $y$
s.t.    $-2x$   $+$     $y$   $\le$   $1$
              $x$   $+$   $3y$   $\le$   $8$
            $3x$   $+$     $y$   $\le$   $12$
                       $x,y$   $\ge$   $0$

Converts it into a dictionary:

$\zeta~$   $=$   $0$     $+$     $x$   $+$     $y$
                                             
$w_{1}$  $=$   $1$     $+$   $2x$   $-$     $y$
$w_{2}$  $=$   $8$     $-$     $x$   $-$   $3y$
$w_{3}$  $=$   $12$   $-$   $3x$   $-$     $y$

$x,y,w_{1},w_{2},w_{3} \ge 0$

And uses the dictionary to perform operations that rearranges the basic variables (rows of the dictionary below $\zeta$) and non-basic variables (columns of dictionary, ie. $x,y$) such that $\zeta$ is maximized, like so:

$\zeta~$   $=$     $5$     $-$     $\frac{1}{4}w_{2}$     $-$     $\frac{1}{4}w_{3}$
                                                           
$w_{1}$  $=$   $\frac{13}{2}$    $+$     $\frac{5}{8}w_{2}$     $-$     $\frac{7}{8}w_{3}$
$y$     $=$   $\frac{3}{2}$     $-$     $\frac{3}{8}w_{2}$     $+$     $\frac{1}{8}w_{3}$
$x$     $=$   $\frac{7}{2}$     $+$     $\frac{1}{8}w_{2}$     $-$     $\frac{3}{8}w_{3}$

Since the non-basic variables are all subtracted in $\zeta$, the maximum value they can have is $0$ given above, thus $\zeta = 5$, $w_{1} = \frac{13}{2}$, $w_{2} = w_{3} = 0$, $y = \frac{3}{2}$ and $x = \frac{7}{2}$.

The program tests the following before running the procedure above:

Feasibility: The program ensures that all linear programs are feasible, meaning that no basic variable is less than $0$. If the program is initially infeasible, an auxiliary problem is solved using the Simplex Method to assert whether the linear program can be manipulated such that it becomes feasible.

Unboundedness: The program ensures that the linear program is not unbounded, ie. that $\zeta$ cannot increase indefinitely through the Simplex Method.