[Math] Tutorial for Simplex Method with No Slack Variables

linear programming

I found a nice tutorial here http://www.math.ucla.edu/~tom/LP.pdf for applying the Simplex Method to problems of the form: maximize $c^T x$ with the constraints $Ax\leq b$, $x_i \geq 0$. It suggests introducing "slack variables" to convert it to the form $Ax=b$, $x_i \geq 0$ and going from there.

The issue is, my problem is already of the form $Ax=b$, $x_i \geq 0$, and hence I have no need to introduce slack variables. So I'm not sure how to apply the method, since I don't have any "basic variables" in my initial tableau, and from what I can tell from the linked tutorial, having basic variables is essential to applying the method. Can anyone link me to a tutorial that starts with the problem in the form I have?

Best Answer

You are right, that you canĀ“t get an Initial solution by using only slack variables, if you have $=$-constraints and $\geq$-contraints. I start with the three types of equations and then transform them.

$x+y\leq 8$

$2x-y=6$

$x+2y\geq 12$

Introducing slack variables to get equalities

$x+y+s_1= 8$

$2x-y=6$

$x+2y-s_2= 12$

The second and the third equation have no basic variable. In these cases you need artificial variables ($a_i$).

$x+y+s_1= 8$

$2x-y+a_1=6$

$x+2y-s_2+a_2= 12$

Now you are able to start the Simplex algorithm. Surely you need an objective function.