2

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?

Izzhov
  • 325
  • Out of curiosity, what are you solving this problem for? – littleO Jul 15 '15 at 19:15
  • In order to analyze the contact networks/stability of packings, I'm trying to come up with an algorithm to show whether an arbitrary shape that has specified points of contact with other shapes is fixed in place, of if it has the ability to move anywhere. I've converted the problem to the form described above. – Izzhov Jul 15 '15 at 19:19
  • In general, you need a two phase simplex method. You first solve an auxiliary problem to find the basis variables and then optimize. See http://www.statslab.cam.ac.uk/~ff271/teaching/opt/notes/notes8.pdf – user251257 Jul 15 '15 at 19:20
  • Hi user, that tutorial still assumes you're using slack variables, which my problem doesn't have. So I can't use that. – Izzhov Jul 15 '15 at 19:21
  • read on, the note explain how you get an initial basis. – user251257 Jul 15 '15 at 19:25
  • by the way, you need to write @user251257 or I won't get notified. The post creator is notified automatically. – user251257 Jul 15 '15 at 19:28
  • Ah ok, I think I understand it now, Thanks, @user251257 – Izzhov Jul 15 '15 at 19:29
  • Since you actually want to solve this problem for a practical purpose, rather than an educational purpose (to learn about the simplex method), I think you probably shouldn't implement your own LP solver. Rather, you can use existing software that can solve LPs, such as CVX or MOSEK. It will be less work, you won't have to worry about a bug in your implementation, and their solvers will probably work more efficiently than one you write (unless you put a lot of effort into it). – littleO Jul 15 '15 at 19:32
  • Ok @littleO, I'll look into those. Thanks for the recommendation. – Izzhov Jul 15 '15 at 19:35

1 Answers1

1

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.

callculus42
  • 30,550
  • So every equation needs to start with at least one variable in basic form? Why couldn't $s2$ satisfy as one in the third equation? – Athan Clark Nov 19 '15 at 18:10
  • @AthanClark In the table $-s_2$ is displayed as $-1$. $s_2$ is the name of the column. Therefore the entry has to be $-1$ and we need to add an artificial variable. – callculus42 Nov 19 '15 at 18:16
  • I'm confused, can you explain it without referencing a matrix-based tableau? Why did you come to the conclusion that an artificial variable was needed from the (only) $-1$ coefficient? – Athan Clark Nov 19 '15 at 18:20
  • 1
    You need a basic solution at the beginning. Here it is $(s_1, a_1, a_2)=(8,6,12)$. $s_2$ is greater or equal to zero. Therefore $-s_2=12 \Rightarrow s_2=-12$ cannot be a part of the (non-optimal) solution. – callculus42 Nov 19 '15 at 18:25