# Simplex method - infeasible

1. Aug 13, 2014

### liquidFuzz

Simplex method - infeasible

I'm looking at some linear optimization problems. In one example I must be missing something, maybe someone can point it out. Here's the example:

\begin{align*} \textrm{max } f(\textbf{x}) = & 2x_1 + x_2 \\ \textrm{subject to} & x_1 + x_2 \leq 5 \\ & -x_1 + x_2 \geq 1 \\ & \textbf{x} \geq 0 \end{align*}

When I try to perform iterations of the simplex method I get funky results, not feasible stuff. I suspect that it is due to how I set up my slack variables, $x_3$ and $x_4$. My starting point $x=(0,0)$ is not in the feasible set, but that shouldn't matter, right?

\begin{align*} \textrm{min } f(\textbf{x}) = & -2x_1 - x_2 \\ \textrm{subject to} & x_1 + x_2 + x_3 = 5 \\ & x_1 - x_2 + x_4 = - 1 \\ & \textbf{x} \geq 0 \end{align*}

Are my slack variables wrong..? Or is it something else causing me to end up in infeasible points in my iterations?

2. Aug 13, 2014

### elegysix

Have you tried a starting point that is in your set? like, x1 = 1, x2 = 2?

I am not familiar with the method you're talking about, but whenever I get crazy results or errors in matlab from fitting, it's usually because of the starting point I've chosen.

3. Aug 13, 2014

### MrAnchovy

Of course it matters - the trial solution blindly heads off down the line of steepest descent, how do you expect it is going to find its way into the feasible set?

4. Aug 13, 2014

### liquidFuzz

Eh could you refresh my memory. Where do you calculate the steepest descent direction in the simplex algorithm..?

5. Aug 13, 2014

### liquidFuzz

I haven't tinkered with this in matlab. Is the optimixation tool kit good? I'll try different starting points and see what I get.

6. Aug 13, 2014

### liquidFuzz

Maybe it's how I chose pivoting element..?

I'll post some iterations, maybe you can comment on them.

Tableau
\begin{matrix}
& x_1 & x_2 & s_1 & s_2 & f(x) & \hat{x} \\
r1 & 1 & 1 & 1 & 0 & 0 & 5 \\
r2 & 1 & -1 & 0 & 1 & 0 & -1 \\
obj & -2 & -1 & 0 & 0 & 1 & 0 \\
\end{matrix}

If I chose column $x_1$ as pivoting column the ratio test gives pivoting element $r_1,x_1$. The updated tableau is then:
\begin{matrix}
& x_1 & x_2 & s_1 & s_2 & f(x) & \hat{x} \\
r1 & 1 & 1 & 1 & 0 & 0 & 5 \\
r2 & 0 & -2 & -1 & 1 & 0 & -6 \\
obj & 0 & 1 & 2 & 0 & 1 & 10 \\
\end{matrix}
This would imply that there are no descent direction, so no further optimization is possible. The current solution however is $x =(5,0)$ which isn't feasible.

If I instead chose starting pivoting element $r2,x1$ I end up in the point $x=(2,3)$ after a couple of iterations with $f(2,3) = 7$. This suggests that I don't have a clue on how to chose pivoting elements. Pointers would be appreciated...

7. Aug 13, 2014

### liquidFuzz

Sigh, I got now. I just needed to iterate until I had the solution...

8. Aug 13, 2014

### MrAnchovy

I could have put that better, but it would have taken more words. At each vertex (the initial vertex in particular) you have a number of choices of which variable to vary. An efficient implementation generally chooses the variable that descends most steeply (or possibly the one which achieves the greatest descent when reaching the next extremum).

This is not really relevant to the point though, which is that the simplex method works by traversing (a subset of) the extrema of the feasible set. If you start outside the feasible set you are only going to end up inside it by luck.

9. Aug 13, 2014

### MrAnchovy

No, it demonstrates that unless you are at an extremum the choice of reaching the solution is purely down to luck. Now you have struck lucky and found your way to x = (2,3) which is clearly an extremum, the algorithm starts to work and...

Bingo!

10. Aug 13, 2014

### liquidFuzz

Could you, or someone else, show me ho to start in, lets say x =(0,1)..?

11. Aug 13, 2014

### MrAnchovy

Set the slack variables to 0 and solve the simultaneous equations.